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

浅浅的花香味﹌ 2023-01-22 12:57 22阅读 0赞

![41528d3028836879cd698677c3999917.gif][]数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库

/\* 数据结构C语言版 线性表的动态分配顺序存储结构表示和实现 编译环境：Dev-C++ \*/ \#include \#include \#include typedef int ElemType;// 定义数据结构元素的数据类型 \#define LIST\_INIT\_SIZE 10// 线性表存储空间的初始分配量 \#define LISTINCREMENT 5// 线性表存储空间的分配增量 // 线性表的动态分配顺序存储结构 typedef struct \{ ElemType \*elem;// 存储空间基址 int length;// 当前长度 int listsize;// 当前分配的存储容量(以sizeof(ElemType)为单位) \}SqList; // 算法2.3，P23 // 构造一个空的顺序线性表即对顺序表结构体中的所有元素 // 进行初始化。 int InitList(SqList \*L) \{ // 分配指定大小的存储空间给顺序表 (\*L).elem = (ElemType\*)malloc(LIST\_INIT\_SIZE \* sizeof(ElemType)); if( !(\*L).elem ) // 存储分配失败 exit(0); (\*L).length = 0; // 当前长度初始化为0 // 指定分配的存储容量 (\*L).listsize = LIST\_INIT\_SIZE; return 1; \} // 销毁顺序线性表L即将顺序表结构体中的所有成员销毁(空间释放， // 数值置0)。 int DestroyList(SqList \*L) \{ // 先释放空间，然后置空 free( (\*L).elem ); (\*L).elem = NULL; (\*L).length = 0; (\*L).listsize = 0; return 1; \} // 将L重置为空表(当前长度为0即是空表)。 int ClearList(SqList \*L) \{ (\*L).length = 0; return 1; \} /\* 若L为空表，则返回1，否则返回0。 如何判断是否为空表呢？结构体中已经包含一个可以说明的元素， 那就是length，表示当前顺序表的长度，根据当前的长度就可以 判断了，为0就是空表，不为0就不是空表了。 \*/ int ListEmpty(SqList L) \{ if(0 == L.length) return 1; else return 0; \} // 返回L中数据元素个数。 int ListLength(SqList L) \{ // L.length刚好记录了当前顺序表的长度，直接返回 return L.length; \} // 用e返回L中第i个数据元素的值，第i个数据元素就是L.elem\[i-1\]。 int GetElem(SqList L,int i,ElemType \*e) \{ // 首先进行异常处理 if(i L.length) exit(0); /\* 注意顺序表基址L.elem\[0\] 表示第一个数，而第i个数则是用 基址L.elem + i - 1来表示,也可以用L.elem\[i-1\]表示。为什么 可以那样表示呢？因为l.elem是基地址，相当于数组头一样，指 示了一个首地址，然后对地址进行加减，形成不同元素的地址。 \*是取地址所指的内容，所以\*(L.elem+i-1)就是第i个数据的值了。 \*/ \*e = \*(L.elem + i - 1); // \*e = L.elem\[i-1\]; return 1; \} /\*算法2.6，P26 返回L中第1个与e满足关系compare()的数据元素的位序。 若这样的数据元素不存在，则返回值为0。 \*/ int LocateElem(SqList L,ElemType e, int(\* compare)( ElemType, ElemType)) \{ ElemType \*p; int i = 1;// i的初值为第1个元素的位序 p = L.elem;// p的初值为第1个元素的存储位置即地址 // 循环比较，直到找到符合关系的元素 while(i <= L.length if(i <= L.length) return i; else return 0; \} \#if 0 /\*算法2.7 与算法2.2区别 已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序 线性表Lc,Lc的元素也按值非递减排列。 算法的时间复杂度为O(La.length + Lb.length). \*/ void MergeList(SqList La, SqList Lb, SqList \*Lc) \{ ElemType \*pa, \*pa\_last, \*pb, \*pb\_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).elem = (ElemType \*)malloc((\*Lc).listsize\*sizeof(ElemType)); if( !(\*Lc).elem )/\* 存储分配失败 \*/ exit(0); pa\_last = La.elem + La.length - 1;//pa\_last指向线性表La的尾结点 pb\_last = Lb.elem + Lb.length - 1;//pb\_last指向线性表Lb的尾结点 while(pa <= pa\_last else//\*pb更小接到pc后 \*pc++ = \*pb++; \} while(pa <= pa\_last)/\* 表La非空且表Lb空 \*/ \*pc++ = \*pa++;/\* 插入La的剩余元素 \*/ while(pb

[41528d3028836879cd698677c3999917.gif]: /images/20221020/c7a11108872f4dbf931c28829b78cf2a.png