1、計算機學院 數據結構課程設計報告學號2015-2016學年 第1學期1408010149數據結構課程設計報告題目： 集合的并、交和差運算專業： 計算機科學與技術班級： 14計科（1）班姓名： 張婷婷指導教師： 王峻成績：計算機學院2015年11月13日11目錄1設計內容及要求11.1 設計內容11.2 設計要求12概要設計12.1 有序表的抽象數據類型的定義 12.2 集合的定義 12.3 基本操作 12.4 調用關系 23詳細設計33.1 具體算法流程33.2 具體的程序功能實現 43.3&#

2、160;偽碼算法 44設計結果與分析74.1 調試過程中遇到的問題74.2 算法的時空分析 84.3 測試結果85 總結 106 參考文獻11 附錄1111設計內容及要求1.1 設計內容 編制一個能演示執行集合的并、交和差運算的程序。1.2 設計要求 (1) 集合的元素限定為小寫字母字符 a.z 。   (2) 演示程序以用戶和計算機的對話方式執行。2概要設計 為實現上述程序功能，應以有序鏈表表示集合。為此，需要兩個抽象數據類型：有序表和集合。2.1. 有序表的抽象數據類型定

3、義為 typedef struct LNode    char data;  struct LNode *next;  LinkList; 2.2.  集合的定義為 char set1maxsize,set2maxsize; 2.3.  基本操作 void GreatListR(LinkList *&L,char a,int n) 

4、0;/尾插法建表 void InitList(LinkList *&L)  /初始化線性表 void DestroyList(LinkList *&L) /銷毀線性表void DispList(LinkList *L) /輸出線性表 void sort(LinkList *&L) /元素排序 void bingji(LinkList *L,LinkList *N,LinkL

5、ist *&M) /并集運算 void dels(LinkList *&M)    /刪除相同元素  僅留一個  void jiaoji(LinkList *&M,LinkList *L,LinkList *N)  /交集運算 void chayunsuan(LinkList *L,LinkList *M,LinkList*&K) /集

6、合差運算int main() /為設計程序主頁面的函數，并且使用了所有的函數 2.4. 調用關系 InitList(L); InitList(N); GreatListR(L,set1,i); GreatListR(U,set1,i); sort(U); /元素排序 dels(U);  /刪除相同元素  僅留一個 sort(L); /元素排序dels(L);  /刪除相同元素  僅留一個

7、 printf("請輸入集合set2="); for(j=0;j<maxsize;j+)   scanf("%c",&set2j);  if(set2j='n')    break;       GreatListR(N,set2,j);      sort(N); /元素排序 dels(

8、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是否退出運

9、算？n"); scanf("%c",&n); if(n='e')  exit(0); DestroyList(L); DestroyList(N); DestroyList(U); DestroyList(M); DestroyList(K); system("PAUSE");3詳細設計3.1具體算法流程程序開始輸出提示信息輸入兩個集合合合輸出集合的交、并和差集是否進行下次 計算 程序結束YN3.2. 具體的程序

10、功能實現 (1)利用c+引用類型，對線性表LinkList *L,*N 進行初始化，并用for循環將將集合set1maxsize,set2maxsize分別存入線性表L和 K。 (2)用sort()函數對兩個線性表里的元素進行排序，得到兩個有序表。(3)用dels()函數分別刪除兩個有序表里相同元素，僅留一個。 (4)用函數bingji(L,N,M)合并兩個有序表，得到有序表M，并再次調用函數dels(M)刪除有序表里相同的元素，僅留下一個，從而得到集合的并集。(5)調用函數jiaoji(M,L,N)，進行交集運算，從而得到一個新的有

11、序表M，存著兩個集合的交集。 (6)利用交集運算得到的結果M進行集合差運算，調用函數chayunsuan(U,M,K)，得到兩個集合差集為有序表K。 (7)調用函數DispList()輸出并集，交集和差集的結果。   (8) 用代碼 char n;   printf("n是否退出運算？n");   scanf("%c",&n);   if(n='e') 

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

13、kList *&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)  

