数据结构课程设计集合的并交和差运算.docx

数据结构课程设计集合的并交和差运算.docx

《数据结构课程设计集合的并交和差运算.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计集合的并交和差运算.docx（25页珍藏版）》请在冰点文库上搜索。

数据结构课程设计集合的并交和差运算

课程设计报告

课程名称数据结构

课题名称集合的并、交和差运算

专业通信工程

班级通信1101

学号201103020127

姓名皮锋

指导教师张鏖烽田娟秀李杰君

2013年6月29日

湖南工程学院

课程设计任务书

课程名称数据结构

课题集合的并、交和差运算

专业班级通信1101

学生姓名皮锋

学号201103020127

指导老师张鏖烽田娟秀李杰君

审批

任务书下达日期2013年6月23日

任务完成日期2013年6月29日

集合的并、交和差运算

1.需求分析

1.1.问题描述

编制一个能演示执行集合的并、交和差运算的程序。

1.2.基本要求

（1）集合的元素限定为小写字母字符[‘a’..’z’]。

（2）演示程序以用户和计算机的对话方式执行。

1.3.测试数据

（1）Set1="magazine"，Set2="paper"，

Set1∪Set2="aegimnprz"，Setl∩Set2="ae"，Set1-Set2="gimnz"。

（2）Set1="012oper4a6tion89"，Set2="errordata"，

Set1∪Set2="adeinoprt"，Setl∩Set2="aeort"，Set1-Set2="inp"。

1.4.实现提示

以有序链表表示集合。

2.概要设计

为实现上述程序功能，应以有序链表表示集合。

为此，需要两个抽象数据类型：

有序表和集合。

2.1.有序表的抽象数据类型定义为

typedefstructLNode

{

chardata;

structLNode*next;

}LinkList;

2.2.集合的定义为

charset1[maxsize],set2[maxsize];

2.3.基本操作

voidGreatListR（LinkList*&L,chara[],intn）//尾插法建表

voidInitList（LinkList*&L）//初始化线性表

voidDestroyList（LinkList*&L）//销毁线性表

voidDispList（LinkList*L）//输出线性表

voidsort（LinkList*&L）//元素排序

voidbingji（LinkList*L,LinkList*N,LinkList*&M）//并集运算

voiddels（LinkList*&M）//删除相同元素仅留一个

voidjiaoji（LinkList*&M,LinkList*L,LinkList*N）//交集运算

voidchayunsuan（LinkList*L,LinkList*M,LinkList*&K）//集合差运算

intmain（）//为设计程序主页面的函数，并且使用了所有的函数

2.4.调用关系

InitList（L）;

InitList（N）;

GreatListR（L,set1,i）;

GreatListR（U,set1,i）;

sort（U）;//元素排序

dels（U）;//删除相同元素仅留一个

sort（L）;//元素排序

dels（L）;//删除相同元素仅留一个

printf（"请输入集合set2="）;

for（j=0;j

{

scanf（"%c",&set2[j]）;

if（set2[j]=='\n'）

break;

}

GreatListR（N,set2,j）;

sort（N）;//元素排序

dels（N）;//删除相同元素仅留一个

bingji（L,N,M）;//集合合并

dels（M）;//删除相同元素仅留一个

DispList（M）;

jiaoji（M,L,N）;//交集运算

DispList（M）;

chayunsuan（U,M,K）;//集合差运算

DispList（K）;

charn;

printf（"\n是否退出运算？

\n"）;

scanf（"%c",&n）;

if（n=='e'）

exit（0）;

DestroyList（L）;

DestroyList（N）;

DestroyList（U）;

DestroyList（M）;

DestroyList（K）;

system（"PAUSE"）;

3.详细设计

3.1.具体算法流程

图3-1具体算法流程

3.2.具体的程序功能实现

（1）利用c++引用类型，对线性表LinkList*L,*N

