數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-集合的交并差運算

編號：730 氧;）技林電孑科蕊火容GUILINUNIVERSITYOFELECTRONICTECHNOLOGY數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計說明書集合的交并差運算學院： 海洋信息工程學院專業(yè):網(wǎng)絡(luò)工程TOC\o"1-5"\h\z學生姓名： xx學號： xx指導(dǎo)教師：XX2017年12月21日目錄\o"CurrentDocument"目錄 2概述 3程序說明 3\o"CurrentDocument"1實驗內(nèi)容 41。1實驗?zāi)康?4\o"CurrentDocument"1.2實驗任務(wù) 41.3要求 42數(shù)據(jù)結(jié)構(gòu)設(shè)計及流程圖 52。 1抽象數(shù)據(jù)結(jié)構(gòu)類型定義 5\o"CurrentDocument"2.2本程序包含四個模塊 73測試數(shù)據(jù) 8\o"CurrentDocument"3.1源程序 8\o"CurrentDocument"3。 2測試數(shù)據(jù)及程序運行情況 144總結(jié) 15參考文獻 15本演示程序的編寫，主要運用的我們學的第二章《線性表》中的知識。線性結(jié)構(gòu)的特點是:在數(shù)據(jù)元素的非空有限集中，（1）存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素；（2）存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素；（3）除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；（4）除最后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼.本程序需要兩個抽象數(shù)據(jù)類型：有序表和集合。而且采用了單鏈表來實現(xiàn)。一、程序說明本程序主要利用單鏈表及函數(shù)，實現(xiàn)集合的交集、并集和差集運算.運行程序說明：菜單執(zhí)行的命令包括〈0-7>：〈1〉“請輸入A集合的個數(shù)與A集合元素”〈2〉“請輸入8集合個數(shù)與B集合的元素〃〈3〉“A集合的有序集合”<4〉“B集合的有序集合”〈5〉“AB集合的并集〃<6>“AB集合的交集”〈7>“AB集合的差集”<0〉“退出〃注：展示程序中，集合元素限定為小寫字母數(shù)據(jù)，以“回車鍵〃束標志。1、 實驗內(nèi)容1。1實驗?zāi)康模涸O(shè)計一個演示集合的交、并、差的運算程序1。2實驗任務(wù)1） 使用單鏈表來表示集合，完成集合的交集、并集、差等操作。2） 采用鏈表等數(shù)據(jù)結(jié)構(gòu)。3） 集合的元素限定為數(shù)字和小寫的英文字母1。3實驗要求：初步完成總體設(shè)計，建立頭文件，確定函數(shù)個數(shù)。完成以下條件：1） 界面清楚，函數(shù)功能劃分好2） 總體設(shè)計應(yīng)畫流程圖3） 程序要加必要的注釋4） 提供測試方案注：程序多次測試，彌補漏洞。要求：1） 展示程序中，集合元素限定為小寫字母數(shù)據(jù)。集合輸入的形式為一以“回車鍵”束標志。2） 展示程序以用戶和計算機的對話方式執(zhí)行，即在程序輸出顯示“提示信息'之

