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

编号： 730

数据结构和算法课程设计
说明书

集合交并差运算

学　　院： 海洋信息工程学院
专 业： 网络工程
学生姓名： xx
学 号： xx
指导老师： xx

12 月 21 日

目录
目录 2
概述 3
程序说明 3
1 试验内容 4
1.1试验目标 4
1.2试验任务 4
1.3要求 4
2数据结构设计及步骤图 5
2.1抽象数据结构类型定义 5
2.2本程序包含四个模块 7
3测试数据 8
3.1源程序 8
3.2测试数据及程序运行情况 14
4总结 15
参考文件 15

概述
本演示程序编写，关键利用我们学第二章《线性表》中知识。线性结构特点是：在数据元素非空有限集中，（1）存在唯一一个被称做“第一个”数据元素；（2）存在唯一一个被称做“最终一个”数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最终一个之外，集合中每个数据元素均只有一个后继。
本程序需要两个抽象数据类型：有序表和集合。而且采取了单链表来实现。

一、程序说明
本程序关键利用单链表及函数，实现集合交集、并集和差集运算。
运行程序说明：
菜单实施命令包含<0-7>：
<1>“请输入A集合个数和A集合元素”
<2>“请输入B集合个数和B集合元素”
<3>“A集合有序集合”
<4>“B集合有序集合”
<5>“AB集合并集”
<6>“AB集合交集”
<7>“AB集合差集”
<0>“退出”
注：展示程序中，集合元素限定为小写字母数据，以“回车键”束标志。

1、 试验内容
1.1试验目标：设计一个演示集合交、并、差运算程序
1.2试验任务
1） 使用单链表来表示集合，完成集合交集、并集、差等操作。
2） 采取链表等数据结构。
3） 集合元素限定为数字和小写英文字母
1.3试验要求：
1. 初步完成总体设计，建立头文件，确定函数个数。
2. 完成以下条件:
1) 界面清楚，函数功效划分好
2) 总体设计应画步骤图
3) 程序要加必需注释
4) 提供测试方案
注：程序数次测试，填补漏洞。
要求：
1） 展示程序中，集合元素限定为小写字母数据。集合输入形式为一以“回车键”束标志。
2）展示程序以用户和计算机对话方法实施，即在程序输出显示“提醒信息”以后，然后再输入命令；对应输入数据和运算结果显示在其后。
3）程序实施命令包含<0-7>：
<1>“请输入A集合个数和A集合元素”
<2>“请输入B集合个数和B集合元素”
<3>“A集合有序集合”
<4>“B集合有序集合”
<5>“AB集合并集”
<6>“AB集合交集”
<7>“AB集合差集”
<0>“退出”
程序功效：计算两个集合交、并、差和重新输入集合功效。

一、数据结构设计及步骤图
实现功效：
集合交 集合并

为了实现上述程序功效，应以有序单链表表示集合。为此，需要抽象数据类型：有序表和集合
2.1数据类型定义
1、//线性表单链表存放结构
typedef struct LNode
{ ElemType data;
struct LNode *next;
} LinkList;
1、 实现输出功效函数
void DispList()//输出函数
2、 输入n个元素值，建立带表头结点单链线性表L
void CreateList_L1(LinkList *&L,int n)
4、实现集合元素由小到大排序功效
void sort(LinkList *&L)
5、实现了将A、B集合并集，并放到新单链表C中
void Union(LinkList *ha,LinkList*hb,LinkList*&hc)
6、实现了将A、B集合交集，并放到新单链表C中
void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)
7、实现了将A、B集合差集，并放到新单链表C中
void Subs(LinkList *ha,LinkList*hb,LinkList*&hc)
8、销毁表L
void DestroyList(LinkList *&L)
3、 主程序模块（）
{
初始化；
定义变量；
While（）
{
选择菜单
Switch（）
{case1：……case2:……case3：……}
}
Return 0；
}

2.2本程序包含四个模块
1）主菜单模块
2）输入集合单元模块：利用单链表输入；
3）集合运算单元模块：实现集合抽象数据类型；
4）有序表单元模块：实现有序表抽象数据类型；
模块关系：