进行初始化，并用for循环将将集合set1[maxsize],set2[maxsize]分别存入线性表L和K。

（2）用sort（）函数对两个线性表里的元素进行排序，得到两个有序表。

（3）用dels（）函数分别删除两个有序表里相同元素，仅留一个。

（4）用函数bingji（L,N,M）合并两个有序表，得到有序表M，并再次调用函数dels（M）删除有序表里相同的元素，仅留下一个，从而得到集合的并集。

（5）调用函数jiaoji（M,L,N），进行交集运算，从而得到一个新的有序表M，存着两个集合的交集。

（6）利用交集运算得到的结果M进行集合差运算，调用函数chayunsuan（U,M,K），得到两个集合差集为有序表K。

（7）调用函数DispList（）输出并集，交集和差集的结果。

（8）用代码

charn;

printf（"\n是否退出运算？

\n"）;

scanf（"%c",&n）;

if（n=='e'）

exit（0）;

判断是否进行下一次运输，如果进行下一次运算按回车键继续，否则输入字母“e”退出运算。

（9）最后利用函数DestroyList（）销毁所有线性表。

（10）加上头文件#include和语句system（"colorB5"）对界面进行颜色设置，得到自己喜欢的颜色。

3.3.伪码算法

（1）并集运算

voidbingji（LinkList*L,LinkList*N,LinkList*&M）//并集运算

{

LinkList*pa=L->next,*pb=N->next,*r,*s;//时归并算法

M=（LinkList*）malloc（sizeof（LinkList））;

r=M;

while（pa!

=NULL&&pb!

=NULL）//集合合并

{

if（pa->datadata）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pa->data;

r->next=s;r=s;

pa=pa->next;

}

else

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pb->data;

r->next=s;r=s;

pb=pb->next;

}

}

while（pa!

=NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pa->data;

r->next=s;r=s;

pa=pa->next;

}

while（pb!

=NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pb->data;

r->next=s;r=s;

pb=pb->next;

}

r->next=NULL;

printf（"两个集合的并集为set1∪set2:

"）;

}

voiddels（LinkList*&M）//删除相同元素仅留一个

{

LinkList*p=M->next,*q;

while（p->next!

=NULL）

{

if（p->data==p->next->data）

{

q=p->next;

p->next=q->next;

free（q）;

}

else

p=p->next;

}

}

（2）交集运算

voidjiaoji（LinkList*&M,LinkList*L,LinkList*N）//交集运算

{

LinkList*pa=L->next,*pb=N->next,*q,*r;//以单链表M的头节点创建一个空单链表

M->next=NULL;

r=M;//r指向这个新链表的最后一个节点

while（pa!

=NULL）//以pa扫描单链表M的数据节点，判断是否在单链表L和N中

{

while（pb!

=NULL&&pa->data>pb->data）

pb=pb->next;

if（pa!

=NULL&&pb!

=NULL&&pa->data==pb->data）

{

r->next=pa;

r=pa;

pa=pa->next;

}

else

{

q=pa;

pa=pa->next;

free（q）;

}

}

r->next=NULL;

printf（"两个集合的交集为set1∩set2="）;

}

（3）差集运算

voidchayunsuan（LinkList*L,LinkList*M,LinkList*&K）//集合差运算

{

LinkList*p1=L->next,*p2=M->next,*s,*r;

K=（LinkList*）malloc（sizeof（LinkList））;

r=K;

r->next=NULL;

while（p1!

=NULL）

{

p2=M->next;

while（p2!

=NULL&&p2->data!

=p1->data）

p2=p2->next;

if（p2==NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

r->next=s;r=s;

}

p1=p1->next;

}

r->next=NULL;

printf（"两个集合的差集为set1-set2="）;

}

4.调试分析

4.1.调试过程中遇到的问题

（1）由于对集合的三种运算的算法推敲不足,在有序链表类型的早期版本未设置尾指针操作,导致算法低效。

