数据结构实验课程大纲
本大纲是针对计算机科学与技术专业本科对数据结构的基本要求而编写的。
一、目的与任务
数据结构是一门实践性很强的课程，每个学生必须完成一定数量的上机作业。通过上机作业，要求在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。
二、课程内容
1.顺序表的表示和运算（0-2学时）
2.链表的表示和运算（2学时）
3.栈的应用（2-3学时）
4.队列的应用（2-3学时）
5.二叉树的基本操作和应用（2-6学时）
6.图及其应用（2-6学时）
7.排序（4-6学时）
8.查找（2-4学时）
三、基本要求
1.逐步理解和掌握程序设计和上机操作的基本方法和技能。
2.理解并实现各种基本数据结构的存贮表示、运算方法及其典型应用；学会根据实际问题的要求设计算法的
数据结构，并具有一定的比较和选用数据结构及算法的能力。
3.理解并实现常用的查找和排序的基本方法。
四、学时分配
五、实验内容
注：带*的内容以及练习与思考题，可根据实际学时、专业方向特点等具体要求，做相应调整或从略。
实验一、顺序表
实验目的：
熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。
实验要求：
了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
实验内容：
编写程序实现下列的要求：
(1) 设数据元素为整数，实现这样的线性表的顺序存储表示。
(2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。
(3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。
(4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。要求尽可能少地修改前面的程序来得到新程序。（这里用于比较的字段为分数）
练习及思考题：
（1）不同类型的数据元素所对应的顺序表在类型定义和操作实现上有什么异同？
（2）顺序表的操作上有什么特点？
（3）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。
实验二、链表
实验目的：
熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。
实验要求：
了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。
实验内容：
编写程序实现下列的要求：
(1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。
(2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。
(3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。（用于比较的关键字字段为分数）。
(4) 输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。
(5) * 释放该链表（删除所有结点）。
(6) * 若要求建立的学生成绩单链表为有序表，重新编写算法和程序实现前面的要求（3）。（用于比较的字段为分数）。
练习及思考题：
（1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？
（2）有头结点的链式表，有什么特点？
实验三、栈的应用
实验目的：
熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
实验要求：
了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。
实验内容：
(1) 判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。编写并实现它的算法。
(2) 用不同的存储方法，求解上面的问题。
(3) * 若表达式中既有小括号，又有大括号（或中括号），且允许互相嵌套，但不能交叉，写出判断这样的
表达式是否合法的算法。如2+3*（4-{5+2}*3）为合法；2+3*（4-{5+2 * 3} 、2+3*（4-[5+2 * 3）为不合法。
练习及思考题：
（1）求解八皇后问题，并将它扩展到n皇后问题。
（2）递归问题是如何利用栈来求解的。
实验四、队列的应用
实验目的：
熟悉队列的逻辑特性、存储表示方法和队列的基本操作及应用。
实验要求：
了解并熟悉队列的逻辑特性、顺序和链式存储表示方法和队列的基本操作的实现和应用。
实验内容：
迷宫问题
(1) 定义不同存储类型的队列并实现队列的基本操作。
(2) *求解m*n迷宫问题，输出解的个数及每个解。编写并实现它的算法。
(3)* 用不同的存储方法，求解上面的问题。
练习及思考题：
（1）队列是特殊的线性表，它的特殊性体现在什么地方。
实验五、二叉树的基本操作和应用
实验目的：
熟悉树的基本概念，树状结构的逻辑特性、存储表示方法和二叉树的基本操作。
实验要求：
熟悉树的基本概念，树状结构的逻辑特性、存储表示方法和树的基本操作，实现二叉树的遍历算法（前序、中序和后序遍历）及其简单应用。
实验内容：
(1) 实现行政机构的二叉树表示，设数据元素类型为字符串（如总经理、业务部经理、财务部经理、业务
主管A、业务主管B、业务员A1、业务员A2、业务员B1、业务员B2（可没有）、财务主管A、财务主
管B、财务员A1、财务员A2（可没有）、财务员B1、财务员B2），建立这棵二叉树。
(2) 实现该二叉树的前序、中序和后序遍历，输出遍历结果。
(3) 按职务从高到低的次序依次输出这些职位。（即按层遍历、要求利用队列来实现）
(4) *键盘输入一个职位，查找并输出其上级和下级职位。
(5) *求该机构的职务等级数。
练习及思考题：
（1）不同类型的数据元素所对应的二叉树在类型定义和操作实现上有什么异同？
（2）写出求二叉树的叶子结点数的算法。
（3）如何利用栈，实现二叉树的前序非递归遍历。
实验六、图及其应用
实验目的：
熟悉图的基本概念、逻辑特性、存储表示方法、基本操作和基本应用。
实验要求：
熟悉图的基本概念、逻辑特性、存储表示方法，实现无向网的存储表示、图的深度优先搜索遍历、广度优先搜索遍历、单源最短路径算法。
实验内容：
(1) 实现交通网、通信网或局域网的邻接矩阵存储表示，设数据元素类型为字符串（如地名、房间号等）。
(2) 实现该网的深度优先搜索遍历，输出遍历结果。
(3) *实现上述网络的邻接表存储表示，实现其广度优先搜索遍历，输出遍历结果。
(4) *求从一个地点到其它各个地点的最短路径。
练习及思考题：
（1）图和网的建立算法有何差异？
（2）如何求图中每对顶点之间的最短路径？
实验七（一）、插入排序和交换排序的比较
实验目的：
熟悉插入排序和交换排序算法及其特点。
实验要求：
编写算法实现插入排序和交换排序，并对待排序的数据进行排序。
实验内容：
(1) 设数据元素为学生成绩（含姓名、成绩字段），关键字为学生成绩字段，实现这样的线性表的存储。
数据让用户自行输入。
(2) 编写算法实现插入排序（直接插入排序）和交换排序（快速排序、冒泡排序），要求输出每一趟（遍）
的结果和最终结果，并应用它对上面的数据序列进行排序。
(3)* 证明快速排序算法是不稳定的。
练习及思考题：
（1）简述快速排序的思想。
（2）快速排序算法的效率与每趟排序后分割成的两个文件的大小接近程度有关，这依赖于枢轴元素的选取，试讨论如何选取枢轴元素。
（3）排序方法的稳定性是指什么？那些排序方法是稳定的，那些是不稳定的。
实验七（二）、排序方法的效率比较
实验目的：
熟悉各种排序算法极其特点和效率。
实验要求：
熟悉各种排序算法极其特点和效率。
实验内容：
(1) 输入或给定若干个已经有序或逆序的线性表。
(2) 分别利用选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、*归并排序等各种排序方法对他们进行排序，并输出他们各自的比较和移动记录次数。
(3) 检验实际结果（运行时间和比较、移动记录次数）和理论结果的差异，并进行讨论各种方法的优劣。
(4) * 随机产生100，200，500，1000，2000等若干个随机整数，并将他们存到一个线性表中，再实现内容（2）、（3）的要求。
练习及思考题：
（1）简述各种排序算法的的思想和适用特点。
（2）讨论哪些排序方法适用于单链表，如何实现单链表的这些排序方法。
实验八、顺序和二分查找
实验目的：
熟悉顺序和二分等查找方法。
实验要求：
实现顺序和二分等查找方法。
实验内容：
(1) 建立一个整数构成的顺序表。
(2) 根据用户输入的查找值，实现顺序表的顺序查找。
(3) 建立一个有序的整数构成的顺序表（可直接利用前面排序实验的结果）。
(4) 根据用户输入的查找值，实现二分查找，并输出比较的元素、元素的比较次数等。要求实现递归和非递归算法。
(5) *模拟统计查找长度，随机产生100，200，500，1000，2000等若干个随机整数，在（3）中定义的有序表中查找这些值，统计查找成功和查找不成功的平均查找长度。
练习及思考题：
（1）顺序查找和二分查找的适用范围有何不同。
（2）讨论哪些查找方法适用于单链表，如何实现单链表的这些查找方法。
附：实验报告的主要内容
1.需求和规格说明（问题描述）
描述问题，简述题目要解决的问题是什么，规定软件做什么，原题条件不足时要补全。
2.设计
a.设计思想：存储结构，主要算法的基本思想。不要画框图。
b.设计表示：每个函数或过程的头和规格说明；列出每个函数或过程所调用和被调用的过程和函数。
c.详细设计表示：主要算法的框架。
3.用户手册：即使用说明，如输入怎样的数据、输入多少、何时输入、如何结束等。
4.调试报告：测试用例，测试结果，调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和
分析；改进设想；经验和体会等。
5.附录：源程序清单和结果。程序要加注释，还可手工添加一些注释。测试数据及输出结果。