數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--集合的并、交和差運算

1、.課 程 設(shè) 計 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 集合的并、交和差運算 專 業(yè) 通信工程 班 級 通信1101 學(xué) 號 201103020127 姓 名 皮鋒 指導(dǎo)教師 張鏖烽 田娟秀 李杰君 2013 年6月29日湖南工程學(xué)院課 程 設(shè) 計 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 集合的并、交和差運算 專業(yè)班級 通信1101 學(xué)生姓名 皮鋒 學(xué) 號 201103020127 指導(dǎo)老師 張鏖烽 田娟秀 李杰君 審 批 任務(wù)書下達(dá)日期 2013 年 6 月 23 日任 務(wù) 完成日期 2013 年 6 月 29 日目錄 1. 需求分析11.1. 問題描述11.2. 基本要求11.3. 測試數(shù)據(jù)1

2、1.4. 實現(xiàn)提示12. 概要設(shè)計12.1. 有序表的抽象數(shù)據(jù)類型定義為12.2. 集合的定義為12.3. 基本操作22.4. 調(diào)用關(guān)系23. 詳細(xì)設(shè)計43.1. 具體算法流程43.2. 具體的程序功能實現(xiàn)43.3. 偽碼算法54. 調(diào)試分析94.1. 調(diào)試過程中遇到的問題94.2. 算法的時空分析95. 用戶使用說明106. 測試結(jié)果116.1. 做完一次運算后按回車鍵繼續(xù)下一次運算116.2. 做完運算后輸入字母“e”退出運算127. 總結(jié)128. 附錄138.1. 程序源代碼13;集合的并、交和差運算1. 需求分析1.1. 問題描述編制一個能演示執(zhí)行集合的并、交和差運算的程序。1.2.

3、基本要求(1) 集合的元素限定為小寫字母字符 a.z 。(2) 演示程序以用戶和計算機的對話方式執(zhí)行。1.3. 測試數(shù)據(jù)(1)Set1="magazine"，Set2="paper"，Set1Set2="aegimnprz"，Setl Set2="ae"，Set1-Set2="gimnz"。(2)Set1= " 012oper4a6tion89"，Set2="error data"，Set1Set2="adeinoprt"，Setl S

4、et2="aeort"，Set1-Set2="inp"。1.4. 實現(xiàn)提示以有序鏈表表示集合。2. 概要設(shè)計為實現(xiàn)上述程序功能，應(yīng)以有序鏈表表示集合。為此，需要兩個抽象數(shù)據(jù)類型：有序表和集合。2.1. 有序表的抽象數(shù)據(jù)類型定義為typedef struct LNodechar data;struct LNode *next;LinkList;2.2. 集合的定義為char set1maxsize,set2maxsize;2.3. 基本操作void GreatListR(LinkList *&L,char a,int n) /尾插法建表void I

5、nitList(LinkList *&L)/初始化線性表void DestroyList(LinkList *&L)/銷毀線性表void DispList(LinkList *L)/輸出線性表void sort(LinkList *&L)/元素排序void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運算void dels(LinkList *&M) /刪除相同元素 僅留一個void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運算void cha

6、yunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差運算int main()/為設(shè)計程序主頁面的函數(shù)，并且使用了所有的函數(shù)2.4. 調(diào)用關(guān)系InitList(L);InitList(N);GreatListR(L,set1,i);GreatListR(U,set1,i);sort(U);/元素排序dels(U);/刪除相同元素 僅留一個sort(L);/元素排序dels(L);/刪除相同元素 僅留一個printf("請輸入集合set2=");for(j=0;j<maxsize;j+)scanf("%c&q

7、uot;,&set2j);if(set2j='n')break; GreatListR(N,set2,j); sort(N);/元素排序dels(N);/刪除相同元素 僅留一個bingji(L,N,M);/集合合并dels(M);/刪除相同元素 僅留一個DispList(M); jiaoji(M,L,N);/交集運算DispList(M); chayunsuan(U,M,K);/集合差運算DispList(K);char n;printf("n是否退出運算？n");scanf("%c",&n);if(n='e

8、9;)exit(0);DestroyList(L);DestroyList(N);DestroyList(U);DestroyList(M);DestroyList(K);system("PAUSE");3. 詳細(xì)設(shè)計3.1. 具體算法流程 圖3-1 具體算法流程3.2. 具體的程序功能實現(xiàn)(1)利用c+引用類型，對線性表LinkList *L,*N進行初始化，并用for循環(huán)將將集合set1maxsize,set2maxsize分別存入線性表L和K。(2)用sort()函數(shù)對兩個線性表里的元素進行排序，得到兩個有序表。(3)用dels()函數(shù)分別刪除兩個有序表里相同元素，僅

