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

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