顺序表的建立与操作算法C语言实现

1、顺序表的建立与常用操作的算法(C语言实现)#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/*c2-1.h线性表的动态分配顺序存储结构*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefstructElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/SqList;StatusInitList(SqList*L)/*操作结果：构造一个空的顺序线性表*/(*L).elem=(ElemType*)mallo

2、c(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)exit(OVERFLOW);/*存储分配失败*/(*L).length=0;/*空表长度为0*/(*L).listsize=LIST_INIT_SIZE;/*初始存储容量*/returnOK;StatusDestroyList(SqList*L)/*初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L*/free(*L).elem);(*L).elem=NULL;(*L).length=0;(*L).listsize=0;/*bo2-1.c顺序表(存储结构由c2-1.h定义)的基本操作(12个

3、)returnOK;StatusClearList(SqList*L)/*初始条件：顺序线性表L已存在。操作结果：将L重置为空表*/(*L).length=0;returnOK;*/StatusListEmpty(SqListL)/*初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE否则返回FALSE*/if(L.length=0)returnTRUE;elsereturnFALSE;intListLength(SqListL)/*初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数*/returnL.length;StatusGetElem(SqListL,inti,

4、ElemType*e)/*初始条件：顺序线性表L已存在，1wiwListLength(L)*/*操作结果：用e返回L中第i个数据元素的值*/if(i<1|i>L.length)exit(ERROR);*e=*(L.elem+i-1);returnOK;intLocateElem(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/*初始条件：顺序线性表L已存在，compare。是数据元素判定函数(满足为1,否则为0)*/*操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。*/*若这样的数据元素不存在，则返

5、回值为0。算法2.6*/ElemType*p;inti=1;/*i的初值为第1个元素的位序*/p=L.elem;/*p的初值为第1个元素的存储位置*/while(i<=L.length&&!compare(*p+,e)+i;if(i<=L.length)returni;elsereturn0;StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)/*初始条件：顺序线性表L已存在*/*操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*/*否则操作失败，pre_e无定义*/inti=2;

6、ElemType*p=L.elem+1;while(i<=L.length&&*p!=cur_e)p+;i+;if(i>L.length)returnINFEASIBLE;else*pre_e=*-p;returnOK;StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e)/*初始条件：顺序线性表L已存在*/*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*/*否则操作失败，next_e无定义*/inti=1;ElemType*p=L.elem;while(i<L.len

7、gth&&*p!=cur_e)i+;p+;Jif(i=L.length)returnINFEASIBLE;else*next_e=*+p;returnOK;StatusListInsert(SqList*L,inti,ElemTypee)/*初始条件：顺序线性表L已存在，1WiWListLength(L)+1*/*操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1*/ElemType*newbase,*q,*p;if(i<1|i>(*L).length+1)/*i值不合法*/returnERROR;if(*L).length>=(*L).lists

8、ize)/*当前存储空间已满，增加分配*/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;/*q为插入位置*/for(p=(*L).elem+(*L).length-1;p>=q;-p)/*插入位置及之后的元素右移*/*(p+1)=*p;*q=

9、e;/*插入e*/+(*L).length;/*表长增1*/returnOK;StatusListDelete(SqList*L,inti,ElemType*e)/*初始条件：顺序线性表L已存在，1wiwListLength(L)*/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/ElemType*p,*q;if(i<1|i>(*L).length)/*i值不合法*/returnERROR;p=(*L).elem+i-1;/*p为被删除元素的位置*/*e=*p;/*被删除元素的值赋给e*/q=(*L).elem+(*L).length-1;/*表尾元素的位置*/

10、for(+p;p<=q;+p)/*被删除元素之后的元素左移*/*(p-1)=*p;(*L).length-;/*表长减1*/returnOK;StatusListTraverse(SqListL,void(*vi)(ElemType*)/*初始条件：顺序线性表L已存在*/*操作结果：依次对L的每个数据元素调用函数vi()。一旦vi()失败，则操作失败*/*vi()的形参加'&',表明可通过调用vi()改变元素的值*/ElemType*p;inti;p=L.elem;for(i=1;i<=L.length;i+)vi(p+);printf("n&qu

11、ot;);returnOK;/*main2-1.c检验bo2-1.c的主程序*/#include"c1.h"typedefintElemType;#include"c2-1.h”#include"bo2-1.c”Statuscomp(ElemTypec1,ElemTypec2)/*数据兀素/Ute函数(平方关系)*/if(c1=c2*c2)returnTRUE;elsereturnFALSE;voidvisit(ElemType*c)/*ListTraverse()调用的函数(类型要,致)*/printf("%d",*c);voidd

12、bl(ElemType*c)/*ListTraverse()调用的另函数(兀素值加倍)*/*c*=2;voidmain()SqListL;ElemTypee,e0;Statusi;intj,k;i=InitList(&L);printf("初始化L后：L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);for(j=1;j<=5;j+)i=ListInsert(&L,1,j);printf("在L的表头依次插入15后：*L.elem=");for(j=1;j&

13、lt;=5;j+)printf("%d",*(L.elem+j-1);printf("n");printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,L.listsize);i=ListEmpty(L);printf("L是否空：i=%d(1:是0:否)n",i);i=ClearList(&L);printf("清空L后：L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.length,

14、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的表尾依次插入110后：*L.elem=");for(j=1;j<=10;j+)printf("%d",*(L.elem+j-1);printf("n");printf("L.elem=%uL.length=%dL.listsize=%dn",L.elem,L.lengt

15、h,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,&

16、;e);printf("第5个元素的值为：%dn",e);for(j=3;j<=4;j+)k=LocateElem(L,j,comp);if(k)printf("第个元素的值为%d的平方n",k,j);elseprintf("没有值为%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

17、",e0);elseprintf("元素d的前驱为：%dn",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);elseprintf("元素d的后继为：%dn",e0,e);k=ListLength(L);/*k为表长*/for(j=k+1;j>=k;j-)i=ListDelete(&L,j,&e);/*删除第j个数据*/if(i=ERROR)printf("删除第外数据失败n",j);elseprintf("删除的元素值为：dn",e);)printf("