《数据结构》课程实验大纲

1、数据结构课程实验大纲 实 验 学 时： 12 课程总学时：64 适 用 专 业：计算机科学与技术（考试） 实验项目数：6 软件工程（考试） 教育技术学（考试） 网络工程（考试） 通信工程（考试） 开课教研室(系)： 计算机工程 大纲执笔人： 一、 本实验课的基本理论和目的数据结构是计算机学科的核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。数据结构课程是一门理论和实践相结合的课程。 上机实验是为训练学生的实际程序设计

2、能力安排的、包含在教学课时内的教学内容。实验目的是： （1）进一步深入理解相关部分的基本概念和授课内容。 （2）进一步提高实际动手进行程序设计的能力。二、 本实验课的基本要求 （1）认真阅读掌握和实验相关的教材内容。 （2）自己编程，可以参考别人的程序设计方法，但不得抄袭别人的程序。 （3）程序有错误时，尽量先自己调试，在自己能力达不到时，可请教同学或询问老师。 （4）及时完成实验报告。三、设置的实验项目、实验内容和学时分配 实验一 线性表的基本操作和简单程序（2学时） 实验内容如下： （1）熟悉Visual C+ 6.0实验环境。 （2）阅读教材上顺序堆栈和链式堆栈的程序，并自己键入这些程序

3、。 （3）设计一个使用堆栈的应用程序。 （4）分析应用程序的运行情况。 实验二 顺序栈的实现（2学时）实验内容如下： （1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。（4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。实验三 折半查找算法设计（2学时）实验内容如下： （1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查

4、找函数。 （2）编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中 （3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。 （4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。实验四 二叉树设计（2学时）实验内容如下：（1）定义二叉链存储结构。 （2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等）。 （3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。 （4）编写测试主函数并上

5、机运行。打印出运行结果，并结合程序运行结果进行分析。实验五 图的设计（2学时）实验内容如下： （1）定义邻接矩阵存储结构或邻接表存储结构。 （2）按照建立一个带权有向图的操作需要，编写在邻接矩阵或邻接表存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历、图的广度优先遍历等）。 （3）设计一个测试主函数，首先创建一个图（有n个结点和e条边），然后打印图的n个结点信息和e条边信息，最后分别打印出图的深度优先遍历和广度优先遍历的结点信息序列。实验六顺序队列下的基数排序算法设计（2学时）实验内容如下： （1）编写基于顺序队列的基数排序函数。 （2）设计一个测试主函数，实现对基于顺序队列结构的基数排序算法的测试。 （3）分析程序的运行结果。 （4）分析比较链式队列结构的基数排序算法和顺序队列结构的基