1、單 位: 計(jì)算機(jī)051班 學(xué) 號(hào): 課程設(shè)計(jì)（計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)姓 名： 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)指導(dǎo)教師： 二八年六月一、課程設(shè)計(jì)設(shè)計(jì)題目：?jiǎn)捂湵韮蓚€(gè)集合相加減的算法為了實(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, pointer *head3)，求兩有序集合的交。兩個(gè)集合A

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

3、的并為4. 集合1與集合2的交為5. 集合1與集合2的差為6. 集合2與集合1的差為0 退出管理系統(tǒng)二、鏈表介紹1）建立單向鏈表在函數(shù)中首先為Head申請(qǐng)了個(gè)所指向的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為鏈表的首結(jié)點(diǎn)。開始鏈表的頭指針和尾指針都指向頭結(jié)點(diǎn)，以后每輸入一個(gè)數(shù)則申請(qǐng)一個(gè)結(jié)點(diǎn)，將輸入的數(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)申請(qǐng)一個(gè)存儲(chǔ)pointer類型變量的空間，并將該空間的首地址賦給指向新結(jié)點(diǎn)的指針head，在為該新結(jié)點(diǎn)的信息域

4、賦值后，先要將該結(jié)點(diǎn)插入位置后面一個(gè)結(jié)點(diǎn)的指針賦給該結(jié)點(diǎn)的指針域，然后才能將指向該結(jié)點(diǎn)的指針賦給其前一個(gè)結(jié)點(diǎn)的指針域，這樣來(lái)完成插入過(guò)程。在單向鏈表中刪除個(gè)結(jié)點(diǎn)同樣要引起刪除結(jié)點(diǎn)的前面結(jié)點(diǎn)的指針的變化。2）編歷鏈表由于鏈表是一個(gè)動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，鏈表的各個(gè)結(jié)點(diǎn)由指針鏈接在起，訪問(wèn)鏈表元素時(shí)通過(guò)每個(gè)鏈表結(jié)點(diǎn)的指針逐個(gè)找到該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，直找到鏈表尾，鏈表的最后一個(gè)結(jié)點(diǎn)的指針為空。3）雙向鏈表每個(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)的指針。雙向鏈

5、表的每個(gè)結(jié)點(diǎn)中包括兩個(gè)指針域，分別指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)。在雙向鏈表中由任何一個(gè)結(jié)點(diǎn)都很容易找到其前面的結(jié)點(diǎn)和后面的結(jié)點(diǎn)，而不需要在上述的插入(及刪除)操作中由頭結(jié)點(diǎn)開始尋找。4）本程序中包含如下函數(shù) readdata(pointer *head):建表 sort(pointer *head) : 單鏈表元素排序 disp(pointer *head) :輸出單鏈表L bing(pointer *head1,pointer *head2, pointer *head3):求兩有序集合的并。兩個(gè)集合1和2，它們的并集為集合3 jiao(pointer *head1,pointer *

6、head2, pointer *head3):求兩有序集合的交。兩個(gè)集合1和2，它們的交集為集合3 cha(pointer *head1,pointer *head2, pointer *head3):求兩有序集合的差。兩個(gè)集合1和2，它們的差集為集合3 main():首先建立單鏈表，再調(diào)用函數(shù)sort()構(gòu)成有序單鏈表，最后求用有序單鏈表表示的兩個(gè)集合的相關(guān)運(yùn)算5）建立鏈表 要求建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。我們知道建立單鏈表有兩種方法，一種稱之為頭插法，另一種稱為尾插法。頭插法是每次將新插入的結(jié)點(diǎn)插入在鏈表的表頭，而尾插法是將新插入的結(jié)點(diǎn)插入在鏈表的表尾。在這里只介紹用尾插法建立鏈表的算法設(shè)計(jì)

7、思想及具體算法實(shí)現(xiàn)，頭插法留給讀者自己去做。要建立鏈表，首先要生成結(jié)點(diǎn)，因此，尾插法建立鏈表的算法描述如下：（1） 使鏈表的頭尾指針head, rear指向新生成的頭結(jié)點(diǎn)（也是尾結(jié)點(diǎn)）；（2） 置結(jié)束標(biāo)志0（假）；（3） While (結(jié)束標(biāo)志不為真) P指向新生成的結(jié)點(diǎn)； 讀入一個(gè)通訊者數(shù)據(jù)至新結(jié)點(diǎn)的數(shù)據(jù)域； 將新結(jié)點(diǎn)鏈到尾結(jié)點(diǎn)之后； 使尾結(jié)點(diǎn)指向新結(jié)點(diǎn)； 提示：是否結(jié)束建表，讀入一個(gè)結(jié)束標(biāo)志； （4） 尾結(jié)點(diǎn)指針域置空值NULL。6）鏈表結(jié)點(diǎn)的插入 鏈表結(jié)點(diǎn)的插入，是要求將一個(gè)通訊者數(shù)據(jù)結(jié)點(diǎn)按其編號(hào)的次序插入有序通訊錄表的相應(yīng)位置，以保持通訊錄表的有序性。插入結(jié)點(diǎn)的基本思想是：使用兩個(gè)指針