（2）由于首先没设置数组最大值，导致数组不能正确输入，后来定义了#definemaxsize100才解决这个问题。

（3）在子函数中线性表的创建不正确，导致在输入数组后不能正确执行，出现下图结果，经过多次调试才得到正确结果。

（4）在进行差运算的算法设计时出现逻辑上的错误，导致结果不正确，集合的首元素未能正确参与运算。

进过仔细的推敲才发现没有创建一个空的头结点就直接把pa=pa->next，使第一个数据元素未参加运算。

（5）程序首先只能进行一次运算就退出了，不能人性化的进行多次运算，后来在主函数中加入for语句，进行循环，才能进行多次运算，并在for语句里加入if条件语句，进行是否进行下一次运算的判断，使程序更加优化。

（6）首先把删除相同元素的算法写在交集，并集和差集的算法运算里面，使程序代码冗长，后来为了使代码更加简洁，就另外单独写了一个删除相同元素的算法，只要在各个运算中调用即可。

4.2.算法的时空分析

（1）voidGreatListR（LinkList*&L,chara[],intn）//尾插法建表

本算法的时间复杂度为O（n），其中n为单链表中数据节点的个数。

（2）voidInitList（LinkList*&L）//初始化线性表

本算法的时间复杂度为O

（1）。

（3）voidDestroyList（LinkList*&L）

本算法的时间复杂度为O（n），其中n为单链表中数据节点的个数。

（4）voidDispList（LinkList*L）//输出线性表

本算法的时间复杂度为O（n），其中n为单链表中数据节点的个数。

（6）voidsort（LinkList*&L）//元素排序

本算法的时间复杂度为O（n），其中n为单链表中数据节点的个数。

（7）voidbingji（LinkList*L,LinkList*N,LinkList*&M）//并集运算

本算法的时间复杂度为O（ListLength（L）+ListLength（N））。

（8）voiddels（LinkList*&M）//删除相同元素仅留一个

本算法的时间复杂度为O（n），其中n为单链表中数据节点的个数。

（9）voidjiaoji（LinkList*&M,LinkList*L,LinkList*N）//交集运算

本算法的时间复杂度为O（m+n+p）。

（10）voidchayunsuan（LinkList*L,LinkList*M,LinkList*&K）//集合差运算

本算法的时间复杂度为O（n*n），其中n为单链表中数据节点的个数。

5.用户使用说明

用户在使用时首先输入要进行运算的两个集合，然后按回车键则会出现运算结果。

只能进行小写字母a到z的运算，如果输入其他以外的数字、字母或字符，则不会在运算结果中显示！

若用户需要在进行下一次运算，则按回车键继续，否则按字母“e”退出计算！

6.测试结果

6.1.做完一次运算后按回车键继续下一次运算

图6-1运算完一次进行第二次运算

图6-2进行多次运算

6.2.做完运算后输入字母“e”退出运算

图6-1运算完按字母“e”退出

7.总结

数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。

随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。

数据结构课设使我们巩固了以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在这门课程的实际应用上也有了一个提高。

首先这两周的学习，使我们在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身知识和能力在实际中的应用和发挥。

其次，它激发了我们创新意识，开发创造的能力和培养沟通能力。

另外，让我们进一步熟悉了数据结构的设计应用。

每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对我们数据结构的学习和提高很有益处，并且使我们明白了程序设计过程，如解决一些实际问题，从解决实际问题的角度。

课程设计让我们受益匪浅。

我们深深认识到，要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。

8.附录

8.1.程序源代码

#include

#include

usingnamespacestd;

#definemaxsize100

typedefstructLNode

{

chardata;

structLNode*next;

}LinkList;

voidGreatListR（LinkList*&L,chara[],intn）//尾插法建表

{

LinkList*s,*r;

inti;

L=（LinkList*）malloc（sizeof（LinkList））;//创建头节点

r=L;

for（i=0;i

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=a[i];

r->next=s;

r=s;

}

