NYIST_数据结构实验指导书

《NYIST_数据结构实验指导书》由会员分享，可在线阅读，更多相关《NYIST_数据结构实验指导书（24页珍藏版）》请在金锄头文库上搜索。

1、 南阳理工学院南阳理工学院 数据结构上机实验指导书数据结构上机实验指导书 2011 版 软件学院 软件工程教研室 2011 3 目目 录录 实验实验 1 1 线性表应用线性表应用 2 2 实验实验 2 2 栈和队列的应用栈和队列的应用 2 2 实验实验 3 3 线性表应用线性表应用 3 3 实验实验 4 4 图论及其应用图论及其应用 3 3 实验实验 5 5 查找查找 4 4 实验实验 6 6 排序排序 4 4 实验实验 1 1 线性表应用线性表应用 一 实验目的一 实验目的 1 了解和掌握线性表顺序存储和链式存储在计算机中的表示 基本操做在 计算机中的实现 2 能够利用线性表结构对实际问题进

2、行分析建模 利用计算机求解 3 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特 点及其适用场合 二 实验内容及步骤二 实验内容及步骤 1 利用程序设计语言分别实现顺序表和链表的抽象数据类型 2 掌握程序分文件 头文件和实现文件 书写的方式 3 分别用顺序表和链表实现课本算法 2 2 合并两个非递减有序序列 并 对其时间性能做出分析 P21 include c1 h typedef int ElemType include c2 1 h include bo2 1 c include func2 3 c 包括 equal comp print print2 和 print1 函数

3、 void MergeList SqList La SqList Lb SqList Lc 算法 2 2 已知线性表 La 和 Lb 中的数据元素按值非递减排列 归并 La 和 Lb 得到新的线性表 Lc Lc 的数据元素也按值非递减排列 int i 1 j 1 k 0 int La len Lb len ElemType ai bj InitList Lc 创建空表 Lc La len ListLength La Lb len ListLength Lb while i La len GetElem Lb j if ai bj ListInsert Lc k ai i else ListIn

4、sert Lc k bj j 以下两个 while 循环只会有一个被执行 while i La len 表 La 非空且表 Lb 空 GetElem La i ListInsert Lc k ai while j Lb len 表 Lb 非空且表 La 空 GetElem Lb j ListInsert Lc k bj void main SqList La Lb Lc int j a 4 3 5 8 11 b 7 2 6 8 9 11 15 20 InitList 创建空表 La for j 1 j 4 j 在表 La 中插入 4 个元素 ListInsert printf La 输出表 L

5、a 的内容 ListTraverse La print1 InitList 创建空表 Lb for j 1 j 7 j 在表 Lb 中插入 7 个元素 ListInsert printf Lb 输出表 Lb 的内容 ListTraverse Lb print1 MergeList La Lb printf Lc 输出表 Lc 的内容 ListTraverse Lc print1 实验实验 2 2 栈和队列的应用栈和队列的应用 一 实验目的一 实验目的 1 掌握栈和队列这两种抽象数据类型的特点 并能在相应的应用问题中正 确选用它们 2 熟练掌握栈类型的两种实现方法 3 熟练掌握循环队列和链队列的

6、基本操作实现算法 二 实验内容及步骤二 实验内容及步骤 1 用程序设计语言实现栈和队列的抽象数据类型 2 在第一题的基础上完成以下选择 选择一 1 设计并实现括号匹配算法 2 用队列实现在屏幕上打印杨辉三角 选择二 分别用栈和队列实现迷宫问题求解 选择三 分别用栈和队列实现一个列车调度系统 1 import java util Scanner public class 括号配对 public static void main String args int top 0 堆指针 boolean end true 不匹配时只输出一次 char stack new char 100 存括号 Stri

7、ng s System out println 请输入表达式 Scanner scanner new Scanner System in s scanner next 表达式 char biao s toCharArray 将字符串转化成字符数组 System out println 表达式 s for int i 0 i biao lengthi 遍历表达式中所有字 符 if biao i 如果是 则入栈 stack top top else if biao i 如果是 则出栈 if top 0 top else System out println 括号不匹配 end false 除循环两

8、种可能 if top 0 出循环 stack 空 else if top 0 出循环时 stack 不空 2 include define N 11 void main int i j a N N for i 1 i N i a i i 1 a i 1 1 for i 3 i N i for j 2 j i j a i j a i 1 j 1 a i 1 j for i 1 i N i for j 1 j i j printf 6d a i j printf n 实验实验 3 3 线性表应用线性表应用 一 实验目的一 实验目的 1 领会并理解二叉树的类型定义 2 熟练掌握二叉树的主要特性 3

