數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--單鏈表兩個(gè)集合相加減的算法

1、<p>　　單 位: 計(jì)算機(jī)051班 </p><p>　　學(xué) 號: </p><p><b>　　課程設(shè)計(jì)</b></p><p>　?。ㄓ?jì)算機(jī)科學(xué)與技術(shù)專業(yè)）</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　姓

2、 名： </p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)</p><p><b>　　指導(dǎo)教師： </b></p><p><b>　　二○○八年六月</b></p><p><b>　　一、課程設(shè)計(jì)</b></p><p>　　

3、設(shè)計(jì)題目：單鏈表兩個(gè)集合相加減的算法</p><p>　　為了實(shí)現(xiàn)單鏈表的幾種運(yùn)算功能，需要用到多張函數(shù)程序，例如：建表--readdata(pointer *head)，單鏈表元素排序--sort(pointer *head)，輸出單鏈表L --disp(pointer *head)，求兩有序集合的并。兩個(gè)集合A和B，它們的并集為集合C--bing(pointer *head1,pointer *head2,

4、pointer *head3)，求兩有序集合的交。兩個(gè)集合A和B，它們的交集為集合C-- jiao(pointer *head1,pointer *head2, pointer *head3)，求兩有序集合的差。兩個(gè)集合A和B，它們的差集為集合C-- cha(pointer *head1,pointer *head2, pointer *head3)，首先建立單鏈表，再調(diào)用函數(shù)sort()構(gòu)成有序單鏈表，最后求用有序單鏈表表示的兩個(gè)集合

5、的相關(guān)運(yùn)算-- main()。首先設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單程序，然后再為這些菜單項(xiàng)配上相應(yīng)的功能。</p><p><b>　　一、主控菜單設(shè)計(jì)</b></p><p><b>　　1）菜單內(nèi)容</b></p><p>　　程序運(yùn)行后，給出7個(gè)菜單項(xiàng)的內(nèi)容和輸入提示：</p><p><

6、;b>　　集合1為</b></p><p><b>　　集合2為</b></p><p>　　集合1與集合2的并為</p><p>　　集合1與集合2的交為</p><p>　　集合1與集合2的差為</p><p>　　集合2與集合1的差為</p><p>

7、;<b>　　退出管理系統(tǒng)</b></p><p><b>　　二、鏈表介紹</b></p><p><b>　　1）建立單向鏈表</b></p><p>　　在函數(shù)中首先為Head申請了—個(gè)所指向的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為鏈表的首結(jié)點(diǎn)。開始鏈表的頭指針和尾指針都指向頭結(jié)點(diǎn)，以后每輸入一個(gè)數(shù)則申請一個(gè)結(jié)點(diǎn)，將

8、輸入的數(shù)放到結(jié)點(diǎn)的信息域后。輸入結(jié)束后，置鏈表最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?，返回鏈表頭指針。單向鏈表中插入結(jié)點(diǎn)在單向鏈表中插入一個(gè)結(jié)點(diǎn)要引起插入位置前面結(jié)點(diǎn)的指針的變化，在插入一個(gè)結(jié)點(diǎn)時(shí)首先要由（new pointer)向系統(tǒng)申請一個(gè)存儲(chǔ)pointer類型變量的空間，并將該空間的首地址賦給指向新結(jié)點(diǎn)的指針head，在為該新結(jié)點(diǎn)的信息域賦值后，先要將該結(jié)點(diǎn)插入位置后面一個(gè)結(jié)點(diǎn)的指針賦給該結(jié)點(diǎn)的指針域，然后才能將指向該結(jié)點(diǎn)的指針賦給其前一個(gè)結(jié)點(diǎn)

