数据结构c语言版 线性表的动态分配顺序存储结构表示和实现文库

《数据结构c语言版 线性表的动态分配顺序存储结构表示和实现文库》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*数据结构C语言版线性表的动态分配顺序存储结构表示和实现P22-26编译环境：Dev-C++4.9.9.2日期：2011年2月9日*/#include#include#includetypedefintElemType;//定义数据结构元素的数据类型#defineLIST_INIT_SIZE10//线性表存储空间的初始分配量#defineLISTINCREMENT5//线性表存储空间的分配增量//线性表的动态分配顺序存储结构typedefstruct{ElemT

2、ype*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//算法2.3，P23//构造一个空的顺序线性表即对顺序表结构体中的所有元素//进行初始化。intInitList(SqList*L){//分配指定大小的存储空间给顺序表(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*L).elem)//存储分配失败exit(0);(

3、*L).length=0;//当前长度初始化为0//指定分配的存储容量(*L).listsize=LIST_INIT_SIZE;return1;}//销毁顺序线性表L即将顺序表结构体中的所有成员销毁（空间释放，//数值置0）。intDestroyList(SqList*L){//先释放空间，然后置空free((*L).elem);(*L).elem=NULL;(*L).length=0;(*L).listsize=0;return1;}//将L重置为空表（当前长度为0即是空表）。intClearList(SqList*L

4、){(*L).length=0;return1;}/*若L为空表，则返回1，否则返回0。如何判断是否为空表呢？结构体中已经包含一个可以说明的元素，那就是length，表示当前顺序表的长度，根据当前的长度就可以判断了，为0就是空表，不为0就不是空表了。*/intListEmpty(SqListL){if(0==L.length)return1;elsereturn0;}//返回L中数据元素个数。intListLength(SqListL){//L.length刚好记录了当前顺序表的长度，直接返回returnL.length

5、;}//用e返回L中第i个数据元素的值，第i个数据元素就是L.elem[i-1]。intGetElem(SqListL,inti,ElemType*e){//首先进行异常处理if(i<1

6、

7、i>L.length)exit(0);/*注意顺序表基址L.elem[0]表示第一个数，而第i个数则是用基址L.elem+i-1来表示,也可以用L.elem[i-1]表示。为什么可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指示了一个首地址，然后对地址进行加减，形成不同元素的地址。*是取地址所指的内容，所以*(L.ele

8、m+i-1)就是第i个数据的值了。*/*e=*(L.elem+i-1);//*e=L.elem[i-1];return1;}/*算法2.6，P26返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。*/intLocateElem(SqListL,ElemTypee,int(*compare)(ElemType,ElemType)){ElemType*p;inti=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置即地址//循环比较，直到找

9、到符合关系的元素while(i<=L.length&&!compare(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}#if0/*算法2.7与算法2.2区别已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列。算法的时间复杂度为O(La.length+Lb.length).*/voidMergeList(SqListLa,SqListLb,SqList*Lc){ElemType*pa,*pa_last,*pb,*p

10、b_last,*pc;pa=La.elem;//pa指向线性表La的头结点pb=Lb.elem;//pb指向线性表Lb的头结点/*不用InitList()创建空表Lc*/(*Lc).listsize=(*Lc).length=La.length+Lb.length;//pc指向线性表Lc的头结点pc=(*Lc).el