用單鏈表實現(xiàn)集合交并補(bǔ)

1、課程設(shè)計(論文)任務(wù)書 軟件 學(xué)院軟件工程專業(yè)2010 - 3班 一、課程設(shè)計(論文)題目數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(a)二、課程設(shè)計(論文)工作自 2011 年 12月 22日起至 2011 年 12月 23 日止。三、課程設(shè)計(論文) 地點: 軟件學(xué)院機(jī)房 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的（1）使學(xué)生熟練掌握抽象數(shù)據(jù)類型的組織和定義； （2）使學(xué)生熟練掌握數(shù)據(jù)類型的定義和實現(xiàn)； （3）培養(yǎng)學(xué)生組織和分析數(shù)據(jù)的能力；（4）培養(yǎng)學(xué)生分析和應(yīng)用基于不同數(shù)據(jù)結(jié)構(gòu)的算法的能力；（5）提高學(xué)生的科技論文寫作能力。2基本要求：每位同學(xué)在以下題目中任選一題（在方框中打勾），獨立完成課程設(shè)計： 集合的

2、并交差運算：參見數(shù)據(jù)結(jié)構(gòu)題集p80。 赫夫曼編/譯碼器：參見數(shù)據(jù)結(jié)構(gòu)題集p149。 井字棋：參見數(shù)據(jù)結(jié)構(gòu)教材p2。設(shè)計棋譜，當(dāng)對方落子后，能從棋譜中選擇一種應(yīng)對方式，并能判斷勝負(fù)。3課程設(shè)計論文編寫要求（1）要按照書稿的規(guī)格打印謄寫課設(shè)報告；（2）報告分為封面、任務(wù)書（本文檔）、正文、課程設(shè)計體會和參考文獻(xiàn)四部分；學(xué)生簽名： 2011年 12月 日課程設(shè)計(論文)評審意見（1）題目分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）流程分析（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）數(shù)據(jù)定義（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）代碼編寫（1

3、0分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）創(chuàng)新能力（10分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性、設(shè)計態(tài)度及考勤是否降等級：是（）、否（）評閱人： 職稱： 講 師 2012年 1 月 5 日正 文一、 數(shù)據(jù)結(jié)構(gòu)定義1. 抽象數(shù)據(jù)類型本設(shè)計中用到的數(shù)據(jù)結(jié)構(gòu)adt定義如下：adt list 數(shù)據(jù)對象：d= 數(shù)據(jù)關(guān)系：= 基本操作：initlist(&l) 操作結(jié)果：構(gòu)造一個空的線性表l； destroylist(&l) 初始條件：線性表l已存在 操作結(jié)果：銷毀線性表l clearlist(&l) 初始條件：線性表l已存在 操作結(jié)果：將l重置為空表 listem

4、pty(l) 初始條件：線性表l已存在 操作結(jié)果：若l為空表，則返回true，否則返回false listlenght(l) 初始條件：線性表l已存在 操作結(jié)果：返回l中數(shù)據(jù)元素的個數(shù)2. 存儲結(jié)構(gòu)定義數(shù)據(jù)存儲結(jié)構(gòu)的c語言定義如下：typedef struct lnode/定義單鏈表結(jié)點類型 elemtype data; struct lnode *next;linklist;3. 基本操作數(shù)據(jù)結(jié)構(gòu)的基本操作實現(xiàn)如下：displist(linklist *l)：輸出單鏈表lcreatlistr(linklist *&l,elemtype a,int n)：運用尾插法建立單鏈表sort(link

5、list *&head)：單鏈表元素排序shanchu(linklist *&head)：在進(jìn)行過sort排序之后，刪除單鏈表里相同的元素bing(linklist *&ha,linklist *&hb,linklist *&hc )：求兩個有序集合的并jiao(linklist *ha,linklist *hb,linklist *&hc)：求兩個有序集合的交cha(linklist *ha,linklist *hb,linklist *&hc)：求兩個有序集合的差、main()：采用尾差法建立單鏈表，使用sort進(jìn)行單鏈表排序構(gòu)成有序鏈表，在使用shanchu函數(shù)刪除相同元素和非小寫字母。

6、利用一個switch語句進(jìn)行運算的選擇，使用相關(guān)函數(shù)對有序鏈表進(jìn)行交并差的相關(guān)運算二、 解題過程1. 問題分解該問題主要應(yīng)實現(xiàn)以下功能：1. 利用尾差法建立單鏈表2. 對于輸入的鏈表進(jìn)行有序排列3. 刪除有序鏈表中不符合要求的元素4. 調(diào)用函數(shù)對單鏈表進(jìn)行交，并，差運算，并輸出2. 模塊結(jié)構(gòu)系統(tǒng)主要由8個模塊組成，分別是：1. 單鏈表的建立2. 單鏈表的有序排列3. 刪除單鏈表中不符合條件的元素4. 集合交集5. 集合并集6. 集合差集7. 單鏈表輸出8. 主函數(shù)模塊之間的結(jié)構(gòu)如下：主函數(shù)單鏈表的建立及由于排列刪除不符合條件的元素集合交集集合差集單鏈表輸出集合并集3. 解題思路各模塊的實現(xiàn)步驟