r->next=NULL;

}

voidInitList（LinkList*&L）//初始化线性表

{

L=（LinkList*）malloc（sizeof（LinkList））;

L->next=NULL;

}

voidDestroyList（LinkList*&L）

{

LinkList*pre=L,*p=L->next;

while（p!

=NULL）

{

free（pre）;

pre=p;

p=pre->next;

}

free（pre）;

}

voidDispList（LinkList*L）//输出线性表

{

LinkList*p=L->next;

while（p!

=NULL）

{

if（（p->data>='a'）&&（p->data<='z'））

printf（"%c",p->data）;

p=p->next;

}

printf（"\n"）;

}

voidsort（LinkList*&L）//元素排序

{

LinkList*p,*pre,*q;

p=L->next->next;//p指向L的第2个数据节点

L->next->next=NULL;//构件只含一个数据节点的有序表

while（p!

=NULL）

{

q=p->next;

while（p!

=NULL）

{

q=p->next;//q保存*p节点没后继节点的指针

pre=L;//从有序表开头进行比较，pre指向插入*p的前驱节点

while（pre->next!

=NULL&&pre->next->datadata）

pre=pre->next;

p->next=pre->next;

pre->next=p;

p=q;

}

}

}

voidbingji（LinkList*L,LinkList*N,LinkList*&M）//并集运算

{

LinkList*pa=L->next,*pb=N->next,*r,*s;//时归并算法

M=（LinkList*）malloc（sizeof（LinkList））;

r=M;

while（pa!

=NULL&&pb!

=NULL）//集合合并

{

if（pa->datadata）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pa->data;

r->next=s;r=s;

pa=pa->next;

}

else

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pb->data;

r->next=s;r=s;

pb=pb->next;

}

}

while（pa!

=NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pa->data;

r->next=s;r=s;

pa=pa->next;

}

while（pb!

=NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=pb->data;

r->next=s;r=s;

pb=pb->next;

}

r->next=NULL;

printf（"两个集合的并集为set1∪set2:

"）;

}

voiddels（LinkList*&M）//删除相同元素仅留一个

{

LinkList*p=M->next,*q;

while（p->next!

=NULL）

{

if（p->data==p->next->data）

{

q=p->next;

p->next=q->next;

free（q）;

}

else

p=p->next;

}

}

voidjiaoji（LinkList*&M,LinkList*L,LinkList*N）//交集运算

{

LinkList*pa=L->next,*pb=N->next,*q,*r;//以单链表M的头节点创建一个空单链表

M->next=NULL;

r=M;//r指向这个新链表的最后一个节点

while（pa!

=NULL）//以pa扫描单链表M的数据节点，判断是否在单链表L和N中

{

while（pb!

=NULL&&pa->data>pb->data）

pb=pb->next;

if（pa!

=NULL&&pb!

=NULL&&pa->data==pb->data）

{

r->next=pa;

r=pa;

pa=pa->next;

}

else

{

q=pa;

pa=pa->next;

free（q）;

}

}

r->next=NULL;

printf（"两个集合的交集为set1∩set2="）;

}

voidchayunsuan（LinkList*L,LinkList*M,LinkList*&K）//集合差运算

{

LinkList*p1=L->next,*p2=M->next,*s,*r;

K=（LinkList*）malloc（sizeof（LinkList））;

r=K;

r->next=NULL;

while（p1!

=NULL）

{

p2=M->next;

while（p2!

=NULL&&p2->data!

=p1->data）

p2=p2->next;

if（p2==NULL）

{

s=（LinkList*）malloc（sizeof（LinkList））;

s->data=p1->data;

r->next=s;r=s;

}

p1=p1->next;

}

r->next=NULL;

printf（"两个集合的差集为set1-set2="）;

}

voidmain（）

{

printf（"*************************