9、的指針域，這樣來完成插入過程。在單向鏈表中刪除個(gè)結(jié)點(diǎn)同樣要引起刪除結(jié)點(diǎn)的前面結(jié)點(diǎn)的指針的變化。</p><p><b>　　2）編歷鏈表</b></p><p>　　由于鏈表是一個(gè)動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，鏈表的各個(gè)結(jié)點(diǎn)由指針鏈接在起，訪問鏈表元素時(shí)通過每個(gè)鏈表結(jié)點(diǎn)的指針逐個(gè)找到該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，—直找到鏈表尾，鏈表的最后一個(gè)結(jié)點(diǎn)的指針為空。</p><p

10、><b>　　3）雙向鏈表</b></p><p>　　每個(gè)結(jié)點(diǎn)中只包括一個(gè)指向下個(gè)結(jié)點(diǎn)的指針域，這種鏈表稱為單向鏈表。如果要在單向鏈表一個(gè)指針?biāo)傅漠?dāng)前位置插入一個(gè)新結(jié)點(diǎn)，就必須從鏈表頭指針開始逐個(gè)遍歷直到當(dāng)前指針?biāo)附Y(jié)點(diǎn)的前一結(jié)點(diǎn)，修改這個(gè)結(jié)點(diǎn)的指針。雙向鏈表的每個(gè)結(jié)點(diǎn)中包括兩個(gè)指針域，分別指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)。在雙向鏈表中由任何一個(gè)結(jié)點(diǎn)都很容易找到其前面的結(jié)點(diǎn)和后面

11、的結(jié)點(diǎn)，而不需要在上述的插入(及刪除)操作中由頭結(jié)點(diǎn)開始尋找。</p><p>　　4）本程序中包含如下函數(shù)</p><p>　　readdata(pointer *head):建表</p><p>　　sort(pointer *head) : 單鏈表元素排序</p><p>　　disp(pointer *head) :輸出單鏈表L<

12、;/p><p>　　bing(pointer *head1,pointer *head2, pointer *head3):求兩有序集合的并。兩個(gè)集合1和2，它們的并集為集合3</p><p>　　jiao(pointer *head1,pointer *head2, pointer *head3):求兩有序集合的交。兩個(gè)集合1和2，它們的交集為集合3</p><p>

13、　　cha(pointer *head1,pointer *head2, pointer *head3):求兩有序集合的差。兩個(gè)集合1和2，它們的差集為集合3</p><p>　　main():首先建立單鏈表，再調(diào)用函數(shù)sort()構(gòu)成有序單鏈表，最后求用有序單鏈表表示的兩個(gè)集合的相關(guān)運(yùn)算</p><p><b>　　5）建立鏈表</b></p><

14、;p>　　要求建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。我們知道建立單鏈表有兩種方法，一種稱之為頭插法，另一種稱為尾插法。頭插法是每次將新插入的結(jié)點(diǎn)插入在鏈表的表頭，而尾插法是將新插入的結(jié)點(diǎn)插入在鏈表的表尾。在這里只介紹用尾插法建立鏈表的算法設(shè)計(jì)思想及具體算法實(shí)現(xiàn)，頭插法留給讀者自己去做。</p><p>　　要建立鏈表，首先要生成結(jié)點(diǎn)，因此，尾插法建立鏈表的算法描述如下：</p><p>　　使鏈

15、表的頭尾指針head, rear指向新生成的頭結(jié)點(diǎn)（也是尾結(jié)點(diǎn)）；</p><p>　　置結(jié)束標(biāo)志0（假）；</p><p>　　While (結(jié)束標(biāo)志不為真)</p><p><b>　　{</b></p><p>　　P指向新生成的結(jié)點(diǎn)；</p><p>　　讀入一個(gè)通訊者數(shù)據(jù)至新結(jié)點(diǎn)的數(shù)據(jù)域

16、；</p><p>　　將新結(jié)點(diǎn)鏈到尾結(jié)點(diǎn)之后；</p><p>　　使尾結(jié)點(diǎn)指向新結(jié)點(diǎn)；</p><p>　　提示：是否結(jié)束建表，讀入一個(gè)結(jié)束標(biāo)志；</p><p><b>　　}</b></p><p>　　尾結(jié)點(diǎn)指針域置空值NULL。</p><p><b>