后，然后再輸入命令；相應(yīng)的輸入數(shù)據(jù)和運算結(jié)果顯示在其后。3）程序執(zhí)行的命令包括〈0-7〉：<1〉“請輸入A集合的個數(shù)與A集合元素”<2>“請輸入B集合個數(shù)與B集合的元素”〈3〉“A集合的有序集合”<4〉“B集合的有序集合”〈5>“AB集合的并集”<6〉“AB集合的交集〃〈7〉“AB集合的差集〃<0〉“退出”程序功能：計算兩個的集合的交、并、差以及重新輸入集合功能。一、數(shù)據(jù)結(jié)構(gòu)設(shè)計及流程圖實現(xiàn)功能:C=A+B：A.Add(l);C=A+B：A.Add(l);A.Add⑵：8.Addt3):⑵:A.Add(4):A.Add(9):B.Addt?): cout?C?wndl；町3〔8)；SetA:SetB；SetC:A,Add⑴；B.Add(3)；C=A*8；A.Add{2):B.Add(2);A.Add{4):日.Ad出7）：coul?C?endlA,Add(9)；e.Addifl};6集合的并集合的交集合的并為了實現(xiàn)上述程序的功能，應(yīng)以有序單鏈表表示集合。為此，需要抽象數(shù)據(jù)類型：有序表和集合2.1數(shù)據(jù)類型定義1、//線性表的單鏈表存儲結(jié)構(gòu)typedefstructLNode{ElemTypedata；structLNode大next;}LinkList；1、 實現(xiàn)輸出功能的函數(shù)voidDispList()//輸出函數(shù)2、 輸入門個元素的值，建立帶表頭結(jié)點的單鏈線性表LvoidCreateList_L1(LinkList大&L,intn)4、實現(xiàn)集合元素由小到大排序功能voidsort(LinkList大&L)5、 實現(xiàn)了將A、B集合的并集，并放到新的單鏈表C中voidUnion(LinkList*ha，LinkList*hb,LinkList大&hc)6、 實現(xiàn)了將A、B集合的交集，并放到新的單鏈表C中voidInterSect(LinkList*ha,LinkList*hb,LinkList大&hc)7、 實現(xiàn)了將A、B集合的差集，并放到新的單鏈表C中voidSubs(LinkList*ha,LinkList大hb,LinkList大&hc)8、 銷毀表LvoidDestroyList(LinkList*&L)3、 主程序模塊(){初始化；定義變量；While(){選擇菜單Switch(){casel: case2： case3： }}Return0；}2.2本程序包含四個模塊1） 主菜單模塊2） 輸入集合單元模塊：運用單鏈表輸入；3） 集合運算單元模塊：實現(xiàn)集合的抽象數(shù)據(jù)類型;4） 有序表單元模塊：實現(xiàn)有序表的抽象數(shù)據(jù)類型；模塊關(guān)系：3.1測試數(shù)據(jù)：集合A={dop}，B={dli},運算其交集、并集、差集。3.2源程序：源程序代碼如下：include〈iostream>include〈stdio.h>#include<malloc。h〉#include〈cstdio>usingnamespacestd；typedefcharElemType；typedefstructLNode(ElemTypedata；structLNode*next；}LinkList；voidDispList(LinkList*L)//輸出函數(shù){LinkList*p=L—>next;while(p!=NULL){printf("%c",p->data)；p=p-〉next;}printf("\n");}voidCreateList_L1(LinkList大&L,intn){//輸入n個元素的值，建立帶表頭結(jié)點的單鏈線性表LLinkList*p,*q;L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL；q=L;for(inti=n；i>0； i){p=(LinkList*)malloc(sizeof(LinkList))；//生成新結(jié)點cin>>p->data；//輸入元素值p—>next=NULL;q-〉next=p;//插入到表尾q=p;}}voidDestroyList(LinkList大&L){LinkList*p=L—>next，*pre=L;while(p!二NULL)(free(pre)；pre=p；p=pre一>next；}free(pre)；}voidsort(LinkList大&L)//從小到大排序{LinkList大pre,*p,*q;p=L一>next-〉next；L一>next一>next=NULL；while(p!=NULL)(q=p-〉next；pre=L；while(pre-〉next!二NULL&&pre—>next一〉data<p一>data)pre=pre-〉next;p->next=pre—>next;pre-〉next=p;p=q;}}voidUnion(LinkList*ha,LinkList*hb,LinkList*&hc)//求集合的并(LinkList大pa=ha—>next,*pb=hb->next,*pc,*s；hc=(LinkList*)malloc(sizeof(LinkList));pc=hc;while(pa!=NULL&&pb!二NULL){if(pa—>data〈pb—>data){s=(LinkList*)malloc(sizeof(LinkList));s->data=pa->data；pc-〉next=s；pc=s;pa=pa->next；}elseif(pa-〉data〉pb-〉data)(s=(LinkList*)malloc(sizeof(LinkList))；s—>data=pb—〉data;pc—>next=s；pc=s；pb=pb—〉next；}else(s=(LinkList*)malloc(sizeof(LinkList))；s—〉data=pa->data；pc—>next=s;pc=s；pa=pa->next;pb=pb->next；}}if(pb!=NULL)pa=pb；while(pa!=NULL)(s=(LinkList*)malloc(sizeof(LinkList));s一〉data=pa—>data；pc—〉next=s；pc=s；pa=pa-〉next；}pc—〉next=NULL；}voidInterSect(LinkList大ha,LinkList*hb,LinkList*&hc)〃求兩個有序集合的交用尾插法(LinkList大pa=ha—〉next,*pb,*pc,*s;hc=(LinkList*)malloc(sizeof(LinkList));pc=hc；while(pa!=NULL)(pb=hb—>next;while(pb!二NULL&&pb—〉data<pa—>data)pb=pb-〉next;if(pb!=NULL&&pb—>data==pa->data)///B節(jié)點在A節(jié)點中復(fù)制A節(jié)點(s=(LinkList*)malloc(sizeof(LinkList))；s—>data=pa—>data；pc-〉next=s；pc=s；}pa=pa——>next;}pc一>next=NULL;}voidSubs(LinkList大ha,LinkList*hb,LinkList*&hc)//求兩個有序集合的差(LinkList大pa=ha-〉next,*pb,*pc,*s;hc=(LinkList*)malloc(sizeof(LinkList))；pc=hc;while(pa!=NULL){pb=hb->next;while(pb!=NULL&&pb一>data〈pa—>data)pb=pb-〉next;if(!(pb!=NULL&&pb-〉data=二pa->data))///B節(jié)點不在A節(jié)點中復(fù)制A節(jié)點(s=(LinkList*)malloc(sizeof(LinkList))；s->data=pa——〉data;pc——>next=s;pc=s;}pa=pa-〉next；}pc-〉next=NULL;}intmain()(LinkList*ha,大hb,*hc;

