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

.淮陰工學院數據結構課程設計報告作者:學號：班級:學院:專業(yè):題目:指導教師：2016年1月.目錄TOC\o"1-3"\h\u121871課題描述 1245152系統(tǒng)設計 1123062.1功能模塊設計 1222122.1.1基于單鏈表設計 1249912.1.2基于順序表設計 278422.2數據結構設計 2197772.2.1基于單鏈表設計 289732.1.2基于順序表設計 385602.3算法設計 380702.3.1基于單鏈表，順序表設計 3319713.1菜單設計（基于單鏈表） 5153433.2源代碼設計（基于單鏈表） 5238533.3菜單設計（基于順序表） 10193993.4源代碼設計（基于順序表） 10221214.1最終結果（基于單鏈表） 2027814.2最終結果（基于順序表） 2010598結論 2112113致 2231086參考文獻 23.1課題描述編制一個能演示執(zhí)行集合的交、并和差運算的程序。集合元素用小寫英文字母，執(zhí)行各種操作應以對話方式執(zhí)行。利用單鏈表表示集合；理解好三種運算的含義2系統(tǒng)設計2.1功能模塊設計2.1.1基于單鏈表設計（1）節(jié)點結構單元模塊——定義有序表的節(jié)點結構；typedefstructLNode//定義結構體類型指針{chardata; structLNode*next;}*pointer;（2）有序表單元模塊——實現有序表的抽象數據類型；readdata(pointerhead)初始條件：head是以head為頭節(jié)點的空鏈表。操作結果：生成以head為頭節(jié)點的非空鏈表。pop(pointerhead)初始條件：head是以head為頭節(jié)點的非空鏈表。操作結果：將以head為頭節(jié)點的鏈表中數據逐個輸出。（3）集合單元模塊——實現集合獲得抽象數據類型；and(pointerhead1,pointerhead2,pointerhead3)初始條件：鏈表head1、head2、head3已存在操作結果：生成一個由head1和head2的并集構成的集合head3。or(pointerhead1,pointerhead2,pointerhead3)初始條件：鏈表head1、head2、head3已存在操作結果：生成一個由head1和head2的交集構成的集合head3。（4）主程序模塊Voidmain（）{初始化；do{接受命令；處理命令；}while（“命令”!=“退出”）；}2.1.2基于順序表設計（1）順序表結構單元模塊——定義順序表的結構體；typedefstruct//定義SeqList的結構體{DataTypelist[MaxSize];intsize;}SeqList;（2）函數單元模塊——定義各種所需函數；intListDel(SeqList*L,inti,DataType*x)//順序表的刪除函數intListGet(SeqListL,inti,DataType*x)//獲取順序表的元素函數voidListFind(SeqListL,DataTypex)//順序表查找元素函數voidSelcetSort(SeqList*L)//順序表選擇排序函數voidUnionSet(SeqListmylist1,SeqListmylist2)//求并集函數voidMixedSet(SeqListmylist1,SeqListmylist2)//求交集元素函數voidDiffentSet(SeqListmylist1,SeqListmylist2)//求差集元素函數（3）主函數單元模塊——定義主函數；voidmain(){SeqListmylist1,mylist2;//定義順序表mylistinti; DataTypetemp; ListInitiate(&mylist1); ListInitiate(&mylist2);}//初始化兩個順序表2.2數據結構設計2.2.1基于單鏈表設計定義結構體類型指針，集合采用單鏈表存儲。typedefstructLNode//定義結構體類型指針head1=(pointer)malloc(sizeof(structLNode)); head1->next=NULL; head2=(pointer)malloc(sizeof(structLNode)); head2->next=NULL; head3=(pointer)malloc(sizeof(structLNode));2.1.2基于順序表設計typedefstruct//定義SeqList的結構體{DataTypelist[MaxSize];intsize;voidUnionSet(SeqListmylist1,SeqListmylist2)//求并集{ intm,i,j; DataTypex; SeqListTest ; ListInitiate(&Test);//定義并初始化2.3算法設計2.3.1基于單鏈表，順序表設計數據輸入界面數據輸入界面主菜單界面主菜單界面 結束集合的差集運算集合的交集運算集合的并集運算 結束集合的差集運算集合的交集運算集合的并集運算圖2.1系統(tǒng)模塊流程圖調用輸入函數，輸入集合信息調用輸入函數，輸入集合信息顯示主菜單顯示主菜單接受用戶選擇接受用戶選擇是否合法是否合法否是是否為4是否為4否是退出系統(tǒng)調用對應選項函數退出系統(tǒng)調用對應選項函數圖2.2主菜單流程圖主菜單主菜單用戶選擇序號用戶選擇序號是否合法是否合法否是是否為1是否為1否是調用并集函數和輸出函數調用并集函數和輸出函數圖2.3并集模塊流程圖求交集與差集的流程圖與并集類似。3詳細設計3.1菜單設計（基于單鏈表）圖3.1主界面3.2源代碼設計（基于單鏈表）#include<stdio.h>#include<stdlib.h>typedefstructLNode//定義結構體類型指針{ chardata; structLNode*next;}*pointer;voidreaddata(pointerhead)//定義輸入集合函數{ pointerp; chartmp; scanf("%c",&tmp); while(tmp!='\n') { p=(pointer)malloc(sizeof(structLNode));//為指針P申請存空間 p->data=tmp; p->next=head->next; head->next=p; scanf("%c",&tmp); }}voidpop(pointerhead)//定義輸出集合函數pop()出棧函數{ pointerp; p=head->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}voidand(pointerhead1,pointerhead2,pointerhead3)//定義集合的并集函數{ pointerp1,p2,p3; p1=head1->next; while(p1!=NULL)//遍歷鏈表head1 { p3=(pointer)malloc(sizeof(structLNode)); p3->data=p1->data; p3->next=head3->next; head3->next=p3; p1=p1->next; } p2=head2->next; while(p2!=NULL)//遍歷鏈表head2 { p1=head1->next; while((p1!=NULL)&&(p1->data!=p2->data)) p1=p1->next; if(p1==NULL) { p3=(pointer)malloc(sizeof(structLNode)); p3->data=p2->data; p3->next=head3->next; head3->next=p3; } p2=p2->next; }}voidor(pointerhead1,pointerhead2,pointerhead3)//定義集合的交集函數{ pointerp1,p2,p3; p1=head1->next; while(p1!=NULL) { p2=head2->next; while((p2!=NULL)&&(p2->data!=p1->data)) p2=p2->next; if((p2!=NULL)&&(p2->data==p1->data)) { p3=(pointer)malloc(sizeof(structLNode)); p3->data=p1->data; p3->next=head3->next; head3->next=p3; } p1=p1->next; }}voiddiffer(pointerhead1,pointerhead2,pointerhead3)//定義集合的差集函數{ pointerp1,p2,p3; p1=head1->next; while(p1!=NULL) { p2=head2->next; while((p2!=NULL)&&(p2->data!=p1->data)) p2=p2->next; if(p2==NULL) { p3=(pointer)malloc(sizeof(structLNode)); p3->data=p1->data; p3->next=head3->next; head3->next=p3; } p1=p1->next; }}voidmain()//主函數{ intx;printf("(輸入數據,按回車鍵結束,第一個集合大于第二個集合)\n"); pointerhead1,head2,head3; head1=(pointer)malloc(sizeof(structLNode)); head1->next=NULL; head2=(pointer)malloc(sizeof(structLNode)); head2->next=NULL; head3=(pointer)malloc(sizeof(structLNode)); head3->next=NULL; printf("請輸入集合1：\n"); readdata(head1);//調用輸入集合函數 printf("請輸入集合2：\n"); readdata(head2);//調用輸入集合函數A:printf("1.并集2.交集3.差集4.結束x.重新運算\n");do{ printf("請選擇序號\n"); scanf("%d",&x);switch(x){case1: printf("兩集合的并是\n"); and(head1,head2,head3);//調用并集函數 pop(head3); head3->next=NULL; break;case2: printf("兩集合的交是\n"); or(head1,head2,head3);//調用交集函數 pop(head3); head3->next=NULL; break;case3:printf("兩集合的差是\n"); differ(head1,head2,head3);//調用差集函數 pop(head3); head3->next=NULL; break;case4:break; default:gotoA;} }while(x!=4);}3.3菜單設計（基于順序表）圖3.2主界面3.4源代碼設計（基于順序表）#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMaxSize100#defineEQUAL"================================="typedefcharDataType;typedefstruct//定義SeqList的結構體{ DataTypelist[MaxSize];intsize;}SeqList;voidListInitiate(SeqList*L)//初始化操作{ L->size=0;}intListLength(SeqListL)//獲取長度{ returnL.size;}intListInsert(SeqList*L,inti,DataTypex)//插入函數的參數分別是SeqList類型的變量，插入位置I，和插入的元素X{ intj;if(L->size>=MaxSize) { printf("順序表已滿，無法插入其他元素！\n"); return0; system("pause"); }elseif(i<0&&i>L->size){ printf("參數i不合法！\n");return0;system("pause");}else{ for(j=L->size;j>i;j--){ L->list[j]=L->list[j-1];//將i至size中間的元素依次后移一個單位}L->list[i]=x;//將x插入指定的位置iL->size++;//L的size，及長度加一return1;}}intListDel(SeqList*L,inti,DataType*x)//順序表的刪除函數{ intj; if(L->size<=0) { printf("順序表已無數據可刪！\n"); return0; system("pause"); }elseif(i<0&&i>L->size-1){ printf("參數i不合法！\n");return0;system("pause");}else{ *x=L->list[i];//保存刪除的元素到x中for(j=i+1;j<=L->size-1;j++){ L->list[j-1]=L->list[j];//將i+1至size中間的元素依次前移一個單位}L->size--;//L的size，及長度加一return1;}}intListGet(SeqListL,inti,DataType*x)//獲取順序表的元素函數{ if(i<0||i>L.size-1){ printf("參數i不合法！\n");return0;}else{ *x=L.list[i];return1;}}voidListFind(SeqListL,DataTypex)//順序表查找元素函數{ inti;for(i=0;i<L.size;i++){ if(L.list[i]==x) {printf("與查找元素相同的位置為：%d\n",i+1);continue; }}if(i==L.size-1) { printf("沒有找到與所查詢相同的元素！\n"); }}voidSelcetSort(SeqList*L)//順序表選擇排序函數{ inti,j; DataTypetemp; intlength=ListLength(*L); for(i=0;i<length-1;i++) { temp=L->list[i+1]; j=i; while(j>-1&&temp<L->list[j]) { L->list[j+1]=L->list[j]; j--; } L->list[j+1]=temp; }}voidUnionSet(SeqListmylist1,SeqListmylist2)//求并集{ intm,i,j; DataTypex; SeqListTest ; ListInitiate(&Test);//定義并初始化 for(m=0;m<ListLength(mylist1);m++){ ListGet(mylist1,m,&x); ListInsert(&Test,m,x);//先將順序表一中的元素放入順序表中} for(i=0;i<ListLength(mylist2);i++){ ListGet(mylist2,i,&x); ListInsert(&Test,m,x);//再將順序表二中的元素放入順序表中 m++;} for(i=0;i<ListLength(Test);i++)//求并集 { for(j=i+1;j<ListLength(Test);j++)//將順序表中的相同的元素刪除 if(Test.list[i]==Test.list[j]) ListDel(&Test,j,&x); } SelcetSort(&Test); printf("TheelementsoftheUnionSetare:"); for(i=0;i<ListLength(Test);i++){ ListGet(Test,i,&x);printf("%c",x);}printf("\n");}voidMixedSet(SeqListmylist1,SeqListmylist2)//求交集元素函數{ intm,i,j; DataTypex; SeqListmylist ; ListInitiate(&mylist);//定義并初始化 SeqListTest; ListInitiate(&Test); m=0; for(i=0;i<ListLength(mylist1);i++)//求交集 { for(j=0;j<ListLength(mylist2);j++) if(mylist1.list[i]==mylist2.list[j]) { ListInsert(&Test,m,mylist1.list[i]); //將相同的元素放在Test順序表中 m++; continue; } } for(i=0;i<ListLength(Test);i++)//求并集 { for(j=i+1;j<ListLength(Test);j++)//將順序表中的相同的元素刪除 if(Test.list[i]==Test.list[j]) ListDel(&Test,j,&x); } SelcetSort(&Test);//對順序表進行有序化 printf("TheelementsoftheMixedSetare:"); for(i=0;i<Test.size;i++){ ListGet(Test,i,&x);printf("%c",x);}printf("\n");}voidDiffentSet(SeqListmylist1,SeqListmylist2)//求差集元素函數{ intm=0,n,i,j; DataTypex; SeqListTest; ListInitiate(&Test); for(i=0;i<ListLength(mylist1);i++) { n=0; for(j=0;j<ListLength(mylist2);j++) if(mylist1.list[i]==mylist2.list[j]) n++; if(n==0) { ListInsert(&Test,m,mylist1.list[i]); //將相同的元素放在Test順序表中 m++; } } for(i=0;i<ListLength(Test);i++)//求并集 { for(j=i+1;j<ListLength(Test);j++)//將順序表中的相同的元素除 if(Test.list[i]==Test.list[j]) ListDel(&Test,j,&x); } SelcetSort(&Test); printf("TheelementsoftheDiffrentSetare:"); for(i=0;i<ListLength(Test);i++){ ListGet(Test,i,&x);printf("%c",x);}printf("\n");}voidmain(){ SeqListmylist1,mylist2;//定義順序表mylistinti; DataTypetemp; ListInitiate(&mylist1); ListInitiate(&mylist2);//初始化兩個順序表 printf("\n%s%s\n",EQUAL,EQUAL); printf("\nWelcometotheProgramofCollection!\n"); printf("\n%s%s\n",EQUAL,EQUAL); printf("\n請輸入兩個集合!\n"); printf("\n請輸入集合1！:"); i=0;while((temp=getchar())!='\n') { if(96<temp&&temp<123) { ListInsert(&mylist1,i,temp);//順序表一賦值temp; i++; }} printf("\n輸入集合2！:"); i=0;while((temp=getchar())!='\n') { if(96<temp&&temp<123) { ListInsert(&mylist2,i,temp);//順序表一賦值temp; i++; }} printf("\ncollectionone:"); for(i=0;i<mylist1.size;i++) printf("%c",mylist1.list[i]); printf("\n\n"); printf("collectiontwo:"); for(i=0;i<mylist2.size;i++) printf("%c",mylist2.list[i]); printf("\n\n"); //調用各個函數 printf("\n請選擇功能:!\n"); printf("\n%s%s\n",EQUAL,EQUAL); printf("Thenumber1is:并集.\n"); printf("Thenumber2is:交集.\n"); printf("Thenumber3is:差集.\n"); printf("%s%s\n",EQUAL,EQUAL); while(1) { intchoice; printf("\n請輸入您的選擇?。篭n(othersexittheprograme!):");