集合的運算 課程設計報告

1、 學號2015-2016學年 第二學期高級語言程序設計課程設計報告題目：集合的運算專業(yè)：網(wǎng)絡工程班級：15（1）姓名：邱敏指導教師：代美麗成績：計算機學院2016年4月22日目錄一、需求分析11、程序的實現(xiàn)1（1）功能1（2）實施12、設計的要求1二、概要設計11、問題分析12、模塊結(jié)構(gòu)2（1）結(jié)構(gòu)分析2（2）結(jié)構(gòu)分析圖2三、詳細設計31、解題思路3（1）數(shù)據(jù)結(jié)構(gòu)設計3（2）邏輯結(jié)構(gòu)存儲結(jié)構(gòu)32、算法設計3四、調(diào)試分析和測試結(jié)果41、模塊分析4（1）定義單鏈表結(jié)點類型4（2）運用尾插法建立單鏈表4（3）建立有序鏈表52、結(jié)果分析5五、總結(jié)61、解決的問題6（1）集合的運算算法6（2）解決方式7

2、2、心得體會7六、參考文獻（資料不得少于5篇）7七、致謝7八、附錄（含程序源碼）8一、需求分析1、程序的實現(xiàn)（1）功能使用鏈表來表示集合，完成集合的合并，求交集等操作。 （2）實施1) 初步完成總體設計，搭好框架，確定函數(shù)個數(shù)；2) 完成最低要求；3) 繼續(xù)完成進一步要求。2、設計的要求(1) 界面友好，函數(shù)功能要劃分好；(2) 總體設計應畫流程圖；(3) 程序要加必要的注釋；(4) 要提供程序測試方案；(5) 程序要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。二、概要設計1、問題分析該問題主要實現(xiàn)以下功能：(1) 利用尾插法建立單鏈表；(2) 對于輸入的鏈表進行有

3、序排列(3) 刪除有序鏈表中不符合要求的元素(4) 調(diào)用函數(shù)對單鏈表進行交、并運算并輸出 2、模塊結(jié)構(gòu)（1）結(jié)構(gòu)分析程序以用戶和計算機的對話方式執(zhí)行，即在計算及終端顯示提示信息之后，由用戶在鍵盤輸入演示程序中規(guī)定的運算命令；相應的輸入數(shù)據(jù)（過濾輸入中的非法字符）和運算結(jié)果閑時間在其后。系統(tǒng)由以下幾個模塊組成，分別是：1) 單鏈表的建立2) 單鏈表的有序排列3) 刪除單鏈表中不符合條件的元素4) 集合交集5) 集合并集6) 單鏈表輸出7) 主函數(shù) （2）結(jié)構(gòu)分析圖主函數(shù)main()創(chuàng)建鏈表LinkList *求交集void jiao()求并集void bing()單鏈表結(jié)點類型typedef s

4、truct LNode比較并保存相同元素while語句刪除重復的元素void shangchu()三、詳細設計1、解題思路（1）數(shù)據(jù)結(jié)構(gòu)設計創(chuàng)建三個帶頭結(jié)點的單鏈表,用來存儲兩個集合中的元素和最終的結(jié)果,為實現(xiàn)集合的交、并運算功能，應以有序鏈表表示集合。為此，需要兩個抽象數(shù)據(jù)類型：有序表和集合。（2）邏輯結(jié)構(gòu)存儲結(jié)構(gòu)邏輯結(jié)構(gòu)：創(chuàng)造一個帶結(jié)點的單鏈表包括（頭結(jié)點L、結(jié)點若干、尾結(jié)點）；單鏈表中每個結(jié)點包括（*next表示指針data表示域） 2、算法設計程序執(zhí)行的命令包括：(1) 定義單鏈表結(jié)點類型typedef struct LNode (2) 運用尾插法建立單鏈表void CreatList

