《大数据结构实验》由会员分享，可在线阅读，更多相关《大数据结构实验（15页珍藏版）》请在金锄头文库上搜索。
1、实用标准实验报告实验课程：实验项目：实验一集合的并交差运算 专 业：班 级：姓名：学号：指导教师:文案大全一、问题定义及需求分析(1) 实验目的(2) 实验任务(3)需求分析二、概要设计：(1) 抽象数据类型定义(2) 主程序流程(3) 模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析算法时空分析经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1) 源代码一、问题定义及需求分析(1) 实验目的设计一个能演示集合的并、交、差运算程序。(2) 实验任务1) 采用顺序表或链表等数据结构。2) 集合的元素限定为数字和小写英文字母。(
2、3) 需求分析：输入形式为：外部输入字符串；输入值限定范围为：数字和小写英文字母；输出形式为：字符集；程序功能：计算两个集合的交、并、差以及重新输入集合功能;二、概要设计：(1) 抽象数据类型定义：线性表(2) 主程序流程：调用主菜单函数始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息初始化两个线性表 创建选择功能菜单界面通过不同选项调用不同功能函数 在每个功能函数里面加结束选择功能，实现循环调用功能菜单 计算完毕退出程序；(3) 模块关系：三、详细设计抽象数据类型定义： typedef structElemType *elem; in t le ngth; in t listsi
3、ze;SqList;存储结构：顺序表;模块1-在顺序表的逻辑为i的位置插入新元素e的函数;算法如下：/*在顺序表的逻辑为i的位置插入新元素 e的函数*/Status List In sert_Sq(SqList &L,i nt i,ElemType e)的合法值为(1 = i = L.length_Sq(L)ElemType *n ewbase,*p,*q;if(i L.length + 1) return 0;/i+ 1) if(L.len gth = L.li stsize)/当前储存空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.list
4、size+ LISTINCREMENT) *储存分配失败新基址增加储存容量为插入位置插入位置及之后的元素往右移 插入e 表长加1sizeof(ElemType);if(!n ewbase) exit(-1);/L.elem = n ewbase;/L.listsize += LISTINCREMENT; /q = & (L.elemi - 1);/qfor(p = & (L.elemL.le ngth - 1); p = q; -p)(p + 1) = p;/q = e;/+L.le ngth;/return 1;模块二在顺序线性表L中查找第1个与e满足compare。的元素位序，若找到， 则
5、返回其在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.le ngth & !(* compare)(*p+,e)+i;/从表L中的第一个元素开始与e比较，直到找到L中与e相等的元素时返回该元素的位
6、置if(i = L.length) return i; /若i的大小小于表长，则满足条件返回i elsereturn 0;/否则，i值不满足条件，返回 0模块三集合交运算/*求集合的交集的函数*/算法如下:void Mix_Sq(SqList La,SqList Lb,SqList &Lc) int i;ElemType elem;Lc.le ngth = 0;/for(i = 1; i = La.len gth; i+) /elem = La.elemi-1;/if(LocateElem_Sq(Lb,elem,Equal) / 素ListI nsert_Sq(Lc,Lc.le ngth+1,
7、elem); /中将表Lc的长度设为0依次查看表La的所有元素将表La中i位置的元素赋值给 elem在表Lb中查找是否有与elem相等的元将表La与Lb中共同的元素放在Lc模块四集合并运算 算法如下: /*求集合的并集的函数*/void Un ion_Sq(SqList La,SqList Lb,SqList &Lc)int i;ElemType elem;将表Lc的长度初设为0先将表La的元素全部复制到表Lc.le ngth=0;/for(i = 0; i La.len gth; i+)/Lc中Lc.elemLcen gth+=La.elemi;for(i = 1; i = Lb.len g
8、th; i+)依次将表Lb的值赋给elem判断表La中是否有与elem相同若有的话将 elem放入表Lcelem = Lb.elemi-1;/if(!LocateElem_Sq(La,elem,Equal) /的值ListI nsert_Sq(Lc,Lc.le ngth+1,elem);/中模块五集合的差运算算法如下:/*求集合的差集函数*/void Differ_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;/
9、elemif(!LocateElem_Sq(Lb,elem,Equal)/同的元素ListI nsert_Sq(Lc,Lc.le ngth+1,elem);/中，否则，就不存放for(i = 1; i = Lb.len gth; i+)elem = Lb.elemi-1;/elemif(!LocateElem_Sq(La,elem,Equal)/同的元素ListI nsert_Sq(Lc,Lc.le ngth+1,elem);/中，否则，就不存放把表La中第i个元素赋值给判断elem在表Lb中是否有相若有，则把elem放入表Lc把表Lb中第i个元素赋值给判断elem在表La中是否有相若有，则把
10、elem放入表Lc四、调试分析导致集LIST INIT SIZE 100 和 #define问题分析及解决：首先，在编写程序时没有设置线性表的初始长度, 合元素输入错误；然后通过#defi neLISTINCREMENT 1 解 决;compare)(ElemType,ElemType)时空分析：int LocateElem_Sq(SqList L,ElemType e,Status(*时间复杂度为0( n);时间复杂度为O(m* n);时间复杂度为O(m* n);时间复杂度为O(2*m* n);时间复杂度为O(n);Status List In sert_Sq(SqList &L,i nt
11、i,ElemType e) void Un ion_Sq(SqList La,SqList Lb,SqList &Lc) void Mix_Sq(SqList La,SqList Lb,SqList & Lc) void Differ_Sq(SqList La,SqList Lb,SqList &Lc)然后在于另外的集改进设想： 当同时求两个以上的结合间的运算是需要先进性两个集合间的运算， 合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会：顺序表使用起来比较简单， 但长度不可随意变化， 适用于大量访问元素， 而不适用于大 量增添和删除元素；在内存中存储地址连续；五、使用说明第
12、一步：点击运行按钮；第二步：根据提示输入集合A（可以连续输入，只限输入小写字母和数字）； 第三步：程序自动显示输入结果； 第四步：输入集合B （同第二步）；第五步：跳出主菜单界面；第六步：根据选项输入对应运算项的数字序号； 第七步：显示运算结果，并可继续进行选择运算还是退出； 第八步：若继续运算则返回主菜单，否则退出； 第九步：循环第六、七、八步，直至选择退出；六、测试结果输入界面： F:CodeBI ocksJ一 X 欢迎使用集合操作运算器请输入集合A: 12霧be 集合A为1 2 3 a b c 此集合中的个数n二6请输入集合B：345cde集合B为3 4 5 c d e 此集合中的个数n
13、 = &*请输入您的操作选项1、2、8、4. *1、进亍集合的井运算2、进行集合的交运算皐进行集合的差运算4.重新建立两个集合并运算结果: F:5deEllgGJ玻结恂宾验一寰合2,曲口X集音A与集合B的并集为：123abc45de卜此集合中的个数n = 10继续计算请输入1,停止计算请输入0F:CodeBI-=2.6X6*请输人您的操作选项1、2、粘4、*K进行集合的并运算2.进行集合的交运算 父进行集合的差运算4、重薪建立两个集合交运算结果:3 F忙odmBlocks读I握结构妄螫一便舍2上- X集合沟集合目的交集为：3 c此集合中的个数n = 2聲计算请输入1,停止计算请输入0A1 FASckBIcxki；逵屋结构蹲一懐合2冶畑X*请输入您朗操作选顶K 2s g、4. *+K进行集合的并运算2.进行集合的交运算进行集合的差运算4、重薪建吉两个集合A差运算结果: F:Code EM2.exe-X集合疥集合B的差集为:1 2 a b 4 5 d e 此集合中的个数n二B讎续计算请输入1，停止计算请输入01A1 F:Codeeiac ksSig-
