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

《数据结构实验-集合的并交差运算实验报告.pdf》由会员分享，可在线阅读，更多相关《数据结构实验-集合的并交差运算实验报告.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告 实验课程：_ 实验项目：实验一集合的并交差运算 专 业：_ 班 级：_ 姓 名:_ 学 号:_ 指导教师:_ 一、问题定义及需求分析(1)实验目的(2)实验任务(3)需求分析 二、概要设计：(1)抽象数据类型定义(2)主程序流程(3)模块关系 三、详细设计(1)数据类型及存储结构(2)模块设计 四、调试分析(1)调试分析(2)算法时空分析(3)经验体会 五、使用说明(1)程序使用说明 六、测试结果(1)运行测试结果截图 七、附录(1)源代码、问题定义及需求分析(1)实验目的 设计一个能演示集合的并、交、差运算程序。(2)实验任务 1)采用顺序表或链表等数据结构。2)集合的元素限定为数

2、字和小写英文字母。(3)需求分析：输入形式为：外部输入字符串；输入值限定范围为：数字和小写英文字母；输出形式为：字符集；程序功能：计算两个集合的交、并、差以及重新输入集合功能;二、概要设计：(1)抽象数据类型定义：线性表(2)主程序流程：调用主菜单函数始化两个线性表作为集合给两个集合输入数据输出集 合数据元素信息初始化两个线性表 创建选择功能菜单界面通过不同选 项调用不同功能函数 在每个功能函数里面加结束选择功能，实现循环调用功能菜单 计算完毕退出程序；(3)模块关系：三、详细设计 抽象数据类型定义：typedef struct ElemType*elem;in t le ngth;in t

