《数据结构》实验指导
(计算机信息大类适用)
实验报告至少包含以下内容：
实验名称
实验目的与要求:
实验内容与步骤（需要你进行细化）:
实验结果（若顺利完成，可简单说明；若实验过程中遇到问题，也请在此说明）
收获与体会（根据个人的实际情况进行说明，不得空缺）
实验1 大整数加法（8课时）
目的与要求：
1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。

2、单链表的简单应用训练。

3、熟悉标准模版库STL中的链表相关的知识。

内容与步骤:
1、编程实现单链表的基本操作。

2、利用单链表存储大整数（大整数的位数不限）。

3、利用单链表实现两个大整数的相加运算。

4、进行测试，完成HLOJ() 9515 02-线性表大整数A+B。

5、用STL之list完成上面的任务。

6、尝试完成HLOJ 9516 02-线性表大菲波数。

实验2 栈序列匹配（8课时）
目的与要求
1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。

2、栈的简单应用训练。

3、熟悉标准模版库STL中的栈相关的知识。

内容与步骤:
1、编程实现顺序栈及其基本操作。

2、对于给出的入栈序列和出栈序列，判断2个序列是否相容。

即：能否利用栈
将入栈序列转换为出栈序列。

3、进行测试，完成HLOJ 9525 03-栈与队列栈序列匹配。

4、用STL之stack完成上面的任务。

5、尝试完成HLOJ 9522 03-栈与队列胡同。

实验3 二叉排序树（8课时）
目的与要求
1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。

2、二叉树的遍历方法的训练。

3、二叉树的简单应用。

内容与步骤:
1、编程实现采用链式存储结构的二叉排序树。

2、实现插入节点的操作。

3、实现查找节点的操作（若查找失败，则将新节点插入二叉排序树）。

4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出，完成
HLOJ 9576 07-查找二叉排序树。

5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。

实验4 最小生成树（8课时）
目的与要求
1、图的邻接矩阵存储结构及其相关运算的训练。

2、掌握最小生成树的概念。

3、利用Prim算法求解最小生成树。

实验背景：
给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。

要求显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。

内容与步骤:
1、建立采用邻接矩阵的图。

2、编程实现Prim算法，求解最小生成树的代价。

3、尝试利用Prim算法完成：HLOJ 9561 06-图最小生成树。