intn,k;while(1)(cout〈<”\n\t\t一集合的簡單運算一\n\n〃;cout<〈"\t\t\t菜單\n”；cout<<”\t\t\t\n”；cout<<”\t\t\t1.請輸入A集合個數(shù)與A集合的元素\n";cout<〈"\t\t\t 2.請輸入Bintn,k;while(1)(cout〈<”\n\t\t一集合的簡單運算一\n\n〃;cout<〈"\t\t\t菜單\n”；cout<<”\t\t\t\n”；cout<<”\t\t\t1.請輸入A集合個數(shù)與A集合的元素\n";cout<〈"\t\t\t 2.請輸入B集合個數(shù)與B集合的元素\n”；cout<〈”\t\t\t3。A集合的有序集合\n”；cout<<”\t\t\t4.B集合的有序集合\n"；cout〈〈”\t\t\t5。AB集合的并集\n";cout〈〈”\t\t\t6。AB集合的交集\n”；cout<<”\t\t\t7.AB集合的差集\n”;\n";\n"；cout〈<”\t\t\t 0.退出\n";\n"；cout<<"\t\t\tcout<〈”\t\t\t請選擇(0—7):"；cin>>k；switch(k){case1:cout〈<”請輸入A集合的個數(shù)與A集合元素："；cin>〉n;CreateList_L1(ha,n);break;case2:cout<〈”請輸入B集合的個數(shù)與B集合元”；cin>〉n；CreateList_L1(hb,n);break；case3：sort(ha);cout<<"\nA的有序集合為：";DispList(ha)；break;case4：sort(hb)；cout<<"\nB的有序集合為："；DispList(hb);break；case5:Union(ha,hb,hc)；cout〈〈"\nAB集合的并集為："；DispList(hc);break;case6:InterSect(ha,hb,hc);cout〈〈"\nAB集合的交集為："；DispList(hc);break;桂林電子科技大學數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書case7:Subs(ha,hb,hc);cout<<”\nAB集合的差集為："；DispList(hc);break;case0：cout<<〃\n\t\t\t 謝謝使用！ \n〃；cout<<"\n\t\t\t按任意鍵退出。..°..\n"；return0；}//switch}//whileDestroyList(ha);DestroyList(hb);DestroyList(hc);return0;}3。3測試數(shù)據(jù)及運行情況選擇功能<0—7〉23■156■23■156■.rr與與??X..-■-,■.IT-rp頃邙_"=一BBBnEJAhnL請選擇輸入A集合的個數(shù)與A集合的元素{dop}土至不=?=■芝二.H.B.呆MA@與與,TT*里乓杉杉弟3一fiBJ-ruvr-日白白mz.Z.-AA12J4SLVM請:1諸初W集合的個數(shù)與嶂合元素;3dDP輸入B集合的個數(shù)與B集合的元素{dli}一-.■■'M-.-:.一-.■■'M-.-:..:Wg-B..-ftnB-上_?**一|-|B勺.Jzr1￡n.日.日妃L、■B白土n二n二nA飩擇＜0-?＞：2請輸入蝶合的佛與B集合元素，3MA集合的有序集合—集合的簡單運其一1

234

5固7

0請選擇E-gD的有序集合為：dovB集合的有序集合與」??1元元的的?■1.TTiK靠哭4.一■sH?L?E±JBiIL:r-宕砂I--r二■-I舞AIIAIIABin12345670AB集合的并集宣口sAH-與與救蓍臺耳禁nJr_AflEII1234E670清A；±<0-7>：5AB集合的交集打.衛(wèi)打.衛(wèi)請旅擇CH6W集?含b?土桌7［，“AB集合的差集r5-—'.■'□_=r".g-“■w.身hr」一」一拓帝l:.nsi并交差??■?1.H1Afl