logo资料库

华科计院数据结构报告-1.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.26M 资料格式：docx 举报 版权申诉
第1页 / 共41页
第2页 / 共41页
第3页 / 共41页
第4页 / 共41页
第5页 / 共41页
第6页 / 共41页
第7页 / 共41页
第8页 / 共41页
资料共41页，剩余部分请下载后查看
    1 基于顺序存储结构的线性表实现
    1.1 问题描述
    1.1.1 实验目的
    1.1.2 实验要求及实现
    1.2 系统设计
    1.2.1 系统总体设计
    1.2.2 算法设计
    1.3 系统实现
    1.3.1 功能模块实现
    1.3.2 系统测试。
    1.4 实验小结
    2 基于链式存储结构的线性表实现
    2.1 问题描述
    2.2 系统设计
    2.3 系统实现
    2.4 实验小结
    3 基于二叉链表的二叉树实现
    3.1 问题描述
    3.2 系统设计
    3.3 系统实现
    3.4 实验小结
    4 基于邻接表的图实现
    4.1 问题描述
    4.2 系统设计
    4.3 系统实现
    4.4 实验小结
    参考文献
    附录A 基于顺序存储结构线性表实现的源程序
    附录B 基于链式存储结构线性表实现的源程序
    附录C 基于二叉链表二叉树实现的源程序
    附录D 基于邻接表图实现的源程序
    课 程 实 验 报 告 课程名称： 数据结构实验 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术学院
    华中科技大学计算机学院数据结构实验报告 目 录 1 基于顺序存储结构的线性表实现 ..................................... 3 1.1 问题描述 ..................................................... 3 1.1.1 实验目的 ................................................... 3 1.1.2 实验要求及实现 ............................................. 3 1.2 系统设计 ..................................................... 4 1.2.1 系统总体设计 ............................................... 4 1.2.2 算法设计 ................................................... 4 1.3 系统实现 ..................................................... 5 1.3.1 功能模块实现 ............................................... 4 1.3.2 系统测试。 ................................................ 11 1.4 实验小结 ..................................................... 5 2 基于链式存储结构的线性表实现 .................................... 14 2.1 问题描述 .................................................... 14 2.2 系统设计 .................................................... 14 2.3 系统实现 .................................................... 14 2.4 实验小结 .................................................... 14 3 基于二叉链表的二叉树实现 ........................................ 16 3.1 问题描述 .................................................... 16 3.2 系统设计 .................................................... 16 3.3 系统实现 .................................................... 16 3.4 实验小结 .................................................... 16 4 基于邻接表的图实现 .............................................. 17 4.1 问题描述 .................................................... 17 4.2 系统设计 .................................................... 17 4.3 系统实现 .................................................... 17 4.4 实验小结 .................................................... 17 1
    华中科技大学计算机学院数据结构实验报告 参考文献 .......................................................... 18 附录 A 基于顺序存储结构线性表实现的源程序 ......................... 21 附录 B 基于链式存储结构线性表实现的源程序 ......................... 36 附录 C 基于二叉链表二叉树实现的源程序 ............................. 37 附录 D 基于邻接表图实现的源程序 ....................................39 2
    华中科技大学计算机学院数据结构实验报告 1 基于顺序存储结构的线性表实现 1.1 问题描述 1.1.1 实验目的 本次实验采用顺序表作为线性表的物理结构，构造一个具有菜单的功能演示 系统实现对线性表的操作，该系统可以实现多个线性表管理，选择实现线性表的 文件形式存取。 依据最小完备性和常用性相结合的原则，以函数形式定义了线性表的初始化 表、销毁表、清空表、判定空表、求表长和获得元素等 12 种基本运算供主函数 调用，以实现对线性表的操作。 1.1.2 实验要求及实现 实验所要完成的算法有：添加线性表；删除线性表；初始化线性表；销毁线 性表；清空线性表；判定线性表是否为空；取得线性长度；取得线性表指定位置 上的元素；取得线性表指定元素的位置；取得线性表中指定元素的前一个元素； 取得线性表中指定元素的后一个元素；在线性表指定位置插入元素；删除线性表 指定位置的元素；遍历线性表等。 实验中线性表的物理结构形式如图 1-1 所示。线性表分为主表和子表，主表 以顺序存储结构存储各个子表，对其进行管理，子表以顺序存储结构存储每个元 素。（以下说线性表默认为子表）。 图 1-1 顺序表物理结构示意图 3
    华中科技大学计算机学院数据结构实验报告 1.2 系统设计 1.2.1 系统总体设计 本程序使用顺序结构实现了线性表，能够对线性表进行添加删除修改等基本 操作，并且设计一个主表，可以对多个线性表进行操作。主表也采用顺序表的实 现方式，能进行动态分配。 程序具备 17 种操作：添加线性表；删除线性表；初始化线性表；销毁线性 表；清空线性表；判定线性表是否为空；取得线性长度；取得线性表指定位置上 的元素；取得线性表指定元素的位置；取得线性表中指定元素的前一个元素；取 得线性表中指定元素的后一个元素；在线性表指定位置插入元素；删除线性表指 定位置的元素；遍历线性表；存储数据到文件；从文件读取数据；退出。 其中初始化线性表 InitaList(L)；会在添加线性表的过程中自动调用，故不提 供用户调用接口；销毁线性表 DestroyList 由 DeleteList 自动调用，故也不提供用 户调用接口。 系统使用了两种类型的线性表进行实现，一个称之为主表，之后每次添加线 性表都会在主表上存储信息；每次添加到线性表称为子表，用于存储数据链。 系统还具有文件存储功能，选择存储数据到文件，可以将当前所有线性表的数据 存入指定的文件，之后退出系统再次进入时，依旧能使用从文件读取数据的操作 恢复之前的数据。 1.2.2 算法设计 AddList:判断主表的 length 是否大于等于 listsize，若是，重新分配存储空间。 在已有的线性表后添加一个线性表（线性表的元素设为 NULL，主表的长度增加 一）。时间复杂度为 O(1)，空间复杂度为 O(1)。 DeleteList:若输入的值合法，先销毁要删除的表，然后将该表后的线性表整 体前移一位，主表长度减一。时间复杂度为 O(n)，空间复杂度为 O(1)。 InitList:此函数由 AddList 自动调用；若线性表已被初始化，返回 ERROR， 否则为线性表分配空间，将 elem 初始化为 NULL，length 初始化为 0，listsize 初 始化为 LIST_INIT_SIZE。时间复杂度为 O(1)，空间复杂度为 O(1)。 DestroyList:此函数由 DeleteList 自动调用；释放为线性表动态分配的空间， 4
    华中科技大学计算机学院数据结构实验报告 将 elem 设为 NULL，length 设为 0。时间复杂度为 O(1)，空间复杂度为 O(1)。 ClearList:将线性表的 length 置为 0。时间复杂度为 O(1)，空间复杂度为 O(1)。 ListEmpty:判断 length 是否为 0。时间复杂度为 O(1)，空间复杂度为 O(1)。 ListLength:返回 length。时间复杂度为 O(1)，空间复杂度为 O(1)。 GetElem:若给定的位置不合法，返回 ERROR，否则输出指定位置的元素。 时间复杂度为 O(1)，空间复杂度为 O(1)。 LocateElem:遍历线性表，若找到给定元素，返回元素位置，否则返回 0。由 于要遍历线性表，故时间复杂度为 O(n)，空间复杂度为 O(1)。 PriorElem:遍历线性表，若找到给定元素，输出前一个元素。否则返回 ERROR。 由于要遍历线性表，故时间复杂度为 O(n)，空间复杂度为 O(1)。 NextElem:遍历线性表，若找到给定元素，输出后一个元素。否则返回 ERROR。 由于要遍历线性表，故时间复杂度为 O(n)，空间复杂度为 O(1)。 ListInsert:先判断位置是否合法，若 length 大于等于 listsize，则重新分配存 储空间，listsize 增加 LISTINCREMENT。将该位置及以后的元素整体后移一位， 再把要插入的元素放入该位置，将 length 加 1。由于平均要移动 n/2 个元素，故 时间复杂度为 O(n)，空间复杂度为 O(1)。 ListDelete: 先判断位置是否合法，输出该位置的元素。将该位置以后的元素 整体前移一位，将 length 减 1。由于平均要移动 n/2 个元素，故时间复杂度为 O(n)， 空间复杂度为 O(1)。 ListTraverse:遍历线性表，打印每一个元素。由于要遍历线性表，故时间复 杂度为 O(n)，空间复杂度为 O(1)。 SaveToFile：将当前所有线性表的数据存入指定文件。 LoadFromFile: 从指定文件加载数据，如果文件不存在，则返回失败。 1.3 系统实现 1.3.1 功能模块实现 一、多链操作功能实现 在程序运行的整个过程中，设计总表的结构体，作为总线性表，将指向每个 线性表指针存入到总表中，并在总表中设定子线性表个数及总表分配空间大小， 5
    华中科技大学计算机学院数据结构实验报告 实现程序可以对多个线性表进行操作。 在总表中添加线性表的基本操作中，首先判断是否有足够空间，没有则重新 分配，并对总表中长度进行增加；文件读取时，将文件中的线性表添加到总表之 中，同样涉及到空间分配和判断。 在总表中调用各个线性表进行基本运算时，涉及到判断线性表是否存在、显 示线性表的总数目、与用户交互选择需要的线性表和选择过程中出现错误的提示 等操作。 二、线性表基本运算实现 1、初始化表：函数名称是 InitaList(L)； 初始条件：线性表 L 不存在。 操作结果：构造一个空的线性表。 首先判断线性表是否已经存在，如果已经存在返回 INFEASTABLE，否则动态 分配一段长为 LIST_INIT_SIZE 的元素类型为 ElemType 的存储空间，如果分配失 败就显示溢出，不然将 length 设置为 0，listsize 设置为 LIST_INIT_SIZE，返 回 OK。 2、销毁表：函数名称是 DestroyList(L)； 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L。 如果线性表不存在，则返回 INFEASTABLE，不然将链表所在空间释放，并将 length 和 listsize 设置为 0，返回 OK。 3、清空表：函数名称是 ClearList(L)； 初始条件：线性表 L 已存在； 操作结果：将 L 重置为空表。 如果线性表不存在，则返回 INFEASTABLE，不然将线性表的 length 设置为 0， 返回 OK。 4、判定空表：函数名称是 ListEmpty(L)； 初始条件：线性表 L 已存在； 操作结果：若 L 为空表则返回 TRUE,否则返回 FALSE。 如果线性表不存在，则返回 INFEASTABLE，不然如果 length 不为 0，则返回 6
    华中科技大学计算机学院数据结构实验报告 TRUE,否则返回 FLASE。 5、求表长：函数名称是 ListLength(L)； 初始条件：线性表已存在； 操作结果：返回 L 中数据元素的个数。 如果线性表不存在，则返回 INFEASTABLE，不然返回线性表 length 的值。 6、获得元素：函数名称是 GetElem(L,i,e)； 初始条件：线性表已存在，1≤i≤ListLength(L)； 操作结果：用 e 返回 L 中第 i 个数据元素的值。 如果线性表不存在，则返回 INFEASTABLE，不然判断 i 是否满足初始条件， 如果不满足则返回 ERROR，否则将线性表第 i 个元素赋给 e，返回 OK。 7、查找元素：函数名称是 LocateElem(L,e)； 初始条件：线性表已存在； 操作结果：返回 L 中第 1 个与 e 满足关系 compare（）关系的数据元素的位 序，若这样的数据元素不存在，则返回值为 0。 如果线性表不存在，则返回 INFEASTABLE，不然从第一个元素开始和 e 进行 比较，如果有相等则返回该元素的序号，否则返回 0。 算法的流程如图 1-3 所示。 图 1-2 查找线性表元素的流程图 8、获得前驱：函数名称是 PriorElem(L,cur,pre_e)； 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料