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

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

2、整数集合差运算6.5 字母集合并运算6.6 字母集合交运算6.7 字母集合差运算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. 链

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

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

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

7、"nttt*n"); void main() /* 主函数 */ struct set *p,*q,*r; int m,n,node; bangzhu(); for(;) do printf("请输入您要选择操作的代码:n"); printf("1：求两集合的并ABn"); printf("2：求两集合的交ABn"); printf("3：求两集合的差A-Bn"); printf("0：退出该程序n"); scanf("%d",&node); wh

8、ile(node<0|node>3); if(node=0) exit(1); printf("ttt/*请输入集合A中元素的个数：*/n"); scanf("%d",&m); createlist_p(p,m); /* 调用链表生成函数生成A链表 */ printf("ttt/*请输入集合B中元素的个数：*/n"); scanf("%d",&n); /* 调用链表生成函数生成B链表 */ createlist_p(q,n); printf("集合A中元素为:");

9、printlist_p(p); /* 调用集合输出函数输出集合A */ printf("集合B中元素为:"); printlist_p(q); /* 调用集合输出函数输出集合A */while(node<0|node>3); switch(node) case 1: Addset( p,q,r);printf("AB:n");printlist_p(r);break; case 2: Subset( p,q,r);printf("AB:n");printlist_p(r);break; case 3: Intset(p,q

10、,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;i>0;i-) L=(struct set *)malloc(sizeof(set); /* 申请结点L*/

11、 printf("请输入该集合中第%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->

12、coef); L=L->next; i+; printf("n"); /打印输入的两集合中的元素 5.4 并运算函数void Addset(struct set *&p,struct set *&q,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

13、*)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(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->c

14、oef)&&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循环来消除新集合中相同的元

15、素，是其在屏幕上只显示一次。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

16、->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; /* 求AB */该函数用于实现集合的并运算，利用for嵌套实现两链表中数据的比较，输出两链表中相同的元素。5.6 差函数void Intset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r

17、=(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) /* 比较链表p与q ,找出p中不同于q的元素存入链表r中 */ k=(struct set *)malloc(sizeof(set); k->next=r->next; r-&g

18、t;next=k; k->coef=m->coef; m=m->next; /* 求A-B */ 该函数用于实现集合的差运算，利用链表中的数据域进行判断。输出不同于被减集合中不存在的元素。六 运行结果分析6.1 程序主界面图 6.1 程序主界面6.2整数集合并运算 图6.2 整数集合并运算6.3 整数集合交运算 图 6.3 整数集合交运算6.4 整数集合差运算图6.4 整数集合差运算6.5 字母集合并运算图6.5 字母集合并运算6.6 字母集合交运算图6.6 字母集合交运算6.7 字母集合差运算图6.7 字母集合差运算6.8 字母和数据集合并运算图6.8 字母和数据集合并运算

19、6.9 字母和数据集合交运算图6.9 字母和数据集合交运算6.10 字母和数据集合差运算图6.10 字母和数据集合差运算6.11 退出程序 图6.11退出程七 源代码#include<stdio.h> #include<malloc.h> #include<stdlib.h> struct set char coef; struct set *next; ; /线性表的单链表存储结构void createlist_p(struct set *&p,int n) int i; struct set *L; p=(struct set *)malloc(

20、sizeof(set); p->next=NULL; /建立一个带头结点的单链表for(i=n;i>0;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 set *L; int i; L=p->n

21、ext; 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

22、=(struct set *)malloc(sizeof(set); m->next=r->next; r->next=m; m->coef=k->coef; k=k->next; /r中存放p k=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)&&

23、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 void Subset(struct set *&p,struct set *&q,struct set *&r) struct set *k,*m,*n; r=(struct set *)m

24、alloc(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; /求AB void Intset(struct s

25、et *&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(s

26、izeof(set); k->next=r->next; r->next=k; k->coef=m->coef; m=m->next; /求A-B void bangzhu() printf("nttt*"); printf("nttt* 求集合的交并差 *"); printf("nttt*n"); void main() struct set *p,*q,*r; int m,n,node; bangzhu(); for(;) do printf("请输入您要选择操作的代码:n"); printf("1：求两集合的并ABn"); printf("2：求两集合的交ABn"); printf("3：求两集合的差A-Bn"); printf("0：退出该程序n"); scanf("%d",&node); while(node<0|node>3); if(node=0) exit(1); pri