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

#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 struct ElemType * elem; int length; int listsize;SqList;int InitList(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; (*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，否则返回FALSE if(L.length=0) return TRUE; else return FALSE;int ListLength(SqList L) / 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 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的初值为第1个元素的位序 p=L.elem; / p的初值为第1个元素的存储位置 while(i=L.length&(*p+!=e) +i; if(i=L.length) return i; else return 0;int PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) / 初始条件：顺序线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。 int i=2; ElemType *p=L.elem+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(iL.length&*p!=cur_e) i+; p+; if(i=L.length) return INFEASIBLE; else *next_e=*+p; return OK; int ListInsert(SqList *L,int i,ElemType e) / 初始条件：顺序线性表L已存在，1iListLength(L)+1 。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase,*q,*p; if(i(*L).length+1) / i值不合法 return 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) / 插入位置及之后的元素右移 *(p+1)=*p; *q=e; / 插入e +(*L).length; / 表长增1 return OK;int ListDelete(SqList *L,int i,ElemType *e) / 初始条件：顺序线性表L已存在，1iListLength(L) 。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ElemType *p,*q; if(i(*L).length) / i值不合法 return ERROR; if(*L).length=0) / i值不合法 return ERROR; p=(*L).elem+i-1; / p为被删除元素的位置 *e=*p; / 被删除元素的值赋给e q=(*L).elem+(*L).length-1; / 表尾元素的位置 for(+p;p=q;+p) / 被删除元素之后的元素左移 *(p-1)=*p; (*L).length-; / 表长减1 return 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,j=1,k=0; La_len=ListLength(La); / 求线性表的长度 Lb_len=ListLength(Lb); while(i=La_len)&(j=Lb_len) / La和Lb均非空 GetElem(La,i,&ai); / 取La中第i个数据元素赋给ai GetElem(Lb,j,&bj); / 取Lb中第j个数据元素赋给bj if(ai=bj) / 将La和Lb中较小的数赋值给Lc ListInsert(Lc,+k,ai); +i; else ListInsert(Lc,+k,bj); +j; while(i=La_len) / 若La中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc GetElem(La,i+,&ai); ListInsert(Lc,+k,ai); while(j=Lb_len) / 若Lb中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc GetElem(Lb,j+,&bj); ListInsert(Lc,+k,bj); void print(ElemType *c) printf(%d ,*c);void main() SqList La,Lb,Lc; int i,j,k; InitList(&La); / 创建空表La成功 printf(请输入La的4个数据元素Please enter the La four data elements：); for(j=1;j=4;j+) / 在表La中插入4个元素 scanf(%d,&k); i=ListInsert(&La,j,k); printf(La=); / 输出表La的内容 for(i=0;iLa.length;i+) print(&La.elemi); printf(n); InitList(&Lb); / 也可不判断是否创建成功 printf(请输入Lb的7个数据元素Please input Lb seven data elements：); for(j=1;j=7;j+) / 在表Lb中插入7个元素 scanf(%d,&k); i=ListInsert(&Lb,j,k); print