Posted on 2012-08-21 16:25
hoshelly 阅读(357)
评论(0) 编辑 收藏 引用 所属分类:
DS && Algorithm
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType *elem; //存储空间基址
int length; //当前的线性表长度
int listsize; //当前分配的存储容量
}SqList;
//初始化线性表
Status InitList_Sq(SqList *L) //用线性表的指针操作
{
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList L)
{
return L.length;
}
Status ListEmpty(SqList L)
{
if(L.length == 0)
return OK;
else
return ERROR;
}
Status ClearList(SqList *L)
{
(*L).length=0;
return OK;
}
Status DestroyList(SqList *L)
{
free((*L).elem);
(*L).elem=NULL;
(*L).length=0;
(*L).listsize=0;
return OK;
}
Status GetElem(SqList L,int i,ElemType *e)
{
if(i<1 || i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase,*p,*q;
if(i<1 || i>(*L).length+1)
return ERROR;
if((*L).length >= (*L).listsize)
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem=newbase;
(*L).listsize +=LISTINCREMENT;
}
q=(*L).elem+i-1; //插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++(*L).length;
return OK;
}
Status Visit(ElemType *c)
{
printf("%d ",*c);
return OK;
}
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
Visit(L.elem+i);
printf("\n");
return OK;
}
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=0;i<L.length;i++)
{
if(*(L.elem+i) == e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if(L->length == 0)
return ERROR;
if(i<1 || i>=L->length)
return ERROR;
*e=*(L->elem+i-1);
if(i<L->length)
{
for(k=i;k<L->length;k++)
*(L->elem+k-1)=*(L->elem+k);
}
L->length--;
return OK;
}
int main()
{
int i,e;
SqList mylist;
int m = InitList_Sq(&mylist);
if(m)
{
printf("线性表创建成功!\n");
printf("当前表长: %d \n",ListLength(mylist));
}
else
printf("线性表创建失败.");
for(i=1;i<=10;i++)
ListInsert(&mylist,i,i);
ListTraverse(mylist);
printf("当前表长:%d \n",ListLength(mylist));
GetElem(mylist,5,&e);
printf("第5个元素为:%d\n",e);
ListDelete(&mylist,4,&e);
printf("删除第4个元素后:");
ListTraverse(mylist);
printf("当前表长:%d \n",ListLength(mylist));
i=ClearList(&mylist);
printf("清空线性表后:表长为 %d\n",mylist.length);
i=ListEmpty(mylist);
printf("表是否为空:%d (1:空 0:否)\n",i);
return 0;
}