14、    s=(LinkList *)malloc(sizeof(LinkList);     s->data=pa->data;     r->next=s;r=s;   pa=pa->next;     else         s=(LinkList *)malloc(sizeof(LinkList); 

15、60;   s->data=pb->data;     r->next=s;r=s;     pb=pb->next;          while(pa!=NULL)       s=(LinkList *)malloc(sizeof(LinkList);     s->data=pa->d

16、ata;     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-&

17、gt;next;       r->next=NULL;     printf("兩個集合的并集為set1set2:");   void dels(LinkList *&M)    /刪除相同元素  僅留一個     LinkList *p=M->next,*q;   while(p->next!=NULL) &

18、#160;   if(p->data=p->next->data)         q=p->next;     p->next=q->next;     free(q);        else     p=p->next;      (2)交集運算

19、60;void jiaoji(LinkList *&M,LinkList *L,LinkList *N)  /交集運算    LinkList *pa=L->next,*pb=N->next,*q,*r; /以單鏈表M的頭節點創建一個空單鏈表   M->next=NULL;  r=M;  /r指向這個新鏈表的最后一個節點   while(pa!=NULL)  /以pa掃描單鏈表M的

20、數據節點，判斷是否 在單鏈表L和N中       while(pb!=NULL&&pa->data>pb->data)     pb=pb->next;    if(pa!=NULL&&pb!=NULL&&pa->data=pb->data)         r->next=pa;  &#

21、160;  r=pa;  pa=pa->next;        else        q=pa; pa=pa->next;     free(q);          r->next=NULL;   printf("兩個集合的交集為set1set2=");   (3)

22、差集運算 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->nex

23、t;    while(p2!=NULL&&p2->data!=p1->data)     p2=p2->next;    if(p2=NULL)         s=(LinkList *)malloc(sizeof(LinkList);     s->data=p1->data;     

24、r->next=s;r=s;            p1=p1->next;     r->next=NULL;   printf("兩個集合的差集為set1 - set2=");  4設計結果與分析4.1. 調試過程中遇到的問題 (1)由于對集合的三種運算的算法推敲不足,在有序鏈表類型的早期版本未設置。 尾指針操作,導致算法低效。 (2)

25、由于首先沒設置數組最大值，導致數組不能正確輸入，后來定義了#define maxsize 100才解決這個問題。 (3)在子函數中線性表的創建不正確，導致在輸入數組后不能正確執行，出現下圖結果，經過多次調試才得到正確結果。(4)在進行差運算的算法設計時出現邏輯上的錯誤，導致結果不正確，集合的首元素未能正確參與運算。進過仔細的推敲才發現沒有創建一個空的頭結點就直接把pa=pa->next，使第一個數據元素未參加運算。 (5)程序首先只能進行一次運算就退出了，不能人性化的進行多次運算，后來在主函數中加入for語句，進行循環，才能進行多次運算，并在for

26、語句里加入if條件語句，進行是否進行下一次運算的判斷，使程序更加優化。 (6)首先把刪除相同元素的算法寫在交集，并集和差集的算法運算里面，使程序代碼冗長，后來為了使代碼更加簡潔，就另外單獨寫了一個刪除相同元素的算法，只要在各個運算中調用即可。4.2. 算法的時空分析 (1) void GreatListR(LinkList *&L,char a,int n)  /尾插法建表 本算法的時間復雜度為O(n)，其中n為單鏈表中數據節點的個數。 (2)void InitLis

27、t(LinkList *&L)  /初始化線性表 本算法的時間復雜度為O(1)。 (3)void DestroyList(LinkList *&L)本算法的時間復雜度為O(n)，其中n為單鏈表中數據節點的個數。(4)void DispList(LinkList *L)  /輸出線性表 本算法的時間復雜度為O(n)，其中n為單鏈表中數據節點的個數。 (6)void sort(LinkList *&L) /元素排序&

28、#160;本算法的時間復雜度為O(n)，其中n為單鏈表中數據節點的個數。 (7) void bingji(LinkList *L,LinkList *N,LinkList *&M) /并集運算 本算法的時間復雜度為O(ListLength(L)+ListLength(N)。 (8)void dels(LinkList *&M)    /刪除相同元素  僅留一個 本算法的時間復雜度為O(n)，其中n為單鏈表中數據

29、節點的個數。 (9)void jiaoji(LinkList *&M,LinkList *L,LinkList *N /交集運算 本算法的時間復雜度為O(m+n+p)。 (10) void chayunsuan(LinkList*L,LinkList*M,LinkList*&K)/集合差運算 本算法的時間復雜度為O(n*n)，其中n為單鏈表中數據節點的個數。4.3 測試結果 （1） 做完一次運算后按回車鍵繼續下一次運算圖4.3.1運算完一次進行第二次運算圖4.3.1&#

30、160;進行多次運算 （2）做完運算后輸入字母“e”退出運算圖4.3.2 運算完按字母“e”退出5 總結 數據結構是計算機程序設計的重要理論技術基礎，它不僅是計算機科學的核心課程，而且也已經成為其他理工專業的熱門選修課。隨著高級語言的發展，數據結構在計算機的研究和應用中已展現出強大的生命力，它兼顧了諸多高級語言的特點，是一種典型的結構化程序設計語言，它處理能力強，使用靈活方便，應用面廣，具有良好的可移植性。 數據結構課設使我們鞏固了以前的知識并在此基礎上還對數據結構的特點和算法有了更深的了解，使我們在這門課程的實際應用上也有了一個提高。 首先這兩周的學習

31、，使我們在鞏固了原有的理論知識上，又培養了靈活運用和組合集成所學過知識及技能來分析、解決實際問題的能力，使我們體會到自身知識和能力在實際中的應用和發揮。其次，它激發了我們創新意識，開發創造的能力和培養溝通能力。另外，讓我們進一步熟悉了數據結構的設計應用。每一處編碼都是在反復的熟悉數據結構的結構特性，及其語法、函數和程序設計思想的過程，對我們數據結構的學習和提高很有益處，并且使我們明白了程序設計過程，如解決一些實際問題，從解決實際問題的角度。 課程設計讓我們受益匪淺。我們深深認識到，要學好一門學科，沒有刻苦鉆研的精神是不行的，只有在不斷的嘗試中，經歷失敗，從失敗中總結經驗，然后再不斷的

32、嘗試，才能獲得成功。6參考文獻1 趙文靜. 數據結構與算法M.北京：科學出版社 2 海童偉.C語言精彩編程百例M. 北京：水利水電出版社 3 嚴蔚敏,吳偉民.數據結構(C語言版)M. 北京:清華大學出版社附錄 程序源代碼#include<iostream> #include <windows.h>  using namespace std; #define maxsize 100 typedef struct LNode  

33、0; char data;  struct LNode *next; LinkList; void GreatListR(LinkList *&L,char a,int n) /尾插法建表    LinkList *s,*r;   int i;   L=(LinkList *)malloc(sizeof(LinkList);  /創建頭節點 

34、60;r=L;   for(i=0;i<n;i+)       s=(LinkList *)malloc(sizeof(LinkList); s->data=ai;    r->next=s;    r=s;      r->next=NULL;  void InitList(LinkList *&L)  /初始化線性表 &#

35、160; 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

36、=pre->next;      free(pre);  void DispList(LinkList *L)  /輸出線性表    LinkList *p=L->next;   while(p!=NULL)       if(p->data>='a')&&(p->data<='z')   &#

37、160; printf("%c",p->data);     p=p->next;      printf("n");   void sort(LinkList *&L) /元素排序    LinkList *p,*pre,*q;   p=L->next->next; /p指向L的第2個數據節點 L->next

38、->next=NULL; /構件只含一個數據節點的有序表   while(p!=NULL)       q=p->next;     while(p!=NULL)       q=p->next; /q保存*p節點沒后繼節點的指針     pre=L;  /從有序表開頭進行比較，pre指向插入*p的前驅節點   

39、0; while(pre->next!=NULL&&pre->next->data<p->data)      pre=pre->next;     p->next=pre->next;     pre->next=p;     p=q;         void bingji(

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

41、;data<pb->data)         s=(LinkList *)malloc(sizeof(LinkList);     s->data=pa->data;     r->next=s;r=s;     pa=pa->next;       else      

42、s=(LinkList *)malloc(sizeof(LinkList);    s->data=pb->data;      r->next=s;r=s;     pb=pb->next;          while(pa!=NULL)       s=(LinkList *)malloc(sizeof(LinkList);&#

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

44、; 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->

45、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->n

46、ext=NULL;    printf("兩個集合的并集為set1set2:");    void dels(LinkList *&M)   /刪除相同元素  僅留一個     LinkList *p=M->next,*q;   while(p->next!=NULL)       if(p->data=p->nex

47、t->data)   q=p->next;    p->next=q->next;     free(q);        else     p=p->next;      void jiaoji(LinkList*&M,LinkList*L,LinkList*N)  /交集運算  

48、60;LinkList *pa=L->next,*pb=N->next,*q,*r; /以單鏈表M的頭節點創建一個空單鏈表   M->next=NULL;   r=M;     /r指向這個新鏈表的最后一個節點   while(pa!=NULL) /以pa掃描單鏈表M的數據節點，判斷是否在單鏈表L和N中        while(pb!=NULL&&pa->data&

49、gt;pb->data)     pb=pb->next;  if(pa!=NULL&&pb!=NULL&&pa->data=pb->data)         r->next=pa;     r=pa;     pa=pa->next;         else

50、60;     q=pa;     pa=pa->next;     free(q);       r->next=NULL;  printf("兩個集合的交集為set1set2=");   void chayunsuan(LinkList*L,LinkList*M,LinkList*&K)/集合差運算    LinkList&

51、#160;*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;   

52、0;if(p2=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-&

53、gt;data;     r->next=s;r=s;            p1=p1->next;      r->next=NULL;   printf("兩個集合的差集為set1 - set2=");   void main()    printf("*集合的并、交和差運算*n運算完輸入“e”退出運算，否則按回車鍵繼續下次運算！n");   system("color B5");