数据结构课程设计报告(集合的交并差运算)

.1/22淮阴工学院数据结构课程设计报告作者:学号：班级:学院:专业:题目:指导2016年1月.目录TOC\o"1-3"\h\u121871课题描述1245152系统设计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课题描述编制一个能演示执行集合的交、并和差运算的程序。集合元素用小写英文字母,执行各种操作应以对话方式执行。利用单链表表示集合；理解好三种运算的含义2系统设计2.1功能模块设计2.1.1基于单链表设计〔1节点结构单元模块——定义有序表的节点结构；typedefstructLNode//定义结构体类型指针{chardata;structLNode*next;}*pointer;〔2有序表单元模块——实现有序表的抽象数据类型；readdata<pointerhead>初始条件：head是以head为头节点的空链表。操作结果：生成以head为头节点的非空链表。pop<pointerhead>初始条件：head是以head为头节点的非空链表。操作结果：将以head为头节点的链表中数据逐个输出。〔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系统模块流程图调用输入函数,输入集合信息调用输入函数,输入集合信息显示主菜单显示主菜单接受用户选择接受用户选择是否合法是否合法否是是否为4是否为4否是退出系统调用对应选项函数退出系统调用对应选项函数图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!>:">; scanf<"%d",&choice>; switch<choice> { case