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

合肥学院计算机科学与技术系课程设计报告20122013学年第二学期课程 数据结构与算法课程设计名称集合的并、交和差运算学生姓名张文浩 学号1104032028专业班级11网工2班指导教师何立新 华珊珊2013年 6月题目： 集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。【基本要求】(1) 集合的元素限定为小写字母字符 a.z 。(2) 演示程序以用户和计算机的对话方式执行。【测试数据】(1)Set1=magazine，Set2=paper，Set1Set2=aegimnprz，Setl Set2=ae，Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89，Set2=error data，Set1Set2=adeinoprt，Setl Set2=aeort，Set1-Set2=inp。【实现提示】以有序链表表示集合。【选作内容】(1) 集合的元素判定和子集判定运算。(2) 求集合的补集。(3) 集合的混合运算表达式求值。(4) 集合的元素类型推广到其他类型 ， 甚至任意类型。一、 实验内容实验题目：编制一个演示集合的并、交和差运算的程序。需求分析：1、 本演示程序中，集合的元素限定为小写字母字符“a”z”。集合输入的形式为一个以“回车符“为结束标志的字符串，串中字符顺序不限。2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。3、 程序执行的命令包括：1） 构造集合1；2）构造在集合2；3）求并集；4）求交集；5)求差集；6）返回；7）结束。“构造集合1”和“构造集合2”时，需以字符的形式键入集合元素。二、数据结构设计为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。1、有序表的抽象数据类型定义为：readdata(pointer head)初始条件：head是以head为头节点的空链表。操作结果：生成以head为头节点的非空链表。pop(pointer head)初始条件：head是以head为头节点的非空链表。操作结果：将以head为头节点的链表中数据逐个输出。2、集合的抽象数据类型定义为：and(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的并集构成的集合head3。or(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的交集构成的集合head3。differ(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的差集构成的集合head3。3、本程序抱含四个模块：1） 节点结构单元模块定义有序表的节点结构；2） 有序表单元模块实现有序表的抽象数据类型；3） 集合单元模块实现集合获得抽象数据类型；4）主程序模块：Void main（）初始化；do接受命令；处理命令；while（“命令”!=“退出”）；三、算法设计#include#includetypedef struct LNode/定义结构体类型指针char data;struct LNode*next;*pointer;void readdata(pointer head)/定义输入集合函数pointer p;char tmp;scanf(%c,&tmp);while(tmp!=n)p=(pointer)malloc(sizeof(struct LNode);p-data=tmp;p-next=head-next;head-next=p;scanf(%c,&tmp);void pop(pointer head)/定义输出集合函数pointer p;p=head-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);void and(pointer head1,pointer head2,pointer head3)/定义集合的并集函数pointer p1,p2,p3;p1=head1-next;while(p1!=NULL) p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;p2=head2-next;while(p2!=NULL)p1=head1-next;while(p1!=NULL)&(p1-data!=p2-data) p1=p1-next;if (p1=NULL)p3=(pointer)malloc(sizeof(struct LNode);p3-data=p2-data;p3-next=head3-next;head3-next=p3;p2=p2-next;void or(pointer head1,pointer head2,pointer head3)/定义集合的交集函数pointer p1,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(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;void differ(pointer head1,pointer head2,pointer head3)/定义集合的差集函数pointer p1,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(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;void main()/主函数int x; printf(输入数据,按回车键结束,第一个集合大于第二个集合)n);pointer head1,head2,head3;head1=(pointer)malloc(sizeof(struct LNode);head1-next=NULL;head2=(pointer)malloc(sizeof(struct LNode);head2-next=NULL;head3=(pointer)malloc(sizeof(struct LNode);head3-next=NULL;printf(请输入集合1：n);readdata(head1);/调用输入集合函数printf(请输入集合2：n);readdata(head2);/调用输入集合函数A:printf(1.并集 2.交集 3.差集 4.结束 x.重新运算n); doprintf(请选择序号n);scanf(%d,&x);switch(x)case 1:printf(两集合的并是n);and(head1,head2,head3);/调用并集函数pop(head3);head3-next=NULL;break;case 2:printf(两集合的交是n);or(head1,head2,head3);/调用交集函数pop(head3);head3-next=NULL;break;case 3: printf(两集合的差是n);differ(head1,head2,head3);/调用差集函数pop(head3);head3-next=NULL;break; case 4:break;default:goto A;while(x!=4);四、测试数据及程序运行情况 运行时提示输入：输入集合1：asd输入集合2：asf根据提示输入运算类型：1.并集 2.交集 3.差集 4.结束 x.重新运算 输入1，输出”fasd”输入2，输出”as”输入3，输出”d”输入4，输出”press any key to continue”(结束)输入其他数，输出” 1.并集 2.交集 3.差集 4.结束 x.重新运算”(重新选择运算类型)下面是运行时的界面(附图):五、参考资料1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 陈朔