为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

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

2019-04-21 11页 doc 54KB 129阅读

用户头像

is_014457

暂无简介

举报
数据结构实验-集合的并交差运算实验报告实  验  报  告 实验课程:数 据 结 构 实验项目:实验一集合的并交差运算 专  业:计算机科学与技术 班  级: 姓  名: 学  号: 指导教师: 目  录 1、问题定义及需求分析 (1)实验目的 (2)实验任务 (3)需求分析 二、概要设计: (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 3、详细设计 (1)数据类型及存储结构 (2)模块设计 4、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 5、使用说明 (1)程序使用说明 6、测试结果 (1)运行测试结果截图 ...
数据结构实验-集合的并交差运算实验报告
实  验  报  告 实验课程:数 据 结 构 实验项目:实验一集合的并交差运算 专  业:计算机科学与技术 班  级: 姓  名: 学  号: 指导教师: 目  录 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);
/
本文档为【数据结构实验-集合的并交差运算实验报告】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索