兩個(gè)有序鏈表的合并.doc

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