7、為：1. 在尾差法建立單鏈表時，開始時指針指向頭結(jié)點。2. 建立有序列表是利用指針的移動來是后續(xù)的元素和第一次個元素進(jìn)行比較，并使用while循環(huán)實現(xiàn)單鏈表的有序排列。3. 判定有序單鏈表中的重復(fù)元素定義指針p，通過指針p訪問鏈表中的元素并且通過if語句檢測鏈表中的元素。對于不屬于小寫字母的元素判定后進(jìn)行刪除操作。4. 定義三個頭結(jié)點pa，pb，pc，把ha的元素賦給hc，在使用指針移動與hb中的元素進(jìn)行比較，不同的元素則插入到hc中，相同時指針移動到ha的下一個元素。當(dāng)ha為空，直接把hb賦給hc。5. 同樣定義了三個結(jié)點，不過hc是pa與pb不同的元素。6. 差集是通過指針的移位把兩個有序

8、單鏈表中的元素進(jìn)行比較，不同的話，則賦給hc。7. 利用主函數(shù)把有序單鏈表，及三個函數(shù)輸出鏈表進(jìn)行輸出8. 主函數(shù)通過一個switch語句，方便的對函數(shù)進(jìn)行調(diào)用，從而進(jìn)行集合的交，并，差運算。三、 實現(xiàn)代碼及注釋:#include #include using namespace std;typedef char elemtype;typedef struct lnode/定義單鏈表結(jié)點類型 elemtype data; struct lnode *next;linklist;void creatlistr(linklist *&l,elemtype a,int n) /運用尾插法建立單鏈表

9、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(linklist *&head)/建立有序鏈表 linklist *p=head-next,*q,*r; if(p!=null) r=p-next; p-next=null; p=r; while(p!=null)/后續(xù)元素與第一個

10、元素進(jìn)行比較 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)/刪除有序鏈表中重復(fù)的元素及非小寫字母的元素 linklist *p=head-next,*r=head,*q,*f; while(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

11、(r-next-dataz|r-next-datanext; r-next=f-next; free(f); void bing(linklist * ha,linklist * hb,linklist * hc)/求并集hclinklist * pa,* pb,* pc;pa=ha-next;while(pa!=null)pc=(linklist *)malloc(sizeof(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(p

12、a!=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,linklist *hb,linklist *&hc)/求交集hc linklist *pa=ha-next,*pb,*s,*tc; hc=(linklist *)malloc(sizeof(linklist);/定義hc的頭結(jié)點 tc=hc; while(pa) pb

13、=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 cha(linklist *ha,linklist *hb,linklist *&hc)/求差集hc linklist *pa=ha-next,*pb,*s,*tc; hc=(linklist *)malloc(sizeof(linklist);/定義hc的頭

14、結(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 displist(linklist *l)/輸出單鏈表l linklist *p=l-next; while(p!=null) coutdata; p=p-next; coutendl;int main() li

15、nklist *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!=

16、0) /循環(huán)對運算的選擇 coutx; switch(x) case 1: cout有序1集合:;displist(ha); cout有序2集合:;displist(hb);/輸出有序集合 break; case 2: jiao(ha,hb,hc); cout交集合:;displist(hc);/調(diào)用求交集函數(shù) break; case 3: bing(ha,hb,hc); cout并集合:;displist(hc);/調(diào)求用并集函數(shù) break; case 4: cha(ha,hb,hc); cout差集合:;displist(hc);/調(diào)用求差集函數(shù) break; return 0; 四、

17、實驗結(jié)果1. 實驗數(shù)據(jù)集合1：xiaosihehe集合2：wuhaha2. 實驗結(jié)果五、 實驗小結(jié)1. 數(shù)據(jù)結(jié)構(gòu)使用小結(jié)鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街?，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。單鏈表的建立有頭插法、尾插法兩種方法。在本次課程設(shè)計中采取了尾差法進(jìn)行建立單鏈表。尾插法建立鏈表時，頭指針固定不動，故必須設(shè)立一個搜索指針，向鏈表右邊延伸，則整個算法中應(yīng)設(shè)立三個鏈表指針，即頭指針、搜索指針、申請單元指針。在使用尾差法建立單鏈表時最先得到的一定是頭結(jié)點。2. 需完善之處本次選取的求取集合的交并差運算，只是限于小寫字母，不能推廣到所有字符。對于非小寫字母只能使用函數(shù)刪除，有一定的局限性，有待完善課程設(shè)計體會通過此次課程設(shè)計，我更加熟悉了單鏈表的運用，對于書上的關(guān)于運用單鏈表進(jìn)行集合的的交，并，差，進(jìn)行了添加模塊和修改，參考了同學(xué)的建議，使之能夠簡單的運算小寫字母的交并補(bǔ)。這次課程設(shè)計讓我明白，設(shè)計思路十