北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗報告選作1

PAGEPAGE9《數(shù)據(jù)結(jié)構(gòu)與算法統(tǒng)計》實驗報告學(xué)院：班級：學(xué)號：姓名：一、實驗?zāi)康?.熟悉VC++6.0環(huán)境，學(xué)習(xí)使用C++實現(xiàn)鏈表的存儲結(jié)構(gòu)；2.通過編程，上機(jī)調(diào)試，進(jìn)一步理解線性表、鏈表的基本概念。二、實驗內(nèi)容歸并順序表（選作）。請按以下要求編程實現(xiàn)：從鍵盤輸入兩個升序排列的整數(shù)序列l(wèi)inka和linkb，每個序列以輸入0為結(jié)束標(biāo)記。將鏈表linka和linkb歸并為linkc，linkc仍然為升序排列。歸并完成后，linka和linkb為空表。輸出linkc。對linkc進(jìn)行處理，保持升序不變，刪除其中重復(fù)的整數(shù)，對重復(fù)的整數(shù)只保留一個，輸出刪除重復(fù)整數(shù)后的鏈表。例如：linka輸入為：10203040500linkb輸入為：15202530354045500歸并后的linkc為：10152020253030354040455050刪除重復(fù)后的linkc為：101520253035404550三、程序設(shè)計1、概要設(shè)計說明程序的主要功能，主程序的流程以及各個程序模塊之間的調(diào)用關(guān)系，給出主要流程圖。應(yīng)用單鏈線性表寄存數(shù)字序列。⑴單鏈線性表的抽象數(shù)據(jù)類型線性表的定義如下：ADTLinkList{ 數(shù)據(jù)對象： D={ai|ai?ElemSet,i=1,…,n，n≥0} 數(shù)據(jù)關(guān)系： R1={<ai-1,ai>|ai-1,ai?D,i=2,…,n} 基本操作：Creat(LinkList&L) 操作結(jié)果：構(gòu)造單鏈線性表L。 MergeList(LinkList&La,LinkList&Lb,LinkList&Lc) 初始條件：單鏈線性表La，Lb，Lc已經(jīng)存在。 操作結(jié)果：歸并La，Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。Delete(LinkList&L)初始條件：鏈表L已經(jīng)存在。 操作結(jié)果：刪除L中的重復(fù)元素。 Output(LinkList&L)初始條件：單鏈線性表L已經(jīng)存在。 操作結(jié)果：輸出單鏈線性表L中的各項值。}ADTLinkList⑵主程序流程主程序首先調(diào)用Creat(LinkList&L)函數(shù)，構(gòu)造單鏈線性表La，Lb;再調(diào)用MergeList(LinkList&La,LinkList&Lb,LinkList&Lc)函數(shù)歸并La，Lb，得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列;再釋放La，Lb的頭結(jié)點；再調(diào)用Delete(LinkList&L)刪除Lc中的重復(fù)元素；最后調(diào)用Output(LinkList&L)函數(shù)，在屏幕上顯示計算結(jié)果。⑶模塊調(diào)用關(guān)系 由主函數(shù)模塊調(diào)用創(chuàng)建模塊、歸并模塊、刪除模塊和輸出模塊。⑷流程圖開始開始結(jié)束構(gòu)造單鏈線性表La，Lb歸并La，Lb得到新的單鏈線性表Lc刪除L中的重復(fù)元素輸出單鏈線性表L中的各項值2、詳細(xì)設(shè)計⑴數(shù)據(jù)類型設(shè)計typedefstructLNode{ intdata;LNode*next;}LNode,*LinkList;//結(jié)點類型，指針類型⑵操作算法設(shè)計voidCreat(LinkList&L)//構(gòu)造單鏈線性表L{ LinkListp,q; intnum; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; p=L;//建立頭結(jié)點 scanf("%d",&num);while(num!=0)//每個序列以輸入0為結(jié)束標(biāo)記。{ q=(LinkList)malloc(sizeof(LNode)); q->data=num; q->next=p->next; p->next=q;//插入到表尾 p=q; scanf("%d",&num); }} voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)//歸并La，Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。{ LinkListpa,pb,pc,p,q; pa=La->next; pb=Lb->next; Lc=(LinkList)malloc(sizeof(LNode)); Lc->next=NULL; pc=Lc;//建立頭結(jié)點 while(pa&&pb) { q=(LinkList)malloc(sizeof(LNode)); if(pa->data<=pb->data)//La，Lb中的數(shù)據(jù)進(jìn)行比較，插入小的數(shù)據(jù)//小數(shù)據(jù)所在單線性鏈表指針向后移，另一鏈表指針位置不變 { q->data=pa->data; pa=pa->next; } else { q->data=pb->data; pb=pb->next; } q->next=pc->next; pc->next=q; pc=q;//插入到表尾 } while(pa)//若La剩余,插入剩余部分 { p=(LinkList)malloc(sizeof(LNode)); p->data=pa->data; p->next=pc->next; pc->next=p; pa=pa->next; } while(pb)//若Lb剩余,插入剩余部分 { p=(LinkList)malloc(sizeof(LNode)); p->data=pb->data; p->next=pc->next; pc->next=p; pb=pb->next; }}voidDelete(LinkList&L)//刪除Lc中的重復(fù)元素{ LinkListp,q,r; p=L->next; q=L->next->next; r=q; while(q!=NULL) { if(q->data==p->data)//比較數(shù)據(jù) { q=q->next; p->next=r->next; free(r); r=q; } else { p=p->next; q=q->next; r=q; } }}voidOutput(LinkList&L)//輸出單鏈線性表L中的各項值{ LinkListp; p=L->next; while(p->next!=NULL) { printf("%d,",p->data); p=p->next; } printf("%d\n",p->data);}⑶主函數(shù)設(shè)計voidmain(){ LinkListLa,Lb,Lc; Creat(La);//構(gòu)造單鏈線性表La Creat(Lb);//構(gòu)造單鏈線性表Lb MergeList(La,Lb,Lc);//歸并La，Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列 free(La);//釋放La的頭結(jié)點 free(Lb);//釋放Lb的頭結(jié)點 Delete(Lc);//刪除Lc中的重復(fù)元素 Output(Lc);//輸出單鏈線性表Lc中的各項值}四、程序調(diào)試分析在構(gòu)造單線性鏈表La時，直接按照書上的算法進(jìn)行編寫（p->next=L->next;L->next=p）,結(jié)果將新構(gòu)造的結(jié)點插入到了表頭，不符合題目要求，以后應(yīng)注意審題，并加強(qiáng)對于基本編碼的掌握和理解。五、程序運行結(jié)果從鍵盤輸入兩個升序排列的整數(shù)序列l(wèi)inka和linkb，每個序列以輸入0為結(jié)束標(biāo)記。輸出刪除重復(fù)整數(shù)后的鏈表Lc，保持升序不變。測試1：10203040500101520253035404550010,15,20,25,30,35,40,45,50測試2：13579024681001,2,3,4,5,6,7,8,9,10六、程序清單#include<iostream>#include<stdio.h>typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkList;voidCreat(LinkList&L);voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc);voidDelete(LinkList&L);voidOutput(LinkList&L);voidmain(){ LinkListLa,Lb,Lc; Creat(La);//構(gòu)造單鏈線性表La Creat(Lb);//構(gòu)造單鏈線性表Lb MergeList(La,Lb,Lc);//歸并La，Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列 free(La);//釋放La的頭結(jié)點 free(Lb);//釋放Lb的頭結(jié)點 Delete(Lc);//刪除Lc中的重復(fù)元素 Output(Lc);//輸出單鏈線性表Lc中的各項值}voidCreat(LinkList&L)//構(gòu)造單鏈線性表L{ LinkListp,q; intnum; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; p=L;//建立頭結(jié)點 scanf("%d",&num);while(num!=0)//每個序列以輸入0為結(jié)束標(biāo)記。{ q=(LinkList)malloc(sizeof(LNode)); q->data=num; q->next=p->next; p->next=q;//插入到表尾 p=q; scanf("%d",&num); }} voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)//歸并La，Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。{ LinkListpa,pb,pc,p,q; pa=La->next; pb=Lb->next; Lc=(LinkList)malloc(sizeof(LNode)); Lc->next=NULL; pc=Lc;//建立頭結(jié)點 while(pa&&pb) { q=(LinkList)malloc(sizeof(LNode)); if(pa->data<=pb->data)//La，Lb中的數(shù)據(jù)進(jìn)行比較，插入小的數(shù)據(jù)//小數(shù)據(jù)所在單線性鏈表指針向后移，另一鏈表指針位置不變 { q->data=pa->data; pa=pa->next; } else { q->data=pb->data; pb=pb->next; } q->next=pc->next; pc->next=q; pc=q;//插入到表尾 } while(pa)//若La剩余,插入剩余部分 { p=(LinkList)malloc(sizeof(LNode)); p->data=pa->data; p->next=pc->next; pc->next=p; pa=pa->next; } while(pb)//若Lb剩余,插入剩余部分 { p=(LinkList)malloc(sizeof(LNode)); p->data=pb->data; p->next=pc->next; pc->next=p; pb=pb->next; }}voidDelete(LinkList&L)//刪除Lc中的重復(fù)元素{ LinkListp,q,r; p=L->next; q=L->next->next; r=q; while(q!=NULL) { if(q->data==p->data