数据结构课程设计集合运算完整.docx
《数据结构课程设计集合运算完整.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计集合运算完整.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构课程设计集合运算完整
电子与信息工程学院数据结构
实验报告
实验名称:
集合的运算
实验类型：
设计（验证、设计、创新）
班级:
2013级电信三班
学号:
201307014327姓名：
陆杰
实验时间：
2015年6月16日
指导教师：
余先伦成绩：
八总结
九参考文献
一课程设计目的和要求
目的：
深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。
在实践中培养独立分析问题和解决问题的作风和能力。
要求：
熟练运用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主函数
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（;;）
{
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）
{
case1:
Addset（p,q,r）;printf（"A∪B:
\n"）;printlist_p（r）;break;
case2:
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;i>0;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）
{
structset*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;
}/*把第一个集合中的元素放在新集合中*/
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循环来消除新集合中相同的元素，是其在屏幕上只显示一次。
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;
}
}/*求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;
}
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
#include
#include
structset{
charcoef;
structset*next;
};//线性表的单链表存储结构
voidcreatelist_p（structset*&p,intn）
{
inti;
structset*L;
p=（structset*）malloc（sizeof（set））;
p->next=NULL;//建立一个带头结点的单链表
for（i=n;i>0;i--）
{
L=（structset*）malloc（sizeof（set））;//生成新节点
printf（"请输入该集合中第%d个整数元素:
",n-i+1）;
scanf（"%s",&L->coef）;
L->next=p->next;
p->next=L;//插入到表头
}
}
voidprintlist_p（structset*&p）
{
structset*L;
inti;
L=p->next;
if（!
L）printf（"该表为空!
\n"）;
while（L!
=NULL）
{
printf（"%c",L->coef）;
L=L->next;
i++;
}
printf（"\n"）;
}
voidAddset（structset*&p,structset*&q,structset*&r）
{
structset*k,*m,*n;
r=（structset*）malloc（sizeof（set））;
r->next=NULL;
k=p->next;
for（;k;）
{
m=（structset*）malloc（sizeof（set））;
m->next=r->next;
r->next=m;
m->coef=k->coef;
k=k->next;//r中存放p
}
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
voidSubset（structset*&p,structset*&q,structset*&r）
{
structset*k,*m,*n;
r=（structset*）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=（structset*）malloc（sizeof（set））;
k->next=r->next;
r->next=k;
k->coef=m->coef;
}
n=n->next;
}
}//求A∩B
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））
{
k=（structset*）malloc（sizeof（set））;
k->next=r->next;
r->next=k;
k->coef=m->coef;
}
m=m->next;
}
}//求A-B
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（;;）
{
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）
{
case1:
Addset（p,q,r）;printf（"A∪B:
\n"）;printlist_p（r）;break;
case2:
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"）;
}
}
八总结
通过这次数据结构的课程设计，加深对所学知识理解的同时也将所学知识系统化。
经过这几天的思考发现，数据结构自己学习的有多么的糟糕和肤浅，最初的程序之中有许多的漏洞和不足，调试之中不断出现错误，自己无法解决。
向老师同学请教之后才得以解决，我深刻的意识到我与其他同学的差距，所幸通过这次课程设计能够是自己有所提高
本程序经过的反复修改和调试，发现错误，解决错误，才能在正常运行，有正确的结果。
兴奋之余也深深体会到编程的工作人员的不易，希望自己能将现在的收获应用到以后的工作中。
九参考文献
1.c语言程序设计清华大学出版社
2.数据结构严蔚敏版清华大学出版社
3.c++面向对象程序设计清华大学出版社
4.c++语言课程设计清华大学出版社
5.上网查阅的有关停集合的运算的资料
升级会员 