线性表有两种物理存储结构：顺序表和链表。
1、顺序表的基本操作
#includestdio.h#includestdlib.h//提供malloc、realloc、free、exit原型/*宏定义*/#defineLIST_INIT_SIZE//顺序表存储空间的初始分配量#defineLISTINCREMENT10//顺序表存储空间的分配增量/*顺序表元素类型定义*/typedefintElemType;/**顺序表结构**注：elem在使用前需要先为其分配内存，且元素从elem[0]处开始存储*/typedefstruct{ElemType*elem;//顺序表存储空间的基址（指向顺序表所占内存的起始位置）intlength;//当前顺序表长度（包含多少元素）intlistsize;//当前分配的存储容量（可以存储多少元素）}SqList;/**████████算法2.3████████**初始化**初始化成功则返回OK，否则返回ERROR。*/StatusInitList(SqList*L);/**销毁(结构)**释放顺序表所占内存。*/StatusDestroyList(SqList*L);/**置空(内容)**只是清理顺序表中存储的数据，不释放顺序表所占内存。*/StatusClearList(SqList*L);/**判空**判断顺序表中是否包含有效数据。**返回值：*TRUE:顺序表为空*FALSE:顺序表不为空*/StatusListEmpty(SqListL);/**计数**返回顺序表包含的有效元素的数量。*/intListLength(SqListL);/**取值**获取顺序表中第i个元素，将其存储到e中。*如果可以找到，返回OK，否则，返回ERROR。***教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。*通常，i的含义应该指索引，即从0开始计数。*/StatusGetElem(SqListL,inti,ElemType*e);/**████████算法2.6████████**查找**返回顺序表中首个与e满足Compare关系的元素位序。*如果不存在这样的元素，则返回0。***元素e是Compare函数第二个形参*/intLocateElem(SqListL,ElemTypee,Status(Compare)(ElemType,ElemType));/**前驱**获取元素cur_e的前驱，*如果存在，将其存储到pre_e中，返回OK，*如果不存在，则返回ERROR。*/StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e);/**后继**获取元素cur_e的后继，*如果存在，将其存储到next_e中，返回OK，*如果不存在，则返回ERROR。*/StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e);/**████████算法2.4████████**插入**向顺序表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。***教材中i的含义是元素位置，从1开始计数*/StatusListInsert(SqList*L,inti,ElemTypee);/**████████算法2.5████████**删除**删除顺序表第i个位置上的元素，并将被删除元素存储到e中。*删除成功则返回OK，否则返回ERROR。***教材中i的含义是元素位置，从1开始计数*/StatusListDelete(SqList*L,inti,ElemType*e);/**遍历**用visit函数访问顺序表L*/voidListTraverse(SqListL,void(Visit)(ElemType));
/**████████算法2.3████████**初始化**初始化成功则返回OK，否则返回ERROR。*/StatusInitList(SqList*L){//分配指定容量的内存，如果分配失败，则返回NULL(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if((*L).elem==NULL){//存储内存失败exit(OVERFLOW);}(*L).length=0;//初始化顺序表长度为0(*L).listsize=LIST_INIT_SIZE;//顺序表初始内存分配量returnOK;//初始化成功}
/**销毁(结构)**释放顺序表所占内存。*/StatusDestroyList(SqList*L){//确保顺序表结构存在if(L==NULL
(*L).elem==NULL){returnERROR;}//释放顺序表内存free((*L).elem);//释放内存后置空指针(*L).elem=NULL;//顺序表长度跟容量都归零(*L).length=0;(*L).listsize=0;returnOK;}
/**置空(内容)**只是清理顺序表中存储的数据，不释放顺序表所占内存。*/StatusClearList(SqList*L){//确保顺序表结构存在if(L==NULL
(*L).elem==NULL){returnERROR;}(*L).length=0;returnOK;}
/**判空**判断顺序表中是否包含有效数据。**返回值：*TRUE:顺序表为空*FALSE:顺序表不为空*/StatusListEmpty(SqListL){returnL.length==0?TRUE:FALSE;}
/**计数**返回顺序表包含的有效元素的数量。*/intListLength(SqListL){returnL.length;}
/**取值**获取顺序表中第i个元素，将其存储到e中。*如果可以找到，返回OK，否则，返回ERROR。***教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。*通常，i的含义应该指索引，即从0开始计数。*/StatusGetElem(SqListL,inti,ElemType*e){//因为i的含义是位置，所以其合法范围是：[1,length]if(i1
iL.length){returnERROR;//i值不合法}*e=L.elem[i-1];returnOK;}
/**████████算法2.6████████**查找**返回顺序表中首个与e满足Compare关系的元素位序。*如果不存在这样的元素，则返回0。***元素e是Compare函数第二个形参*/intLocateElem(SqListL,ElemTypee,Status(*Compare)(ElemType,ElemType)){inti;ElemType*p;//确保顺序表结构存在if(L.elem==NULL){returnERROR;}/**i的初值为第1个元素的位序**其实，更自然的写法是将i初始化为第1个元素的索引*但由于教材中是按位序计数的，所以这里仍写作位序*/i=1;//p的初值为第1个元素的存储位置p=L.elem;//遍历顺序表while(i=L.length!(*Compare)(*p++,e)){++i;}if(i=L.length){returni;}else{return0;}}
/**前驱**获取元素cur_e的前驱，*如果存在，将其存储到pre_e中，返回OK，*如果不存在，则返回ERROR。*/StatusPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e){inti;//确保顺序表结构存在，且最少包含两个元素if(L.elem==NULL
L.length2){returnERROR;}//这里的i初始化为第1个元素的i=0;//从第1个元素开始，查找cur_e的位置while(iL.lengthL.elem!=cur_e){++i;}//如果cur_e是首个元素(没有前驱)，或者没找到元素cur_e，返回ERRORif(i==0
i=L.length){returnERROR;}//存储cur_e的前驱*pre_e=L.elem[i-1];returnOK;}
/**后继**获取元素cur_e的后继，*如果存在，将其存储到next_e中，返回OK，*如果不存在，则返回ERROR。*/StatusNextElem(SqListL,ElemTypecur_e,ElemType*next_e){inti;//确保顺序表结构存在，且最少包含两个元素if(L.elem==NULL
L.length2){returnERROR;}//这里的i初始化为第1个元素的i=0;//从第1个元素开始，查找cur_e的位置while(iL.length-1L.elem!=cur_e){++i;}//如果cur_e是最后1个元素(没有前驱)，或者没找到元素cur_e，返回ERRORif(i=L.length-1){returnERROR;}//存储cur_e的前驱*next_e=L.elem[i+1];returnOK;}
/**████████算法2.4████████**插入**向顺序表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。***教材中i的含义是元素位置，从1开始计数*/StatusListInsert(SqList*L,inti,ElemTypee){ElemType*newbase;ElemType*p,*q;//确保顺序表结构存在if(L==NULL
(*L).elem==NULL){returnERROR;}//i值越界if(i1
i(*L).length+1){returnERROR;}//若存储空间已满，则增加新空间if((*L).length=(*L).listsize){//基于现有空间扩容newbase=(ElemType*)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase==NULL){//存储内存失败exit(OVERFLOW);}//新基址(*L).elem=newbase;//存的存储空间(*L).listsize+=LISTINCREMENT;}//q为插入位置q=(*L).elem[i-1];//1.右移元素，腾出位置for(p=(*L).elem[(*L).length-1];p=q;--p){*(p+1)=*p;}//2.插入e*q=e;//3.表长增1(*L).length++;returnOK;}
/**████████算法2.5████████**删除**删除顺序表第i个位置上的元素，并将被删除元素存储到e中。*删除成功则返回OK，否则返回ERROR。***教材中i的含义是元素位置，从1开始计数*/StatusListDelete(SqList*L,inti,ElemType*e){ElemType*p,*q;//确保顺序表结构存在if(L==NULL
(*L).elem==NULL){returnERROR;}//i值越界if(i1
i(*L).length){returnERROR;}//p为被删除元素的位置p=(*L).elem[i-1];//1.获取被删除元素*e=*p;//表尾元素位置q=(*L).elem+(*L).length-1;//2.左移元素，被删除元素的位置上会有新元素进来for(++p;p=q;++p){*(p-1)=*p;}//3.表长减1(*L).length--;returnOK;}
/**遍历**用visit函数访问顺序表L*/voidListTraverse(SqListL,void(Visit)(ElemType)){inti;for(i=0;iL.length;i++){Visit(L.elem);}printf("\n");}
2、求两个线性表的并集（La与Lb无序）
/*==============*求并集**包含算法:2.1===============*/#include"Union.h"//**▲02线性表**///**████████算法2.1████████**A=A∪B**计算La与Lb的并集并返回。*由于生成的并集会拼接在La上，所以La的入参为指针类型。*/voidUnion(SqList*La,SqListLb){intLa_len,Lb_len;inti;ElemTypee;//求顺序表长度La_len=ListLength(*La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){//取Lb中第i个元素赋给eGetElem(Lb,i,e);//若e不在La中则插入if(!LocateElem(*La,e,equal)){ListInsert(La,++La_len,e);}}}/**判等**判断两元素是否相等。*如果相等，则返回TRUE，否则，返回FALSE。*/Statusequal(ElemTypee1,ElemTypee2){returne1==e2?TRUE:FALSE;}预览时标签不可点收录于话题#个上一篇下一篇