3、listsize;SqList;存储结构：顺序表;模块 1-在顺序表的逻辑为 i 的位置插入新元素 e 的函数;算法如下：/*在顺序表的逻辑为 i 的位置插入新元素 e 的函数*/Status List In sert_Sq(SqList&L,i nt i,ElemType e)ElemType*n ewbase,*p,*q;if(i L.length+1)return 0;/i 的合法值为(1=i=L.li stsize)/当前储存空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(Ele

4、mType);if(!n ewbase)exit(-1);L.elem=n ewbase;/储存分配失败/新基址 L.listsize+=LISTINCREMENT;q=&(L.elemi-1);/增加储存容量 q 为插入位置 for(p=&(L.elemL.le ngth-1);p=q;-p)(p+1)=p;q=e;+Len gth;return 1;插入位置及之后的兀素往右移 II插入 e/表长加 1 模块二在顺序线性表 L 中查找第 1 个与 e 满足 compare()的元素位序，若找到，则返回其在 L 中的位序，否则返回 0 算法如下：/*在顺序线性表 L 中查找第 1 个与 e 满

5、足 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.le ngth&!(*compare)(*p+,e)if(i=L.len gth)return i;else return 0;/否则，i 值不满足条件，返回 0+i;与 e 相等的元素时返回该元素的位置/从表

6、L 中的第一个兀素开始与 e 比较，直到找到 L 中/若 i 的大小小于表长，则满足条件返回 i 算法如下:模块三集合交运算/*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList&Lc)int i;ElemType elem;Lcen gth=0;for(i=1;i=La.len gth;i+)elem=La.elemi-1;if(LocateElem_Sq(Lb,elem,Equal)ListI nsert_Sq(Lc,Lcen gth+1,elem);II将表 Lc 的长度设为 0/依次查看表 La 的所有元素 II 将表 La 中 i 位置

7、的元素赋值给 elem II 在表 Lb 中查找是否有与 elem 相等的元素 II 将表 La 与 Lb 中共同的元素放在 Lc 中 模块四集合并运算 I*求集合的并集的函数*I 算法如下:void Union_Sq(SqList La,SqList Lb,SqList&Lc)int i;ElemType elem;Lcen gth=0;for(i=0;i La.len gth;i+)Lc.elemLcen gth+=La.elemi;for(i=1;i=Lb.len gth;i+)elem=Lb.elemi-1;if(!LocateElem_Sq(La,elem,Equal)ListI n

8、sert_Sq(Lc,Lcen gth+1,elem);II 将表 Lc 的长度初设为 0 II 先将表 La 的元素全部复制到表 Lc 中 II 依次将表 Lb 的值赋给 elem II 判断表 La 中是否有与 elem 相同的值 II 若有的话将 elem 放入表 Lc 中 模块五集合的差运算 算法如下:I*求集合的差集函数*I void Differ_Sq(SqList La,SqList Lb,SqList&Lc)int i;ElemType elem;Lcen gth=0;for(i=1;i=La.len gth;i+)四、调试分析 问题分析及解决：首先，在编写程序时没有设置线性表

9、的初始长度，导致集 合元素输入错误；然后通过#define LIST_INIT_SIZEOO 和#define LISTINCREMENT 10 解决；时空分析：int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)时间复杂 度为0(n);Status ListI nsert_Sq(SqList&L,i nt i,ElemType e)时间复杂度为 0(n);void Union_Sq(SqList La,SqList Lb,SqList&Lc)时间复杂度为 O(m*n);void Mix_Sq(SqL

10、ist La,SqList Lb,SqList&Lc)时间复杂度为 O(m*n);void Differ_Sq(SqList La,SqList Lb,SqList&Lc)时间复杂度为 O(2*m*n);改进设想：当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集 合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会：顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大 量增添和删除元素；在内存中存储地址连续；五、使用说明 第一步：点击运行按钮；第二步：根据提示输入集合 A(可以连续输入，只限输入小写字母和数字)；第三步：程序自动

11、显示输入结果；第四步：输入集合 B(同第二步)；elem=La.elemi-1;if(!LocateElem_Sq(Lb,elem,Equal)ListI nsert_Sq(Lc,Lcen gth+1,elem);则，就不存放 for(i=1;i=Lb.len gth;i+)elem=Lb.elemi-1;if(!LocateElem_Sq(La,elem,Equal)兀素 ListI nsert_Sq(Lc,Lcen gth+1,elem);则，就不存放/把表 La 中第 i 个元素赋值给 elem/判断 elem 在表 Lb 中是否有相同的/若有，则把 elem 放入表 Lc 中，否/把表

12、 Lb 中第 i 个元素赋值给 elem/判断 elem 在表 La 中是否有相同的/若有，则把 elem 放入表 Lc 中，否 跳出主菜单界面；根据选项输入对应运算项的数字序号；显示运算结果，并可继续进行选择运算还是退出;若继续运算则返回主菜单，否则退出；循环第六、七、八步，直至选择退出；六、测试结果 输入界面:玻结起略一台乙母g 欢迎使用集合操作运算器 请输入集合A:123abc 集合A为1 2 3 a b c 此集合中的个数n=6 请输入集合B：345cde 集合B为3 4 5 c d e 此集合中的个数n=6*请输入您的操作选项1、2、8、4.*1、进行集合的并运算 鉄进疔集合的交运算

13、 3.进行集合的差运算 冬重新建立两个集合 并运算结果：F:CodeBl Gurks 2.exe 继续计算请输入h停止计算请输入0 RCode6l 2.exe 屈刖人您的操作选项 1、2、2、4,甘档:*进行集合的并运算 进行集合的交运算 进行集合的差运算 重新蠢立两个集合 第五步:第六步:第七步:第八步:第九步:k 2.3、交运算结果：13班匸屛魂10：応读I握结构妄验一濮舍NBM-X 燈计算请输入1,停止计算请输入0:a F:5ckBlcxki；谓腊结构毘验一懐合2冶畑 X *请输入圾的操件选项1、2s鉄4.*+A 1、进行集合的并运算 2、进行集合的交运算 缶进行集合的差运算 4、重薪建

14、吉两个集合 差运算结果:琨匚口血El*“1旅结梅妄瞪一AM合2占畑 X 集合底奥合B的差集为：1 2 b 4 5 d m A 此集合中的个数n二B 讎续计算请输入1，停止计算请输入0 1 1 F:CodeBI oc 2.exe X+*+请输人您的噪作选项1、2、3、4.+k 进行集合的并运算 进行集合的交运算 2.3.进行集合的差运算 4.重新建立两个集合 重新建立集合并运算：F：UEZW備结扫丈验一偉合2一吨 X 请输入集合A：7S9efE 集合妙?E 9 e f g 此集合中的个数n二6 请辅人集合D:67Sdef 集合为6 7 S d s f 此集合中的个数n=6 七、附录#i nclu

15、de#i nclude#defi ne LIST_INIT_SIZE 10)(初 始表空间大小 4.重新建立两个集合#defi ne LISTINCREMENT 1表长增量 typedef int Status;/*Status 是函数类型*/typedef char ElemType/*ElemType 类型根据实际情况而定，这里假设为 char*/typedef struct ElemType*elem;/*储存空间基地址*/int length;/*当前长度*/int listsize;/*当前分配的储存容量(以 sizeof(Elemtype)为单位)*/SqList;SqList L

