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

《数据结构课程设计报告(集合的交并差运算)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

......淮阴工学院数据结构课程设计报告作者:学号：班级:学院:专业:题目:指导教师：2016年1月学习好帮手 ......学习好帮手 ......目录1课题描述12系统设计12.1功能模块设计12.1.1基于单链表设计12.1.2基于顺序表设计22.2数据结构设计22.2.1基于单链表设计22.1.2基于顺序表设计32.3算法设计32.3.1基于单链表，顺序表设计33.1菜单设计（基于单链表）53.2源代码设计（基于单链表）53.3菜单设计（基于顺序表）103.4源代码设计（基于顺序表）104.1最终结果（基于单链表）204.2最终结果（基于顺序表）20结论21致谢22参考文献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否是退出系统调用对应选项函数图2.2主菜单流程图主菜单用户选择序号是否合法否是是否为1否是调用并集函数和输出函数图2.3并集模块流程图求交集与差集的流程图与并集类似。学习好帮手 ......3详细设计3.1菜单设计（基于单链表）图3.1主界面3.2源代码设计（基于单链表）#include#includetypedefstructLNode//定义结构体类型指针{chardata;structLNode*next;}*pointer;voidreaddata(pointerhead)//定义输入集合函数{pointerp;chartmp;scanf("%c",&tmp);while(tmp!=' '){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(" ");}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("(输入数据,按回车键结束,第一个集合大于第二个集合) ");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： ");readdata(head1);//调用输入集合函数printf("请输入集合2： ");readdata(head2);//调用输入集合函数A:printf("1.并集2.交集3.差集4.结束x.重新运算 ");do{学习好帮手 ......printf("请选择序号 ");scanf("%d",&x);switch(x){case1:printf("两集合的并是 ");and(head1,head2,head3);//调用并集函数pop(head3);head3->next=NULL;break;case2:printf("两集合的交是 ");or(head1,head2,head3);//调用交集函数pop(head3);head3->next=NULL;break;case3:printf("两集合的差是 ");differ(head1,head2,head3);//调用差集函数pop(head3);head3->next=NULL;break;case4:break;default:gotoA;}}while(x!=4);}学习好帮手 ......3.3菜单设计（基于顺序表）图3.2主界面3.4源代码设计（基于顺序表）#include#include#include#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("顺序表已满，无法插入其他元素！ ");return0;system("pause");}elseif(i<0&&i>L->size){printf("参数i不合法！ ");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("顺序表已无数据可删！ ");return0;system("pause");}elseif(i<0&&i>L->size-1){printf("参数i不合法！ ");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不合法！ ");return0;}else{*x=L.list[i];return1;}}voidListFind(SeqListL,DataTypex)//顺序表查找元素函数{inti;for(i=0;ilist[i+1];j=i;while(j>-1&&templist[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