2024年3月12日发(作者：)
实验报告
题目：编制一个演示集合的并、交、和差运算的程序
一、问题描述：设计一个程序，要求实现集合的并、交、和差的运算
二、需求分析
1. 本演示程序中，集合的元素限定为数字。
2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，
由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法
字符）和运算结果显示在其后。
3. 程序执行的命令包括：
1） 构造集合1；2）构造集合2；3）求并集；4)求交集；5）求差集；6）结束。
“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。
4． 测试数据
（1） A={1、2、3、4、9} B={2、3、5、7、8}
A∪B={9、4、3、2、1、8、7、5} A∩B={3、2} A－B={9、4、1}
三、概要设计
为实现上述程序功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集
合
1. 有序表的抽象数据类型定义为：
ADT OrderedList{
数据对象：D={ai|ai∈CharSet,i=1,2,„,n,n>=0}
数据关系：R1={ 基本操作： InitList(&L) 操作结果：构造一个空的有序表L。 DestroyList(&L) 初始条件：有序表L已存在 操作结果：销毁有序表L。 CreateList（&L，n） 操作结果：构造一个含有n个元素的链表L。 ListLength(L) 初始条件：链表L已经存在。 操作结果：返回L中数据元素的个数。 GetElem(L,i,&e) 初始条件：链表L已经存在。 操作结果：用e返回L中第i个元素的值。 Equal（c1，c2） 初始条件：链表L已经存在且不为空。 操作结果：判断链表L中两元素是否相等，若相等则返回true，否则返回false。 LocateElem(L,e,equal) 初始条件：链表L已经存在，Equal是数据元素的判定函数。 操作结果：返回L中第一个与e满足关系Equal的数据元素的位序。若这样 的元素不存在，则返回值为0。 ListInsert(&L,I,e) 初始条件：链表L已经存在，1<=i<=ListLength(L)+1. 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelete(&L,I,&e) 初始条件：链表L已经存在且非空，1<=i<=ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit()) 初始条件：链表L已经存在。 操作结果：依次对L中每个数据元素调用函数visit（）。一旦visit（）失 败，则操作失败。 Append(%L,e) 初始条件:有序表L已存在。 操作结果：在有序表L的末尾擦人元素e。 }ADT OrderedList 2. 集合的抽象数据类型定义为： ADT Set{ 数据对象：D={ai|ai为小写英文字母且互不相同，i=1,2,„,n,0<=n<=26} 数据关系：R1={ } 基本操作： CreatSet(&T,Str) 初始条件：Str为字符串 操作结果：生成一个由Str中小写字母构成的集合T。 DestroySet(&T) 初始条件：集合T已存在 操作结果：销毁集合T的结构。 Union(&T,S1,S2) 初始条件：集合S1和S2存在 操作结果：生成一个由S1和S2的并集构成的集合T。 Intersection(&T,S1,S2) 初始条件：集合A和B已经存在。 操作结果：生成一个由A和B的交集构成的集合T。 Difference(&T,A,B) 初始条件：集合A和B已经存在。 操作结果：生成一个由A和B的差集构成的集合T。 PrintSet(T) 初始条件：集合T已经存在。 操作结果：将集合T中的元素打印出来。 }ADT Set 四、详细设计 1. 单链表的存储结构 typedef struct LNode { int data; struct LNode *next； }LNode, *LinkList; 2. 链表的基本操作的实现 void InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); if(!L)exit(OVERFLOW); L->next=NULL; } void CreateList(LinkList&L,int) { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;--i) p=(LinkList)malloc(sizeof(LNode)); printf(“please input the datas:n”); for(i=1;i<=n;i++) {p=(LinkList)malloc(sizeof(LNode)); scanf(“%d”,&p->data); p->next=L->next; L->next=p; } } 3. 集合的并运算 void Union(LinkList A,LinkList B,LinkList C) { LinkList pa=A->next,pb=B->next,pc,s,r; C=(LinkList)malloc(sizeof(LNode)); C->next=NULL; r=C; while(pa!=NULL) { s=(LinkList)malloc(sizeof(LNode)); s->data=pa->data; s->next=NULL; r->next=s;r=s; pa=pa->next; } while(pb!=NULL) { pc=C->next; while(pc!=Null&&pb->data!=pc->data) pc=pc->next; if(pc==NULL) {s=(LinkList)malloc(sizeof(LNode)); s->data=pb->data;s->next=NULL; r->next=s; r=s; } pb=pb->next; } r->next=NULL; 4. 集合的交运算 void Intersection(LinkList A, LinkList B, LinkList C) { LinkList pa=A->next, pb, s, r; C=( LinkList)malloc(sizeof(LNode)); C->next=NULL; r=C; while (pa!=NULL) { pb=B->next; while (pb!=NULL &&pb->data!=pa->data) pb=pb->next; if (pb!=NULL) { s=( LinkList)malloc(sizeof(LNode)); s->data=pa->data;s->next=NULL; r->next=s; r=s; } pa=pa->next; } r->next=NULL; } 5. 集合的差运算 void Diffence(LinkList A, LinkList B, LinkList C) { LinkList pa=A->next, pb, s, r; C=( LinkList)malloc(sizeof(LNode)); C->next=NULL; r=C; while (pa!=NULL) { pb=B->next; while (pb!=NULL && pb->data!=pa->data) pb=pb->next; if(pb==NULL) { s=( LinkList)malloc(sizeof(LNode)); s->data=pa->data; s->next=NULL; r->next=s; r=s; } pa=pa->next; } r->next=NULL; } 五、测试： 结果如下图：
发布评论