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

数据结构课程设计报告--集合的并、交和差运算本文简介：合肥学院计算机科学与技术系课程设计报告2012～2013学年第二学期课程数据结构与算法课程设计名称集合的并、交和差运算学生姓名张文浩学号1104032028专业班级11网工2班指导教师何立新华珊珊2013年6月题目：集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。【基本

数据结构课程设计报告--集合的并、交和差运算本文内容：

合肥学院

计算机科学与技术系

课程设计报告

2012～2013学年第二学期

课程

数据结构与算法

课程设计名称

集合的并、交和差运算

学生姓名

张文浩

学号

1104032028

专业班级

11网工2班

指导教师

何立新

华珊珊

2013年

6月

题目：

集合的并、交和差运算

【问题描述】

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

【基本要求】

(1)

集合的元素限定为小写字母字符

[‘a’’z’]

。

(2)

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

【测试数据】

(1)Set1=“magazine“，Set2=“paper“，

Set1∪Set2=“aegimnprz“，Setl

∩Set2=“ae“，Set1-Set2=“gimnz“。

(2)Set1=

“012oper4a6tion89“，Set2=“error

data“，

Set1∪Set2=“adeinoprt“，Setl

∩Set2=“aeort“，Set1-Set2=“inp“。

【实现提示】

以有序链表表示集合。

【选作内容】

(1)

集合的元素判定和子集判定运算。

(2)

求集合的补集。

(3)

集合的混合运算表达式求值。

(4)

集合的元素类型推广到其他类型

，

甚至任意类型。

一、

实验内容

实验题目：编制一个演示集合的并、交和差运算的程序。

需求分析：

1、

本演示程序中，集合的元素限定为小写字母字符[“a”…”z”]。集合输入的形式为一个以“回车符“为结束标志的字符串，串中字符顺序不限。

2、

演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。

3、

程序执行的命令包括：

1）

构造集合1；2）构造在集合2；3）求并集；4）求交集；5)求差集；6）返回；7）结束。“构造集合1”和“构造集合2”时，需以字符的形式键入集合元素。

二、数据结构设计

为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。

1、有序表的抽象数据类型定义为：

readdata(pointer

head)

初始条件：head是以head为头节点的空链表。

操作结果：生成以head为头节点的非空链表。

pop(pointer

head)

初始条件：head是以head为头节点的非空链表。

操作结果：将以head为头节点的链表中数据逐个输出。

2、集合的抽象数据类型定义为：

and(pointer

head1,pointer

head2,pointer

head3)

初始条件：链表head1、head2、head3已存在

操作结果：生成一个由head1和head2的并集构成的集合head3。

or(pointer

head1,pointer

head2,pointer

head3)

初始条件：链表head1、head2、head3已存在

操作结果：生成一个由head1和head2的交集构成的集合head3。

differ(pointer

head1,pointer

head2,pointer

head3)

初始条件：链表head1、head2、head3已存在

操作结果：生成一个由head1和head2的差集构成的集合head3。

3、本程序抱含四个模块：

1）

节点结构单元模块——定义有序表的节点结构；

2）

有序表单元模块——实现有序表的抽象数据类型；

3）

集合单元模块——实现集合获得抽象数据类型；

4）主程序模块：

Void

main（）{

初始化；

do{

接受命令；

处理命令；

}while（“命令”!=“退出”）；

}

三、算法设计

#include

#include

typedef

struct

LNode//定义结构体类型指针

{

char

data;

struct

LNode*next;

}*pointer;

void

readdata(pointer

head)//定义输入集合函数

