数据结构课程设计-集合运算(完整)

集合运算1电子与信息工程学院数据结构实验报告实验名称:集合的运算实验类型：设计(验证、设计、创新)班级:2013级电信三班学号:201307014327姓名：陆杰实验时间：2015年6月16日指导教师：余先伦成绩：集合运算2目录一课程设计目的和要求二问题描述及分析三算法思想和程序的实现概述3.1算法思想3.2程序的实现概述四程序流程图流程图五程序的实现5.1主函数5.2链表的生成5.3集合的输出5.4并运算函数5.5交运算函数5.6差函数六运行结果分析6.1程序主界面6.2整数集合并运算6.3整数集合交运算6.4整数集合差运算6.5字母集合并运算6.6字母集合交运算6.7字母集合差运算6.8字母和数据集合并运算6.9字母和数据集合交运算6.10字母和数据集合差运算6.11退出程序七源代码八总结九参考文献集合运算3一课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求：熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二问题描述及分析问题描述：本课程设计中，集合的元素可以是字母[a,b,…z],也可以是整数[0,1,…9]，集合的大小集合输入的形式为一个以“回车符”为结束标志的字符，允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。问题描述：有两个集合A、B，要求它的交集、并集和差集C。用两个链表p、q存储集合A、B，用链表r存储集合C。描述该问题的存储结构，算法，并通过编写程序来实现。问题分析：集合运算41.定义一个链表来存储集合元素；2.链表L包括数据域和指针域，数据域中存储集合元素，指针域中存储下一个集合元素的位置；3.创建若干个基本函数，通过函数调用对链表进行操作，实现集合的交、并、差运算。三算法思想和程序的实现概述3.1算法思想定义一个链表，链表有整型数据和一个指向链表的指针，程序包含定义一个新链表的函数，集合并函数，集合交函数，集合差函数。求两集合交集并集差集从两集合的头结点开始，比较两集合元素大小，进行对应的操作，直到读取到两集合的末尾元素。主程序先定义三个集合，创建集合A读入A数据，创建集合B读入B数据，然后输出集合A,B的元素，求出两集合并集并输出。求两集合的交集和差集的运算与求并集的步骤类似，只需按提示输入即可。3.2程序的实现概述（1）输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为整数。（2）输出的形式从屏幕输出，显示用户输入集合的元素，并显示进行运算后的值。（3）存储结构在这次设计中开始我是采用链式存储结构，使得集合的算法定义十分简洁。（4）算法实现定义链表，创建链表，输出链表。利用链表的来存储集合。利用三个函数分别实现课程要求程序实现的求并、求交和差三中运算。现分述如下：A）并运算函数集合运算5该函数采取了用新集合存储两集合并后的新集合，利用一个for循环来消除新集合中相同的元素，使其在屏幕上只显示一次。B）交运算函数该函数用于实现集合的并运算，利用for嵌套实现两链表中数据的比较，输出两链表中相同的元素。C）差函数该函数用于实现集合的差运算，利用链表中的数据域进行判断。输出不同于被减集合中不存在的元素。四程序流程图流程图：开始创建链表定义链表求两集合的并集求两集合的交集输入数据输入数据集合运算6五程序的实现改程序的实现步骤是定义链表，创建链表，输出链表。利用链表的来存储集合。利用三个函数分别实现课程要求程序实现的求并、求交和差三中运算。现分述如下：5.1主函数voidbangzhu(){printf(\n\t\t\t***********************************);printf(\n\t\t\t*求集合的交并差*);printf(\n\t\t\t*********************************\n);}voidmain()/*主函数*/{structset*p,*q,*r;intm,n,node;bangzhu();for(;;)输入数据求两集合的差集集合运算7{do{printf(请输入您要选择操作的代码:\n);printf(1：求两集合的并A∪B\n);printf(2：求两集合的交A∩B\n);printf(3：求两集合的差A-B\n);printf(0：退出该程序\n);scanf(%d,&node);}while(node0||node3);if(node==0)exit(1);printf(\t\t\t/*请输入集合A中元素的个数：*/\n);scanf(%d,&m);createlist_p(p,m);/*调用链表生成函数生成A链表*/printf(\t\t\t/*请输入集合B中元素的个数：*/\n);scanf(%d,&n);/*调用链表生成函数生成B链表*/createlist_p(q,n);printf(集合A中元素为:);printlist_p(p);/*调用集合输出函数输出集合A*/printf(集合B中元素为:);printlist_p(q);/*调用集合输出函数输出集合A*/while(node0||node3);switch(node){case1:Addset(p,q,r);printf(A∪B:\n);printlist_p(r);break;集合运算8case2:Subset(p,q,r);printf(A∩B:\n);printlist_p(r);break;case3:Intset(p,q,r);printf(A-B:\n);printlist_p(r);break;}printf(\n);}}5.2链表的生成voidcreatelist_p(structset*&p,intn){inti;structset*L;p=(structset*)malloc(sizeof(set));/*申请结点p*/p-next=NULL;/*定义p的next指针为空*/for(i=n;i0;i--){L=(structset*)malloc(sizeof(set));/*申请结点L*/printf(请输入该集合中第%d个整数元素:,n-i+1);scanf(%s,&L-coef);L-next=p-next;p-next=L;}}//生成新链表用于存放两集合中的元素5.3集合的输出voidprintlist_p(structset*&p){集合运算9structset*L;inti;L=p-next;if(!L)printf(该表为空!\n);while(L!=NULL){printf(%c,L-coef);L=L-next;i++;}printf(\n);}//打印输入的两集合中的元素5.4并运算函数voidAddset(structset*&p,structset*&q,structset*&r){structset*k,*m,*n;r=(structset*)malloc(sizeof(set));/*申请结点r*/r-next=NULL;/*定义r的next指针为空*/k=p-next;/*k指向p的下一个结点*/for(;k;){m=(structset*)malloc(sizeof(set));/*申请结点m*/m-next=r-next;r-next=m;m-coef=k-coef;k=k-next;集合运算10}/*把第一个集合中的元素放在新集合中*/k=q-next;m=(structset*)malloc(sizeof(set));m-next=r-next;r-next=m;m-coef=k-coef;k=k-next;for(;k;){for(n=r-next;(k-coef!=n-coef)&&n-next;){n=n-next;}/*与新集合中的元素比较，如果不同则链入链表中*/if((k-coef!=n-coef)&&!(n-next)){m=(structset*)malloc(sizeof(set));m-next=r-next;r-next=m;m-coef=k-coef;}k=k-next;}/*对第二个集合中的元素进行分析*/}/*求A∪B*/该函数采取了用新集合存储两集合并后的新集合，利用一个for循环来集合运算11消除新集合中相同的元素，是其在屏幕上只显示一次。5.5交运算函数voidSubset(structset*&p,structset*&q,structset*&r){structset*k,*m,*n;r=(structset*)malloc(sizeof(set));/*申请结点r*/r-next=NULL;n=q-next;for(;n;)/*比较p和q链表中的元素，相同的元素存入链表r中*/{m=p-next;for(;(m-coef!=n-coef)&&m-next;){m=m-next;}if(m-coef==n-coef){k=(structset*)malloc(sizeof(set));k-next=r-next;r-next=k;k-coef=m-coef;}n=n-next;}集合运算12}/*求A∩B*/该函数用于实现集合的并运算，利用for嵌套实现两链表中数据的比较，输出两链表中相同的元素。5.6差函数voidIntset(structset*&p,structset*&q,structset*&r){structset*k,*m,*n;r=(structset*)malloc(sizeof(set));r-next=NULL;m=p-next;for(;m;){n=q-next;for(;(m-coef!=n-coef)&&n-next;){n=n-next;}if(!n-next&&(m-coef!=n-coef))/*比较链表p与q,找出p中不同于q的元素存入链表r中*/{k=(structset*)malloc(sizeof(set));k-next=r-next;r-next=k;k-coef=m-coef;}集合运算13m=m-next;}}/*求A-B*/该函数用于实现集合的差运算，利用链表中的数据域进行判断。输出不同于被减集合中不存在的元素。六运行结果分析6.1程序主界面图6.1程序主界面集合运算146.2整数集合并运算图6.2整数集合并运算6.3整数集合交运算图6.3整数集合交运算集合运算156.4整数集合差运算图6.4整数集合差运算6.5字母集合并运算图6.5字母集合并运算集合运算166.6字母集合交运算图6.6字母集合交运算6.7字母集合差运算图6.7字母集合差运算集合运算176.8字母和数据集合并运算图6.8字母和数据集合并运算6.9字母和数据集合交运算图6.9字母和数据集合交运算集合运算186.10字母和数据集合差运算图6.10字母和数据集合差运算6.11退出程序集合运算19图6.11退出程七源代码#includestdio.h#includemalloc.h#includestdlib.hstructset{charcoef;structset*next;};//线性表的单链表存储结构voidcreatelist_p(structset*&p,intn){inti;structset*L;p=(structset*)malloc(sizeof(set));p-next=NULL;//建立一个带头结点的