数据结构课程设计集合的多种运算.docx
- 文档编号:3204280
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:12
- 大小:48.05KB
数据结构课程设计集合的多种运算.docx
《数据结构课程设计集合的多种运算.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计集合的多种运算.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构课程设计集合的多种运算
集合的多种运算
一目的
1.通过这次的课程设计,让我们掌握现实复杂问题的分析建模和解决方法;
2.提高利用计算机分析解决综合性实际问题的基本能力;
3.加深我们对线性表和排序等理论知识的理解。
二需求分析
1.本程序中,集合的元素可以是字母也可以是数字。
集合输入的形式为一个以“回车符”为结束标志的字符串,串中的字符顺序不限,且允许出现重复字符或非法字符,程序应能自动滤去。
输出的运算结果字符串中将不含重复字符或非法字符。
2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输人数据(滤去输入中的非法字符)和运算结果显示在其后。
3.程序执行的命令包括:
(1)构造集合1;
(2)构造集合2;
(3)求并集;
(4)求交集;
(5)求差集;
(6)结束。
“构造集合1”和“构造集合2”时,需以字符串的形式键入集合元素。
三概要设计
1.数据结构设计
本实验以单链表作为集合的数据存储结构,定义三个单链表src1、src2和dest:
(1)求并集:
先对表src1和src2进行排序,然后比较表src1和src2,将表src1和src2中的元素挨个插入表dest中;
(2)求交集:
先对表src1和src2进行排序,之后比较表src1、src2,两表中相同的元素逐个插入到表dest中;
(3)求差集:
先对表src1和src2进行排序,之后比较表src1、src2,将表src1中表src2中没有的元素逐个插入到表dest.
2.函数的定义和功能
(1)创建新集合的函数voidCreateSet(Setdest):
以程序定义的一个单链表作为参数,从键盘读入数据作为链表的元素;
(2)打印集合元素的函数voidDisplaySet(Setsrc):
以单链表为参数,使元素逐个输出到屏幕上;
(3)排序函数voidSortSet(Setdest):
对一个单链表进行的排序;
(4)长度函数intLengthOf(Setsrc):
对一个链表的结点数目进行确定;
(5)判断函数intExistElem(Setdest,ElemTypee):
判断元素是否存在此链表当中;
(6)追加函数voidAddElem(Setdest,ElemTypee):
对一个链表的末尾追加元素;
(7)求并函数voidAddSet(Setdest,Setsrc1,Setsrc2):
以三个单链表作为参数,将表src1、src2的元素的并集输出到表dest;
(8)求交函数voidMulSet(Setdest,Setsrc1,Setsrc2):
以三个单链表作为参数,将表src1、src2的元素的交集输出到表dest;
(9)求差函数voidSubSet(Setdest,Setsrc1,Setsrc2):
以三个单链表作为参数,将表src1、src2的元素的差集集输出到表dest;
(10)主函数main():
显示主菜单,分别调用求并、交和差函数来满足相应的功能;
3.模块层次关系
本程序包含4个模块:
(1)主程序模块:
voidmain(){
初始化;
do{
接受命令;
处理命令;
}while(“命令”=“退出”);
}
(2)集合单元模块——实现集合的抽象数据类型;
(3)有序表单元模块——实现有序表的抽象数据类型;
(4)结点结构单元模块——定义有序表的结点结构.
四详细设计
1.链表的创建
根据键盘输入的数据创建链表。
voidCreateSet(Setdest)
{
//创建一个新的集合
ElemTypech;
Setp=dest,n;
for(;;)
{
ch=getchar();
if(ch=='\n')break;
n=(Set)malloc(sizeof(ElemNode));
p->next=n;
n->elem=ch;
n->next=NULL;
p=n;
}
return;
}
2.集合的排序
使用冒泡排序法进行排序,对链表中的元素从前往后两两之间进行比较,取出最大值之后再进行循环,之后依次取出第二大,第三大......直到链表排序完成,具体代码如下:
voidSortSet(Setdest)
{
//对一个集合进行从小到大的排序
inti,j,l,flag;
Setp,q,n;
l=LengthOf(dest);
if(l<2)return;
flag=1;
for(i=l-1;i>0&&flag==1;i--)
{
flag=0;
p=dest;
q=p->next;
n=q->next;
for(j=0;j
{
if(q->elem>n->elem)
{
flag=1;
p->next=n;
q->next=n->next;
n->next=q;
q=p->next;
n=q->next;
}
p=q;
q=n;
n=n->next;
}
}
}
2.集合的并运算
先输入A、B集合的内容和一个空集合,以单链表的形式作为函数voidAddSet()的三个实参,再对A、B集合进行排序,通过比较A、B中的元素求出A、B集合中所有的元素,从前往后将A、B中的所有元素逐个插入到表dest中,具体代码如下:
voidAddSet(Setdest,Setsrc1,Setsrc2)
{
//集合并运算
SortSet(src1);SortSet(src2);
inti=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2);
src1=src1->next;src2=src2->next;
while(i { if(src1->elem<=src2->elem) { i++; if(! ExistElem(dest,src1->elem)) { AddElem(dest,src1->elem); src1=src1->next; } else { src1=src1->next; } } else { j++; if(! ExistElem(dest,src2->elem)) { AddElem(dest,src2->elem); src2=src2->next; } else { src2=src2->next; } } } while(i { i++; if(! ExistElem(dest,src1->elem)) { AddElem(dest,src1->elem); } src1=src1->next; } while(j { j++; if(! ExistElem(dest,src2->elem)) { AddElem(dest,src2->elem); } src2=src2->next; } } 3.集合的交运算 A、B集合的内容和一个空集合,以单链表的形式作为函数voidMulSet()的三个实参,再对A、B集合进行排序,通过比较A、B中的元素求出A、B集合中相同元素,从前往后将A、B中相同的元素插入到表dest中,具体代码如下: voidMulSet(Setdest,Setsrc1,Setsrc2) { //集合交运算 SortSet(src1);SortSet(src2); inti=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2); src1=src1->next;src2=src2->next; while(i { if(src1->elem elseif(src1->elem>src2->elem){j++;src2=src2->next;} else { i++;j++; if(! ExistElem(dest,src1->elem)) { AddElem(dest,src1->elem); src1=src1->next; src2=src2->next; } } } } 4.集合的差运算 将A、B集合的内容和一个空集合,以单链表的形式作为函数voidSubSet()的三个实参,再对集合A、B进行排序,通过比较A、B中的元素求出A、B集合差集,从前往后将满足条件的元素逐个插入到表dest中,具体代码如下: voidSubSet(Setdest,Setsrc1,Setsrc2) { //集合差运算 SortSet(src1);SortSet(src2); inti=0,len=LengthOf(src1); src1=src1->next; while(i { i++; if(! ExistElem(src2,src1->elem)) { if(! ExistElem(dest,src1->elem)) { AddElem(dest,src1->elem); src1=src1->next; } } else { src1=src1->next; } } } 5.集合的显示 将最后得到的链表中的数据进行输出,具体代码如下: voidDisplaySet(Setsrc) { //打印集合的所有元素 Setp; if(src->next==NULL) { printf("φ"); return; } p=src; do { p=p->next; putchar(p->elem); }while(p->next! =NULL); } 五调试分析 1.在对数据进行排序时,由于对循环控制没有做到精确限制,导致输出结果不能按预期递增有序输出,后不断调试和分析后是问题得到正确解决。 2.最初进行并运算时,总是没有屏蔽重复的数据,最后分析发现: 是判断元素是否存在集合中的函数intExistElem()错误,导致对数据的重复判断失误。 3.本次课程设计采用链表形式的数据抽象的程序设计方案,将程序化分为四个主要模块,使得设计时思路清晰,实现时调试顺利,各模块具有较好的可用性,确实得到了一次良好的程序设计训练。 4.在测试求交集运算时,总显示存取错误,经分析分析调试后发现是在voidMulSet()函数定义链表时出现错误,对其中一个链表没有初始化,导致数据存取失败。 六测试结果 1.集合并运算测试: 2.集合交运算测试: 3.集合差运算: 七用户使用说明 1.在进入使用界面后,根据系统提示从键盘输入两组元素到A、B中,元素可以是数字,可以是字母; 2.根据界面提示选择要进行的集合运算: 1.并集、2.交集、3.差集0.退出; 3.完成操作之后输入“0”退出。 八课程设计总结 通过本次课程设计我学习到了很多内容,尤其是对于C++和数据结构中的专业知识有了更深的理解。 此程序中尚有一些不足之处,比如缺少循环使用的功能,每次想要更换集合的元素都得重启程序之后才行。 在编写代码时也遇到了各种问题,大部分都是自己考虑不全面和经验不足的结果,但在反复思考分析,并请教同学之后,这些问题都得到了有效的解决。 这些将为我以后学习提供宝贵的经验。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 集合 多种 运算