归并La和Lb得到新的线性表Lc-(2).doc

1、#include#include#define LIST_INIT_SIZE 100 / 初始化大小#define LISTINCREMENT 15 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 / 不可实行的#define OVERFLOW -2 / 溢出#include / exit()typedef int ElemType; / 基本(元素)类型typedef structElemType * elem;int length;int listsize;SqList;int In

2、itList(SqList *L) / 操作结果：构造一个空的顺序线性表(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem) / 存储分配失败exit(OVERFLOW); (*L).length=0; / 空表长度为 0(*L).listsize=LIST_INIT_SIZE; / 初始存储容量return OK;int DestroyList(SqList *L) / 初始条件：顺序线性表 L 已存在。操作结果：销毁顺序线性表 L free(*L).elem);(*L).elem=NULL;(*

3、L).length=0;(*L).listsize=0;return OK;int ClearList(SqList *L) / 初始条件：顺序线性表 L 已存在。操作结果：将 L 重置为空表 (*L).length=0;return OK;int ListEmpty(SqList L) / 初始条件：顺序线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSEif(L.length=0)return TRUE;elsereturn FALSE;int ListLength(SqList L) / 初始条件：顺序线性表 L 已存在。操作结果：返回 L 中数据元素个数

4、return L.length;int GetElem(SqList L,int i,ElemType *e) / 初始条件：顺序线性表 L 已存在，1iListLength(L) 。操作结果：用 e 返回L 中第 i 个数据元素的值if(iL.length)exit(ERROR);*e=*(L.elem+i-1);return OK;int LocateElem(SqList L,ElemType e) / 初始条件：顺序线性表 L 已存在。操作结果：返回 L 中第 1 个与 e 相等的数据元素的位序。若这样的数据元素不存在，则返回值为 0。ElemType *p;int i=1; / i

5、的初值为第 1 个元素的位序p=L.elem; / p 的初值为第 1 个元素的存储位置while(iL.length)return INFEASIBLE;else*pre_e=*-p;return OK;int NextElem(SqList L,ElemType cur_e,ElemType *next_e) / 初始条件：顺序线性表 L 已存在。操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继，否则操作失败，next_e 无定义int i=1;ElemType *p=L.elem;while(i(*L).length+1) / i 值不合法r

6、eturn ERROR;if(*L).length=(*L).listsize) / 当前存储空间已满，增加分配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)

7、 / 插入位置及之后的元素右移*(p+1)=*p;*q=e; / 插入 e+(*L).length; / 表长增 1return OK;int ListDelete(SqList *L,int i,ElemType *e) / 初始条件：顺序线性表 L 已存在，1iListLength(L) 。操作结果：删除 L的第 i 个数据元素，并用 e 返回其值，L 的长度减 1ElemType *p,*q;if(i(*L).length) / i 值不合法return ERROR;if(*L).length=0) / i 值不合法return ERROR;p=(*L).elem+i-1; / p 为被

8、删除元素的位置*e=*p; / 被删除元素的值赋给 eq=(*L).elem+(*L).length-1; / 表尾元素的位置for(+p;p=q;+p) / 被删除元素之后的元素左移*(p-1)=*p;(*L).length-; / 表长减 1return OK;void MergeList(SqList La,SqList Lb,SqList *Lc) / 算法 2.2/ 已知线性表 La 和 Lb 中的数据元素按值非递减排列/ 归并 La 和 Lb 得到新的线性表 Lc，Lc 的数据元素也按值非递减有序排列ElemType ai,bj;int La_len,Lb_len;int i=1,

9、j=1,k=0;La_len=ListLength(La); / 求线性表的长度Lb_len=ListLength(Lb); while(i=La_len) / 取 La 中第 i 个数据元素赋给 aiGetElem(Lb,j, / 取 Lb 中第 j 个数据元素赋给 bjif(ai=bj) / 将 La 和 Lb 中较小的数赋值给 LcListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La_len) / 若 La 中数据元素没有全部赋给 Lc，则将剩下的元素都赋给 LcGetElem(La,i+,ListInsert(L

10、c,+k,ai);while(j=Lb_len) / 若 Lb 中数据元素没有全部赋给 Lc，则将剩下的元素都赋给 LcGetElem(Lb,j+,ListInsert(Lc,+k,bj);void print(ElemType *c)printf(“%d “,*c);void main()SqList La,Lb,Lc;int i,j,k;InitList( / 创建空表 La 成功 printf(“请输入 La 的 4 个数据元素 Please enter the La four data elements：“);for(j=1;j=4;j+) / 在表 La 中插入 4 个元素 scan

11、f(“%d“,i=ListInsert(printf(“La=“); / 输出表 La 的内容 for(i=0;iLa.length;i+)print(printf(“n“);InitList( / 也可不判断是否创建成功 printf(“请输入 Lb 的 7 个数据元素 Please input Lb seven data elements：“);for(j=1;j=7;j+) / 在表 Lb 中插入 7 个元素scanf(“%d“,i=ListInsert(printf(“Lb=“); / 输出表 Lb 的内容 for(i=0;iLb.length;i+)print(printf(“n“);i=InitList( / 创建空表 La 成功 MergeList(La,Lb,printf(“Lc=“); / 输出表 Lc 的内容 for(i=0;iLc.length;i+)print(printf(“n“);