集合的并交差運算.doc

數(shù) 據(jù) 結(jié) 構(gòu)課程設(shè)計說明書題 目集合的并交差運算學 號姓 名指導教師康懿日 期2015年7月2日內(nèi)蒙古科技大學課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目集合的并交差運算指導教師康懿時間2013年秋學期第15周至第19周一、教學要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力4. 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學的工作方法和作風二、設(shè)計資料及參數(shù)每個學生在教師提供的課程設(shè)計題目中任意選擇一題，獨立完成，題目選定后不可更換。集合的并交差運算以鏈表存儲集合，在此基礎(chǔ)上完成對集合的操作。要求設(shè)計類（或類模板）來描述集合，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：v 輸入、輸出集合v 查詢集合中的元素v 在集合中進行插入、刪除元素v 實現(xiàn)集合的并、交、差運算 并設(shè)計主函數(shù)測試該類。三、設(shè)計要求及成果1. 分析課程設(shè)計題目的要求2. 寫出詳細設(shè)計說明3. 編寫程序代碼，調(diào)試程序使其能正確運行4. 設(shè)計完成的軟件要便于操作和使用5. 設(shè)計完成后提交課程設(shè)計報告四、進度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設(shè)計說明書和驗收（2天）五、評分標準1. 根據(jù)平時上機考勤、表現(xiàn)和進度，教師將每天點名和檢查2. 根據(jù)課程設(shè)計完成情況，必須有可運行的軟件。3. 根據(jù)課程設(shè)計報告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準確、簡練的語言敘述自己的設(shè)計和回答教師的提問六、建議參考資料1數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴蔚敏、吳偉民 主編 清華大學出版社 2004.112數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述），李建學 等 編著，清華大學出版社 2007.23.數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語言描述，殷人昆 主編，清華大學出版社 2007目錄目錄3第1章 需求分析4第2章 總體設(shè)計4第3章 抽象數(shù)據(jù)類型定義53.1 LinkList抽象數(shù)據(jù)類型的設(shè)計53.2 集合抽象數(shù)據(jù)類型的設(shè)計5第4章 詳細設(shè)計54.1 工程視圖54.2 類圖視圖64.3 主要算法的詳細設(shè)計64.3.1 插入算法的詳細設(shè)計74.3.2 清除算法的詳細設(shè)計74.3.3 求交集算法的詳細設(shè)計74.3.4 求并集算法的詳細設(shè)計84.3.5 求差集算法的詳細設(shè)計9第5章 測試9第6章 總結(jié)11附錄：程序代碼11第1章 需求分析1、 本演示程序中，集合的元素限定為小寫字母字符“a”z”。集合輸入的形式為一個以“0“為結(jié)束標志的字符串，串中字符順序不限。2、 演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息“之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應(yīng)的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。3、 程序執(zhí)行的命令包括：1）構(gòu)造集合A；2）構(gòu)造在集合B；3）刪除集合A內(nèi)的元素；4）刪除集合B內(nèi)的元素；5） 在集合A中插入元素；6）在集合B中插入元素；7）求AB集合的并集；8)求AB集合的交集；9）求AB及BA的差集第2章 總體設(shè)計 總體設(shè)計框架圖，如圖2.1所示： 開始 輸入A集合 輸入B集合 添加 刪除 添加 刪除 B-A A-B AB AB圖2.1 總體設(shè)計框架第3章 抽象數(shù)據(jù)類型定義定義格式如下：3.1 LinkList抽象數(shù)據(jù)類型的設(shè)計 ADT LinkList 基本操作： InitList(LinkList *L) 構(gòu)造一個空的線性表L DestroyList(LinkList *L) 初始條件：線性表L已存在 ListEmpty(LinkList L) 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE Status ListInsert(LinkList L,int i,ElemType e） 在帶頭結(jié)點的單鏈線性表L中第i個位置之前插入元素e ListPrint(LinkList L) 依次輸出鏈表中的元素3.2 集合抽象數(shù)據(jù)類型的設(shè)計 typedef struct LNode char data; struct LNode *next; LNode, *LinkList;第4章 詳細設(shè)計4.1 工程視圖 圖4.1 工程視圖4.2 類圖視圖 圖4.2 類圖視圖4.3 主要算法的詳細設(shè)計4.3.1 插入算法的詳細設(shè)計 void ListSort(LinkList L)LinkList first; /*為原鏈表剩下用于直接插入排序的節(jié)點頭指針*/LinkList t; /*臨時指針變量：插入節(jié)點*/LinkList p; /*臨時指針變量*/LinkList q; /*臨時指針變量*/first = L-next; /*原鏈表剩下用于直接插入排序的節(jié)點鏈表*/L-next = NULL; /*只含有一個節(jié)點的鏈表的有序鏈表。*/while (first != NULL) /*遍歷剩下無序的鏈表*/*插入排序*/for (t = first, q = L; (q!=NULL) & (q-data data); p=q, q=q-next); /*無序節(jié)點在有序鏈表中找插入的位置*/*退出for循環(huán)，就是找到了插入的位置*/first = first-next; /*無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中。*/if (q = L) L = t; /*插在第一個節(jié)點之前*/else p-next = t; /*p是q的前驅(qū)*/t-next = q; /*完成插入動作*/4.3.2 清除算法的詳細設(shè)計void qingchu(LinkList La)/*清除鏈表中相同的元素*/char i,j;LinkList p,q;La-next;p=La;q=p-next;while(q)i=p-data; j=q-data; if(i=j) q=p-next; /* 刪除并釋放結(jié)點 */ p-next=q-next; free(q); p=p-next; q=p-next;4.3.3 求交集算法的詳細設(shè)計void Jiaoji(LinkList La,LinkList Lb,LinkList Lc) /*求兩集合的交集，將結(jié)果存入另一個鏈表中*/ char i,j; LinkList p ,q; La-next; Lb-next; p=La; q=Lb; while(p&q) i=p-data; j=q-data; if(inext; if(i=j) ListInsert(Lc,1,i); p=p-next;q=q-next; if(ij) q=q-next; ListSort(Lc); printf(AB=);ListPrint(Lc);4.3.4 求并集算法的詳細設(shè)計void bingji(LinkList La,LinkList Lb,LinkList Lc) char i,j;/*求兩集合的并集*/LinkList p,q;La-next;Lb-next;p=La;q=Lb;while(p&q)i=p-data; j=q-data; if(inext; if(i=j) ListInsert(Lc,1,i); p=p-next;q=q-next; if(ij) ListInsert(Lc,1,j); q=q-next; while(p)i=p-data;ListInsert(Lc,1,i);p=p-next; while(q)j=q-data;ListInsert(Lc,1,j);q=q-next;ListSort(Lc);printf(AB=);ListPrint(Lc); 4.3.5 求差集算法的詳細設(shè)計void chaji(LinkList La,LinkList Lb,LinkList Lc)char i,j;LinkList p,q;La-next;Lb-next;p=La;q=Lb;while(p&q)i=p-data; j=q-data;if(inext;if(i=j)p=p-next;if(ij)q=q-next;while(p)i=p-data;ListInsert(Lc,1,i);p=p-next;ListSort(Lc);ListPrint(Lc);第5章 測試圖5.1 輸入輸出AB集合圖5.2 對AB集合進行刪除操作圖5.3 對AB集合進行插入操作圖5.4 對AB集合進行并交差操作第6章 總結(jié)在本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的過程中，深刻的意識到對程序代碼設(shè)計的難度，不過這更讓我在這過程中受益匪淺，體味到計算機系的高大上。這個課程具有很高的挑戰(zhàn)性和耐性。進行程序設(shè)計的時候注意模塊的劃分，從各個小模塊開始進行設(shè)計。設(shè)計的過程中，出現(xiàn)了很多錯誤，但是通過查找資料，反復(fù)對比內(nèi)容的真?zhèn)涡?，找出了問題的所在，并最終解決了問題，這過程中結(jié)果并不顯的那么重要，因為有艱辛的過程，所以才顯出了結(jié)果的完美，它讓我更加堅定了在這條路上的努力發(fā)展。附錄：程序代碼 #include #include #include / malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi() #include / eof() #include / floor(),ceil(),abs() #include / exit() #include / cout,cin / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因為在math.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALSE typedef int ElemType;/*線性表的單鏈表存儲結(jié)構(gòu)*/typedef struct LNodechar data;struct LNode *next;LNode, *LinkList;LinkList h;/*帶有頭結(jié)點的單鏈表的基本操作*/void InitList(LinkList *L) /* 操作結(jié)果：構(gòu)造一個空的線性表L */*L=(LinkList)malloc(sizeof( LNode); /* 產(chǎn)生頭結(jié)點，并使L指向此頭結(jié)點 */if(!*L) /* 存儲分配失敗 */exit(OVERFLOW);(*L)-next=NULL; /* 指針域為空 */void DestroyList(LinkList *L) /* 初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L */LinkList q;while(*L)q=(*L)-next;free(*L);*L=q;void ClearList(LinkList L) /* 不改變L */ /* 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 */LinkList p,q;p=L-next; /* p指向第一個結(jié)點 */while(p) /* 沒到表尾 */q=p-next;free(p);p=q;L-next=NULL;printf(刪除成功n); /* 頭結(jié)點指針域為空 */Status ListEmpty(LinkList L) /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */if(L-next) /* 非空 */return FALSE;elsereturn TRUE;Status ListInsert(LinkList L,int i,ElemType e) /* 不改變L */ /* 在帶頭結(jié)點的單鏈線性表L中第i個位置之前插入元素e */int j=0;LinkList p=L,s;while(p&j next;j+;if(!p|ji-1) /* i小于1或者大于表長 */return ERROR;s=(LinkList)malloc(sizeof(struct LNode); /* 生成新結(jié)點 */s-data=e; /* 插入L中 */s-next=p-next;p-next=s;return OK;Status ListDelete(LinkList L,int i,ElemType *e) /* 不改變L */ /* 在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值 */int j=0;LinkList p=L,q;while(p-next&jnext;j+;if(!p-next|ji-1) /* 刪除位置不合理 */return ERROR;q=p-next; /* 刪除并釋放結(jié)點 */p-next=q-next;*e=q-data;free(q);return OK;void ListPrint(LinkList L) /*依次輸出鏈表中的元素*/LinkList p=L-next;if(!p)printf(空集n);while(p)printf(%c, p-data);p = p-next;printf(n);void ListSort(LinkList L)LinkList first; /*為原鏈表剩下用于直接插入排序的節(jié)點頭指針*/LinkList t; /*臨時指針變量：插入節(jié)點*/LinkList p; /*臨時指針變量*/LinkList q; /*臨時指針變量*/first = L-next; /*原鏈表剩下用于直接插入排序的節(jié)點鏈表*/L-next = NULL; /*只含有一個節(jié)點的鏈表的有序鏈表。*/while (first != NULL) /*遍歷剩下無序的鏈表*/*插入排序*/for (t = first, q = L; (q!=NULL) & (q-data data); p=q, q=q-next); /*無序節(jié)點在有序鏈表中找插入的位置*/*退出for循環(huán)，就是找到了插入的位置*/first = first-next; /*無序鏈表中的節(jié)點離開，以便它插入到有序鏈表中。*/if (q = L) L = t; /*插在第一個節(jié)點之前*/else p-next = t; /*p是q的前驅(qū)*/t-next = q; /*完成插入動作*/void qingchu(LinkList La)/*清除鏈表中相同的元素*/char i,j;LinkList p,q;La-next;p=La;q=p-next;while(q)i=p-data; j=q-data; if(i=j) q=p-next; /* 刪除并釋放結(jié)點 */ p-next=q-next; free(q); p=p-next; q=p-next;void zengtian(LinkList La)/*向集合中添加元素*/char a;printf(請輸入要增添的元素,加0結(jié)束n);scanf(%c,&a);while(a!=0)if(a=a&a=A&anext; Lb-next; p=La; q=Lb; while(p&q) i=p-data; j=q-data; if(inext; if(i=j) ListInsert(Lc,1,i); p=p-next;q=q-next; if(ij) q=q-next; ListSort(Lc); printf(AB=);ListPrint(Lc);void bingji(LinkList La,LinkList Lb,LinkList Lc) char i,j;/*求兩集合的并集*/LinkList p,q;La-next;Lb-next;p=La;q=Lb;while(p&q)i=p-data; j=q-data; if(inext; if(i=j) ListInsert(Lc,1,i); p=p-next;q=q-next; if(ij) ListInsert(Lc,1,j); q=q-next; while(p)i=p-data;ListInsert(Lc,1,i);p=p-next; while(q)j=q-data;ListInsert(Lc,1,j);q=q-next;ListSort(Lc);printf(AB=);ListPrint(Lc);void chaji(LinkList La,LinkList Lb,LinkList Lc)char i,j;LinkList p,q;La-next;Lb-next;p=La;q=Lb;while(p&q)i=p-data; j=q-data;if(inext;if(i=j)p=p-next;if(ij)q=q-next;while(p)i=p-data;ListInsert(Lc,1,i);p=p-next;ListSort(Lc);ListPrint(Lc);int main()char a;char b;ch