實驗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變?yōu)椋?/for(k=0;k=(la.length-1);k+)/ /coutla.elemk;/cout ;/coutendl;/*i= ListDelete_sq(la,2);cout刪除第二個元素后la變?yōu)椋?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