8、變量p1和p2分別指向當(dāng)前剛訪問(wèn)過(guò)的結(jié)點(diǎn)和下一個(gè)待訪問(wèn)的結(jié)點(diǎn)，循環(huán)順序查找鏈表，尋找插入結(jié)點(diǎn)的位置，其中p1指向待插入位置的前一個(gè)結(jié)點(diǎn)。插入操作是非常簡(jiǎn)單的。其實(shí)現(xiàn)算法描述如下：（1）用p1指向原鏈表頭結(jié)點(diǎn)，p2指向鏈表的第一個(gè)結(jié)點(diǎn)；（2） While (p2 != NULL && strcmp(p2->data.num, p->data.num) < 0) P1 = p2; /p1指向剛訪問(wèn)過(guò)的結(jié)點(diǎn) P2 = p2->next; /p2指向表的下一個(gè)結(jié)點(diǎn)（3） 插入新結(jié)點(diǎn)7）鏈表的輸出鏈表的輸出相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，只要將表頭指針賦給一個(gè)指針變量p,然后p

9、向后掃描，直至表尾，p為空為止三 程序代碼及功能實(shí)現(xiàn) 程序代碼如下： */#include<stdio.h> #include<stdlib.h> typedef struct pointer char dat; struct pointer *link; pointer; void readdata(pointer *head) /讀集合 pointer *p; char tmp; printf("請(qǐng)輸入任意字符串n"); scanf("%c",&tmp); while(tmp!='n') p=(poin

10、ter *)malloc(sizeof(struct pointer); p->dat=tmp; p->link=head->link; head->link=p; scanf("%c",&tmp); void sort(pointer *head)/單鏈表排序 pointer *p=head->link,*q,*r; if(p!=NULL) r=p->link; p->link=NULL; p=r; while(p!=NULL) r=p->link; q=head; while(q->link!=NULL&am

11、p;&q->link->dat<p->dat) q=q->link; /在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q p->link=q->link; /將*p插到*q之后 q->link=p; p=r; void disp(pointer *head) /顯示集合數(shù)據(jù) pointer *p; p=head->link; while(p!=NULL) printf("%c ",p->dat); p=p->link; printf("n"); void bing(pointer *head1,

12、pointer *head2, pointer *head3) /計(jì)算集合1與集合2的并 pointer *p1,*p2,*p3; p1=head1->link; while(p1!=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link; head3->link=p3; p1=p1->link; p2=head2->link; while(p2!=NULL) p1=head1->link; while(p1!=NULL

13、)&&(p1->dat!=p2->dat) p1=p1->link; if(p1=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p2->dat; p3->link=head3->link; head3->link=p3; p2=p2->link; void jiao(pointer *head1,pointer *head2, pointer *head3) /計(jì)算集合1與集合2的交 pointer *p1,*p2,*p3; p1=head1->l

14、ink; while(p1!=NULL) p2=head2->link; while(p2!=NULL)&&(p2->dat!=p1->dat) p2=p2->link; if(p2!=NULL)&&(p2->dat=p1->dat) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link; head3->link=p3; p1=p1->link; void cha(pointer

15、*head1,pointer *head2, pointer *head3) /計(jì)算集合1與集合2的差 pointer *p1,*p2,*p3; p1=head1->link; while(p1!=NULL) p2=head2->link; while(p2!=NULL)&&(p2->dat!=p1->dat) p2=p2->link; if(p2=NULL) p3=(pointer *)malloc(sizeof(struct pointer); p3->dat=p1->dat; p3->link=head3->link;

16、 head3->link=p3; p1=p1->link; int menu_select( ) int sn; printf(" 集合運(yùn)算 n"); printf("=n"); printf(" 1. 集合1為 n"); printf(" 2. 集合2為 n"); printf(" 3. 集合1與集合2的并為 n"); printf(" 4. 集合1與集合2的交為 n"); printf(" 5. 集合1與集合2的差為 n"); printf

17、(" 6. 集合2與集合1的差為 n"); printf(" 0. 退出管理系統(tǒng) n"); printf("=n"); printf(" 請(qǐng)選擇 0-6 ： n"); for ( ; ;) scanf( "%d", &sn);if (sn < 0 | sn > 6) printf("nt 輸入錯(cuò)誤， 重選0-8 : ");else break; return sn;界面如下：void readdata(pointer *head);void sort(po

18、inter *head);void disp(pointer *head);void bing(pointer *head1,pointer *head2, pointer *head3);void jiao(pointer *head1,pointer *head2, pointer *head3);void cha(pointer *head1,pointer *head2, pointer *head3);int menu_select( );void main() pointer *head1,*head2,*head3; head1=(pointer *)malloc(sizeof(

19、struct pointer); head1->link=NULL; head2=(pointer *)malloc(sizeof(struct pointer); head2->link=NULL; head3=(pointer *)malloc(sizeof(struct pointer); head3->link=NULL;printf("* 輸入集合1 *n");readdata(head1);printf("*n");printf("輸入集合2：n"); printf("*n");rea

20、ddata(head2); for ( ; ;) switch (menu_select( ) ) case 1: printf("*n"); printf("集合1為：n"); printf("*n"); sort(head1); disp(head1); break; case 2: printf("*n"); printf("集合2為：n"); printf("*n"); sort(head2); disp(head2); break; case 3: printf("*n"); printf("集合1與集合2的并為: