2007.6.11 线性表的完整代码(Linux下编绎通过)

今天把昨晚复习的线性表代码完整的调试了一次...



#include
#include
#include
#include
#include
#include  
#include


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
 
typedef int Status;
typedef int Boolean;
typedef int ElemType;

#define LIST_INIT_SIZE 40
#define LIST_INCREMENT 4

typedef struct
{
   ElemType *elem;
   int length;
   int listsize;
}SqList;

Status equal(ElemType c1,ElemType c2)
{
   if(c1==c2)
     return TRUE;
   else
     return FALSE;
}

int comp(ElemType a,ElemType b)
{
   if(a==b)
     return 0;
   else
     return (a-b)/abs(a-b);
}

 void print(ElemType c)
 {
   printf("%d ",c);
 }

 void print2(ElemType c)
 {
   printf("%c ",c);
 }

 void print1(ElemType *c)
 {
   printf("%d ",*c);
 }


void InitList(SqList *L)
{
   (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
   if(!(*L).elem)
     exit(OVERFLOW);
   (*L).length=0;
   (*L).listsize=LIST_INIT_SIZE;
}

void DestroyList(SqList *L)
{
   free((*L).elem);
   (*L).elem=NULL;
   (*L).length=0;
   (*L).listsize=0;
}

void ClearList(SqList *L)
{
   (*L).length=0;
}

Status ListEmpty(SqList L)
{
   if(L.length==0)
     return TRUE;
   else
     return FALSE;
}

int ListLength(SqList L)
{
   return L.length;
}

Status GetElem(SqList L,int i,ElemType *e)
{
   if(i<1||i>L.length)
     return ERROR;
   *e=*(L.elem+i-1);
   return OK;
}

int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
   ElemType *p;
   int i=1;
   p=L.elem;
   while(i<=L.length&&!compare(*p++,e))
     ++i;
   if(i<=L.length)
     return i;
   else
     return 0;
}

Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{
   int i=2;
   ElemType *p=L.elem+1;
   while(i<=L.length&&*p!=cur_e)
   {
     p++;
     i++;
   }
   if(i>L.length)
     return INFEASIBLE;
   else
   {
     *pre_e=*--p;
     return OK;
   }
}

Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
 {
   int i=1;
   ElemType *p=L.elem;
   while(i   {
     i++;
     p++;
   }
   if(i==L.length)
     return INFEASIBLE;
   else
   {
     *next_e=*++p;
     return OK;
   }
 }

Status ListInsert(SqList *L,int i,ElemType e)
{
   ElemType *newbase,*q,*p;
   if(i<1||i>(*L).length+1)
     return ERROR;
   if((*L).length>=(*L).listsize)
   {
     newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LIST_INCREMENT)*sizeof(ElemType));
     if(!newbase)
       exit(OVERFLOW);
     (*L).elem=newbase;
     (*L).listsize+=LIST_INCREMENT;
   }
   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 ListDelete(SqList *L,int i,ElemType *e)
 {
   ElemType *p,*q;
   if(i<1||i>(*L).length)
     return ERROR;
   p=(*L).elem+i-1;
   *e=*p;
   q=(*L).elem+(*L).length-1;
   for(++p;p<=q;++p)
     *(p-1)=*p;
   (*L).length--;
   return OK;
 }

 void ListTraverse(SqList L,void(*vi)(ElemType*))
 {
   ElemType *p;
   int i;
   p=L.elem;
   for(i=1;i<=L.length;i++)
     vi(p++);
   printf("\n");
 }

Status sq(ElemType c1,ElemType c2)
{
   if(c1==c2*c2)
     return TRUE;
   else
     return FALSE;
}

void dbl(ElemType *c)
{
   *c*=2;
}

int  main(void)
 {
   SqList L;
   ElemType e,e0;
   Status i;
   int j,k;
   InitList(&L);
   printf("初始化L后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
   for(j=1;j<=5;j++)
     i=ListInsert(&L,1,j);
   printf("在L的表头依次插入1～5后：*L.elem=");
   for(j=1;j<=5;j++)
     printf("%d ",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u L.length=%d L.listsize=%d ",L.elem,L.length,L.listsize);
   i=ListEmpty(L);
   printf("L是否空：i=%d(1:是 0:否)\n",i);
   ClearList(&L);
   printf("清空L后：L.elem=%u L.length=%d L.listsize=%d ",L.elem,L.length,L.listsize);
   i=ListEmpty(L);
   printf("L是否空：i=%d(1:是 0:否)\n",i);
   for(j=1;j<=10;j++)
     ListInsert(&L,j,j);
   printf("在L的表尾依次插入1～10后：*L.elem=");
   for(j=1;j<=10;j++)
     printf("%d ",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
   ListInsert(&L,1,0);
   printf("在L的表头插入0后：*L.elem=");
   for(j=1;j<=ListLength(L);j++) /* ListLength(L)为元素个数 */
     printf("%d ",*(L.elem+j-1));
   printf("\n");
   printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变)\n",L.elem,L.length,L.listsize);
   GetElem(L,5,&e);
   printf("第5个元素的值为：%d\n",e);
   for(j=10;j<=11;j++)
   {
     k=LocateElem(L,j,equal);
     if(k) /* k不为0，表明有符合条件的元素，且其位序为k */
       printf("第%d个元素的值为%d\n",k,j);
     else
       printf("没有值为%d的元素\n",j);
   }
   for(j=3;j<=4;j++)
   {
     k=LocateElem(L,j,sq);
     if(k) /* k不为0，表明有符合条件的元素，且其位序为k */
       printf("第%d个元素的值为%d的平方\n",k,j);
     else
       printf("没有值为%d的平方的元素\n",j);
   }
   for(j=1;j<=2;j++) /* 测试头两个数据 */
   {
     GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
     i=PriorElem(L,e0,&e); /* 求e0的前驱 */
     if(i==INFEASIBLE)
       printf("元素%d无前驱\n",e0);
     else
       printf("元素%d的前驱为：%d\n",e0,e);
   }
   for(j=ListLength(L)-1;j<=ListLength(L);j++) /* 最后两个数据 */
   {
     GetElem(L,j,&e0); /* 把第j个数据赋给e0 */
     i=NextElem(L,e0,&e); /* 求e0的后继 */
     if(i==INFEASIBLE)
       printf("元素%d无后继\n",e0);
     else
       printf("元素%d的后继为：%d\n",e0,e);
   }
   k=ListLength(L); /* k为表长 */
   for(j=k+1;j>=k;j--)
   {
     i=ListDelete(&L,j,&e); /* 删除第j个数据 */
     if(i==ERROR)
       printf("删除第%d个元素失败\n",j);
     else
       printf("删除第%d个元素成功，其值为：%d\n",j,e);
   }
   printf("依次输出L的元素：");
   ListTraverse(L,print1); /* 依次对元素调用print1()，输出元素的值 */
   printf("L的元素值加倍后：");
   ListTraverse(L,dbl); /* 依次对元素调用dbl()，元素值乘2 */
   ListTraverse(L,print1);
   DestroyList(&L);
   printf("销毁L后：L.elem=%u L.length=%d L.listsize=%d\n",L.elem,L.length,L.listsize);
   
   return OK;
 }