数据结构课程设计-集合的并、交和差运算

一、课程题目集合的并、交和差运算二、问题描述功能：编制一个能演示执行集合的并、交和差运算的程序。三、基本要求1）集合的元素限定为小写字母字符【‘a’..‘z’】2）演示程序以用户和计算机的对话方式执行。四、测试数据（1）Set1=”magazine”,Set2=’paper”,Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”;(2)Set1=”012oper4a6tion89”,Set2=”errordata”,Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”,Set1-Set2=”inp”.五、算法思想为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。1、有序表的抽象数据类型定义为：input(linklistl)初始条件：l是以l为头节点的空链表。操作结果：生成以l为头节点的非空链表。output(linklistl)初始条件：l是以l为头节点的非空链表。操作结果：将以l为头节点的链表中数据逐个输出。2、集合的抽象数据类型定义为：heji(linklistA,linklistB,linklistC)初始条件：链表A、B、C已存在操作结果：生成一个由A和B的并集构成的集合C。jiaoji(linklistA,linklistB,linklist,C)初始条件：链表A、B、C已存在操作结果：生成一个由A和B的交集构成的集合C。六、模块化分本程序抱含四个模块：1）节点结构单元模块——定义有序表的节点结构；2）有序表单元模块——实现有序表的抽象数据类型；3）集合单元模块——实现集合获得抽象数据类型；4）主程序模块：Voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”!=“退出”）；}七、源程序#includestdio.h#includestring.h#includestdlib.h#includeconio.htypedefstructnode{intdata;structnode*next;}lnode,*linklist;lnode*init_lnode();voidinput(linklistl);voidjiaoji(linklistA,linklistB,linklistC);voidheji(linklistA,linklistB,linklistC);voidoutput(linklistl);voidmain(){lnode*a,*b,*c;a=init_lnode();b=init_lnode();c=init_lnode();printf(求AB集合的交集和并集\n);printf(请输入A集合的元素:);input(a);printf(\n请输入B集合的元素:);input(b);printf(\n输入完成\n);printf(\n按任意键进入主菜单:);getch();do{charmenu[]={\n\n\n-----☆1.交集运算☆---------\n\n---------☆2和集运算☆---------\n\n---------☆3.差集运算☆---------\n\n---------☆0.退出☆---------\n\n};printf(%s,menu);printf(\n请在0-3中选择:);scanf(%d,&sel);switch(sel){case1:printf(AB集合的交集是:);jiaoji(A,B,C);output(C);C-next=NULL;break;case2:printf(AB的合集是:);heji(A,B,C);output(C);C-next=NULL;break;case3:chaji(A,B,C);break;case0:break;}}while(sel!=0);}/*主函数结束*//**********初始化函数***************/lnode*init_lnode(){lnode*l;l=(lnode*)malloc(sizeof(lnode));l-next=NULL;returnl;}/***************录入函数********************/voidinput(linklistl){lnode*s;intx;scanf(%d,&x);while(x!=0){s=(lnode*)malloc(sizeof(lnode));s-data=x;s-next=l-next;l-next=s;scanf(%d,&x);}}/************交集函数*********************/voidjiaoji(linklistA,linklistB,linklistC){lnode*p,*q,*t;p=A-next;while(p!=NULL){q=B-next;while((q!=NULL)&&(q-data!=p-data))q=q-next;if((q!=NULL)&&(q-data==p-data)){t=(lnode*)malloc(sizeof(lnode));t-data=p-data;t-next=C-next;C-next=t;}p=p-next;}}/***********输出函数*****************/voidoutput(linklistl){lnode*s;s=l-next;while(s!=NULL){printf(%5d,s-data);s=s-next;}printf(\n);}/********并集函数*************************/voidheji(linklistA,linklistB,linklistC){lnode*p,*q,*t;p=A-next;while(p!=NULL){t=(lnode*)malloc(sizeof(lnode));t-data=p-data;t-next=C-next;C-next=t;p=p-next;}q=B-next;while(q!=NULL){p=A-next;while((p!=NULL)&&(p-data!=q-data))p=p-next;if(p==NULL){t=(lnode*)malloc(sizeof(lnode));t-data=q-data;t-next=C-next;C-next=t;}q=q-next;}/*********************差集函数****************/voidchaji(linklistA,linklistB,linklistC){lnode*p,*q,*s,*t;p=A-next;printf(A与B的差集是:\n);while(p!=NULL){q=B-next;while((q!=NULL)&&(p-data!=q-data))q=q-next;if(q==NULL){s=(lnode*)malloc(sizeof(lnode));s-data=p-data;s-next=C-next;C-next=s;}p=p-next;}output(C);C-next=NULL;q=B-next;printf(B与A的差集是:\n);while(q!=NULL){p=A-next;while((p!=NULL)&&(p-data!=q-data))p=p-next;if(p==NULL){t=(lnode*)malloc(sizeof(lnode));t-data=q-data;t-next=C-next;C-next=t;}q=q-next;}output(C);}}四、测试数据及程序运行情况程序运行结果:八、心得体会1、由于对集合的三种运算的算法推敲不足，在链表类型及其尾指针的设置时出现错误，导致程序低效。2、刚开始时曾忽略了一些变量参数的标识”&”，使调试程序浪费时间不少。今后应重视确定参数的变量和赋值属性的区分和标识。3、开始时输入集合后，程序只能进行一次运算，后来加入switch语句,成功解决了这一难题。4、该算法并不能排除重复输入相同字符的情况，也不能自动滤去非法字符(如空格、阿拉伯数字等)。5、本程序的模块划分比较合理，且尽可能的将指针的操作封装在节点和链表的两个模块中，致使集合模块的调试比较顺利。6、本实习作业采用数据抽象的程序设计方案，将程序化分为四个层次结构，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可用性，确实得到了一次良好的程序设计训练。