《算法与数据结构》实验指导书《算法与数据结构》实验指导书2006年8月25日长江大学电子信息学院计算机系列课程组-
《算法与数据结构》实验指导书 1 《算法与数据结构》实验指导书 《算法与数据结构》实验指导书 《算法与数据结构》实验指导书 《算法与数据结构》实验指导书 2006 年 8 月 25 日 长江大学电子信息学院计算机系列课程组
《算法与数据结构》实验指导书目录《算法与数据结构》实验指导书0绪论实验一：线性表的存储结构定义及基本操作（必做：基本2学时，扩展4学时）一、实验目的：二、实验内容：6（一）基本实验内容（顺序表）：6(二）基本实验内容（链表）：（三）扩展实验内容（顺序表）（四）扩展实验内容（链表）99三、实验指导..四、基本实验的参考程序11五、实验环境和实验步骤.24六、思考题25实验二：线性表的综合应用（选做：2学时）.27一、实验目的：2727二、实验内容三、编程指导.28四、参考程序...28五、实验步骤....30六、思考题：30实验三：栈和队列的定义及基本操作（必做：2学时)3232一、实验目的：二、实验内容..32三、实验指导3434（一）顺序栈的实验指导（二）链式队列的实验指导3434四、参考程序..（一）顺序栈34（二）链式队列39五、实验环境和实验步骤44（一）基本实验的实验步骤：（顺序栈的定义以及应用).44（二）基本实验的实验步骤：（链式队列定义以及应用)..45六、思考题45实验四：栈和队列的综合应用（选做：2学时）47一、实验目的：47二、实验内容....47（一）基本实验内容：..47三、参考程序.47（一）实现Hanoi塔问题(只需建立如下的一个文件hanoi.cpp即可)...47（二）迷宫问题参考程序(只需建立如下的一个文件maze.cpp即可）.48四、实验环境和实验步骤.51.53实验五：二叉树的定义及基本操作（必做：基本2学时，扩展4学时）2
《算法与数据结构》实验指导书 2 目 录 《算法与数据结构》实验指导书. 1 0 绪 论. 5 实验一：线性表的存储结构定义及基本操作（必做：基本 2 学时，扩展 4 学时）.6 一、实验目的：. 6 二、实验内容：. 6 （一）基本实验内容（顺序表）：. 6 (二）基本实验内容（链表）：.7 （三）扩展实验内容（顺序表）. 8 （四）扩展实验内容（链表）. 9 三、实验指导. 9 四、基本实验的参考程序. 11 五、实验环境和实验步骤. 24 六、思考题. 25 实验二：线性表的综合应用（选做： 2 学时）. 27 一、实验目的：. 27 二、实验内容:.27 三、编程指导. 28 四、参考程序. 28 五、实验步骤. 30 六、思考题：. 30 实验三：栈和队列的定义及基本操作（必做： 2 学时）. 32 一、实验目的：. 32 二、实验内容:.32 三、实验指导. 34 （一）顺序栈的实验指导. 34 （二）链式队列的实验指导. 34 四、参考程序. 34 （一）顺序栈. 34 （二）链式队列. 39 五、实验环境和实验步骤. 44 （一）基本实验的实验步骤：(顺序栈的定义以及应用).44 （二）基本实验的实验步骤：(链式队列定义以及应用).45 六、思考题. 45 实验四：栈和队列的综合应用（选做： 2 学时）. 47 一、实验目的：. 47 二、实验内容:.47 （一）基本实验内容：. 47 三、参考程序. 47 （一）实现 Hanoi 塔问题(只需建立如下的一个文件 hanoi.cpp 即可).47 （二）迷宫问题参考程序(只需建立如下的一个文件 maze.cpp 即可).48 四、实验环境和实验步骤. 51 实验五：二叉树的定义及基本操作 （必做：基本 2 学时，扩展 4 学时）.53
《算法与数据结构》实验指导书53、实验目的：53二、实验内容（一）基本实验内容：5354（二）扩展实验内容：三、实验指导..55（一）基本实验指导.55（二）扩展实验指导56四、参考程序...57（一）基本实验的参考程序57（二）扩展实验的参考程序...63（三）线索二叉树的参考程序.66.71五、实验环境和实验步骤71（一）基本实验的实验步骤：（二）二叉链表扩展实验的实验步骤：7171（三）线索二叉树的实验步骤：六、思考题72实验六：赫夫曼编码及其应用（选做：基本2学时，扩展2学时）.73一、实验目的：7373二、实验内容...73（一）基本实验内容（二）扩展实验内容：7474三、实验指导...（一）基本实验指导....74四、参考程序...74（一）基本实验的参考程序74五、实验环境和实验步骤.77六、思考题79实验七：图及其应用（选做：2学时）79一、实验目的：79二、实验内容三、实验指导..80四、参考程序80..89五、实验环境和实验步骤六、思考题9091实验八：最短路径和关键路径的研究与实现（选做：2学时）、实验目的：91、实验内容...91三、实验指导：9192四、参考程序..99五、实验环境和实验步骤六、思考题99实验九：查找和排序算法的实现（选做：基本2学时，扩展4学时）..101、实验目的.101二、实验内容..101（一）基本实验内容：101（二）扩展实验内容：1023
《算法与数据结构》实验指导书 3 一、实验目的：. 53 二、实验内容:.53 （一）基本实验内容：. 53 （二）扩展实验内容：. 54 三、实验指导. 55 （一）基本实验指导. 55 （二）扩展实验指导. 56 四、参考程序. 57 （一）基本实验的参考程序. 57 （二）扩展实验的参考程序. 63 （三）线索二叉树的参考程序. 66 五、实验环境和实验步骤. 71 （一）基本实验的实验步骤：. 71 （二）二叉链表扩展实验的实验步骤：. 71 （三）线索二叉树的实验步骤:. 71 六、思考题. 72 实验六：赫夫曼编码及其应用（选做：基本 2 学时，扩展 2 学时）.73 一、实验目的：. 73 二、实验内容:.73 （一）基本实验内容. 73 （二）扩展实验内容：. 74 三、实验指导. 74 （一）基本实验指导. 74 四、参考程序. 74 （一）基本实验的参考程序. 74 五、实验环境和实验步骤. 77 六、思考题. 78 实验七：图及其应用（选做： 2 学时）. 79 一、实验目的：. 79 二、实验内容:.79 三、实验指导:.80 四、参考程序:.80 五、实验环境和实验步骤. 89 六、思考题. 90 实验八：最短路径和关键路径的研究与实现（选做：2 学时）. 91 一、实验目的：. 91 二、实验内容:.91 三、实验指导:.91 四、参考程序:.92 五、实验环境和实验步骤. 99 六、思考题. 99 实验九：查找和排序算法的实现 （选做：基本 2 学时，扩展 4 学时）.101 一、实验目的. 101 二、实验内容. 101 (一) 基本实验内容：.101 （二）扩展实验内容：. 102
《算法与数据结构》实验指导书三、实验指导、..103四、参考程序...103...103（一）基本实验的参考程序（二）扩展实验的参考程序. 112五、实验环境和实验步骤..六、思考题...119
《算法与数据结构》实验指导书 4 三、实验指导. 103 四、参考程序. 103 （一） 基本实验的参考程序. 103 （二） 扩展实验的参考程序. 112 五、实验环境和实验步骤. 118 六、思考题. 119
《算法与数据结构》实验指导书0绪论本书是以《算法与数据结构》课程教学大纲和实验教学大纲为指导，分别从实验（包含：基本实验和扩展实验）的六个方面（实验目的、实验内容、实验指导、参考程序、实验步骤以及思考题）来组织内容。其中实验目的强调了每个实验要掌握的内容和要达到的层次；实验内容是对基本实验和扩展实验的问题进行描述，并且对实现要求进行了规划；实验指导对整个实验的结构进行了组织和指导；而参考程序则列出了实验要求中，特别是一些重要算法的参考描述；实验步骤则是指导学生进行实验的具体操作；思考题则是布置给学生对同类实验的一种思考和提示。在参考程序中，主要实现了数据结构定义，基本操作和算法的验证。其中：在所有实验中我们建议采用VisualC++作为实验的开发环境，也可以用BC++,TC++环境，如果用C环境，那么后面的参考程序中凡是涉及到“引用”内容的，均要改为“指针”。用VC++作为实验开发环境，首先建立Win32ConsoleApplication工程，其目的是在Windows图形环境中模拟DoS字符方式。由于工程是以一组相关的文件组织的，将严格地按照文件内容的不同功能进行细致的划分，为了便于大家认真理解本指导书的内容，特对各类文件的名称作了如下的规定：文件名的标识基本以每个实验的内容作为依据，如顺序表的存储结构定义文件为SeqListDef.h。这些程序文件主要包含了如下4类：（1）pubuse.h是几乎所有实验中都涉及到的，包含了一些常量定义，系统函数原型声明和类型（Status）重定义，结果状态代码等。在本文中的内容对某一个实验可能没有完全用到，但对本课程的其他实验可能有用；(2)数据结构定义：以_Def.h为文件名(3)基本操作和算法：以Algo.h为文件名：(4)调用基本操作的主程序：以_Use.cpp为文件名
《算法与数据结构》实验指导书 5 0 绪 论 本书是以《算法与数据结构》课程教学大纲和实验教学大纲为指导，分别从实验（包含：基本实验 和扩展实验）的六个方面（实验目的、实验内容、实验指导、参考程序、实验步骤以及思考题）来组织内 容。其中实验目的强调了每个实验要掌握的内容和要达到的层次；实验内容是对基本实验和扩展实验的问 题进行描述，并且对实现要求进行了规划；实验指导对整个实验的结构进行了组织和指导；而参考程序则 列出了实验要求中，特别是一些重要算法的参考描述；实验步骤则是指导学生进行实验的具体操作；思考 题则是布置给学生对同类实验的一种思考和提示。 在参考程序中，主要实现了数据结构定义，基本操作和算法的验证。其中：在所有实验中我们建议 采用 Visual C++作为实验的开发环境,也可以用 BC++,TC++环境，如果用 C 环境，那么后面的参考程序中， 凡是涉及到“引用”内容的，均要改为“指针”。用 VC++作为实验开发环境，首先建立 Win32 Console Application 工程,其目的是在 Windows 图形环境中模拟 DOS 字符方式。由于工程是以一组相关的文件组织 的，将严格地按照文件内容的不同功能进行细致的划分，为了便于大家认真理解本指导书的内容，特对各 类文件的名称作了如下的规定： 文件名的标识基本以每个实验的内容作为依据，如顺序表的存储结构定义文件为 SeqListDef.h。这 些程序文件主要包含了如下 4 类： （1） pubuse.h 是几乎所有实验中都涉及到的，包含了一些常量定义，系统函数原型声明和类型 （Status）重定义,结果状态代码等。在本文中的内容对某一个实验可能没有完全用到，但对本课 程的其他实验可能有用； （2） 数据结构定义：以_Def.h 为文件名； （3） 基本操作和算法：以_Algo.h 为文件名； （4） 调用基本操作的主程序：以_Use.cpp 为文件名