计算机系信管专业
数据结构课程设计
题 目： 集合运算
班 级： 信管11101班
姓名： 学号：201117020127
同组人姓名：
起 迄 日 期:20##-12-24—20##-12-28
课程设计地点: E3-A512
指导教师：
完成日期：20##年12月28日
目录
一、需求分析. 3
1、程序的实现. 3
（1）功能. 3
（2）实施. 3
2、设计的要求. 3
二、概要设计. 3
1、问题分析. 3
2、模块结构. 4
（1）结构分析. 4
（2）结构分析图. 4
三、详细设计. 5
1、解题思路. 5
（1）数据结构设计. 5
（2）逻辑结构存储结构. 5
2、算法设计. 5
四、调试分析和测试结果. 6
1、模块分析. 6
（1）定义单链表结点类型. 6
（2）运用尾插法建立单链表. 6
（3）建立有序链表. 6
2、结果分析. 7
五、总结. 8
1、解决的问题. 8
（1）集合的运算算法. 8
（2）解决方式. 8
2、心得体会. 9
六、参考文献（资料不得少于5篇）. 9
七、致谢. 9
八、附录（含程序源码）. 9
一、需求分析
1、程序的实现
（1）功能
使用链表来表示集合，完成集合的合并，求交集等操作。
（2）实施
1) 初步完成总体设计，搭好框架，确定函数个数；
2) 完成最低要求；
3) 继续完成进一步要求。
2、设计的要求
(1) 界面友好，函数功能要划分好；
(2) 总体设计应画流程图；
(3) 程序要加必要的注释；
(4) 要提供程序测试方案；
(5) 程序要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
二、概要设计
1、问题分析
该问题主要实现以下功能：
(1) 利用尾插法建立单链表；
(2) 对于输入的链表进行有序排列
(3) 删除有序链表中不符合要求的元素
(4) 调用函数对单链表进行交、并运算并输出
2、模块结构
（1）结构分析
程序以用户和计算机的对话方式执行，即在计算及终端显示提示信息之后，由用户在键盘输入演示程序中规定的运算命令；相应的输入数据（过滤输入中的非法字符）和运算结果闲时间在其后。系统由以下几个模块组成，分别是：
1) 单链表的建立
2) 单链表的有序排列
3) 删除单链表中不符合条件的元素
4) 集合交集
5) 集合并集
6) 单链表输出
7) 主函数
（2）结构分析图
三、详细设计
1、解题思路
（1）数据结构设计
创建三个带头结点的单链表,用来存储两个集合中的元素和最终的结果,为实现集合的交、并运算功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。
（2）逻辑结构存储结构
逻辑结构：创造一个带结点的单链表包括（头结点L、结点若干、尾结点）；单链表中每个结点包括（*next表示指针data表示域）
2、算法设计
程序执行的命令包括：
(1) 定义单链表结点类型typedef struct LNode
(2) 运用尾插法建立单链表void CreatListR（LinkList *&L,ElemType a[],int n）
(3) 创建头结点，为头结点分配空间
(4) 创建新结点
(5) 建立有序链表void Sort（LinkList *&head）
(6) 将两个集合的元素进行比较 while语句
(7) 删除有序链表中的重复元素void shanchu(LinkList *&head)
(8) 求交集 void jiao（struct Lnode **L1，struct Lnode **L2，struct Lnode **L3）
(9) 求并集 void bing（struct Lnode ** L1，struct Lnode **L2，struct Lnode **L3）
(10) 输出单链表void Display（LinkList *L）
四、调试分析和测试结果
1、模块分析
（1）定义单链表结点类型
typedef struct LNode
{ ElemType data;
struct LNode *next;
} LinkList;
（2）运用尾插法建立单链表
void CreatListR（LinkList*&L，ElemType a[],int n）
{ LinkList *s,*r;int I;
L=( LinkList *)malloc(sizeof(LinkList)); //创建并为头结点分配空间
L->next=NULL;
r=L;
for(i=0;i<n;i++)
{ s=( LinkList *)malloc(sizeof(LinkList)); //创建新结点
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL; //尾结点指向空
（3）建立有序链表
void Sort(LinkList *&head)
{ LinkList *p=head->next,*q,*r; if(p!=NULL)
{ r=p->next;
p->next=NULL; p=r;
while(p!=NULL)//后续元素与第一个元素进行比较
{ r=p->next; q=head; while(q->next!=NULL&&q->next->data<p->data) q=q->next; p->next=q->next; q->next=p; p=r; }
}
}
2、结果分析
选择数字1，进行排序输出；
选择数字2，输出集合1与集合2的交集；
选择数字3，输出集合1与集合2的并集。
可以看出，该程序成功是实现了集合的排序和两个集合的交集运算，而两个集合的并集运算显然还存在问题，在以后的学习与操作中，我们要更加注重程序的运行，尽量做到零问题出现。
五、总结
1、解决的问题
（1）集合的运算算法
由于对集合的两种运算的算法推敲不足，在链表类型及其尾指针的设置时出现错误，导致程序低效。
刚开始时曾忽略了一些变量参数的标识”&”，使调试程序浪费时间不少。今后应重视确定参数的变量和赋值属性的区分和标识。
（2）解决方式
开始时输入集合后，程序只能进行一次运算，后来加入switch语句,成功解决了这一难题。
本程序的模块划分比较合理，且尽可能的将指针的操作封装在节点和链表的两个模块中，致使集合模块的调试比较顺利。
2、心得体会
通过实践才发现程序设计的掌握直接关系到数据结构上机实验效果。对各个知识点的熟练掌握是在数据结构课程中理解理论算法和完成上机实验的重要保证。本课程设计采用数据抽象的程序设计方案，将程序化分为四个层次结构，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可用性，确实得到了一次良好的程序设计训练。
六、参考文献（资料不得少于5篇）
[1] 催俊凯。计算机软件基础。机械工业出版社。2007.7
[2] 唐发根。数据结构教程（第二版）。北京航空航天大学出版社。2005.5.
[3] 严尉敏,吴伟民.数据结构(C语言版)[M].清华大学出版社，20##年11月
[4] 谭浩强。C程序设计（第三版）。清华大学出版社。2005.
[5] 李建学，李光元，吴春芳。数据结构课程设计案例精编（用C/C++描述）。北京：清华大学出版社。2007.2
[6] 王宏生，宋继红。数据结构。北京：国防工业出版社，2006.1
七、致谢
感谢辅导我们数据结构的老师在这个学期细心耐心的指导我们的基础课学习，为我们的课程设计打下良好的基础。在这次课程设计中，席老师给我很多的指导和帮助，让我能够使程序正常运行且实现实验的要求。
我也很感谢和我同组的同学，整个程序基本上由她构思，我负责创建单链表等较简单的操作，在这次的课程设计中，我们分工合作共同完成这次课程设计的要求，再次对她表示感谢。
八、附录（含程序源码）
#include <iostream>
#include <malloc.h>
using namespace std;
typedef char ElemType;
typedef struct LNode//定义单链表结点类型
{ ElemType data;
struct LNode *next;
}LinkList;
void CreatListR(LinkList *&L,ElemType a[],int n) //运用尾插法建立单链表
{ LinkList *s,*r;int i;
L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点，为头结点分配空间
L->next=NULL;
r=L; //r先指向头结点后指向尾结点，开始时指针指向头结点
for(i=0;i<n;i++)
{ s=(LinkList *)malloc(sizeof(LinkList));//创建新结点
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;//尾结点指向空
}
void Sort(LinkList *&head)//建立有序链表
{ LinkList *p=head->next,*q,*r;
if(p!=NULL)
{ r=p->next;
p->next=NULL;
p=r;
while(p!=NULL)//后续元素与第一个元素进行比较
{ r=p->next;
q=head;
while(q->next!=NULL&&q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
void shanchu(LinkList *&head)//删除有序链表中重复的元素及非小写字母的元素
{ LinkList *p=head->next,*r=head,*q,*f;
while(p->next)
{ if(p->data==p->next->data||((p->next->data>'z')||(p->next->data<'a')))
{ q=p->next;
p->next=q->next;
free(q);
}
else
p=p->next;
}
if(r->next->data>'z'||r->next->data<'a')
{ f=r->next;
r->next=f->next;
free(f);
}
}
void bing(LinkList * ha,LinkList * hb,LinkList * hc)//求并集hc
{ LinkList * pa,* pb,* pc;
pa=ha->next;
while(pa!=NULL)
{ pc=(LinkList *)malloc(sizeof(LinkList));
pc->data=pa->data;
pc->next=hc->next;
hc->next=pc;
pa=pa->next;
}
pb=hb->next;
while(pb!=NULL)
{ pa=ha->next;
while((pa!=NULL)&&(pa->data!=pb->data))
pa=pa->next;
if(pa==NULL)
{ pc=(LinkList *)malloc(sizeof(LinkList));
pc->data=pb->data;
pc->next=hc->next;
hc->next=pc;
}
pb=pb->next;
}
}
void jiao(LinkList *ha,LinkList *hb,LinkList *&hc)//求交集hc
{ LinkList *pa=ha->next,*pb,*s,*tc;
hc=(LinkList *)malloc(sizeof(LinkList));//定义hc的头结点
tc=hc;
while(pa)
{ pb=hb->next;
while(pb&&pb->data<pa->data)
pb=pb->next;
if(pb&&pb->data==pa->data)
{ s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;
}
tc->next=NULL;
}
void cha(LinkList *ha,LinkList *hb,LinkList *&hc)//求差集hc
{ LinkList *pa=ha->next,*pb,*s,*tc;
hc=(LinkList *)malloc(sizeof(LinkList));//定义hc的头结点
tc=hc;
while(pa)
{ pb=hb->next;
while(pb&&pb->data<pa->data)
pb=pb->next;
if(!(pb&&pb->data==pa->data))
{ s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;
}
tc->next=NULL;
}
void DispList(LinkList *L)//输出单链表L
{ LinkList *p=L->next;
while(p!=NULL)
{ cout<<p->data;
p=p->next;
}
cout<<endl;
}
int main()
{ LinkList *ha,*hb,*hc;
ElemType a[100],b[100];//建立两个数组存储集合
int la,lb,x;
cout << "请输入集合1：" ;
cin.getline(a,100);
cout << "请输入集合2：";
cin.getline(b,100);
la=strlen(a);
lb=strlen(b);
CreatListR(ha,a,la);
CreatListR(hb,b,lb);
Sort(ha);
Sort(hb);
shanchu(ha);
shanchu(hb);
cout<<"1.输出有序集合 2.求集合交集 3.求集合并集 4.求集合并集"<<endl;
while(x!=0)
{ //循环对运算的选择
cout<<"请选择运算：（选0退出）";
cin>>x;
switch(x)
{ case 1: cout<<"有序1集合:";
DispList(ha);
cout<<"有序2集合:";
DispList(hb);//输出有序集合
break;
case 2: jiao(ha,hb,hc);
cout<<"交集合:";DispList(hc);//调用求交集函数
break;
case 3: bing(ha,hb,hc);
cout<<"并集合:";DispList(hc);//调求用并集函数
break;
case 4: cha(ha,hb,hc);
cout<<"差集合:";DispList(hc);//调用求差集函数
break;
}
}
return 0;
}