數(shù)據結構課程設計-集合的交并差運算

數(shù)據結構課程設計-集合的交并差運算編號：730數(shù)據結構與算法課程設計說明書集合的交并差運算學院：海洋信息工程學院專業(yè)：網絡工程學生姓名：xx學號：xx指導教師：xx2017年12月21日數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第1頁。數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第1頁。目錄目錄 2概述 3程序說明 31HYPERLINK實驗任務 41.3要求 42數(shù)據結構設計及流程圖 52.1HYPERLINK測試數(shù)據 83.1源程序 83.2測試數(shù)據及程序運行情況 144總結 15參考文獻 15數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第2頁。數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第2頁。概述本演示程序的編寫，主要運用的我們學的第二章《線性表》中的知識。線性結構的特點是：在數(shù)據元素的非空有限集中，（1）存在唯一的一個被稱做“第一個”的數(shù)據元素；（2）存在唯一的一個被稱做“最后一個”的數(shù)據元素；（3）除第一個之外，集合中的每個數(shù)據元素均只有一個前驅；（4）除最后一個之外，集合中每個數(shù)據元素均只有一個后繼。本程序需要兩個抽象數(shù)據類型：有序表和集合。而且采用了單鏈表來實現(xiàn)。一、程序說明本程序主要利用單鏈表及函數(shù)，實現(xiàn)集合的交集、并集和差集運算。運行程序說明：菜單執(zhí)行的命令包括<0-7>：<1>“請輸入A集合的個數(shù)與A集合元素”<2>“請輸入B集合個數(shù)與B集合的元素”<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”注：展示程序中，集合元素限定為小寫字母數(shù)據，以“回車鍵”束標志。數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第3頁。數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第3頁。實驗內容1.1實驗目的：設計一個演示集合的交、并、差的運算程序1.2實驗任務使用單鏈表來表示集合，完成集合的交集、并集、差等操作。采用鏈表等數(shù)據結構。集合的元素限定為數(shù)字和小寫的英文字母1.3實驗要求：初步完成總體設計，建立頭文件，確定函數(shù)個數(shù)。完成以下條件:界面清楚，函數(shù)功能劃分好總體設計應畫流程圖程序要加必要的注釋提供測試方案注：程序多次測試，彌補漏洞。要求：展示程序中，集合元素限定為小寫字母數(shù)據。集合輸入的形式為一以“回車鍵”束標志。2）展示程序以用戶和計算機的對話方式執(zhí)行，即在程序輸出顯示“提示信息”之后，然后再輸入命令；相應的輸入數(shù)據和運算結果顯示在其后。3）程序執(zhí)行的命令包括<0-7>：<1>“請輸入A集合的個數(shù)與A集合元素”數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第4頁。<2>“請輸入B集合個數(shù)與B集合的元素”數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第4頁。<3>“A集合的有序集合”<4>“B集合的有序集合”<5>“AB集合的并集”<6>“AB集合的交集”<7>“AB集合的差集”<0>“退出”程序功能：計算兩個的集合的交、并、差以及重新輸入集合功能。一、數(shù)據結構設計及流程圖實現(xiàn)功能：集合的交集合的并為了實現(xiàn)上述程序的功能，應以有序單鏈表表示集合。為此，需要抽象數(shù)據類型：有序表和集合2.1數(shù)據類型定義1、//線性表的單鏈表存儲結構typedefstructLNode數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第5頁。{ElemTypedata;數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第5頁。structLNode*next;}LinkList;實現(xiàn)輸出功能的函數(shù)voidDispList()//輸出函數(shù)輸入n個元素的值，建立帶表頭結點的單鏈線性表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)主程序模塊（）{初始化；定義變量；While（）數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第6頁。{數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第6頁。選擇菜單Switch（）{case1：……case2:……case3：……}}Return0；}2.2本程序包含四個模塊1）主菜單模塊2）輸入集合單元模塊：運用單鏈表輸入；3）集合運算單元模塊：實現(xiàn)集合的抽象數(shù)據類型；4）有序表單元模塊：實現(xiàn)有序表的抽象數(shù)據類型；模塊關系：數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第7頁。數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第7頁。3.1測試數(shù)據：集合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個元素的值，建立帶表頭結點的單鏈線性表LLinkList*p,*q;L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;q=L;for(inti=n;i>0;--i){p=(LinkList*)malloc(sizeof(LinkList));//生成新結點cin>>p->data;//輸入元素值p->next=NULL;q->next=p;//插入到表尾q=p;}}數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第8頁。voidDestroyList(LinkList*&L)數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第8頁。{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數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第9頁。{s=(LinkList*)malloc(sizeof(LinkList));數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第9頁。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é)點中復制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;數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第10頁。while(pa!=NULL)數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第10頁。{pb=hb->next;while(pb!=NULL&&pb->data<pa->data)pb=pb->next;if(!(pb!=NULL&&pb->data==pa->data))///B節(jié)點不在A節(jié)點中復制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\t2.請輸入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";cout<<"\t\t\t0.退出\n";cout<<"\t\t\t———————————\n";cout<<"\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;case7:Subs(ha,hb,hc);cout<<"\nAB集合的差集為：";DispList(hc);break;case0:cout<<"\n\t\t\t謝謝使用！\n";數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第11頁。cout<<"\n\t\t\t按任意鍵退出\n";數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第11頁。return0; }//switch}//whileDestroyList(ha);DestroyList(hb);DestroyList(hc);return0;}3.3測試數(shù)據及運行情況選擇功能<0-7>輸入A集合的個數(shù)與A集合的元素{dop}數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第12頁。輸入B集合的個數(shù)與B集合的元素{dli}數(shù)據結構課程設計-集合的交并差運算全文共15頁，當前為第12頁。A集合的有