华中科技university计算机11级数据结构实验汇报.doc

课 程 设 计 报 告 课程名称： 数据结构 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术  目录 1 1.1问题描述 1 1.2系统设计 1 1.3.系统实现 1 1.4效率分析 5 实验二 基于链式结构的线性表实现 6 2.1问题描述 6 2.2系统设计 6 2.3系统实现 6 2.4效率分析 10 实验三 基于二叉链表的二叉树实现 11 3.1问题描述 11 3.2系统设计 11 3.3 系统实现 11 3.4 效率分析 17 四 实验总结与评价 17 实验一 1.1问题描述 基于顺序存储结构，实现线性表的基本的、常见的运算。 1系统设计 1提供 1. InitiaList 8. PriorElem 2. DestroyList 9. NextElem 3. ClearList 10. ListInsert 4. ListEmpty 11. ListDelete 5. ListLength 12. ListTrabverse 6. GetElem 13.Savelist 7. LocatElem 14.Loadlist 0. Exit 1.2.2物理结构为顺序存储结构，数据元素为包含一个整型变量的结构体： 1构建线性表之前先声明一个头结点，用于存储该表的基本信息和首结点地址： 1.3.系统实现List功能 初始化线性表，传入的是头结点地址。申请一个大小为LIST_INT_SIZE、类型为 1.3.2 DestroyList功能 销毁 1.3.3 ClearList功能 与List并不销毁物理空间，而是修改逻辑关系值： 1.3.4ListEmpt功能 判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。实现如下： 1.3.5ListLenth功能 求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可： 1.3.6GetElem功能 获取第i号元素，传入的是头结点值、元素编号i、以及出口表结点地址。 1.3.7LocatElem功能 ,O(n)。 1.3.8PriorElem功能 求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储表结点地址。主要思路是先调用Elem确定指定元素的位置，如果不是首结点则可直接取到Elem的地址。n)。具体实现如下： 1.3.9 NextElem功能 与Elem功能类似，不再赘述。 ListInset功能 插入一个数据元素，传入头结点地址、插入位置 ，n)，n即。 1.3.11 ListDelete功能 n)。如下： 1.3.12 ListTraverse功能 遍历顺序表元素，传入头结点值、display函数地址。时间复杂度为n) 1.3.13 SaveList功能 将顺序表保存到文件，通过 1.3.14 LoadList功能 读取功能，通过fscanf实现格式化读取，同时结合 1.3.15 display与equal函数 1.4效率分析 在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。 具有同数量级复杂度的功能在实现方法上一般近似。 比如Traverse、List、List，它们都是基于Traverse来设计的，所以效率都是n)； Elem、Elem、Elem是基于Elem，平均效率为n)； 由于在头结点结构体中已经包含了ListEmpty、Length所需信息，所以效率为Insert、Delete都要对顺序表进行“移位”运算，平均效率为n)。 实验二 2.1问题描述 基于链式存储结构，实现线性表的基本的、常见的运算。 系统设计 2.2.1同样提供 2.2.2物理结构为链式结构，数据元素包含一个整型变量以及自身类型的指针 2.2.3类似与线性表，也使用一个头结点存储链首和链表信息： 系统实现 InitiaList 由于链表的创建是动态的，因此初始化不需要创建一个巨大的存储空间。 2.3.2 DestroyLi