兩個有序鏈表的合并.doc

數(shù)據(jù)結(jié)構(gòu)實驗報告班級：JS001001 姓名：周衛(wèi)華 學(xué)號：2010300028 E-mail:770234417實驗題目: 將兩個帶頭結(jié)點的有序循環(huán)鏈表合并成一個帶頭結(jié)點的有序循環(huán)鏈表實驗?zāi)康模?.掌握使用visual c+6.0上機(jī)調(diào)試程序的基本方法。 2.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-循環(huán)鏈表的定義及C語言實現(xiàn)。 3.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)-循環(huán)鏈表中的基本操作如將兩個循環(huán)鏈表合并為一個循環(huán)鏈表的操作。實驗內(nèi)容：設(shè)A與B分別為兩個帶有頭結(jié)點的有序循環(huán)鏈表（所謂有序是指鏈接點按數(shù)據(jù)域值大小鏈接，本題不妨設(shè)按數(shù)據(jù)域值從小到大排列），list1和list2分別為指向兩個鏈表的頭指針。將這兩個鏈表合并為一個帶頭結(jié)點的有序循環(huán)鏈表。一、需求分析 本程序需要實現(xiàn)將兩個有序循環(huán)鏈表合成一個有序循環(huán)鏈表的功能，即對這個程序輸入兩個有序循環(huán)鏈表，該程序輸出一個有序循環(huán)鏈表。對于輸入的兩個循環(huán)鏈表要求是必須是有序非遞減的，如1，2，3，5，7符合輸入條件，但是3，5，4，7，2，9則不符合輸入條件。輸入值可以是任意實數(shù)。輸出的有序循環(huán)鏈表依賴于輸入的兩個有序循環(huán)鏈表。如輸入的兩個鏈表為1，3，4，6，8；2，5，7，9則輸出的鏈表為1，2，3，4，5，6，7，8，9.上面展示了輸入正確時的預(yù)期輸出，當(dāng)輸入不正確時則不能得到正確的輸出，如輸入1，3，5，4，6；2，5，3，7時輸出為1，2，3，5，4，5，3，6，7顯然不正確。二、 概要設(shè)計 按照題意，本程序中使用單向循環(huán)鏈表作為存儲結(jié)構(gòu)，每一個節(jié)點為結(jié)構(gòu)體類型，存放數(shù)據(jù)和下一個節(jié)點的地址?；玖鞒倘缦拢憾x三個該結(jié)構(gòu)體類型的指針變量list1,list2,head；期中l(wèi)ist1,list2用來構(gòu)造存放輸入數(shù)據(jù)的兩個循環(huán)鏈表的頭指針，head用來作為生成的第三個循環(huán)鏈表的頭指針。接下來主函數(shù)調(diào)用creat()函數(shù)并手工輸入數(shù)據(jù)構(gòu)成兩個待合并鏈表。然后調(diào)用print()函數(shù)用來打印list1,list2來驗證構(gòu)造的鏈表正確。鏈表構(gòu)造完成后調(diào)用mergell()函數(shù)來合并list1,list2并存放在head中，最后把head打印出來。本程序主要模塊有：主程序模塊，構(gòu)造鏈表并輸入數(shù)據(jù)模塊，打印輸出鏈表模塊，合并鏈表模塊。三、詳細(xì)設(shè)計 1.元素類型，節(jié)點類型和指針類型：元素類型：int num; int lista=0,listb=0; 節(jié)點類型： struct list int num; struct list *next;指針類型：struct list *head,*end; struct list *pa,*pb,*pc; struct list *list1,*list2,;2每個模塊的分析： （1）主程序模塊： int main() /主函數(shù) printf( 歡迎使用將兩個有序循環(huán)鏈表合并成一個有序循環(huán)鏈表程序); struct list*list1,*list2,*head;/定義三個struct list類型的指針變量 list1=(struct list *)malloc(sizeof(struct list); list2=(struct list *)malloc(sizeof(struct list); head=(struct list *)malloc(sizeof(struct list);/為list1,list2,head申請空間 printf(n請按從小到大的順序輸入第一組有序循環(huán)鏈表，以0結(jié)束n); list1=creat(); /調(diào)用創(chuàng)建鏈表的函數(shù) printf(輸入的這組鏈表是：n); print(list1); /打印第一個鏈表 printf(nn請按從小到大的順序輸入第二組有序循環(huán)鏈表，以0結(jié)束n); list2=creat(); /調(diào)用創(chuàng)建鏈表的函數(shù) printf(輸入的這組鏈表是：n); print(list2); /打印第二個循環(huán)鏈表 mergell (list1,list2,head) ; /調(diào)用合并兩個鏈表的函數(shù) printf(nn合并后的有序循環(huán)鏈表為：n); print(head-next);/打印合并后的循環(huán)鏈表 return 0; （2）構(gòu)造鏈表并輸入每個數(shù)據(jù)模塊： struct list *creat() /定義創(chuàng)建鏈表的函數(shù) struct list*p=NULL; struct list*q=NULL; /定義兩個活動指針變量 head=NULL; int num; scanf(%d,&num); while(num!=0) p=(struct list *)malloc(sizeof (struct list); /開辟空間 p-num=num; if(head=NULL) head=p; else q-next=p; q=p; scanf(%d,&num); end=q; /將鏈表的結(jié)尾最后一個結(jié)點賦給end end-next=head; /讓最后一個結(jié)點的的下個結(jié)點的地址不為空而指向頭指針 return(head); /返回新建鏈表的頭指針（3）打印已經(jīng)構(gòu)造完成的鏈表模塊void print(struct list*head) /定義打印循環(huán)鏈表的函數(shù) struct list*r=head; /定義活動指針變量以輸出各節(jié)點數(shù)據(jù) do printf(%d ,r-num); r=r-next; while(r!=head); /當(dāng)活動指針重新指向頭結(jié)點時，循環(huán)結(jié)束 （4）合并兩個有序循環(huán)鏈表模塊struct list *mergell(struct list *la,struct list *lb,struct list * lc) /定義合并函數(shù)struct list *pa,*pb,*pc; /定義三個活動指針變量分別指向la,lb,lcint lista=0,listb=0;pc=lc;pa=la;pb=lb; /為pa,pb,pc賦值while(pa!=la)|(lista=0)&(pb!=lb)|(listb=0)/使用while循環(huán)語句 if(pa-numnum)pc-next=pa;pc=pa;pa=pa-next;lista=1;elsepc=pb;pb=pb-next;listb=1;if(pa!=la) /如果lb數(shù)據(jù)已經(jīng)完成排序而la還有數(shù)據(jù)未排，則把la未排數(shù)據(jù)插入到lc后面 while(pa!=la) pc-next=pa; pc=pa; pa=pa-next; pc-next=lc-next; else /如果la數(shù)據(jù)已經(jīng)完成排序而lb還有數(shù)據(jù)未排，則把lb未排數(shù)據(jù)插入到lc后面 while(pb!=lb) pc-next=pb; pc=pb; pb=pb-next; pc-next=lc-next; 函數(shù)調(diào)用關(guān)系如下所示：main() creat();print();creat();print();mergell();print();3.完整的程序見附件。四、程序使用說明及測試結(jié)果1.程序使用說明（1）本程序的運行環(huán)境是codeblocks (2)當(dāng)程序運行后，界面出現(xiàn)“請按從小到大的順序輸入第一組有序循環(huán)鏈表，以0結(jié)束”字樣，這時，將第一組有序循環(huán)鏈表輸入，并在有效數(shù)據(jù)后面添加0作為結(jié)束標(biāo)志。接著界面出現(xiàn)“請按從小到大的順序輸入第二組有序循環(huán)鏈表，以0結(jié)束”按照同樣的方法輸入即可。輸入完畢后程序會自動輸出合并后的有序循環(huán)鏈表。2.測試結(jié)果 當(dāng)?shù)谝唤M鏈表為：1，3，5，6，9第二組鏈表為3，4，5，7，8時，該程序輸出為1，3，3，4，5，5，6，7，8，93調(diào)試過程中遇到的問題及解決辦法在調(diào)試發(fā)現(xiàn)輸出有亂數(shù)的問題，后來發(fā)現(xiàn)當(dāng)定義一個結(jié)構(gòu)體指針變量時必須給它申請一個空間才能實際應(yīng)用，即struct list*list1,*list2,*head;/定義三個struct list類型的指針變量 list1=(struct list *)malloc(sizeof(struct list); list2=(struct list *)malloc(sizeof(struct list); head=(struct list *)malloc(sizeof(struct list);另外我對循環(huán)結(jié)構(gòu)的應(yīng)用不夠靈活，尤其對循環(huán)終止條件的確定比較弱。4運行界面如下所示 五、實驗總結(jié) 在剛開始進(jìn)行編程時，由于大腦中沒有形成具體的思路，導(dǎo)致思維比較混亂，到后來我靜下心來，采用從上到下的編程方法，將一個大問題分解成幾個小問題進(jìn)行逐一突破，例如我編寫了creat（）