实 验 报 告
实验课程:数 据 结 构
实验项目:实验一集合的并交差运算
专 业:计算机科学与技术
班 级:
姓 名:
学 号:
指导教师:
目 录
1、问题定义及需求分析
(1)实验目的
(2)实验任务
(3)需求分析
二、概要设计:
(1)抽象数据类型定义
(2)主程序流程
(3) 模块关系
3、详细设计
(1)数据类型及存储结构
(2)模块设计
4、调试分析
(1)调试分析
(2)算法时空分析
(3)经验体会
5、
(1)程序使用说明
6、测试结果
(1)运行测试结果截图
7、附录
(1)源代码
1、问题定义及需求分析
(1)实验目的
设计一个能演示集合的并、交、差运算程序。
(2)实验任务
1)采用顺序
或链表等数据结构。
2)集合的元素限定为数字和小写英文字母。
(3)需求分析:
输入形式为:外部输入字符串;
输入值限定范围为:数字和小写英文字母;
输出形式为:字符集;
程序功能:计算两个集合的交、并、差以及重新输入集合功能;
2、概要设计:
(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);