数据结构课程设计题 目 集合运算 学生姓名 孟茹 指导教师 秦飞 学 院 管理科学与工程学院 专业班级 息 121 班 完成时间 2014.6 1目录第一章 课程设计目的 .2第二章 课程设计内容和要求 .3第三章 课程设计分析 .4第四章 算法（数据结构）描述 .5第五章 源代码（源代码必须给注释） .8第六章 运行结果分析 .8第七章 结束语 .13第八章 参考文献 .132第一章 课程设计目的本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握数据结构中的各方面知识，还要求实习者具备一定的 C 语言基础和编程能力。具体说来，这次课程设计主要有以下几个方面的目的。1.会定义单链表得顺序存储结构2.熟悉 C+程序的基本结构，掌握程序的基本结构，掌握程序中的用户头文件，实现文件和主文件之间的相互关系及各自作用。3.熟悉对单链表的一些基本操作和具体的函数定义4.掌握使用单链表来表示集合，完成集合的合并，求交集等操作。5.熟悉 C+操作环境的使用以及多文件程序的输入，编辑，调试和运行的全过程。3第二章 课程设计内容和要求2.1 课程设计内容题目：集合运算功能：使用链表来表示集合，完成集合的合并，求交集等操作。主要包含以下内容：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求； 3进一步要求：2.2 课程设计要求1.界面友好，函数功能要划分好2.总体设计应画一流程图3.程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。2.2 运行环境该程序的运行环境为 Windows xp 系统，Microsoft Visual C+6.0 版本。4第三章 课程设计分析3.1 集合的存储本课题要求采用单链表的存储结构。分别用两个带头结点的单链表存储集合 A 和 B。在单链表中，包括数据域和指针域，数据域中存储集合元素，指针域中存储下一个集合元素的位置。所以一开始必须先定义单链表的结点类型，并对单链表进行初始化，然后根据所输入的相关信息，建立集合的单链表。本课程设计中，链表长度不能超过 100，集合输入的形式为一个以“ 回车符”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤。输出的运算结果字符串中将不含重复字符或非法字符。3.2 集合交集并集的实现3.2.1 求集合 A 和 B 的交集A 交 B 就是 A 和 B 中都存在的元素，方法是删除单链表 A 中所有没有在B 中出现的元素。具体过程应为：定义两个指针变量 Linklist pre 和 Linklist p。定义一个和集合中元素同类型的数据即 DataType x。一开始 pre 指向 A 的头结点，p 指向第一个链表结点。建立一个 while（）循环，以指针 p 所指对象不为空为控制条件，将 P 所指向的集合元素赋值给 x。然后利用查找函数查找 B 中值为 x 的元素，若查找成功，则保留指针 p 所指向的元素，并将 p 结点赋值给 pre，将 p 的 next赋值给 p。若查找失败，则将 p 的 next 赋值给 pre 的 next，然后释放 p 结点，将 pre 的 next 赋值给 p，这样就可以完成求集合 A 和 B 的交集了。3.2.2 求集合 A 和 B 的并集A 并 B 就是 A 或 B 中存在的元素，方法是将 B 中所有不在单链表 A 中的元素都加入到 A 中。具体过程应为：定义一个和集合中元素同类型的数据即 DataType x。定义一个指针变量 linklist p，初始 p 指向 B 的第一个结点。建立一个 while（）循环以指针 p 所指对象不为空为控制条件，将 p 所指向的几何元素赋值给 x。利用查找函数查找 A 中值为 x 的元素，若查找成功，将 p 的 next 赋值给 p。若查找失败，利用插如函数将 B 中有而集合 A 中没有的元素加入到集合 A 中，这样就可以完成秋集合 A 和 B 的并集了。5第四章 算法（数据结构）描述4.1 集合的存储结构的建立。4.1.1 定义单链表的结点类型typedef struct node DataType data; /*每个数据元素的信息*/struct node *next; /*存放后继元素的地址*/LNode,*Linklist;4.1.2 创建集合的单链表需创建一个所有结点都为空的单链表。Linklist Creat_Linklist(void)/*创建空单链表，入口数参无；返回值：单链表的头指针，0 代表创建失败，非零代表创建成功*/Linklist H;H=(Linklist)malloc(sizeof(LNode);if (H)H-next=NULL;return H;4.1.3 建立并输出图的邻接表首先必须输入集合的相关信息，即集合的各个元素。为了保证集合输出的正确性，要将集合按顺序存放在单链表中。即集合中的第一个元素存放在单链表的第一个结点，以下是集合输入输出的相关代码如下：void readdata(Linklist head)/定义输入集合函数Linklist p,q;q=head;char tmp;scanf(%c,while(tmp!=n)p=(Linklist)malloc(sizeof(LNode);p-data=tmp;p-next=q-next;q-next=p;6q=p;scanf(%c,void pop(Linklist head)/定义输出集合函数Linklist p;p=head-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);4.2 求集合的交集和并集4.2.1 求 ABAB 就是 A 和 B 中都存在的元素，方法是删除单链表 A 中所有没有在 B中出现的元素。具体过程应为：定义两个指针变量 Linklist pre 和 Linklist p。定义一个和集合中元素同类型的数据即 DataType x。一开始 pre 指向 A 的头结点，p 指向第一个链表结点。建立一个 while（）循环，以指针 p 所指对象不为空为控制条件，将 P 所指向的集合元素赋值给 x。然后利用查找函数查找 B 中值为 x 的元素，若查找成功，则保留指针 p 所指向的元素，并将 p 结点赋值给 pre，将 p 的 next赋值给 p。若查找失败，则将 p 的 next 赋值给 pre 的 next，然后释放 p 结点，将 pre 的 next 赋值给 p，这样就可以完成求集合 A 和 B 的交集了。求 AB 的具体代码如下：void Inter_sec(Linklist A, Linklist B)/*求集合 A 和 B 的交集，入口参数：指向集合 A 和 B 的指针，返回值：无*/DataType x;Linklist pre,p;pre=A;p=pre-next; /*刚开始 pre 指向头结点，p 指向第一个链表接点*/while(p)x=p-data;if(!Locate_Linklist_Value (B,x) /*集合 B 中没有 x*/pre-next=p-next;7free(p); /*删除该结点，考察下一节点*/p=pre-next;elsepre=p;p=p-next; /*考察下一结点 */4.2.2 求 ABA 并 B 就是 A 或 B 中存在的元素，方法是将 B 中所有不在单链表 A 中的元素都加入到 A 中。具体过程应为：定义一个和集合中元素同类型的数据即 DataType x。定义一个指针变量 linklist p，初始 p 指向 B 的第一个结点。建立一个 while（）循环以指针 p 所指对象不为空为控制条件，将 p 所指向的几何元素赋值给 x。利用查找函数查找 A 中值为 x 的元素，若查找成功，将 p 的 next 赋值给 p。若查找失败，利用插入函数将集合 B 中有而集合 A 中没有的元素加入到集合 A 中，这样就可以完成求集合 A 和 B 的并集了。具体代码如下：void Merge_sec(Linklist A, Linklist B)/*求集合 A 和 B 的并集，入口参数：指向集合 A 和 B 的指针，返回值：无*/DataType x;Linklist p;p=B-next; /*初始 P 指向第一结点*/while(p)x=p-data;if(!Locate_Linklist_Value (A,x) /*集合 A 中没有 x*/Insert_Linklist(A,1,x); /*将集合 B 中有而集合 A 中没有的元素加入到集合A 中*/p=p-next;8第五章 源代码（源代码必须给注释）求集合 A 和集合 B 的交集合#include#includetypedef struct node/定义结构体类型指针char data; /*每个数据元素的信息*/struct node*next; /*存放后继元素的地址*/LNode,*Linklist;void readdata(Linklist head)/定义输入集合函数Linklist p,q;q=head;char tmp;scanf(%c,while(tmp!=n)p=(Linklist)malloc(sizeof(LNode);p-data=tmp;p-next=q-next;q-next=p;q=p;scanf(%c,void pop(Linklist head)/定义输出集合函数Linklist p;p=head-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);Linklist Locate_Linklist_Value(Linklist H,char x)Linklist p=H-next;9while(p&p-data!=x)p=p-next;return(p);void Inter_sec(Linklist A, Linklist B)/*求集合 A 和 B 的交集，入口参数：指向集合 A 和 B