1、 计算机科学与技术系 课程设计报告 20122013 学年第二学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 集合的并、交和差运算 学生姓名学生姓名 学号学号 专业班级专业班级 指导教师指导教师 2013 年 6 月 题目：题目： 集合的并、交和差运算集合的并、交和差运算 【问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】 (1) 集合的元素限定为小写字母字符 az 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】 (1)Set1=“magazine“，Set2=“paper“， Set1Set2=“aegimnprz“，S
2、etl Set2=“ae“，Set1-Set2=“gimnz“。 (2)Set1= “ 012oper4a6tion89“，Set2=“error data“， Set1Set2=“adeinoprt“，Setl Set2=“aeort“，Set1-Set2=“inp“。 【实现提示】 以有序链表表示集合。 【选作内容】 (1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。 (3) 集合的混合运算表达式求值。 (4) 集合的元素类型推广到其他类型 ， 甚至任意类型。 一、一、 实验内容实验内容 实验题目：编制一个演示集合的并、交和差运算的程序。 需求分析： 1、 本演示程序中，集合的
3、元素限定为小写字母字符“a”z”。集合输入的形式为一个以 “回车符“为结束标志的字符串，串中字符顺序不限。 2、 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后， 由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其 后。 3、 程序执行的命令包括： 1） 构造集合 1；2）构造在集合 2；3）求并集；4）求交集；5)求差集；6）返回；7）结束。 “构造集合 1”和“构造集合 2”时，需以字符的形式键入集合元素。 二、数据结构设计二、数据结构设计 为了实现上述程序的功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表 和集合。 1、
4、有序表的抽象数据类型定义为： 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。
5、 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
6、） 集合单元模块实现集合获得抽象数据类型； 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(“
