數(shù)據(jù)結(jié)構(gòu)習(xí)題集（李冬梅 第2版）C語(yǔ)言版源程序習(xí)題源代碼 習(xí)題集-算法2-2

1、include include using namespace std;/函數(shù)結(jié)果狀態(tài)代碼define OK 1define ERROR 0define OVERFLOW -2 /Status是函數(shù)的返回值類(lèi)型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;/結(jié)點(diǎn)的數(shù)據(jù)域/結(jié)點(diǎn)的指針域/LinkList為指向結(jié)構(gòu)體LNode的指/初始化/銷(xiāo)毀鏈表/后插法創(chuàng)立單鏈表/合并/輸出鏈表typedef struct LNode int data;struct LNode *next;LNode, *LinkList; 針類(lèi)型Status InitList(LinkList &L);St

2、atus DestroyList(LinkList &L);void CreateList_R(LinkList &L,int L_Data,int n);void MergeList(LinkList &LA,LinkList &LB,LinkList &LC);void PrintList(LinkList L);int main() ( int laData=3,5,8,11; int 1bData=2,6,8,9,11,15,20; LinkList la, lb;InitList(la);InitList(lb);CreateList_R(la,laData,sizeof(laDat

3、a)/sizeof(laData0);CreateList_R(lb,IbData,sizeof(IbData)/sizeof(IbData0);LinkList 1c;InitList(lc);MergeList(la,lb,lc); 合并后的線性表為：n; PrintList(lc);DestroyList(lc);return 0; /初始化 Status InitList (LinkList &L) /構(gòu)造一個(gè)空的單鏈表LL=new LNode;/生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)L-next=NULL;/頭結(jié)點(diǎn)的指針域置空return OK; ) /銷(xiāo)毀鏈表 Status D

4、estroyList(LinkList &L) ( while(L)LNode *p=L;L=L-next; delete p;) return OK;)/釋放空間/后插法創(chuàng)立單鏈表void CreateList_R(LinkList &L,int L_Data,int n) /正位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)M單鏈表LLNode *r = L;for (int i=0;idata=L_Datai; p-next=NULL; r-next=p; r=p;)/輸出鏈表void PrintList(LinkList L) LNode *p=L;coutHNonen;p=p-next;whil

5、e(p) coutn - ndata; p=p-next; coutendl;)/尾指針r指向頭結(jié)點(diǎn)/生成新結(jié)點(diǎn)/初始化p的數(shù)據(jù)域?yàn)長(zhǎng)_Datai/將新結(jié)點(diǎn)*P插入尾結(jié)點(diǎn)之后/r指向新的尾結(jié)點(diǎn)*p/合并void MergeList(LinkList &Laz LinkList &Lbz LinkList &Lc) /將兩個(gè)非遞減的有序鏈表La和Lb合并為一個(gè)非遞增的有序鏈表LcLNode *pa=La-next; LNode *pb=Lb-next; Lc=La; LNode *pc=La; Lc-next=NULL;LNode *q;while(pa|pb) (if(!pa) (q=pb;

6、pb=pb-next;)else if(!pb)/pa是鏈表La的工作指針，初始化為首元結(jié)點(diǎn)/pb是鏈表Lb的工作指針，初始化為首元結(jié)點(diǎn)/用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)/只要有一個(gè)表未到達(dá)表尾結(jié)點(diǎn)，用q指向待摘取的元素/La表為空，用q指向pb, pb指針后移/Lb表為空，用q指向pa, pa指針后移q=pa；pa=pa-next;)else if (pa-datadata)/取較小者La中的元素，用q指向pa, pa指針后移q=pa； pa=pa-next;else/取較小者Lb中的元素，用q指向pb, pb指針后移q=pb;pb=pb-next;q-next=Lc-next; Lc-next=q