{

pointer

p;

char

tmp;

scanf(“%c“,while(tmp!=

\n

)

{

p=(pointer)malloc(sizeof(struct

LNode));

p->data=tmp;

p->next=head->next;

head->next=p;

scanf(“%c“,}

}

void

pop(pointer

head)//定义输出集合函数

{

pointer

p;

p=head->next;

while(p!=NULL)

{

printf(“%c“,p->data);

p=p->next;

}

printf(“\n“);

}

void

and(pointer

head1,pointer

head2,pointer

head3)//定义集合的并集函数

{

pointer

p1,p2,p3;

p1=head1->next;

while(p1!=NULL)

{

p3=(pointer)malloc(sizeof(struct

LNode));

p3->data=p1->data;

p3->next=head3->next;

head3->next=p3;

p1=p1->next;

}

p2=head2->next;

while(p2!=NULL)

{

p1=head1->next;

while((p1!=NULL)

if

(p1==NULL)

{

p3=(pointer)malloc(sizeof(struct

LNode));

p3->data=p2->data;

p3->next=head3->next;

head3->next=p3;

}

p2=p2->next;

}

}

void

or(pointer

head1,pointer

head2,pointer

head3)//定义集合的交集函数

{

pointer

p1,p2,p3;

p1=head1->next;

while(p1!=NULL)

{

p2=head2->next;

while((p2!=NULL)

if((p2!=NULL)

p3->data=p1->data;

p3->next=head3->next;

head3->next=p3;

}

p1=p1->next;

}

}

void

differ(pointer

head1,pointer

head2,pointer

head3)//定义集合的差集函数

{

pointer

p1,p2,p3;

p1=head1->next;

while(p1!=NULL)

{

p2=head2->next;

while((p2!=NULL)

if(p2==NULL)

{

p3=(pointer)malloc(sizeof(struct

LNode));

p3->data=p1->data;

p3->next=head3->next;

head3->next=p3;

}

p1=p1->next;

}

}

void

main()//主函数

{

int

x;

printf(“(输入数据,按回车键结束,第一个集合大于第二个集合)\n“);

pointer

head1,head2,head3;

head1=(pointer)malloc(sizeof(struct

LNode));

head1->next=NULL;

head2=(pointer)malloc(sizeof(struct

LNode));

head2->next=NULL;

head3=(pointer)malloc(sizeof(struct

LNode));

head3->next=NULL;

printf(“请输入集合1：\n“);

readdata(head1);//调用输入集合函数

printf(“请输入集合2：\n“);

readdata(head2);//调用输入集合函数

A:printf(“1.并集

2.交集

3.差集

4.结束

x.重新运算\n“);

do{

printf(“请选择序号\n“);

scanf(“%d“,switch(x)

{

case

1:

printf(“两集合的并是\n“);

and(head1,head2,head3);//调用并集函数

pop(head3);

head3->next=NULL;

break;

case

2:

printf(“两集合的交是\n“);

or(head1,head2,head3);//调用交集函数

pop(head3);

head3->next=NULL;

break;

case

3:

printf(“两集合的差是\n“);

differ(head1,head2,head3);//调用差集函数

pop(head3);

head3->next=NULL;

break;

case

4:break;

default:goto

A;

}

}while(x!=4);

}

四、测试数据及程序运行情况

运行时提示输入：

输入集合1：asd

输入集合2：asf

根据提示输入运算类型：1.并集

2.交集

3.差集

4.结束

x.重新运算

输入1，输出”fasd”

输入2，输出”as”

输入3，输出”d”

输入4，输出”press

any

key

to

continue”(结束)

输入其他数，输出”

1.并集

2.交集

3.差集

4.结束

x.重新运算”(重新选择运算类型)

下面是运行时的界面(附图):

五、参考资料

[1]

王昆仑，李红.

数据结构与算法.

北京：中国铁道出版社，2006年5月。

[2]

陈朔鹰，《C语言程序设计习题集（第二版）》，人民邮电出版社，2003.2

[3]

严蔚敏

吴伟民.

《数据结构(C语言版)

》.

北京:

清华大学出版社,2009

[4]

姜仲秋，《C语言程序设计》，南京大学出版社，1998.1

[5]

朱振元.

《数据结构(C++语言描述)

》.

北京:

清华大学出版社,2007

[6]

美]Paul

S.

R.

Chishohm等著，张芳妮

吕波译，《C语言编程常见问题解答清华大学出版社》，1996.12