16、a,Lb,Lc,L/*定义全局变量*/*构造一个空的线性表 L*/Status In itList_Sq(SqList&L)_ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(-1);/*储存分配失败*/L.le ngth=0;L.listsize=LIST_INIT_SIZ*E;初始储存容量*/return 1;/*在顺序表的逻辑为 i 的位置插入新元素 e 的函数*/Status ListI nsert_Sq(SqList&L,i nt i,ElemType e)_ ElemType*n ew

17、base,*p,*q;if(i L.length+1)return 0;if(L.length=L.listsize)当前储存空间已满，增加分配 n ewbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!n ewbase)exit(-1);/储存分配失败 L.elem=n ewbase;L.listsize+=LISTINCREMEN 增加储存容量 q=&(L.elemi-1)q 为插入位置 for(p=&(L.elemL.len gth-1);p=q;-p)*(p+1)=*p;/插入位

18、置及之后的元素往右移*q=e;插入 e+Len gth;return 1;/*创建一个线性表，输入数据*/void CreateList_Sq(SqList&L)_ ElemType ch=0;int in list=0,j;while(ch)!=n)sca nf(%c，&ch);/输入数据 for(j=0;j Len gth;j+)if(ch=L.elemj)/判断表 L 中是否有与 ch 相等的元素 in list=1;/若有，则 in list 置 1 break;/跳出本轮循环 else iniist=0;/否则 inlist 为 0 if(!i nlist&ch!=n)/若 in l

19、ist 为 0 且 ch 不为”n”ListInsert_Sq(L,L.length+1,ch);/则将 ch 存入表 L 中 /*判断两元素是否相等若相等则返回 1;否则返回 0*/Status Equal(ElemType a,ElemType b)if(a=b)return 1;/相等，返回 1 else return 0;/否则，返回 0 /*在顺序线性表 L 中查找第 1 个与 e 满足 compare()的元素位序，若找到，则返 回其在L 中的位序，否则返回 0*/int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(Elem

20、Type,ElemType)_ ElemType*p;int i;i=1;p=L.elem/p 的初值为第 1 个元素的储存位置 while(i=L.length&!(*compare)(*p+,e)循环查找表 L 找出其中与 e 相等的 元素的位置+i；if(i=L.length)/若 i 小于表长 return i;/则 i 满足条件，返回 i 的值 else return 0;/否则返回 0 /*销毁线性表的函数*/Status Clear_Sq(SqList&L)_ ElemType elem;free(L.elem);L.elem=NULL;return 1;/*打印顺序表函数*/v

21、oid Prin t_Sq(SqList L)_ int i;for(i=0;i Len gth;i+)printf(%2c,L.elemi);通过 for 循环将表元素全部输出 if(L.length=0)printf(空集);/若表长为 0,则输出空表 prin tf(nttt 此集合中的个数 n=%dnn,L.le ngth);/*求集合的并集的函数*/void Union _Sq(SqList La,SqList Lb,SqList&Lc)_ int i;ElemType elem;Lc.length=O;/将表 Lc 的长度初设为 0 for(i=0;i La.length;i+)/

22、先将表 La 的元素全部复制到表 Lc 中 Lc.elemLc.le ngth+=La.elemi;for(i=1;i=Lb.len gth;i+)if(!LocateElem_Sq(La,elem,Equal)/判断表 La 中是否有与 elem 相同的值 一 ListInsert_Sq(Lc,Lc.length+1,elem);/若有的话将 elem 放入表 Lc 中 /*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList&Lc)_ int i;ElemType elem;Lc.len gth=0;II将表 Lc 的长度设为 0 for(i=

23、1;i=La.len gth;i+)elem=La.elemi-1;elem/依次查看表 La 的所有元素 II 将表 La 中 i 位置的元素赋值给 if(LocateElem_Sq(Lb,elem,Equal)在表 La 中查找是否有与 elem 相等的元素 ListInsert_Sq(Lc,Lc.length+1,elem)将表 La 与 Lb 中共同的元素放在 Lc 中 _ /*求集合的差集函数*/void Differ_Sq(SqList La,SqList Lb,SqList&Lc)_ int i;ElemType elem;Lc.len gth=0;for(i=1;i=La.le

24、n gth;i+)elem=La.elemi-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*K进行集合的并运算 2.进行集合的交运算 氣进彳亍集合的差运算 system(cls);prin tf(ntt*int main()谢谢使用!*n);prin tf(tt*欢迎使用集合操作运算器*n);继续计算请输入 1,停止计算请输入 0 n);