17、;　　6）鏈表結(jié)點(diǎn)的插入</b></p><p>　　鏈表結(jié)點(diǎn)的插入，是要求將一個(gè)通訊者數(shù)據(jù)結(jié)點(diǎn)按其編號的次序插入有序通訊錄表的相應(yīng)位置，以保持通訊錄表的有序性。插入結(jié)點(diǎn)的基本思想是：使用兩個(gè)指針變量p1和p2分別指向當(dāng)前剛訪問過的結(jié)點(diǎn)和下一個(gè)待訪問的結(jié)點(diǎn)，循環(huán)順序查找鏈表，尋找插入結(jié)點(diǎn)的位置，其中p1指向待插入位置的前一個(gè)結(jié)點(diǎn)。插入操作是非常簡單的。其實(shí)現(xiàn)算法描述如下：</p><

18、;p>　?。?）用p1指向原鏈表頭結(jié)點(diǎn)，p2指向鏈表的第一個(gè)結(jié)點(diǎn)；</p><p>　?。?） While (p2 != NULL && strcmp(p2->data.num, p->data.num) < 0)</p><p><b>　　{</b></p><p>　　P1 = p2;

19、 //p1指向剛訪問過的結(jié)點(diǎn)</p><p>　　P2 = p2->next; //p2指向表的下一個(gè)結(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　插入新結(jié)點(diǎn)</b></p><p><b>　　7）鏈表的輸出</b></p&g

20、t;<p>　　鏈表的輸出相對來說比較簡單，只要將表頭指針賦給一個(gè)指針變量p,然后p向后掃描，直至表尾，p為空為止</p><p>　　三 程序代碼及功能實(shí)現(xiàn)</p><p><b>　　程序代碼如下： </b></p><p><b>　　*/</b></p><p>　　#incl

21、ude<stdio.h> </p><p>　　#include<stdlib.h> </p><p>　　typedef struct pointer{ </p><p>　　char dat; </p><p>　　struct pointer *link; </p><p>　　} poi

22、nter; </p><p>　　void readdata(pointer *head){ //讀集合 </p><p>　　pointer *p; </p><p>　　char tmp; </p><p>　　printf("請輸入任意字符串\n"); </p><p>　　scanf(&qu

23、ot;%c",&tmp); </p><p>　　while(tmp!='\n') </p><p><b>　　{ </b></p><p>　　p=(pointer *)malloc(sizeof(struct pointer)); </p><p>　　p->dat=tmp;

24、 </p><p>　　p->link=head->link; </p><p>　　head->link=p; </p><p>　　scanf("%c",&tmp); </p><p><b>　　} </b></p><p><b>　

25、　} </b></p><p>　　void sort(pointer *head)//單鏈表排序</p><p><b>　　{</b></p><p>　　pointer *p=head->link,*q,*r;</p><p>　　if(p!=NULL) </p

