《数据结构》课程实验报告Word下载.docx

《数据结构》课程实验报告Word下载.docx

《《数据结构》课程实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《《数据结构》课程实验报告Word下载.docx（76页珍藏版）》请在冰点文库上搜索。

相信我们一定会在上机实验的过程中加深对这两种数据结构的理解，收获到在课堂上无法获得的宝贵体验，提高我们的程序编写能力和程序差错能力，同时也体会到数据结构这门课程的魅力。

实验内容

1.顺序表综合实验

2.链表综合实验

3.二叉树综合实验

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

2.1问题描述

基于顺序存储结构，实现线性表ADT,具有12种基本运算。

要求：

⑴提供一个实现功能的演示系统

⑵具体物理结构和数据元素类型自行选定

⑶线性表数据可以使用磁盘文件永久保存

2.2系统设计

在本系统中，先创建一个结构体来作为线性表的表头，在表头中含有线性表的长度，线性表的大小以及指向线性表数组的头指针等信息。

本系统所实现的对线性表的所有操作都通过这个表头来实现。

2.2.1编译环境

操作系统：

windows8.164位

编程语言：

C语言，编译选项添加--std=c99

编译器：

CodeBlocks自带的编译器

2.2.2功能描述

基本功能有：

从文件初始化线性表、销毁线性表、将线性表置空、判断线性表是否为空、求线性表的表长、获取线性表中特定元素值、定位元素在线性表中的位置、返回线性表中某元素的前驱、返回线性表中某元素的后继、在特定位置插入新的元素、删除线性表中特定元素、遍历线性表、将线性表内容保存到文件。

2.3系统实现

2.3.1相关的类型及宏定义

#defineOK1//函数执行成功则返回OK

#defineFAIL0//函数执行失败则返回FAIL

#defineLIST_INIT_SIZE300//线性表的容量

#defineEMPTY1//线性表为空时返回EMPTY

#defineNON_EMPTY0//线性表不为空时返回NON_EMPTY

char*FilePath="

Data.dat"

;

//存储链表数据的文件名

typedefintstatus;

//函数的执行状态的返回值

typedefstruct{

intitem1;

}Elemtype;

//线性表中数据域的定义

Elemtype*elem;

intlength;

//线性表长度

intlistsize;

//线性表所能存储元素的最大值

}SqList;

//线性表的表头

2.3.2相关函数说明及基本算法思想

statusIntiaList（SqList*L）

//功能描述：

初始化线性表。

//算法思想：

从文件中读取数据来初始化线性表并设置表长为数据的个数。

statusDestroyList（SqList*L）

销毁线性表。

将线性表的存储空间释放掉并置表长为0。

statusClearList（SqListL）

清空线性表。

直接置表长为0。

statusListEmpty（SqListL）

线性表是否为空。

检查表长，如果位0，则线性表为空，否则不为空。

intListLength（SqListL）

求线性表的长度。

直接返回表长。

statusGetElem（SqListL,inti,Elemtype*e）

获取线性表中指定元素。

直接利用数组下标来返回指定的元素，如果下标不合法（大于表长或小于0），则返回空。

statusLocatElem（SqListL,Elemtypee,status（*compare）（Elemtypex,Elemtypey））

定位指定元素在线性表中的位置。

对线性表进行扫描，若找到所求的元素则返回元素在表中次序，否则返回0。

statusPriorElem（SqListL,Elemtypecur,Elemtype*pre_e）

获取指定元素的前驱。

对线性表进行扫描，若指定元素存在且不为第一个元素，则返回其前一个元素的值，否则返回空。

statusNextElem（SqListL,Elemtypecur,Elemtype*next_e）

获取指定元素的后继。

对线性表进行扫描，若指定元素存在且不为最后一个元素，则返回其后一个元素的值，否则返回空。

statusListInsert（SqList*L,intposition,Elemtypee）

在线性表的position处插入新的元素。

