集合的并交差运算
《数 据 结 构》
课程设计说明书
题 目 学 号 姓 名 指导教师 日 期
集合的并交差运算
康懿 2015年7月2日
内蒙古科技大学课程设计任务书
目录
目录 ............................................................................................................................................................................3 第1章 需求分析 ......................................................................................................................................................4 第2章 总体设计 ......................................................................................................................................................4 第3章 抽象数据类型定义 ......................................................................................................................................5
3.1 LinkList抽象数据类型的设计 ....................................................................................................................5 3.2 集合抽象数据类型的设计 .........................................................................................................................5 第4章 详细设计 ......................................................................................................................................................5
4.1 工程视图 .....................................................................................................................................................5 4.2 类图视图 .....................................................................................................................................................6 4.3 主要算法的详细设计 .................................................................................................................................6
4.3.1 插入算法的详细设计 ...................................................................................................................... 7 4.3.2 清除算法的详细设计 ...................................................................................................................... 7 4.3.3 求交集算法的详细设计 .................................................................................................................. 7 4.3.4 求并集算法的详细设计 .................................................................................................................. 8 4.3.5 求差集算法的详细设计 .................................................................................................................. 9
第5章 测试 ..............................................................................................................................................................9 第6章 总结 ............................................................................................................................................................ 11 附录:程序代码 ...................................................................................................................................................... 11
第1章 需求分析
1、 本演示程序中,集合的元素限定为小写字母字符[“a”…”z”]。集合输入的形式为一个以“0“为结束标志的字符串,串中字符顺序不限。
2、 演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息“之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据和运算结果显示在其后。
3、 程序执行的命令包括:
1) 构造集合A;2)构造在集合B;3)删除集合A内的元素;4)删除集合B内的元素;5) 在集合A中插入元素;6)在集合B中插入元素;7)求AB集合的并集;8)求AB集合的交集;9)求AB及BA的差集
第2章 总体设计
总体设计框架图,如图2.1所示:
图2.1 总体设计框架
第3章 抽象数据类型定义
定义格式如下:
3.1 LinkList抽象数据类型的设计
ADT LinkList 基本操作:
InitList(LinkList *L) 构造一个空的线性表L DestroyList(LinkList *L) 初始条件:线性表L已存在 ListEmpty(LinkList L)
初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE Status ListInsert(LinkList L,int i,ElemType e)
在带头结点的单链线性表L中第i个位置之前插入元素e ListPrint(LinkList L) 依次输出链表中的元素
3.2 集合抽象数据类型的设计
typedef struct LNode {
char data;
struct LNode *next; }LNode, *LinkList;
第4章 详细设计
4.1 工程视图
图4.1 工程视图
4.2 类图视图
图4.2 类图视图
4.3 主要算法的详细设计
4.3.1 插入算法的详细设计
void ListSort(LinkList L) {
LinkList first; /*为原链表剩下用于直接插入排序的节点头指针*/ LinkList t; /*临时指针变量:插入节点*/ LinkList p; /*临时指针变量*/ LinkList q; /*临时指针变量*/
first = L->next; /*原链表剩下用于直接插入排序的节点链表*/ L->next = NULL; /*只含有一个节点的链表的有序链表。*/ while (first != NULL) /*遍历剩下无序的链表*/ {
/*插入排序*/
for (t = first, q = L; ((q!=NULL) && (q->data data)); p=q, q=q->next); /*无序节点在有序链表中找插入的位置*/
/*退出for循环,就是找到了插入的位置*/
first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/ if (q == L) L = t; /*插在第一个节点之前*/ else p->next = t; /*p是q的前驱*/ t->next = q; /*完成插入动作*/ }
4.3.2 清除算法的详细设计
void qingchu(LinkList La)/*清除链表中相同的元素*/ {
char i,j;
LinkList p,q; La->next; p=La;
q=p->next; while(q) {i=p->data; j=q->data; if(i==j)
{q=p->next; /* 删除并释放结点 */ p->next=q->next; free(q); }
p=p->next; q=p->next; } }
4.3.3 求交集算法的详细设计
void Jiaoji(LinkList La,LinkList Lb,LinkList Lc) {/*求两集合的交集,将结果存入另一个链表中*/ char i,j;
LinkList p ,q; La->next; Lb->next;
p=La; q=Lb;
while(p&&q) {
i=p->data; j=q->data; if(i
p=p->next; if(i==j)
{ListInsert(Lc,1,i); p=p->next;q=q->next;} if(i>j)
q=q->next; }
ListSort(Lc); printf("A∩B="); ListPrint(Lc); }
4.3.4 求并集算法的详细设计
void bingji(LinkList La,LinkList Lb,LinkList Lc) { char i,j;/*求两集合的并集*/ LinkList p,q; La->next; Lb->next; p=La; q=Lb;
while(p&&q) { i=p->data; j=q->data; if(i
{ListInsert(Lc,1,i);p=p->next;} if(i==j)
{ListInsert(Lc,1,i); p=p->next;q=q->next;} if(i>j)
{ListInsert(Lc,1,j); q=q->next;} }
while(p){i=p->data;ListInsert(Lc,1,i);p=p->next;} while(q){j=q->data;ListInsert(Lc,1,j);q=q->next;} ListSort(Lc); printf("A∪B="); ListPrint(Lc);
4.3.5 求差集算法的详细设计
void chaji(LinkList La,LinkList Lb,LinkList Lc) {char i,j; LinkList p,q; La->next; Lb->next; p=La; q=Lb;
while(p&&q) { i=p->data; j=q->data; if(i
{ListInsert(Lc,1,i);p=p->next;} if(i==j) p=p->next; if(i>j)
q=q->next; }
while(p){i=p->data;ListInsert(Lc,1,i);p=p->next;} ListSort(Lc); ListPrint(Lc); }
第5章 测试
图5.1 输入输出AB集合
图5.2 对AB集合进行删除操作
图5.3 对AB集合进行插入操作
图5.4 对AB集合进行并交差操作
第6章 总结
在本次数据结构课程设计的过程中,深刻的意识到对程序代码设计的难度,不过这更让我在这过程中受益匪浅,体味到计算机系的高大上。这个课程具有很高的挑战性和耐性。
进行程序设计的时候注意模块的划分,从各个小模块开始进行设计。设计的过程中,出现了很多错误,但是通过查找资料,反复对比内容的真伪性,找出了问题的所在,并最终解决了问题,这过程中结果并不显的那么重要,因为有艰辛的过程,所以才显出了结果的完美,它让我更加坚定了在这条路上的努力发展。
附录:程序代码
#include
#include
#include // malloc()等
#include // INT_MAX等
#include // EOF(=^Z或F6),NULL
#include // atoi()
#include // eof()
#include // floor(),ceil(),abs()
#include // exit()
#include // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
/*线性表的单链表存储结构*/
typedef struct LNode
{
char data;
struct LNode *next;
}LNode, *LinkList;
LinkList h;
/*带有头结点的单链表的基本操作*/
void InitList(LinkList *L)
{ /* 操作结果:构造一个空的线性表L */
*L=(LinkList)malloc(sizeof( LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */
}
void DestroyList(LinkList *L)
{ /* 初始条件:线性表L已存在。操作结果:销毁线性表L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
void ClearList(LinkList L) /* 不改变L */
{ /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */
LinkList p,q;
p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
printf("删除成功\n"); /* 头结点指针域为空 */
}
Status ListEmpty(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
if(L->next) /* 非空 */
return FALSE;
else
return TRUE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int j=0;
LinkList p=L,s;
while(p&&j
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i小于1或者大于表长 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 不改变L */
{ /* 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j
j++;
}
if(!p->next||j>i-1) /* 删除位置不合理 */
return ERROR;
q=p->next; /* 删除并释放结点 */
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
void ListPrint(LinkList L) /*依次输出链表中的元素*/
{
LinkList p=L->next;
if(!p)
printf("空集\n");
while(p)
{
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
void ListSort(LinkList L)
{
LinkList first; /*为原链表剩下用于直接插入排序的节点头指针*/
LinkList t; /*临时指针变量:插入节点*/
LinkList p; /*临时指针变量*/
LinkList q; /*临时指针变量*/
first = L->next; /*原链表剩下用于直接插入排序的节点链表*/
L->next = NULL; /*只含有一个节点的链表的有序链表。*/
while (first != NULL) /*遍历剩下无序的链表*/
{
/*插入排序*/
for (t = first, q = L; ((q!=NULL) && (q->data data)); p=q, q=q->next); /*无序节点在有序链表中找插入的位置*/
/*退出for循环,就是找到了插入的位置*/
first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/
if (q == L) L = t; /*插在第一个节点之前*/
else p->next = t; /*p是q的前驱*/
t->next = q; /*完成插入动作*/
}
}
void qingchu(LinkList La)/*清除链表中相同的元素*/
LinkList p,q;
La->next;
p=La;
q=p->next;
while(q)
{i=p->data;
j=q->data;
if(i==j)
{q=p->next; /* 删除并释放结点 */
p->next=q->next;
free(q);
}
p=p->next;
q=p->next;
}
}
void zengtian(LinkList La)/*向集合中添加元素*/ {char a;
printf("请输入要增添的元素,加0结束\n");
scanf("%c",&a);
while(a!='0')
{
if((a>='a'&&a='A'&&a
{
ListInsert(La,1,a);scanf("%c",&a);}}getchar(); /*消除空格*/
ListSort(La);
ListPrint(La);}
void Jiaoji(LinkList La,LinkList Lb,LinkList Lc) {/*求两集合的交集,将结果存入另一个链表中*/ char i,j;
LinkList p ,q;
La->next;
Lb->next;
p=La;
q=Lb;
while(p&&q)
{
i=p->data;
j=q->data;
if(i
p=p->next;
if(i==j)
{ListInsert(Lc,1,i); p=p->next;q=q->next;}
if(i>j)
q=q->next;
}
ListSort(Lc);
printf("A∩B=");
ListPrint(Lc);
}
void bingji(LinkList La,LinkList Lb,LinkList Lc) { char i,j;/*求两集合的并集*/
LinkList p,q;
La->next;
Lb->next;
p=La;
q=Lb;
while(p&&q)
{
i=p->data;
j=q->data;
if(i
{ListInsert(Lc,1,i);p=p->next;}
if(i==j)
{ListInsert(Lc,1,i); p=p->next;q=q->next;}
if(i>j)
{ListInsert(Lc,1,j); q=q->next;}
}
while(p){i=p->data;ListInsert(Lc,1,i);p=p->next;} while(q){j=q->data;ListInsert(Lc,1,j);q=q->next;} ListSort(Lc);
printf("A∪B=");
ListPrint(Lc);
}
void chaji(LinkList La,LinkList Lb,LinkList Lc) {char i,j;
LinkList p,q;
La->next;
Lb->next;
p=La;
q=Lb;
while(p&&q)
{ i=p->data;
j=q->data;
if(i
{ListInsert(Lc,1,i);p=p->next;}
if(i==j)
p=p->next;
if(i>j)
q=q->next;
}
while(p){i=p->data;ListInsert(Lc,1,i);p=p->next;} ListSort(Lc);
ListPrint(Lc);
}
int main()
{char a;
char b;char c;
LinkList L1,L2,L3,L4,L5,L6;
InitList(&L1);
InitList(&L2);
InitList(&L3); /*构建需要的链表*/
InitList(&L4);
InitList(&L5);
InitList(&L6);
printf("************************************\n"); printf(" 欢迎使用集合交并差运算程序\n");
printf("************************************\n");
printf("请输入A集合的元素,加0结束\n");
scanf("%c",&a);
while(a!='0')
{
if((a>='a'&&a='A'&&a
{
ListInsert(L1,1,a);
scanf("%c",&a);
}
}
getchar();
ListSort(L1);
qingchu(L1);
ListPrint(L1);
printf("请输入B集合的元素,加0结束\n");
scanf("%c",&b);
while(b!='0')
{
if(b>='a'&&b='A'&&b
ListInsert(L2,1,b);scanf("%c",&b); }
}
getchar();
ListSort(L2);
qingchu(L2);
ListPrint(L2);
printf("请选择你要的操作\n"); printf("1.删除A集合内元素\n"); printf("2.删除B集合内元素\n"); printf("3.添加元素至A集合\n"); printf("4.添加元素至B集合\n"); printf("5.A∩B\n");
printf("6.A∪B\n");
printf("7.A-B\n");
printf("8.B-A\n");
printf("0.结束\n");
do
{ scanf("%c",&c);
getchar();
switch(c)
{
case '1':ClearList(L1);break; case '2':ClearList(L2);break; case '3':zengtian(L1);break; case '4':zengtian(L2);break; case '5':Jiaoji(L1,L2,L4);break; case '6':bingji(L1,L2,L3);break; case '7':chaji(L1,L2,L5);break; case '8':chaji(L2,L1,L6);break; default: printf("欢迎使用\n"); }
}
while(c!='0');}