26、><p><b>　　{</b></p><p>　　r=p->link;</p><p>　　p->link=NULL;</p><p><b>　　p=r;</b></p><p>　　while(p!=NULL)</p><p><

27、b>　　{</b></p><p>　　r=p->link;</p><p><b>　　q=head;</b></p><p>　　while(q->link!=NULL&&q->link->dat<p->dat)</p><p>　　q=q->

28、;link; //在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q</p><p>　　p->link=q->link; //將*p插到*q之后</p><p>　　q->link=p;</p><p><b>　　p=r;</b></p><p><b>　　}&

29、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void disp(pointer *head){ //顯示集合數(shù)據(jù) </p><p>　　pointer *p; </p><p>　　p=head-&g

30、t;link; </p><p>　　while(p!=NULL) </p><p><b>　　{ </b></p><p>　　printf("%c ",p->dat); </p><p>　　p=p->link; </p><p><b>　　} &

31、lt;/b></p><p>　　printf("\n"); </p><p><b>　　} </b></p><p>　　void bing(pointer *head1,pointer *head2, pointer *head3){ //計(jì)算集合1與集合2的并 </p><p>　　po

32、inter *p1,*p2,*p3; </p><p>　　p1=head1->link; </p><p>　　while(p1!=NULL) </p><p><b>　　{ </b></p><p>　　p3=(pointer *)malloc(sizeof(struct pointer)); </p&

33、gt;<p>　　p3->dat=p1->dat; </p><p>　　p3->link=head3->link; </p><p>　　head3->link=p3; </p><p>　　p1=p1->link; </p><p><b>　　} </b></

34、p><p>　　p2=head2->link; </p><p>　　while(p2!=NULL) </p><p><b>　　{ </b></p><p>　　p1=head1->link; </p><p>　　while((p1!=NULL)&&(p1->d

35、at!=p2->dat)) </p><p>　　p1=p1->link; </p><p>　　if(p1==NULL) </p><p><b>　　{ </b></p><p>　　p3=(pointer *)malloc(sizeof(struct pointer)); </p><

36、;p>　　p3->dat=p2->dat; </p><p>　　p3->link=head3->link; </p><p>　　head3->link=p3; </p><p><b>　　} </b></p><p>　　p2=p2->link; </p>&

37、lt;p><b>　　} </b></p><p><b>　　} </b></p><p>　　void jiao(pointer *head1,pointer *head2, pointer *head3){ //計(jì)算集合1與集合2的交 </p><p>　　pointer *p1,*p2,*p3; </p

38、><p>　　p1=head1->link; </p><p>　　while(p1!=NULL) </p><p><b>　　{ </b></p><p>　　p2=head2->link; </p><p>　　while((p2!=NULL)&&(p2->da

39、t!=p1->dat)) </p><p>　　p2=p2->link; </p><p>　　if((p2!=NULL)&&(p2->dat=p1->dat)) </p><p><b>　　{ </b></p><p>　　p3=(pointer *)malloc(sizeof

40、(struct pointer)); </p><p>　　p3->dat=p1->dat; </p><p>　　p3->link=head3->link; </p><p>　　head3->link=p3; </p><p><b>　　} </b></p><p&

41、gt;　　p1=p1->link; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void cha(pointer *head1,pointer *head2, pointer *head3){ //計(jì)算集合1與集合2的差 </p><p

42、>　　pointer *p1,*p2,*p3; </p><p>　　p1=head1->link; </p><p>　　while(p1!=NULL) </p><p><b>　　{ </b></p><p>　　p2=head2->link; </p><p>　　whi

43、le((p2!=NULL)&&(p2->dat!=p1->dat)) </p><p>　　p2=p2->link; </p><p>　　if(p2==NULL) </p><p><b>　　{ </b></p><p>　　p3=(pointer *)malloc(sizeof(s

44、truct pointer)); </p><p>　　p3->dat=p1->dat; </p><p>　　p3->link=head3->link; </p><p>　　head3->link=p3; </p><p><b>　　} </b></p><p>

45、;　　p1=p1->link; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　int menu_select( )</p><p><b>　　{</b></p><p><b>

46、;　　int sn;</b></p><p>　　printf(" 集合運(yùn)算 \n");</p><p>　　printf("================================\n");</p><p>　　printf(" 1. 集合1為

47、 \n");</p><p>　　printf(" 2. 集合2為 \n");</p><p>　　printf(" 3. 集合1與集合2的并為 \n");</p><p>　　printf(" 4. 集合1與集合2的交

48、為 \n");</p><p>　　printf(" 5. 集合1與集合2的差為 \n");</p><p>　　printf(" 6. 集合2與集合1的差為 \n");</p><p>　　printf(

49、" 0. 退出管理系統(tǒng) \n");</p><p>　　printf("================================\n");</p><p>　　printf(" 請選擇 0-6 ： \n");</p><p&

50、gt;　　for ( ; ;)</p><p><b>　　{</b></p><p>　　scanf( "%d", &sn);</p><p>　　if (sn < 0 || sn > 6)</p><p>　　printf("\n\t 輸入錯(cuò)誤， 重選0-8 :

51、 ");</p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　return sn;</p><p><b>　　界面如下：<

52、/b></p><p>　　void readdata(pointer *head);</p><p>　　void sort(pointer *head);</p><p>　　void disp(pointer *head);</p><p>　　void bing(pointer *head1,pointer *head2, po

53、inter *head3);</p><p>　　void jiao(pointer *head1,pointer *head2, pointer *head3);</p><p>　　void cha(pointer *head1,pointer *head2, pointer *head3);</p><p>　　int menu_select( );</

54、p><p>　　void main(){ </p><p>　　pointer *head1,*head2,*head3; </p><p>　　head1=(pointer *)malloc(sizeof(struct pointer)); </p><p>　　head1->link=NULL; </p><p>

55、;　　head2=(pointer *)malloc(sizeof(struct pointer)); </p><p>　　head2->link=NULL; </p><p>　　head3=(pointer *)malloc(sizeof(struct pointer)); </p><p>　　head3->link=NULL;</p>

56、;<p>　　printf("* 輸入集合1 *\n");</p><p>　　readdata(head1);</p><p>　　printf("************************************\n");</p><p>　　printf("輸

57、入集合2：\n"); </p><p>　　printf("************************************\n");</p><p>　　readdata(head2); </p><p>　　for ( ; ;) {</p><p>　　switch (menu_select( )

58、)</p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p>　　printf("************************************\n");</p><p>　　printf("集合1為：\n&q

59、uot;); </p><p>　　printf("************************************\n");</p><p>　　sort(head1);</p><p>　　disp(head1); </p><p><b>　　break;</b></p>

60、<p><b>　　case 2:</b></p><p>　　printf("************************************\n");</p><p>　　printf("集合2為：\n"); </p><p>　　printf("*************

61、***********************\n");</p><p>　　sort(head2);</p><p>　　disp(head2); </p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p&g

62、t;　　printf("************************************\n");</p><p>　　printf("集合1與集合2的并為:\n"); </p><p>　　printf("************************************\n");</p><

63、p>　　bing(head1,head2,head3); </p><p>　　sort(head3);</p><p>　　disp(head3); </p><p>　　head3->link=NULL;</p><p><b>　　break;</b></p><p><b

64、>　　case 4:</b></p><p>　　printf("************************************\n");</p><p>　　printf("集合1與集合2的交為:\n"); </p><p>　　printf("*******************

65、*****************\n");</p><p>　　jiao(head1,head2,head3); </p><p>　　sort(head3);</p><p>　　disp(head3); </p><p>　　head3->link=NULL; </p><p><b>

66、　　break;</b></p><p><b>　　case 5:</b></p><p>　　printf("************************************\n");</p><p>　　printf("集合1與集合2的差為:\n"); </p>

67、<p>　　printf("************************************\n");</p><p>　　cha(head1,head2,head3); </p><p>　　sort(head3);</p><p>　　disp(head3); </p><p>　　head3-&g

68、t;link=NULL; </p><p><b>　　break;</b></p><p><b>　　case 6:</b></p><p>　　printf("************************************\n");</p><p>　　print

69、f("集合2與集合1的差為:\n"); </p><p>　　printf("************************************\n");</p><p>　　cha(head2,head1,head3); </p><p>　　sort(head3);</p><p>　　d

70、isp(head3); </p><p>　　head3->link=NULL; </p><p><b>　　break;</b></p><p><b>　　case 0 :</b></p><p>　　printf("*\t 再見！*\n");</p>

71、<p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　四、界面實(shí)現(xiàn)</b></