数据结构课程设计_集合运算.docx

1、.电子与信息工程学院数据结构实验报告实验名称 :集合的运算实验类型：设计(验 证、设计、创新)班级:2013 级电信三班学号:201307014327：陆杰实验时间：2015年6月16日.指导教师：余先伦成绩：目录一课程设计目的和要求二问题描述及分析三算法思想和程序的实现概述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 字

2、母集合差运算6.8 字母和数据集合并运算6.9 字母和数据集合交运算6.10 字母和数据集合差运算6.11 退出程序七 源代码八 总结九 参考文献一课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力， 提高软件设计能力。 在实践中培养独立分析问题和解决问题的作风和能力。.要求：熟练运用C+ 语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设

3、计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二问题描述及分析问题描述 ：本课程设计中， 集合的元素可以是字母 a,b,z,也可以是整数 0,1,9，集合的大小集合输入的形式为一个以“回车符 ”为结束标志的字符， 允许出现重复字符或非法字符， 程序应能自动滤去。 输出的运算结果字符串中将不含重复字符或非法字符。问题描述：有两个集合 A、B，要求它的交集、并集和差集C。用两个链表p、 q 存储集合 A、B，用链表 r 存储集合 C。描述该问题的存储结构，算法，并通过编写程序来实现。问题分析：1. 定义一个链表来存储集合元素；2. 链表 L 包括数据域和指针域，数据域中存储集合

4、元素，指针域中存储下一.个集合元素的位置；3. 创建若干个基本函数， 通过函数调用对链表进行操作， 实现集合的交、 并、差运算。三算法思想和程序的实现概述3.1 算法思想定义一个链表，链表有整型数据和一个指向链表的指针，程序包含定义一个新链表的函数，集合并函数，集合交函数，集合差函数。求两集合交集并集差集从两集合的头结点开始， 比较两集合元素大小， 进行对应的操作， 直到读取到两集合的末尾元素。主程序先定义三个集合，创建集合A 读入 A 数据，创建集合 B 读入 B 数据，然后输出集合 A,B 的元素，求出两集合并集并输出。 求两集合的交集和差集的运算与求并集的步骤类似，只需按提示输入即可。3

5、.2 程序的实现概述（ 1）输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为整数。（ 2）输出的形式从屏幕输出，显示用户输入集合的元素，并显示进行运算后的值。（ 3）存储结构在这次设计中开始我是采用链式存储结构，使得集合的算法定义十分简洁。.（ 4）算法实现定义链表，创建链表，输出链表。利用链表的来存储集合。利用三个函数分别实现课程要求程序实现的求并、求交和差三中运算。现分述如下：A）并运算函数该函数采取了用新集合存储两集合并后的新集合，利用一个for 循环来消除新集合中相同的元素，使其在屏幕上只显示一次。B）交运算函数该函数用于实现集合的并运算，利用for 嵌套实现两链表中数据的比

6、较，输出两链表中相同的元素。C）差函数该函数用于实现集合的差运算，利用链表中的数据域进行判断。输出不同于被减集合中不存在的元素。四程序流程图流程图：开始定义链表创建链表.输入数据求两集合的并集输入数据求两集合的交集输入数据求两集合的差集五程序的实现改程序的实现步骤是定义链表，创建链表，输出链表。利用链表的来存储集合。利用三个函数分别实现课程要求程序实现的求并、求交和差三中运算。 现分述如下：5.1 主函数void bangzhu()printf(nttt*);.printf(nttt*求集合的交并差*);printf(nttt*n);void main()/* 主函数*/struct set

7、*p,*q,*r;int m,n,node;bangzhu();for(;)doprintf( 请输入您要选择操作的代码:n);.printf(1 ：求两集合的并ABn);printf(2 ：求两集合的交ABn);printf(3 ：求两集合的差A-Bn);printf(0 ：退出该程序 n);scanf(%d,&node); while(node3);if(node=0) exit(1);printf(ttt/* 请输入集合 A 中元素的个数： */n);scanf(%d,&m);createlist_p(p,m);/* 调用链表生成函数生成A 链表*/printf(ttt/*请输入集合 B

8、 中元素的个数： */n);.scanf(%d,&n);/* 调用链表生成函数生成B 链表 */createlist_p(q,n);printf( 集合 A 中元素为 :);printlist_p(p);/*调用集合输出函数输出集合A */printf( 集合 B 中元素为 :);printlist_p(q);/*调用集合输出函数输出集合A */while(node3);switch(node)case 1: Addset( p,q,r);printf(A B:n);printlist_p(r);break;case 2: Subset( p,q,r);printf(AB:n);printli