利用循环将position处之后的元素后移，再在position出插入新元素。

statusListDelete（SqList*L,intposition,Elemtype*e）

删除线性表position处指定元素。

通过循环直接将position之后的元素前移。

statusListTrabverse（SqListL,void（*visit）（Elemtypee））

遍历线性表。

在线性表中利用一个循环输出线性表的全部元素。

statusStoreToFile（SqListL）

将线性表的内容保存到文件中去

利用循环将线性表中的内容全部写入文件中。

2.3.3部分算法流程图

函数核心算法流程图

2.3.4部分运行截图

图2.1ListLength运行结果

图2.2GetElem运行结果

图2.3LocatElem运行结果

图2.4PriorElem运行结果

图2.5NextElem运行结果

图2.6ListTrabverse运行结果

图2.7（a）ListInsert操作前

图2.7（b）ListInsert操作

图2.7（c）ListInsert操作后

图2.8（a）ListDelete操作前

图2.8（a）ListDelete操作

图2.8（a）ListDelete操作后

2.4效率分析

算法的绝大部分时间用在从文件中读数据上，与表长有关，复杂度为O（n）

算法时间为定值，复杂度为O

（1）

算法时间为定值，复杂度为O

（1）

算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O（n）

算法的绝大部分时间用在元素的移动上，与表长有关，复杂度为O（n）

3实验二基于链式结构的线性表实现

3.1问题描述

基于链式存储结构，实现链表ADT,具有13种基本运算。

3.2系统设计

在本系统中，先创建一个结构体来作为线性表的表头，在表头中含有线性表的长度，线性表的大小以及指向线性表链表的头节点等信息。

3.2.1编译环境：

操作系统：

3.2.2实现的函数：

基本功能有：

从文件初始化线性表、销毁线性表、将线性表置空、判断线性表是否为空、求线性表的表长、获取线性表中特定元素值、定位元素在线性表中的位置、返回线性表中某元素的前驱、返回线性表中某元素的后继、在特定位置插入新的元素、删除线性表中特定元素、遍历线性表。

3.3系统实现

