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

电子与信息工程学院数据结构
实 验 报 告

实验名称： 集合得运算
实验类型： 设 计 （验 证、设 计、创 新)
班 级: 2013级电信三班
学 号: 2 姓名： 陆杰
实验时间： 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 字母集合差运算
6、8 字母与数据集合并运算
6、9 字母与数据集合交运算
6、10 字母与数据集合差运算
6、11 退出程序
七 源代码
八 总结
九 参考文献
一 课程设计目得与要求
目得:深入理解数据结构得基本理论,掌握数据存储结构得设计方法，掌握基于数据结构得各种操作得实现方法，训练对基础知识与基本方法得综合运用能力,增强对算法得理解能力,提高软件设计能力。在实践中培养独立分析问题与解决问题得作风与能力。

要求：熟练运用C++语言、基本数据结构与算法得基础知识，独立编制一个具有中等难度得、解决实际应用问题得应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计得全过程,不断地完善程序以提高程序得性能。
二 问题描述及分析
问题描述：
本课程设计中，集合得元素可以就是字母［a,b,…z］,也可以就是整数[0,1，…9］，集合得大小集合输入得形式为一个以“回车符"为结束标志得字符,允许出现重复字符或非法字符,程序应能自动滤去。输出得运算结果字符串中将不含重复字符或非法字符。
问题描述:
有两个集合A、B，要求它得交集、并集与差集C.用两个链表p、q存储集合A、B，用链表r存储集合C.描述该问题得存储结构,算法,并通过编写程序来实现。

问题分析:
1、 定义一个链表来存储集合元素;
2、 链表L包括数据域与指针域,数据域中存储集合元素,指针域中存储下一个集合元素得位置;
3、 创建若干个基本函数，通过函数调用对链表进行操作,实现集合得交、并、差运算。
三 算法思想与程序得实现概述
3、1 算法思想
定义一个链表，链表有整型数据与一个指向链表得指针，程序包含定义一个新链表得函数，集合并函数，集合交函数,集合差函数。求两集合交集并集差集从两集合得头结点开始，比较两集合元素大小,进行对应得操作,直到读取到两集合得末尾元素。主程序先定义三个集合,创建集合A读入A数据，创建集合B读入B数据，然后输出集合A,B得元素,求出两集合并集并输出。求两集合得交集与差集得运算与求并集得步骤类似,只需按提示输入即可。
3、2 程序得实现概述
(1）输入得形式与输入值得范围：
输入就是从键盘输入得,输入得内容为整数。
(2）输出得形式
从屏幕输出，显示用户输入集合得元素,并显示进行运算后得值。
(3)存储结构
在这次设计中开始我就是采用链式存储结构，使得集合得算法定义十分简洁。
（4） 算法实现
定义链表,创建链表，输出链表。利用链表得来存储集合。利用三个函数分别实现课程要求程序实现得求并、求交与差三中运算。现分述如下:
A） 并运算函数
该函数采取了用新集合存储两集合并后得新集合,利用一个for循环来消除新集合中相同得元素,使其在屏幕上只显示一次.
B）交运算函数
该函数用于实现集合得并运算,利用for嵌套实现两链表中数据得比较，输出两链表中相同得元素.
C）差函数
该函数用于实现集合得差运算,利用链表中得数据域进行判断。输出不同于被减集合中不存在得元素.
四 程序流程图
流程图：
开始

定义链表

创建链表

输入数据

求两集合得并集

输入数据

求两集合得交集

输入数据

求两集合得差集

五 程序得实现
改程序得实现步骤就是定义链表,创建链表,输出链表。利用链表得来存储集合。利用三个函数分别实现课程要求程序实现得求并、求交与差三中运算。现分述如下：
5、1 主函数
void bangzhu（）｛
printf("\n\t\t\t＊*＊＊＊＊＊＊＊*＊＊*＊＊*＊*＊***＊*＊＊**＊*＊＊＊＊*”)；
printf(”\n\t\t\t* 求集合得交并差 ＊"）;
printf（"\n\t\t\t*＊＊＊＊＊*＊＊＊＊＊**＊＊***＊*******＊*＊*＊*\n”);
｝
void main() /＊ 主函数 */
{
struct set *p,*q，*r；
int m，n,node；
bangzhu（);
for（;；)
{
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（node〈0||node>3）；
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(node〈0｜|node>3）;
switch(node)
{
case 1： Addset（ p,q,r)；printf（”A∪B:\n”）；printlist_p(r);break;
case 2： Subset（ p,q,r）；printf("A∩B:\n”）；printlist_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；i>0；i-—）
{
L=(struct set *)malloc（sizeof（set））; /＊ 申请结点L*/
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—〉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 ＊）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—>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;
｝ /* 对第二个集合中得元素进行分析 */
｝ /* 求A∪B ＊/
该函数采取了用新集合存储两集合并后得新集合,利用一个for循环来消除新集合中相同得元素，就是其在屏幕上只显示一次。
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 set *)malloc（sizeof(set））；
k-〉next=r—〉next；
r-〉next=k；
k—〉coef=m->coef;
｝
n=n-〉next；
}
} /＊ 求A∩B */
该函数用于实现集合得并运算，利用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!=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 整数集合交运算
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〈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(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->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;
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）&＆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;
｝
}//求A∪B
void Subset（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；
｝
｝//求A∩B
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!=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—B
void bangzhu(){
printf（"\n\t\t\t*＊＊＊＊*＊＊＊******＊＊＊＊＊*＊＊＊＊*******＊＊*”）;
printf（"\n\t\t\t* 求集合得交并差 *”)；
printf（”\n\t\t\t＊＊********＊＊＊*****＊*＊＊**＊＊＊＊＊＊*＊＊\n”);
}
void main（)
{
struct set ＊p，＊q,*r;
int m，n，node；
bangzhu（）;
for(;；）
｛
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（node〈0｜|node〉3）；
if（node==0) exit（1）;
printf("\t\t\t/*请输入集合A中元素得个数:*/\n”）;
scanf（”％d"，&m)；
createlist_p(p，m);
printf("\t\t\t/*请输入集合B中元素得个数:＊/\n”）；
scanf(”%d”，&n);
createlist_p（q,n);
printf（"集合A中元素为:"）;
printlist_p(p）；
printf（"集合B中元素为:"）;
printlist_p（q);
while(node<0｜｜node>3）;
switch（node）
｛
case 1： Addset（ p,q,r）；printf("A∪B：\n”)；printlist_p（r);break；
case 2: Subset（ p,q，r)；printf(”A∩B：\n”）;printlist_p(r)；break;
case 3： Intset（p，q,r）； printf（"A—B:\n")；printlist_p(r);break；
｝
printf（"\n”）;
｝
}
八 总结
通过这次数据结构得课程设计,加深对所学知识理解得同时也将所学知识系统化.经过这几天得思考发现，数据结构自己学习得有多么得糟糕与肤浅，最初得程序之中有许多得漏洞与不足，调试之中不断出现错误,自己无法解决。向老师同学请教之后才得以解决，我深刻得意识到我与其她同学得差距，所幸通过这次课程设计能够就是自己有所提高
本程序经过得反复修改与调试，发现错误，解决错误，才能在正常运行，有正确得结果。兴奋之余也深深体会到编程得工作人员得不易，希望自己能将现在得收获应用到以后得工作中。
九 参考文献
1、c语言程序设计 清华大学出版社
2、数据结构 严蔚敏版 清华大学出版社
3、c++面向对象程序设计 清华大学出版社
4、c++语言课程设计 清华大学出版社
5、上网查阅得有关停集合得运算得资料