华中科技大学计算机11级数据结构实验报告

《华中科技大学计算机11级数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告课程名称：数据结构专业班级：学号：姓名：指导教师：报告日期：计算机科学与技术目录实验一基于顺序结构的线性表实现11.1问题描述11.2系统设计11.3.系统实现11.4效率分析5实验二基于链式结构的线性表实现62.1问题描述62.2系统设计62.3系统实现62.4效率分析10实验三基于二叉链表的二叉树实现113.1问题描述113.2系统设计113.3系统实现113.4效率分析17四实验总结与评价17实验一基于顺序结构的线性表实现1.1问题描述基于顺序存储结构，实现线性表的基本的、常见的运

2、算。1.2系统设计1.2.1提供14个功能，分别是：1.InitiaList8.PriorElem2.DestroyList9.NextElem3.ClearList10.ListInsert4.ListEmpty11.ListDelete5.ListLength12.ListTrabverse6.GetElem13.Savelist7.LocatElem14.Loadlist0.Exit1.2.2物理结构为顺序存储结构，数据元素为包含一个整型变量的结构体：1.2.3构建线性表之前先声明一个头结点，

3、用于存储该表的基本信息和首结点地址：1.3.系统实现1.3.1InitialList功能初始化线性表，传入的是头结点地址。申请一个大小为LIST_INT_SIZE、类型为Elemtype的线性存储空间，并用头结点中的首结点指针指向该空间首地址。具体实现如下：1.3.2DestroyList功能销毁16头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具体实现如下：1.3.3ClearList功能与Destroy类似但是又有不同，ClearList并不销毁物理空间，而是修改逻辑关系值：1.3.

4、4ListEmpt功能判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。实现如下：1.3.5ListLenth功能求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可：1.3.6GetElem功能获取第i号元素，传入的是头结点值、元素编号i、以及出口表结点地址。1.3.7LocatElem功能16获取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点值、equal函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号i。时

5、间复杂度为,O(n)。1.3.8PriorElem功能求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用LocatElem确定指定元素的位置，如果不是首结点则可直接取到PriorElem的地址。时间复杂度为O(n)。具体实现如下：1.3.9NextElem功能与PriorElem功能类似，不再赘述。1.3.10ListInset功能插入一个数据元素，传入头结点地址、插入位置i、临时表结点值。在调用插入函数前构造一个临时表结点，

6、用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。平均时间复杂度为，O(n)，n即listlenth。1.3.11ListDelete功能16删除指定编号的数据元素，传入头结点地址、编号i、表结点类型结构体地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，进行“移位”运算。时间复杂度仍为O(n)。如下：1.3.12ListTraverse功能顺序遍历

7、顺序表元素，传入头结点值、display函数地址。时间复杂度为O(n)1.3.13SaveList功能将顺序表保存到文件，通过C中文件函数fprintf实现格式化写入。时间复杂度同遍历。1.3.14LoadList功能读取功能，通过fscanf实现格式化读取，同时结合CreateList函数实现顺序表建立。161.3.15display与equal函数1.4效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。具有同数量级复杂度的功能在实现方法上一般近似。比如ListTraver

8、se、SaveList、LoadList，它们都是基于ListTraverse来设计的，所以效率都是O(n)；而LocatElem、PriorElem、NextElem是基于LocatElem，平均效率为O(n)；由于在头结点结构体中已经包含了ListEmpty、ListLength所需信息，所以效率为O(1)；ListInsert、ListDelete都要对顺序表进行“移位”运算，平均效率为O(n)。16实验二基于链式结构的线性表实现2.1问题描述基于链式存储结构，