数据结构实验-集合的并交差运算实验报告

实 验 报 告

实验课程：数 据 结 构

实验项目：实验一集合的并交差运算

专 业：计算机科学与技术

班 级：

姓 名：

学 号：

指导教师：

目 录

一、问题定义及需求分析

（1）实验目的

（2）实验任务

（3）需求分析

二、概要设计：

(1)抽象数据类型定义

(2)主程序流程

(3) 模块关系

三、详细设计

(1)数据类型及存储结构

(2)模块设计

四、调试分析

(1)调试分析

(2)算法时空分析

(3)经验体会

五、使用说明

(1)程序使用说明

六、测试结果

(1)运行测试结果截图

七、附录

(1)源代码

一、问题定义及需求分析

（1）实验目的

设计一个能演示集合的并、交、差运算程序。

（2）实验任务

1)采用顺序表或链表等数据结构。

2)集合的元素限定为数字和小写英文字母。

（3）需求分析：

输入形式为:外部输入字符串；

输入值限定范围为:数字和小写英文字母；

输出形式为：字符集；

程序功能:计算两个集合的交、并、差以及重新输入集合功能；

二、概要设计：

(1)抽象数据类型定义：

线性表

(2)主程序流程：

调用主菜单函数

初始化两个线性表作为集合

给两个集合输入数据 输出集

合数据元素信息 另初始化两个线性表 创建选择功能菜单界面 通过不同选

项调用不同功能函数 在每个功能函数里面加结束选择功能，实现循环调用功能菜单

计算完毕退出程序；

（3）模块关系：

主菜单

差运算 并运算 交运算 新建集合 结束/返回

结束

三、详细设计

抽象数据类型定义：

typedef struct{

ElemType *elem;

int length;

int listsize; }SqList;

存储结构：顺序表；

模块1-在顺序表的逻辑为i的位置插入新元素e的函数；

算法如下：

/**在顺序表的逻辑为i的位置插入新元素e的函数**/

Status ListInsert_Sq(SqList &L,int i,ElemType e)

{

ElemType *newbase,*p,*q;

if(i < 1 || i > L.length + 1) return 0; //i的合法值为(1 <= i <= L.length_Sq(L) + 1)

if(L.length >= L.listsize)

{ //当前储存空间已满，增加分配

newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));

if(!newbase) exit(-1); //储存分配失败

L.elem = newbase; //新基址

L.listsize += LISTINCREMENT; //增加储存容量

}

q = &(L.elem[i - 1]); //q为插入位置

for(p = &(L.elem[L.length - 1]); p >= q; --p)

(p + 1) = p; //插入位置及之后的元素往右移

q = e; //插入e

++L.length; //表长加1

return 1;

}

模块二在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0

算法如下：

/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0**/

int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType))

{

ElemType *p;

int i;

i = 1; //i的初值为第1个元素的位序

p = L.elem; //p的初值为第1个元素的储存位置

while(i <= L.length && !(* compare)(*p++,e))

++i; //从表L中的第一个元素开始与e比较，直到找到L中与e相等的元素时返回该元素的位置

if(i <= L.length) return i; //若i的大小小于表长，则满足条件返回i

else

return 0; //否则，i值不满足条件，返回0

}

模块三集合交运算

算法如下：

/**求集合的交集的函数**/

void Mix_Sq(SqList La,SqList Lb,SqList &Lc)

{

int i;

ElemType elem;

Lc.length = 0; //将表Lc的长度设为0

for(i = 1; i <= La.length; i++)

{ //依次查看表La的所有元素

elem = La.elem[i-1]; //将表La中i位置的元素赋值给elem

if(LocateElem_Sq(Lb,elem,Equal)) //在表Lb中查找是否有与elem相等的元素

ListInsert_Sq(Lc,Lc.length+1,elem); //将表La与Lb中共同的元素放在Lc中

}

}

模块四集合并运算

算法如下：

/**求集合的并集的函数**/

void Union_Sq(SqList La,SqList Lb,SqList &Lc)

{

int i;

ElemType elem;

Lc.length=0; //将表Lc的长度初设为0

for(i = 0; i < La.length; i++) //先将表La的元素全部复制到表Lc中

Lc.elem[Lc.length++]=La.elem[i];

for(i = 1; i <= Lb.length; i++)

{

elem = Lb.elem[i-1]; //依次将表Lb的值赋给elem

if(!LocateElem_Sq(La,elem,Equal)) //判断表La中是否有与elem相同的值

ListInsert_Sq(Lc,Lc.length+1,elem); //若有的话将elem放入表Lc中

}

}

模块五集合的差运算

算法如下：

/**求集合的差集函数**/

void Differ_Sq(SqList La,SqList Lb,SqList &Lc)

{

int i;

ElemType elem;

Lc.length = 0;

for(i = 1; i <= La.length; i++) {

elem = La.elem[i-1]; //把表La中第i个元素赋值给elem

if(!LocateElem_Sq(Lb,elem,Equal)) //判断elem在表Lb中是否有相同的元素

ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放

}

for(i = 1; i <= Lb.length; i++)

{

elem = Lb.elem[i-1]; //把表Lb中第i个元素赋值给elem

if(!LocateElem_Sq(La,elem,Equal)) //判断elem在表La中是否有相同的元素

ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放

}

}

四、调试分析

问题分析及解决：首先，在编写程序时没有设置线性表的初始长度，导致集合元素输入错误；然后通过#define LIST_INIT_SIZE 100和#define LISTINCREMENT

10解决；

时空分析：

int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType))时间复杂度为O(n);

Status ListInsert_Sq(SqList &L,int i,ElemType e) 时间复杂度为O(n);

void Union_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);

void Mix_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);

void Differ_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(2*m*n);

改进设想：

当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；

经验体会：

顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大量增添和删除元素；在内存中存储地址连续；