数据结构实验指导书

第一部分课程概述

数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学

科的核心课程，而且已成为其它立功专业的热门选修课。数据结构实验可

以使学生对数据结构课程所教授的内容通过实验环节加以实践，提高学生

的程序设计、编写及调试能力，是一门基础的实验课程。

第二部分实验要求

通过实验，学生对常用数据结构的基本概念及其不同的实现方法的理

论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧

有所体会，从而使学生更好的巩固和掌握所学的内容。

学生应完成教师布置的实验任务，得出正确的实验结果，实验后完成

实验报告或相关的实验记录。

第三部分实验内容

实验一线性表的应用

一、实验目的

I、熟悉C语言的上机环境，掌握C语言编程工具。

2、掌握线性结构的定义、组织形式、结构特征和类型说明以及在这两种存

储方式下实现的插入、删除和按值查找的算法。

3、循环链表、双（循环）链表的结构特点和在其上施加的插入、删除等操作。

二、实验内容（两者任选一题）

1、Joseph问题：设编号为1,2,…,n的n个人围坐一圈，约定编号为k

（l<=k<=n）的人从1开始报数，数到m的那个人出列，他的下一位又从

1开始报数,数到m的那个人又出列，…依次类推，直到所有的人出列为

止，因此产生一个出列编号的序列。

提示：应创建循环链表来存储数据，链表结点的数据域用来存储该结点的

编号，出列结点应从链表中删除，直到最后一个结点为止。

2、一元多项式的相加：选用适当的线性表结构存储一元多项式，并实现两

个多项式相加，并将结果按照数学公式格式输出。多项式的数据应由键盘

输入。

三、思考题

1、在程序设计中，分析顺序表和链表的不同的应用场合。

2、如何改进线性表插入、删除算法的效率？

四、易犯错误及分析

1、在没有定义结构体的前提下，就使用结构体变量组成链表的结点，应注

意基本数据结构的定义。

2、在进行表结点插入或删除时，指针的错误使用，特别需要注意边界条件

的控制。

实验二二叉树的存储与应用

一、实验目的

1、掌握二叉树的二叉链表存储方式、结点结构和类型定义。

2、二又树的卜•的基本运算及应用。

3、栈和队列的实际应用。

二、实验内容(两者任选一题)

1、非递归中序遍历二叉树：要求从键盘输入二叉树各结点的值，并使用二

叉链表来存储二叉树；使用非递归算法遍历二叉树，在屏幕上打印出二叉

树中序遍历序列。

提示：在非递归方法中，可采用堆栈的入栈方法存储当前访问结点的父结

点，采用出栈的方法获得当前访问结点的父结点。

2、哈夫曼编码/译码问题：已知某密码中共含有5个字符A、B、C、D、E,

它们出现的频率依次是01、0.3、0.4、0.15和0.05。要求采用哈夫曼算法,

求出5个字符的最优编码；反之，当用户给出某个0/1序列，解码出相应

的字符序列；如有错误输入的0/1序列，要打印出错提示信息。

三、思考题

1、二叉链表应如何建立？

2、在非递归遍历算法中，应使用以前学过的哪些数据结构？

四、易犯错误及分析

1、堆栈和队列是操作受到限制的线性表，它们具有各自的特点。堆栈的特

点是后进先出(LIFO),而队列的特点是先进先出(FIFO)。在对它们进行频

繁操作的时候，要注意它们进出栈或进出队的次序。

2、对堆栈或队列执行操作时特别需要注意边界条件的控制。

3、在二叉链表的存储中，不能随意交换左右孩子结点的顺序。

实验三图的存储与应用

一、实验目的

1、掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法；

2、图的基本运算及应用。

二、实验内容

拓扑排序：已知有九门课程，依次编号为CO至C8,在图一中给出了

给出了各门课程之间先后关系。例如：CO是C2和C6的前序课程，而在

选修C8之前，必须已经选修过C3和C7。要求存储该拓扑结构图，当用

户从键盘输入任意课程的编号时，可打印出该课程的所有的前序课程。

图一九门课程的拓扑结构图

三、思考题

1、如何用图来存储图形或网络？

2、分析图中多种存储方法的使用场合。

3、在拓扑排序算法中，需要用到那些基本的数据结构？

四、易犯错误及分析

1、在使用二维数组存储邻接矩阵时;在循环时注意边界条件的控制。

2、在使用邻接表存储图的时候，注意指针数组的使用。

实验四学生成绩管理程序的设计

一、实验目的

综合以前所学过的数据组织方式和存储方法，解决实际问题，并掌握

各种查找排序算法的基本思想及存储、运算的实现，达到综合设计的目的。

二、实验内容

(1)记录项的设计：学生成绩信息应包含学生姓名、学号和至少三门的百

分制成绩。学生需根据实际问题，选择合适的数据结构来存储数据。

(2)学生成绩的查找：选择并实现最有效地查找“人名一成绩”或“学号一

成绩”的查找算法。

(3)实现对学生成绩的求和，求平均值及排序(升序或降序)等功能，并

对选