华中科技大学 数据结构 实验报告

课 程 实 验 报 告

课程名称： 数

据 结 构

专业班级：华中科技大学材控1402班 学 号： U201411219 姓 名： 张煌 指导教师： 袁凌 报告日期： 2016年5月20日

计算机科学与技术学院

目录

实验报告要求说明...................................................................... 错误！未定义书签。 1基于顺序存储结构实现线性表的基本运算........................... 错误！未定义书签。 1.1 问题描述.............................................................................. 错误！未定义书签。 1.2 顺序表演示系统设计.......................................................... 错误！未定义书签。 1.2.1 系统总体设计.................................................................... 错误！未定义书签。 1.2.2 有关常量和类型定义........................................................ 错误！未定义书签。 1.2.3 算法设计............................................................................ 错误！未定义书签。 1.3 顺序表演示系统实现与测试.............................................. 错误！未定义书签。 1.3.1 系统实现............................................................................ 错误！未定义书签。 1.3.2 系统测试............................................................................ 错误！未定义书签。 1.4 实验小结.............................................................................. 错误！未定义书签。 2基于链式存储结构实现线性表的基本运算........................... 错误！未定义书签。 2.1 问题描述.............................................................................. 错误！未定义书签。 2.2 单链表演示系统设计.......................................................... 错误！未定义书签。 2.2.1 系统总体设计.................................................................... 错误！未定义书签。 2.2.2 有关常量和类型定义........................................................ 错误！未定义书签。 2.2.3 算法设计............................................................................ 错误！未定义书签。 2.3 单链表演示系统实现与测试.............................................. 错误！未定义书签。 2.3.1 系统实现............................................................................ 错误！未定义书签。 2.3.2 系统测试............................................................................ 错误！未定义书签。 2.4 实验小结.............................................................................. 错误！未定义书签。 参考文献...................................................................................... 错误！未定义书签。

1课程实验概述

本次课程实验旨在加强学生课堂理论学习之后增强上机能力，熟练掌握并应用数据结构中的两种逻辑结构的典型代表——线性表和树。线性表的顺序存储具有随机存取的功能，而链式存储能有效的利用动态存储空间，学会合理的选择这两种存储方式，看似简单，但在实际应用具有很大的用处。而树（二叉树）是非线性逻辑结构的代表，树模型的建立可以说完全建立在递归思想之上，树的几乎所有操作都涉及到递归调用，当然我们也可以用栈来实现非递归调用，但是其思想也是相近的。因此树的实验旨在帮助我们递归思想的建立和成熟。

2实验一 基于顺序结构的线性表实现

2.1实验内容与要求

实验内容：基于顺序存储结构，实现线性表ADT，具有10种基本运算。 具体要求：1.提供一个实现功能的演示系统。 2.具体物理结构和数据元素类型自定。 3.线性表数据可以使用磁盘文件永久保存。

2.2程序概要设计

1.明确基本功能

程序需要实现的12个基本功能分别是：IntiaList（初始化），DestroyList（摧毁线性表），ClearList（清空线性表），ListEmpty（判断表空），ListLength（求表长），GetElem（取表中元素），LocatElem（获得元素地址），PriorElem（取前继），NextElem（取后继）。ListInsert（插入）， ListDelete（删除），ListTrabverse（遍历显示），此外还有辅助功能：Load（载入），Save（保存）

2.确定各功能实现的函数参数 status IntiaList(SqList * L); status DestroyList(SqList * L); status ClearList(SqList L); status ListEmpty(SqList L); int ListLength(SqList L);

status GetElem(SqList L,int i,Elemtype *e); int LocatElem(SqList L,Elemtype *e);

1

status PriorElem(SqList *L,Elemtype cur,Elemtype * pre_e); status NextElem(SqList L,Elemtype cur,Elemtype * next_e); status ListInsert(SqList *L, Elemtype e,int i); status ListDelete(SqList * L,Elemtype * e,int i); status ListTrabverse(SqList L,void (* visit)(Elemtype e)); void Save(SqList L); status Load(SqList*L);

2.3数据结构与算法设计

为了满足概述中的功能，结合线性表结构，给出以下结构的定义： typedef int status; typedef struct{

int item1; }Elemtype; typedef struct{

Elemtype * elem; int length; int listsize;

}SqList,*L; 算法设计： 1.IntiaList：

初始化线性表，传入的是头结点地址。申请一个大小为LIST_INT_SIZE、类型为Elemtype的线性存储空间，并用头结点中的首结点指针指向该空间首地址。

2.DestroyList：

销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。 3.ClearList：

与Destroy类似但是又有不同，ClearList并不销毁物理空间，而是修改逻辑关系值。

4.ListEmpty：

判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。若长度为0，表空，否则不空。

5.ListLength：

求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接

2

调用并显示即可。

6.GetElem：

获取第i号元素，传入的是头结点值、元素编号i、以及出口表结点地址。 7.LocatElem：

取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点值、equal函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号i。

8.PriorElem：

求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用LocatElem确定指定元素的位置，如果不是首结点则可直接取到PriorElem的地址。

9.NextElem：

与PriorElem功能类似，不再赘述。 10.ListInset：

插入一个数据元素，传入头结点地址、插入位置i、临时表结点值。在调用插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。

11.ListDelete:

删除一个数据元素，传入头结点地址、删除位置i。删除前先判断位置是否合理，先删除元素，然后将所有删除元素之后的元素前移一个位置。

12.ListTrabverse:

传入头结点，循环访问各个元素，直至到表尾停止。

2.4输入输出设计

1.输入：

在输入方面，我采用了用户自定义输入的方式，既可以采用用户自行输入，又可以载入之前保存的数据。在每次操作之后，会提示是否保存刚才的数据，以便下次再次使用，以下是用户自行输入的功能实现： void creat(SqList *L){ int a=0;

printf(\ scanf(\

L->elem=(Elemtype*)malloc(a*sizeof(Elemtype)); L->length=a; int i;

3