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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：12 大?。?54.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩11頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　單位: 計算機051班 　　學號: 　　課程設(shè)計　?。ㄓ嬎銠C科學與技術(shù)專業(yè)）　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　姓

2、名： 　　專業(yè)：計算機科學與技術(shù)　　指導教師： 　　二○○八年六月　　一、課程設(shè)計

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

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

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

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

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

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

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

10、>　　3）雙向鏈表　　每個結(jié)點中只包括一個指向下個結(jié)點的指針域，這種鏈表稱為單向鏈表。如果要在單向鏈表一個指針所指的當前位置插入一個新結(jié)點，就必須從鏈表頭指針開始逐個遍歷直到當前指針所指結(jié)點的前一結(jié)點，修改這個結(jié)點的指針。雙向鏈表的每個結(jié)點中包括兩個指針域，分別指向該結(jié)點的前一個結(jié)點和后一個結(jié)點。在雙向鏈表中由任何一個結(jié)點都很容易找到其前面的結(jié)點和后面

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

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

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

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

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

16、；　　將新結(jié)點鏈到尾結(jié)點之后；　　使尾結(jié)點指向新結(jié)點；　　提示：是否結(jié)束建表，讀入一個結(jié)束標志；　　}　　尾結(jié)點指針域置空值NULL。

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

18、;p>　　（1）用p1指向原鏈表頭結(jié)點，p2指向鏈表的第一個結(jié)點；　　（2） While (p2 != NULL && strcmp(p2->data.num, p->data.num) < 0)　　{　　P1 = p2;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、truct pointer)); 　　p3->dat=p1->dat; 　　p3->link=head3->link; 　　head3->link=p3; 　　}

45、;　　p1=p1->link; 　　} 　　} 　　int menu_select( )　　{

46、;　　int sn;　　printf(" 集合運算 \n");　　printf("================================\n");　　printf(" 1. 集合1為

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

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

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

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

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

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

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

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

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

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

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

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

59、uot;); 　　printf("************************************\n");　　sort(head1);　　disp(head1); 　　break;

60、　　case 2:　　printf("************************************\n");　　printf("集合2為：\n"); 　　printf("*************

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

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

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

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

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

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

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

68、t;link=NULL; 　　break;　　case 6:　　printf("************************************\n");　　print

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

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

71、　　return;　　}　　}　　} 　　四、界面實現(xiàn)</

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載