typedefstruct_Elemtype{

//线性链表节点的数据域

struct_Elemtype*next;

//线性表链表头指针节点

//线性表内元素个数

//线性表最大元素个数

3.3.2相关函数说明及基本算法思想

从文件中读取数据来初始化线性表并置表长为数据个数。

利用链表操作将线性表所占空间释放掉

将线性表的节点数据域置0。

。

利用循环，从线性表中第一个元素找起，若存在指定元素，则返回，否则返回空

在线性表的position处插入新的元素

利用链表的插入节点操作插入新元素

删除线性表position处指定元素

利用链表的删除节点操作删除新元素

遍历线性表

在线性表中利用一个循环输出线性表的全部元素

3.3.3部分算法流程图

PriorElem（SqListL,Elemtypecur,Elemtype*pre_e）

3.3.4运行截图

图3.1ListLength运行结果

图3.2GetElem运行结果

图3.3LocatElem运行结果

图3.4PriorElem运行结果

图3.5NextElem运行结果

图3.6ListTraverse运行结果

图3.7（a）ListInsert运行前

图3.7（b）ListInert运行

图3.7（c）ListInsert运行后

图3.8（a）ListDelete运行前

图3.8（b）ListDelete运行

图3.8（c）ListDelete运行后

3.4效率分析

算法的绝大部分时间用在从文件中读数据上，与表长有关，复杂度为O（n）

算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O（n）

4实验三基于二叉链表的二叉树实现

4.1问题描述

实验（三）基于二叉链表，实现二叉树的基本的、常见的运算：

提示：

（1）提供一个实现功能的演示系统；

（2）具体物理结构和数据元素类型自行选定；

（3）可采用递归和非递归算法实现。

4.2系统设计

4.2.1编译环境：

编程语言：

C++，编译时向VS编译器传递/D_CRT_SECURE_NO_WARNINGS参数

编译器：

VisualStudio2013所带编译器

4.2.2实现的函数：

voidInitBiTree（）

初始化二叉树为只有根节点。

若二叉树存在，则先销毁在赋值，否则直接赋值。

voidDestroyBiTree（PntBT*root）

销毁二叉树。

利用递归访问二叉树的每一个节点，访问完成后释放掉其占用的内存。

voidCreateBiTree（）

从文件创建二叉树。

利用文件中读取的先序遍历序列和中序遍历序列生成一个二叉树。

voidClearBiTree（PntBT*root）

清空二叉树。

利用递归访问二叉树的每一个节点，将其数据域释放掉后置指针为空。

intBiTreeEmpty（inta=1）

判断二叉树是否为空。

直接判断其节点数和非空结点数，只要有一个为0则二叉树为空。

intBiTreeDepth（）

返回二叉树的深度。

利用递归来访问二叉树的所有节点，递归调用次数最多的一条路径上的递归调用次数就是二叉树的层数。

PntBT*Root（inta）

返回二叉树的根。

直接返回根节点指针的地址。

PntBT*Value（）

返回二叉树中指定节点的值。

递归遍历二叉树，若发现所寻找的节点，则输出其值。

PntBT*Assign（）

为二叉树指定节点赋值。

递归遍历二叉树，若发现所寻找的节点，则为其赋值。

PntBT*Parent（）

返回指定节点的父节点。

递归遍历二叉树，若某节点的左孩子或右孩子为所寻找的节点，则返回此节点

PntBT*LeftChild（）

返回二叉树的左孩子。

递归遍历二叉树，若发现所寻找的节点，则返回其左孩子。

PntBT*RightChild（）

返回指定节点的右孩子。

递归遍历二叉树，若发现所寻找的节点，则返回其右孩子。

PntBT*LeftSibling（）

返回指定节点的左兄弟。

递归遍历二叉树，若某节点的右孩子为所寻找的节点，则返回其左孩子。

PntBT*RightSibling（）

返回指定节点的右兄弟。

递归遍历二叉树，若某节点的左孩子为所寻找的节点，则返回其右孩子。

voidInsertChild（）

在指定节点的左或右孩子处插入子树，并将节点原有的左或右孩子作为插入节点的右孩子。

遍历二叉树，先找到所寻找的节点，再利用链表操作完成插入功能

voidDeleteChild（）

删除二叉树中以指定节点为根的子树。

遍历二叉树，先找到所要寻找的子树，再利用DestroyBiTree来完成销毁操作。

voidPreOrderTraverse（）

非递归先序遍历二叉树。

利用栈来模仿递归操作，最终实现非递归先序遍历二叉树。

voidInOrderTraverse（）

非递归中序遍历二叉树。

利用栈来模仿递归操作，最终实现非递归中序遍历二叉树。

voidPostOrderTraverse（）

非递归后序遍历二叉树。

利用双栈法来非递归后序遍历二叉树。

PntBT*LevelOrderTraverse（intisVisit）

层序遍历二叉树，并给二叉树的节点编号。

利用队列来暂存二叉树某层的层序遍历序列，并将其中的节点编号并输出。

4.3系统实现

4.3.1本节内容简介：

1.由于代码较长，为阅读方便起见，特专门列出二叉树的部分实现代码。

由于主程序中以及一些基本的操作函数的实现代码大家都是大同小异的，故不再列出。

2.在本系统中，多次使用了栈和队列这两种数据结构，但是为了方便起见，本系统并未按照相应的规范来实现这两种数据结构的操作，而是直接通过相应的指针来进行操作。

并且，出于防止内存泄露的目的，本系统创建的栈和队列都是环状的，这样的设计便于由任意一个指针来销毁整个数据结构。

同时，由于环状结构的特点，为了防止极端情况下数据的丢失，本系统在为栈和队列这两种数据结构分配环状存储链的时候，分