5、R（LinkList *&L,ElemType a,int n）(3) 創(chuàng)建頭結(jié)點，為頭結(jié)點分配空間(4) 創(chuàng)建新結(jié)點(5) 建立有序鏈表void Sort（LinkList *&head）(6) 將兩個集合的元素進行比較 while語句(7) 刪除有序鏈表中的重復元素void shanchu(LinkList *&head)(8) 求交集 void jiao（struct Lnode *L1，struct Lnode *L2，struct Lnode *L3）(9) 求并集 void bing（struct Lnode * L1，struct Lnode *L2，struct Lnode *

6、L3）(10) 輸出單鏈表void Display（LinkList *L）四、調(diào)試分析和測試結(jié)果1、模塊分析（1）定義單鏈表結(jié)點類型typedef struct LNode ElemType data; struct LNode *next; LinkList;（2）運用尾插法建立單鏈表void CreatListR（LinkList*&L，ElemType a,int n） LinkList *s,*r;int I; L=( LinkList *)malloc(sizeof(LinkList); /創(chuàng)建并為頭結(jié)點分配空間 L-next=NULL;r=L;for(i=0;idata=ai;

7、r-next=s; r=s;r-next=NULL; /尾結(jié)點指向空（3）建立有序鏈表void Sort(LinkList *&head) LinkList *p=head-next,*q,*r; if(p!=NULL) r=p-next;p-next=NULL; p=r;while(p!=NULL)/后續(xù)元素與第一個元素進行比較 r=p-next; q=head; while(q-next!=NULL&q-next-datadata) q=q-next; p-next=q-next; q-next=p; p=r; 2、結(jié)果分析選擇數(shù)字1，進行排序輸出；選擇數(shù)字2，輸出集合1與集合2的交集；選

8、擇數(shù)字3，輸出集合1與集合2的并集?？梢钥闯?，該程序成功是實現(xiàn)了集合的排序和兩個集合的交集運算，而兩個集合的并集運算顯然還存在問題，在以后的學習與操作中，我們要更加注重程序的運行，盡量做到零問題出現(xiàn)。五、總結(jié)1、解決的問題（1）集合的運算算法由于對集合的兩種運算的算法推敲不足，在鏈表類型及其尾指針的設置時出現(xiàn)錯誤，導致程序低效。 剛開始時曾忽略了一些變量參數(shù)的標識”&”，使調(diào)試程序浪費時間不少。今后應重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。（2）解決方式開始時輸入集合后，程序只能進行一次運算，后來加入switch語句,成功解決了這一難題。 本程序的模塊劃分比較合理，且盡可能的將指針的操作封裝

9、在節(jié)點和鏈表的兩個模塊中，致使集合模塊的調(diào)試比較順利。2、心得體會通過實踐才發(fā)現(xiàn)程序設計的掌握直接關系到上機實驗效果。對各個知識點的熟練掌握是在課程中理解理論算法和完成上機實驗的重要保證。本課程設計采用數(shù)據(jù)抽象的程序設計方案，將程序化分為四個層次結(jié)構(gòu)，使得設計時思路清晰，實現(xiàn)時調(diào)試順利，各模塊具有較好的可用性，確實得到了一次良好的程序設計訓練。六、參考文獻（資料不得少于5篇）1 催俊凱。計算機軟件基礎。機械工業(yè)出版社。2007.7 2 唐發(fā)根。數(shù)據(jù)結(jié)構(gòu)教程（第二版）。北京航空航天大學出版社。2005.5.3 嚴尉敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)M.清華大學出版社，2011年11月4 譚浩強。C

10、程序設計（第三版）。清華大學出版社。2005.5 李建學，李光元，吳春芳。數(shù)據(jù)結(jié)構(gòu)課程設計案例精編（用C/C+描述）。北京：清華大學出版社。2007.26 王宏生，宋繼紅。數(shù)據(jù)結(jié)構(gòu)。北京：國防工業(yè)出版社，2006.1七、致謝感謝輔導我們的老師在這個學期細心耐心的指導我們的基礎課學習，為我們的課程設計打下良好的基礎。在這次課程設計中，代老師給我很多的指導和幫助，讓我能夠使程序正常運行且實現(xiàn)實驗的要求。八、附錄（含程序源碼）#include #include using namespace std; typedef char ElemType; typedef struct LNode/定義單鏈表

11、結(jié)點類型 ElemType data; struct LNode *next; LinkList; void CreatListR(LinkList *&L,ElemType a,int n) /運用尾插法建立單鏈表 LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList); /創(chuàng)建頭結(jié)點，為頭結(jié)點分配空間 L-next=NULL; r=L; /r先指向頭結(jié)點后指向尾結(jié)點，開始時指針指向頭結(jié)點 for(i=0;idata=ai; r-next=s; r=s; r-next=NULL;/尾結(jié)點指向空 void Sort(LinkLis

12、t *&head)/建立有序鏈表 LinkList *p=head-next,*q,*r; if(p!=NULL) r=p-next; p-next=NULL; p=r; while(p!=NULL)/后續(xù)元素與第一個元素進行比較 r=p-next; q=head; while(q-next!=NULL&q-next-datadata) q=q-next; p-next=q-next; q-next=p; p=r; void shanchu(LinkList *&head)/刪除有序鏈表中重復的元素及非小寫字母的元素 LinkList *p=head-next,*r=head,*q,*f; w

13、hile(p-next) if(p-data=p-next-data|(p-next-dataz)|(p-next-datanext; p-next=q-next; free(q); else p=p-next; if(r-next-dataz|r-next-datanext; r-next=f-next; free(f); void bing(LinkList * ha,LinkList * hb,LinkList * hc)/求并集hc LinkList * pa,* pb,* pc; pa=ha-next; while(pa!=NULL) pc=(LinkList *)malloc(si

14、zeof(LinkList); pc-data=pa-data; pc-next=hc-next; hc-next=pc; pa=pa-next; pb=hb-next; while(pb!=NULL) pa=ha-next; while(pa!=NULL)&(pa-data!=pb-data) pa=pa-next; if(pa=NULL) pc=(LinkList *)malloc(sizeof(LinkList); pc-data=pb-data; pc-next=hc-next; hc-next=pc; pb=pb-next; void jiao(LinkList *ha,LinkLi

15、st *hb,LinkList *&hc)/求交集hc LinkList *pa=ha-next,*pb,*s,*tc; hc=(LinkList *)malloc(sizeof(LinkList);/定義hc的頭結(jié)點 tc=hc; while(pa) pb=hb-next; while(pb&pb-datadata) pb=pb-next; if(pb&pb-data=pa-data) s=(LinkList *)malloc(sizeof(LinkList); s-data=pa-data; tc-next=s; tc=s; pa=pa-next; tc-next=NULL; void c

16、ha(LinkList *ha,LinkList *hb,LinkList *&hc)/求差集hc LinkList *pa=ha-next,*pb,*s,*tc; hc=(LinkList *)malloc(sizeof(LinkList);/定義hc的頭結(jié)點 tc=hc; while(pa) pb=hb-next; while(pb&pb-datadata) pb=pb-next; if(!(pb&pb-data=pa-data) s=(LinkList *)malloc(sizeof(LinkList); s-data=pa-data; tc-next=s; tc=s; pa=pa-ne

17、xt; tc-next=NULL;void DispList(LinkList *L)/輸出單鏈表L LinkList *p=L-next; while(p!=NULL) coutdata; p=p-next; coutendl; int main() LinkList *ha,*hb,*hc; ElemType a100,b100;/建立兩個數(shù)組存儲集合 int la,lb,x; cout 請輸入集合1： ; cin.getline(a,100); cout 請輸入集合2：; cin.getline(b,100); la=strlen(a); lb=strlen(b); CreatListR(ha,a,la); CreatListR(hb,b,lb); Sort(ha); Sort(hb); shanchu(ha); shanchu(hb); cout1.輸出有序集合 2.求集合交集 3.求集合并集 4.求集合并集endl; while(x!=0) /循環(huán)對運算的選擇 coutx; swi