9、留一個。(4)用函數(shù)bingji(L,N,M)合并兩個有序表，得到有序表M，并再次調(diào)用函數(shù)dels(M)刪除有序表里相同的元素，僅留下一個，從而得到集合的并集。(5)調(diào)用函數(shù)jiaoji(M,L,N)，進行交集運算，從而得到一個新的有序表M，存著兩個集合的交集。(6)利用交集運算得到的結(jié)果M進行集合差運算，調(diào)用函數(shù)chayunsuan(U,M,K)，得到兩個集合差集為有序表K。(7)調(diào)用函數(shù)DispList()輸出并集，交集和差集的結(jié)果。 (8)用代碼char n;printf("n是否退出運算？n");scanf("%c",&n);if(n=&

10、#39;e')exit(0);判斷是否進行下一次運輸，如果進行下一次運算按回車鍵繼續(xù)，否則輸入字母“e”退出運算。(9)最后利用函數(shù)DestroyList()銷毀所有線性表。(10)加上頭文件#include <windows.h> 和語句system("color B5")對界面進行顏色設(shè)置，得到自己喜歡的顏色。3.3. 偽碼算法(1)并集運算void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運算LinkList *pa=L->next,*pb=N->next,*r,*s;/時歸

11、并算法M=(LinkList *)malloc(sizeof(LinkList);r=M;while(pa!=NULL&&pb!=NULL)/集合合并if(pa->data<pb->data)s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s;r=s;pa=pa->next;elses=(LinkList *)malloc(sizeof(LinkList);s->data=pb->data;r->next=s;r=s;pb=pb->ne

12、xt;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s;r=s;pa=pa->next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s->data=pb->data;r->next=s;r=s;pb=pb->next;r->next=NULL;printf("兩個集合的并集為set1set2:");void dels(LinkList *&M)

13、 /刪除相同元素 僅留一個LinkList *p=M->next,*q;while(p->next!=NULL)if(p->data=p->next->data)q=p->next;p->next=q->next;free(q);elsep=p->next;(2) 交集運算void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運算LinkList *pa=L->next,*pb=N->next,*q,*r;/以單鏈表M的頭節(jié)點創(chuàng)建一個空單鏈表M->next=NULL

14、;r=M;/r指向這個新鏈表的最后一個節(jié)點while(pa!=NULL)/以pa掃描單鏈表M的數(shù)據(jù)節(jié)點，判斷是否在單鏈表L和N中while(pb!=NULL&&pa->data>pb->data)pb=pb->next;if(pa!=NULL&&pb!=NULL&&pa->data=pb->data)r->next=pa;r=pa;pa=pa->next;elseq=pa;pa=pa->next;free(q);r->next=NULL;printf("兩個集合的交集為set1

15、set2=");(3) 差集運算void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差運算LinkList *p1=L->next,*p2=M->next,*s,*r;K=(LinkList *)malloc(sizeof(LinkList);r=K;r->next=NULL;while(p1!=NULL)p2=M->next;while(p2!=NULL&&p2->data!=p1->data)p2=p2->next;if(p2=NULL)s=(LinkLi

16、st *)malloc(sizeof(LinkList);s->data=p1->data;r->next=s;r=s;p1=p1->next;r->next=NULL;printf("兩個集合的差集為set1 - set2=");4. 調(diào)試分析4.1. 調(diào)試過程中遇到的問題(1)由于對集合的三種運算的算法推敲不足,在有序鏈表類型的早期版本未設(shè)置尾指針操作,導(dǎo)致算法低效。(2)由于首先沒設(shè)置數(shù)組最大值，導(dǎo)致數(shù)組不能正確輸入，后來定義了#define maxsize 100才解決這個問題。(3)在子函數(shù)中線性表的創(chuàng)建不正確，導(dǎo)致在輸入數(shù)組后不能正

17、確執(zhí)行，出現(xiàn)下圖結(jié)果，經(jīng)過多次調(diào)試才得到正確結(jié)果。(4)在進行差運算的算法設(shè)計時出現(xiàn)邏輯上的錯誤，導(dǎo)致結(jié)果不正確，集合的首元素未能正確參與運算。進過仔細(xì)的推敲才發(fā)現(xiàn)沒有創(chuàng)建一個空的頭結(jié)點就直接把pa=pa->next，使第一個數(shù)據(jù)元素未參加運算。(5)程序首先只能進行一次運算就退出了，不能人性化的進行多次運算，后來在主函數(shù)中加入for語句，進行循環(huán)，才能進行多次運算，并在for語句里加入if條件語句，進行是否進行下一次運算的判斷，使程序更加優(yōu)化。(6)首先把刪除相同元素的算法寫在交集，并集和差集的算法運算里面，使程序代碼冗長，后來為了使代碼更加簡潔，就另外單獨寫了一個刪除相同元素的算法，

18、只要在各個運算中調(diào)用即可。4.2. 算法的時空分析(1)void GreatListR(LinkList *&L,char a,int n) /尾插法建表本算法的時間復(fù)雜度為O(n)，其中n為單鏈表中數(shù)據(jù)節(jié)點的個數(shù)。(2) void InitList(LinkList *&L)/初始化線性表本算法的時間復(fù)雜度為O(1)。(3) void DestroyList(LinkList *&L)本算法的時間復(fù)雜度為O(n)，其中n為單鏈表中數(shù)據(jù)節(jié)點的個數(shù)。(4) void DispList(LinkList *L)/輸出線性表本算法的時間復(fù)雜度為O(n)，其中n為單鏈表中數(shù)據(jù)節(jié)

19、點的個數(shù)。(6) void sort(LinkList *&L)/元素排序本算法的時間復(fù)雜度為O(n)，其中n為單鏈表中數(shù)據(jù)節(jié)點的個數(shù)。(7) void bingji(LinkList *L,LinkList *N,LinkList *&M)/并集運算本算法的時間復(fù)雜度為O(ListLength(L)+ListLength(N)。(8) void dels(LinkList *&M) /刪除相同元素 僅留一個本算法的時間復(fù)雜度為O(n)，其中n為單鏈表中數(shù)據(jù)節(jié)點的個數(shù)。(9) void jiaoji(LinkList *&M,LinkList *L,LinkLi

20、st *N)/交集運算本算法的時間復(fù)雜度為O(m+n+p)。(10) void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差運算本算法的時間復(fù)雜度為O(n*n)，其中n為單鏈表中數(shù)據(jù)節(jié)點的個數(shù)。5. 用戶使用說明用戶在使用時首先輸入要進行運算的兩個集合，然后按回車鍵則會出現(xiàn)運算結(jié)果。只能進行小寫字母a到z的運算，如果輸入其他以外的數(shù)字、字母或字符，則不會在運算結(jié)果中顯示！若用戶需要在進行下一次運算，則按回車鍵繼續(xù)，否則按字母“e”退出計算！6. 測試結(jié)果6.1. 做完一次運算后按回車鍵繼續(xù)下一次運算圖6-1運算完一次進行第二次

21、運算圖6-2 進行多次運算6.2. 做完運算后輸入字母“e”退出運算圖6-1 運算完按字母“e”退出7. 總結(jié)數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機科學(xué)的核心課程，而且也已經(jīng)成為其他理工專業(yè)的熱門選修課。隨著高級語言的發(fā)展，數(shù)據(jù)結(jié)構(gòu)在計算機的研究和應(yīng)用中已展現(xiàn)出強大的生命力，它兼顧了諸多高級語言的特點，是一種典型的結(jié)構(gòu)化程序設(shè)計語言，它處理能力強，使用靈活方便，應(yīng)用面廣，具有良好的可移植性。 數(shù)據(jù)結(jié)構(gòu)課設(shè)使我們鞏固了以前的知識并在此基礎(chǔ)上還對數(shù)據(jù)結(jié)構(gòu)的特點和算法有了更深的了解，使我們在這門課程的實際應(yīng)用上也有了一個提高。 首先這兩周的學(xué)習(xí)，使我們在鞏固了原有的理論知識上，又

22、培養(yǎng)了靈活運用和組合集成所學(xué)過知識及技能來分析、解決實際問題的能力，使我們體會到自身知識和能力在實際中的應(yīng)用和發(fā)揮。其次，它激發(fā)了我們創(chuàng)新意識，開發(fā)創(chuàng)造的能力和培養(yǎng)溝通能力。另外，讓我們進一步熟悉了數(shù)據(jù)結(jié)構(gòu)的設(shè)計應(yīng)用。每一處編碼都是在反復(fù)的熟悉數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)特性，及其語法、函數(shù)和程序設(shè)計思想的過程，對我們數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和提高很有益處，并且使我們明白了程序設(shè)計過程，如解決一些實際問題，從解決實際問題的角度。 課程設(shè)計讓我們受益匪淺。我們深深認(rèn)識到，要學(xué)好一門學(xué)科，沒有刻苦鉆研的精神是不行的，只有在不斷的嘗試中，經(jīng)歷失敗，從失敗中總結(jié)經(jīng)驗，然后再不斷的嘗試，才能獲得成功。 8. 附錄8.1. 程序

23、源代碼#include<iostream>#include <windows.h> using namespace std;#define maxsize 100typedef struct LNodechar data;struct LNode *next;LinkList;void GreatListR(LinkList *&L,char a,int n) /尾插法建表LinkList *s,*r;int i;L=(LinkList *)malloc(sizeof(LinkList);/創(chuàng)建頭節(jié)點r=L;for(i=0;i<n;i+)s=(LinkLi

24、st *)malloc(sizeof(LinkList);s->data=ai;r->next=s;r=s;r->next=NULL;void InitList(LinkList *&L)/初始化線性表L=(LinkList *)malloc(sizeof(LinkList);L->next=NULL;void DestroyList(LinkList *&L)LinkList *pre=L,*p=L->next;while(p!=NULL)free(pre);pre=p;p=pre->next;free(pre);void DispList

25、(LinkList *L)/輸出線性表LinkList *p=L->next;while(p!=NULL)if(p->data>='a')&&(p->data<='z')printf("%c",p->data);p=p->next;printf("n");void sort(LinkList *&L)/元素排序LinkList *p,*pre,*q;p=L->next->next;/p指向L的第2個數(shù)據(jù)節(jié)點L->next->next=

26、NULL;/構(gòu)件只含一個數(shù)據(jù)節(jié)點的有序表while(p!=NULL)q=p->next;while(p!=NULL)q=p->next;/q保存*p節(jié)點沒后繼節(jié)點的指針pre=L;/從有序表開頭進行比較，pre指向插入*p的前驅(qū)節(jié)點while(pre->next!=NULL&&pre->next->data<p->data)pre=pre->next;p->next=pre->next;pre->next=p;p=q;void bingji(LinkList *L,LinkList *N,LinkList *&a

27、mp;M)/并集運算LinkList *pa=L->next,*pb=N->next,*r,*s;/時歸并算法M=(LinkList *)malloc(sizeof(LinkList);r=M;while(pa!=NULL&&pb!=NULL)/集合合并if(pa->data<pb->data)s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s;r=s;pa=pa->next;elses=(LinkList *)malloc(sizeof(Link

28、List);s->data=pb->data;r->next=s;r=s;pb=pb->next;while(pa!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s;r=s;pa=pa->next;while(pb!=NULL)s=(LinkList *)malloc(sizeof(LinkList);s->data=pb->data;r->next=s;r=s;pb=pb->next;r->next=NULL;printf(

29、"兩個集合的并集為set1set2:");void dels(LinkList *&M) /刪除相同元素 僅留一個LinkList *p=M->next,*q;while(p->next!=NULL)if(p->data=p->next->data)q=p->next;p->next=q->next;free(q);elsep=p->next;void jiaoji(LinkList *&M,LinkList *L,LinkList *N)/交集運算LinkList *pa=L->next,*pb=

30、N->next,*q,*r;/以單鏈表M的頭節(jié)點創(chuàng)建一個空單鏈表M->next=NULL;r=M;/r指向這個新鏈表的最后一個節(jié)點while(pa!=NULL)/以pa掃描單鏈表M的數(shù)據(jù)節(jié)點，判斷是否在單鏈表L和N中while(pb!=NULL&&pa->data>pb->data)pb=pb->next;if(pa!=NULL&&pb!=NULL&&pa->data=pb->data)r->next=pa;r=pa;pa=pa->next;elseq=pa;pa=pa->next

31、;free(q);r->next=NULL;printf("兩個集合的交集為set1set2=");void chayunsuan(LinkList *L,LinkList *M,LinkList *&K)/集合差運算LinkList *p1=L->next,*p2=M->next,*s,*r;K=(LinkList *)malloc(sizeof(LinkList);r=K;r->next=NULL;while(p1!=NULL)p2=M->next;while(p2!=NULL&&p2->data!=p1->data)p2=p2->next;if(p2=NULL)s=(LinkList *)malloc(sizeof(LinkList);s->data=p1->data;r->next=s;r=s;p1=p1->next;r->