发布时间 : 星期日 文章数据结构课程设计报告--集合的并、交和差运算更新完毕开始阅读d3d42c2a640e52ea551810a6f524ccbff121ca98
题目: 集合的并、交和差运算
【问题描述】
编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】
(1) 集合的元素限定为小写字母字符 [?a?..?z?] 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】
(1)Set1=\,Set2=\,
Set1∪Set2=\,Setl ∩Set2=\,Set1-Set2=\。 (2)Set1= \,Set2=\,
Set1∪Set2=\,Setl ∩Set2=\,Set1-Set2=\。 【实现提示】
以有序链表表示集合。 【选作内容】
(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
typedef struct LNode//定义结构体类型指针 { char data; struct LNode*next; }*pointer;
void readdata(pointer head)//定义输入集合函数
{ pointer p; char tmp; scanf(\ while(tmp!='\\n') { p=(pointer)malloc(sizeof(struct LNode)); p->data=tmp; p->next=head->next; head->next=p; scanf(\ } }
void pop(pointer head)//定义输出集合函数 { pointer p; p=head->next; while(p!=NULL) { printf(\ p=p->next; } printf(\}
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)&&(p1->data!=p2->data)) p1=p1->next; 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)&&(p2->data!=p1->data)) p2=p2->next; if((p2!=NULL)&&(p2->data==p1->data)) { p3=(pointer)malloc(sizeof(struct LNode)); p3->data=p1->data; p3->next=head3->next; head3->next=p3; } p1=p1->next; } }
void differ(pointer head1,pointer head2,pointer head3)//定义集合的差集函数 {