3.1测试数据：
集合A={dop}，B={dli}，运算其交集、并集、差集。
3.2源程序：
源程序代码以下：
#include <iostream>
#include<stdio.h>
#include<malloc.h>
#include<cstdio>
using namespace std;
typedef char ElemType;
typedef struct LNode
{ElemType data;
struct LNode *next;
} LinkList;
void DispList(LinkList*L)//输出函数
{LinkList *p=L->next;
while(p!=NULL)
{printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
void CreateList_L1(LinkList *&L,int n)
{ //输入n个元素值，建立带表头结点单链线性表L
LinkList *p,*q;
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
q=L;
for(int i=n;i>0;--i)
{p=(LinkList*)malloc(sizeof(LinkList));//生成新结点
cin>>p->data;//输入元素值
p->next=NULL;
q->next=p;//插入到表尾
q=p;
}
}
void DestroyList(LinkList *&L)
{LinkList*p=L->next,*pre=L;
while(p!=NULL)
{free(pre);
pre=p;
p=pre->next;
}
free(pre);
}
void sort(LinkList *&L) //从小到大排序
{LinkList *pre,*p,*q;
p=L->next->next;
L->next->next=NULL;
while(p!=NULL)
{q=p->next;
pre=L;
while(pre->next!=NULL&&pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=q;
}
}
void Union(LinkList *ha,LinkList*hb,LinkList*&hc) //求集合并
{LinkList *pa=ha->next,*pb=hb->next,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL &&pb!=NULL )
{if(pa->data<pb->data)
{ s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{s=(LinkList*)malloc(sizeof(LinkList));
s->data=pb->data;
pc->next=s;
pc=s;
pb=pb->next;
}
else
{s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
pb=pb->next;
}
}
if(pb!=NULL)
pa=pb;
while(pa!=NULL)
{s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
pa=pa->next;
}
pc->next=NULL;
}
void InterSect(LinkList *ha,LinkList*hb,LinkList*&hc)
//求两个有序集合交用尾插法
{LinkList *pa=ha->next,*pb,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL)
{ pb=hb->next;
while(pb!=NULL&&pb->data<pa->data)
pb=pb->next;
if(pb!=NULL &&pb->data==pa->data)///B节点在A节点中复制A节点
{s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
void Subs(LinkList *ha,LinkList*hb,LinkList*&hc) //求两个有序集合差
{
LinkList *pa=ha->next,*pb,*pc,*s;
hc=(LinkList*)malloc(sizeof(LinkList));
pc=hc;
while(pa!=NULL)
{pb=hb->next;
while(pb!=NULL&&pb->data<pa->data)
pb=pb->next;
if(!(pb!=NULL &&pb->data==pa->data))///B节点不在A节点中复制A节点
{ s=(LinkList*)malloc(sizeof(LinkList));
s->data=pa->data;
pc->next=s;
pc=s;
}
pa=pa->next;
}
pc->next=NULL;
}
int main()
{LinkList *ha,*hb,*hc;
int n,k;
while(1)
{ cout<<"\n\t\t —集合简单运算—\n\n";
cout<<"\t\t\t 菜单 \n";
cout<<"\t\t\t ——— ————— ——\n";
cout<<"\t\t\t 1. 请输入A集合个数和A集合元素 \n";
cout<<"\t\t\t 2. 请输入B集合个数和B集合元素 \n";
cout<<"\t\t\t 3. A集合有序集合 \n";
cout<<"\t\t\t 4. B集合有序集合 \n";
cout<<"\t\t\t 5. AB集合并集 \n";
cout<<"\t\t\t 6. AB集合交集 \n";
cout<<"\t\t\t 7. AB集合差集 \n";
cout<<"\t\t\t 0. 退出 \n";
cout<<"\t\t\t ———————————\n";
cout<<"\t\t\t 请选择(0-7):";
cin>>k;
switch(k)
{
case 1: cout<<"请输入A集合个数和A集合元素：";cin>>n; CreateList_L1(ha,n);break;
case 2:cout<<"请输入B集合个数和B集合元";
cin>>n;CreateList_L1(hb,n); break;
case 3:sort(ha);cout<<"\n A有序集合为：";DispList(ha);break;
case 4:sort(hb);cout<<"\n B有序集合为：";DispList(hb);break;
case 5:Union(ha,hb,hc);cout<<"\n AB集合并集为：";DispList(hc);break;
case 6:InterSect(ha,hb,hc);cout<<"\n AB集合交集为："; DispList(hc);break;
case 7:Subs(ha,hb,hc);cout<<"\n AB集合差集为：";DispList(hc);break;
case 0: cout<<"\n\t\t\t------ 谢谢使用！-------\n";
cout<<"\n\t\t\t按任意键退出......\n";
return 0;
} // switch
}//while
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;}
3.3测试数据及运行情况

(1) 选择功效<0-7>

(2) 输入A集合个数和A集合元素{dop}

(3) 输入B集合个数和B集合元素{dli}

(4) A集合有序集合

(5) B集合有序集合

(6) AB集合并集

(7) AB集合交集

(8) AB集合差集

(9) 退出程序

在测试过程中出现过很多小问题，如：交集并集二者运算结果颠倒、菜单文字错误、菜单较长等问题，在认真查看修改后，这些问题得到了处理。
4.总结：
在完成此次课程设计过程中，经过自己思索和努力，培养了自学能力和动手能力。而且由原先被动接收知识转换为主动寻求知识，这能够说是学习方法上一个很大突破。在以往传统学习模式下，我们可能会记住很多书本知识，不过经过课程设计，我们学会了怎样将学到知识转化为自己东西，学会了怎么愈加好处理知识和实践相结合问题。
经过编程实践，不仅开发了自己逻辑思维能力，培养了分析问题、处理问题能力，更充足锻炼了我们编程能力。
在设计汇报写作过程中，我也学到了做任何事情全部要有心态，首先我明白了，出现任何问题全部不要轻视，要经过正确路径去处理，在做事情过程中要有耐心和毅力，不要一碰到困难就打退堂鼓，只要坚持下去就能够找到思绪去处理问题。
在这次课程设计中我也知道了自己编码能力不强，有待于深入提升，但在老师和同学帮助下，我坚持到了最终。我在这次课程设计中学到很多。在以后学习中，我一定勤于思索，并灵活利用所学知识，多进行编程实践。在总结反思和编程训练中，不停提升自己编程能力。相信在我努力下，我程序设计水平一定会不停提升。
参考文件
清华大学计算机系教材：数据结构（c语言版）严蔚敏、吴伟民编著