9、熟练掌握二叉树的各种遍历算法 并能灵活运用遍历算法实现二叉树的 其它操作 4 熟练掌握二叉树和树的各种存储结构及其建立的算法 二 实验内容及步骤二 实验内容及步骤 1 实现二叉树的抽象数据类型 2 构造一棵二叉树并用递归实现其先序 中序 后序遍历算法并验证 3 用非递归算法实现二叉树的中序遍历 一 二叉树的抽象数据类型 ADT BinaryTree 数据对象 D D 是具有相同特性的数据元素的集合 数据关系 R 若 D 则 R 称 BinaryTree 为空二叉树 若 D 则 R H H 是如下二元关系 1 在 D 中存在惟一的称为根的数据元素 root 它在关系 H 下无前驱 2 若 D r

10、oot 则存在 D root D1 Dr 且 D1 Dr 3 若 D1 则 D1 中存在惟一的元素 x1 H 且存在 D1 上的关系 H1 H 若 Dr 则 Dr 中存在惟一的元素 xr H 且存在上的关系 Hr H H H1 Hr 4 D1 H1 是一棵符合本定义的二叉树 称为根的左子树 Dr Hr 是一棵符合本定 义的二叉树 称为根的右子树 基本操作 InitBiTree struct BiTNode lchild rchild BiTNode BiTree 二叉树的创建 按照前序遍历建立二叉树 Status CreateBiTree BiTree ch getchar scanf c i

11、f ch T NULL else if T BiTNode malloc sizeof BiTNode exit OVERFLOW T data ch 生成根结点 CreateBiTree T lchild 构造左子树 CreateBiTree T rchild 构造右子树 return OK 按层次顺序建立一棵二叉树 队列 Status LevelCreateBiTree BiTree p 指向父亲结点 s 指向孩子结点 Queue BiNodeQueue char ch ch getchar if ch return NULL T BiTNode malloc sizeof BiTNode

12、 生成根结点 T data ch EnQueue BiNodeQueue T 用队列实现层次遍历 while BiNodeQueue Empty DeQueue BiNodeQueue p ch getchar 为了简化操作 分别对左右子结点进行赋值 if ch 子树不空则进队列进行扩充 下同 s BiTNode malloc sizeof BiTNode s data ch p lchild s EnQueue BiNodeQueue s else p lchild NULL ch getchar if ch s BiTNode malloc sizeof BiTNode s data ch

13、 p rchild s EnQueue BiNodeQueue s else p rchild NULL return OK 2 二叉树的前序遍历 按照前序递归遍历二叉树 Status PreOrderTraverse BiTree T if T printf d T data PreOrderTraverse T lchild PreOrderTraverse T rchild return OK 按照前序非递归遍历二叉树 栈 Status PreOrderTraverse BiTree T stack S InitStack S BiTree p T p 指向当前访问的结点 while p

14、 StackEmpty S if p printf c p data Push S p p p lchild else Pop S p p p rchild return OK 3 二叉树的中序遍历 按照中序递归遍历二叉树 Status InOrderTraverse BiTree T if T InOrderTraverse T lchild printf d T data InOrderTraverse T rchild return OK 按照中序非递归遍历二叉树 Status InOrderTraverse BiTree T stack S BiTree p InitStack S P

15、ush S T while StackEmpty S while GetTop S p 向左走到尽头 Pop S p 空指针退栈 叶子的左孩子 if StackEmpty S 访问结点 向右一步 Pop S p printf d p data 当前根结点 Push S p rchild return OK 按照中序非递归遍历二叉树 Status InOrderTraverse BiTree T stack S InitStack S BiTree p T while p StackEmpty S if p Push S p p p lchild 非空指针进栈 继续左进 else 上层指针退栈

16、访问其所指结点 再向右进 Pop S p printf d p data p p rchild return OK 二叉树的后序遍历 按照后序递归遍历二叉树 Status PostOrderTraverse BiTree T if T PostOrderTraverse T lchild PostOrderTraverse T rchild printf d T data return OK 按照后序非递归遍历二叉树 Status PostOrderTraverse BiTree T stack S InitStack S BiTree p T pre NULL while p StackEmpty S if p Push S p p p left else Pop S p if p right NULL else printf d p data pre p p NULL 按照后序非递归遍历二叉树 Status PostOrderTraverse BiTree T BiTree p T last NULL stack S InitStack S Push S p while Stack