9、st_p(r);break;case 3: Intset(p,q,r); printf(A-B:n);printlist_p(r);break;.printf(n);5.2 链表的生成void createlist_p(struct set *&p,int n)int i;struct set *L;p=(struct set *)malloc(sizeof(set);/* 申请结点 p */p-next=NULL;/* 定义 p 的 next 指针为空*/for(i=n;i0;i-)L=(struct set *)malloc(sizeof(set);/* 申请结点 L*/.printf(

10、请输入该集合中第 %d个整数元素 :,n-i+1);scanf(%s,&L-coef);L-next=p-next;p-next=L;/ 生成新链表用于存放两集合中的元素5.3 集合的输出void printlist_p(struct set *&p)struct set *L;int i;L=p-next;if(!L) printf( 该表为空 !n);.while(L!=NULL)printf(%c ,L-coef);L=L-next;i+;printf(n);/ 打印输入的两集合中的元素5.4 并运算函数void Addset(struct set *&p,struct set *&q,

11、struct set *&r)struct set *k,*m,*n;r=(struct set *)malloc(sizeof(set);/* 申请结点 r */r-next=NULL;/*定义 r 的 next 指针为空*/.k=p-next;/* k 指向 p 的下一个结点*/for(;k;)m=(struct set *)malloc(sizeof(set);/* 申请结点 m */m-next=r-next;r-next=m;m-coef=k-coef;k=k-next;/* 把第一个集合中的元素放在新集合中*/k=q-next;m=(struct set *)malloc(size

12、of(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=(struct set *)malloc(sizeof(set);m-next=r-next;.r-next=m;m-coef=k-coef;k=k-next;/*对第二个集合中的元素进行分析*/*求 AB */该函数采取了用新集合存储两集合并后的新集合，利用一个for

13、 循环来消除新集合中相同的元素，是其在屏幕上只显示一次。5.5 交运算函数void Subset(struct set *&p,struct set *&q,struct set *&r)struct set *k,*m,*n;r=(struct set *)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=(struct s

14、et *)malloc(sizeof(set);k-next=r-next;.r-next=k;k-coef=m-coef;n=n-next;/* 求 AB */该函数用于实现集合的并运算， 利用 for 嵌套实现两链表中数据的比较，输出两链表中相同的元素。5.6 差函数void Intset(struct set *&p,struct set *&q,struct set *&r)struct set *k,*m,*n;.r=(struct set *)malloc(sizeof(set);r-next=NULL;m=p-next;for(;m;)n=q-next;for(;(m-coef!

15、=n-coef)&n-next;)n=n-next;if(!n-next&(m-coef!=n-coef) /*比较链表 p 与 q ,找出 p 中不同于 q的元素存入链表 r 中 */.k=(struct set *)malloc(sizeof(set);k-next=r-next;r-next=k;k-coef=m-coef;m=m-next;/* 求 A-B */该函数用于实现集合的差运算，利用链表中的数据域进行判断。输出不同于被减集合中不存在的元素。六运行结果分析.6.1 程序主界面图 6.1 程序主界面6.2 整数集合并运算图 6.2 整数集合并运算6.3 整数集合交运算.图 6.3

16、 整数集合交运算6.4 整数集合差运算图 6.4 整数集合差运算6.5 字母集合并运算.图 6.5 字母集合并运算6.6 字母集合交运算图 6.6 字母集合交运算.6.7 字母集合差运算图 6.7 字母集合差运算6.8 字母和数据集合并运算.图 6.8 字母和数据集合并运算6.9 字母和数据集合交运算图 6.9 字母和数据集合交运算6.10 字母和数据集合差运算图 6.10 字母和数据集合差运算.6.11 退出程序图 6.11 退出程七源代码#include#include#includestruct setchar coef;.struct set *next; / 线性表的单链表存储结构v

17、oid createlist_p(struct set *&p,int n)int i;struct set *L;p=(struct set *)malloc(sizeof(set);p-next=NULL; / 建立一个带头结点的单链表for(i=n;i0;i-)L=(struct set *)malloc(sizeof(set); / 生成新节点printf( 请输入该集合中第 %d个整数元素 :,n-i+1);scanf(%s,&L-coef);L-next=p-next;p-next=L; / 插入到表头void printlist_p(struct set *&p).struct

18、set *L;int i;L=p-next;if(!L) printf( 该表为空 !n);while(L!=NULL)printf(%c ,L-coef);L=L-next;i+;printf(n);void Addset(struct set *&p,struct set *&q,struct set *&r)struct set *k,*m,*n;r=(struct set *)malloc(sizeof(set);r-next=NULL;k=p-next;for(;k;).m=(struct set *)malloc(sizeof(set);m-next=r-next;r-next=m

19、;m-coef=k-coef;k=k-next; /r中存放 pk=q-next;m=(struct set *)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=(struct set *)malloc(sizeof(set);m-next=r-next;r-next=m;m-coef=k-coef;k=k-next;/ 求 ABvoid Su

20、bset(struct set *&p,struct set *&q,struct set *&r)struct set *k,*m,*n;r=(struct set *)malloc(sizeof(set);r-next=NULL;n=q-next;for(;n;)m=p-next;for(;(m-coef!=n-coef)&m-next;).m=m-next;if(m-coef=n-coef)k=(struct set *)malloc(sizeof(set);k-next=r-next;r-next=k;k-coef=m-coef;n=n-next;/ 求 ABvoid Intset(s

21、truct set *&p,struct set *&q,struct set *&r)struct set *k,*m,*n;r=(struct set *)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)k=(struct set *)malloc(sizeof(set);k-next=r-next;r-next=k;k-coef=m-coef;m=m-next;/ 求 A-Bvoid bangzhu()printf(nttt*);printf(nttt*求集合的交并差*);printf(nttt*n);void main().struct set *p,*q,*r;int m,n,node;bangzhu();for(;)doprintf( 请输入您要选择操作的代码:n);printf(1 ：求两集合的并ABn);printf(2 ：求两集合的交ABn);printf(3 ：求两集合的差A-Bn);printf(0 ：退出该程序 n);scanf(%d,&node); while(node3);if(node=0) exit(1);printf(ttt/*请输入集