集合的并交差運(yùn)算.doc

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