实验1链表的应用-有序表的查找与合并

1. 实验题目 线性表的应用2. 实验内容 有序表的查找与合并3. 实验目的掌握线性表的概念及原理，运用线性表的原理完成实验题目中的内容。4. 实验要求为了更好的掌握与理解课堂上老师所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序代码（写在纸上与盘中均可），以便在实验课中完成老师所布置的实验内容。5.概要设计原理6.详细程序清单及注释说明#include using namespace std;#include#include#include #include #include #include #include #include #include/#define OVERFLOW -2 #define TRUE 1#define FALSE 0 #define OK 1#define ERROR 0#define INFEASIBLE -1#define LIST_INIT_SIZE 100#define LISTINCREMENT 2 / 线性表存储空间的分配增量 typedef int Status;typedef int ElemType; typedef struct int *elem; int length; int listsize;SqList;int InitList_sq(SqList &L ) /构建顺序表LL.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;bool ListEmpty(SqList &L) / 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE if(L.length=0) return TRUE; else return FALSE; int DestroyList_sq(SqList &L) / 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L if(ListEmpty(L) free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return OK; int ClearList(SqList &L) / 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 if(ListEmpty(L) L.length=0; return OK;int ListInsert_sq(SqList &L,int i,int &e) / 初始条件：顺序线性表L已存在，1iListLength(L)+1 / 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1int *q,*p,*newbase;if(i(L.length+1) return ERROR; / i值不合法 if(L.length=L.listsize) / 当前存储空间已满,增加分配 if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) exit(OVERFLOW); / 存储分配失败 L.elem=newbase; / 新基址 L.listsize+=LISTINCREMENT; / 增加存储容量 q=&(L.elemi-1); / q为插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/ 插入位置及之后的元素右移 *q=e; / 插入e +L.length; /表长增1 return OK;/int ListDelete_sq(SqList &L,int i) / 初始条件：顺序线性表L已存在，1iListLength(L)/ int *q,*p; / 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 / int e;/if(i(L.length) return ERROR; /i值不合法/q=&L.elemi-1; /q为删除元素位置/e=*q; /有e存被删元素 /cout删除的元素是：;/couteendl;/p=L.elem+L.length-1; /for(+q;q=p;+q) / *(q-1)=*q;/删除之后元素左移/-L.length;/表长减1/return OK;/int ListLength_sq(SqList L) / 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 return L.length; int GetElem_sq(SqList L,int i) int e ; / 初始条件：顺序线性表L已存在，1iListLength(L) / 操作结果：用e返回L中第i个数据元素的值 if(iL.length) exit(ERROR); e=*(L.elem+i-1); cout查找的元素为：eendl; return OK; int Listbijiao(SqList L) int *p,*p_last,*q; p=L.elem; L.length=ListLength_sq(L); p_last=L.elem+L.length-1; for(p;p=p_last;p+) coutslj; for(q=p+1;q=p_last;q+) if(*p=*q) return OK; else ; void MergeList_sq(SqList &La,SqList &Lb,SqList &Lc) /合并两个线性列表int *pa,*pb,*pc,*pa_last,*pb_last,*pc_last; pa=La.elem; pb=Lb.elem; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;+Lc.length;while(pa=pa_last) *pc+=*pa+;+Lc.length;while(pb=pb_last) *pc+=*pb+;+Lc.length; pc_last=Lc.elem+Lc.length-1;cout链表长：Lc.lengthendl;cout合并后的链表为：endl;for(pc=Lc.elem;pc=pc_last;pc+)cout *pc;coutendl;void main() SqList la,lb,lc; int e,k,j; int i; cout初始化la：; i=InitList_sq(la);/ coutla.elem=;/ coutla.elem; / cout ; if(la.length=0)cout初始化成功!; else cout初始化失败!endl; coutla的初始长度为： la.lengthendl; coutj; coutendl; cout按非递增输入数字：; for(k=1;k=j;k+) coute; i=ListInsert_sq(la,1,e); coutla:; Listbijiao(la);for(k=0;k=(la.length-1);k+) coutla.elemk;cout ;coutendl;/cout在第i(ie;/cout ;/i=ListInsert_sq(la,i,e);/coutla变为：;/for(k=0;k=(la.length-1);k+)/ /coutla.elemk;/cout ;/coutendl;/*i= ListDelete_sq(la,2);cout删除第二个元素后la变为：;for(k=0;(k=la.length-1);k+) coutla.elemk;cout ;coutendl;*/cout初始化lb：;i=InitList_sq(lb);/coutlb.elem=;/coutlb.elem;/cout ;/coutlb.length= ;/coutlb.length;/coutendl;/cout请输入j（jj;/ coutendl; if(lb.length=0)cout初始化成功!; else cout初始化失败!endl; coutlb的初始长度为： lb.lengthendl; coutj; coutendl按非递增输入数字：; for(k=1;k=j;k+) coute; i=ListInsert_sq(lb,1,e); coutlb:;for(k=0;k=(lb.length-1);k+) coutlb.elemk;cout ;coutendl;la.length=ListLength_sq(la);lb.length=ListLength_sq(lb);coutla.length= la.length lb.length=lb.length;coutendl;couti;GetElem_sq(la,i);i=InitLi