《数据结构》实验课件

1、精品教学课件设计| Excellent teaching plan本实验讲义共分为十五个单元，每个单元对应一次上机实验课。不带 “ * ” 号的上机实验题目， 主要是为帮助学生深化理解教学内容， 澄清基本概念， 并以基本程序设计技能训练为主要目的而设； 而带号的上机实验题目，可激起学生的学习潜能，并对广泛开拓思路有益。单元一 顺序存储的线性表【学习要点】了解线性表的逻辑结构特征，熟练掌握线性表的顺序存储结构的描述方法，及在其上实现各种基本运算的方法。设线性表存放在向量Aarrsize 的前 elenum 个分量中， 且递增有序。试设计一算法， 将 x 插入到线性表的适当位置上， 以保持线性表的

2、有序性。用向量作存储结构，试设计一个算法，仅用一个辅助结点，实现将线性表中的结点循环右移 k 位的运算。用向量作存储结构，试设计一个算法，仅用一个辅助结点，实现将线性表逆置的运算。单链表单元二【学习要点】熟练掌握线性表的单链式链接存储结构及在其上实现线性表的各种基本运算的方法。实验一：已知带头结点的动态单链表L 中的结点是按整数值递增排序的，试写一算法将值为 x 的结点插入到表L 中，使 L 仍然有序。实验二：设计一算法，逆置带头结点的动态链表L 。要求利用原表的结点空间，并要求用尽可能少的时间完成。实验三：假设有两个按元素值递增有序的线性表A 和 B, 均以单链表作存储结构，试编写算法将A表

3、和B表归并成一个按元素值递减有序的线性表C,并要求利用原表的空间存放C。单元三 栈和队列【学习要点】1. 掌握栈和队列的数据结构的特点； 2. 熟练掌握在两种存储结构上实现栈和队列的基本运算； 3. 学会利用栈和队列解决一些实际问题。实验一:设单链表中存放着n 个字符，设计算法，判断该字符串中是否有中心对称关系。例如： xyzzyx 、 xyzyx 都算是中心对称的字符串。实验二:设计算法判断一个算术表达式的圆括号是否配对。 （提示： 对表达式进行扫描，遇 （ 进栈，遇 ） 退掉栈顶的 （ ，表达式被扫描完毕，栈为空 ）实验三 :假设以带头结点的循环链表表示队列，并只设一个指针指向队尾，编写相

4、应的置队空、入队和出队算法。单元四 串【学习要点】熟练掌握串的顺序和链接存储结构的实现方法；熟练掌握在两种存储结构上实现串的各种运算。实验一：若 X 和 Y 是用结点大小为1 的单链表表示的串，设计算法找出 X 中第一个不在 Y 中出现的字符。实验二：设计一算法，在顺序串上实现串的比较运算strcmp(S,T) 。单元五 多维数组和广义表【学习要点】理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵试进行矩阵运算采用的处理方法；熟悉广义表的定义及其存储结构，学会广义表的表头、表尾分析方法，学习编制相应的递归算法。* 实验一：假设稀疏矩阵A 和 B 均以三元组表作为存储结构，试

5、分别写出满足以下条件的矩阵相加运算的算法：(1) 另设三元组表C 存放结果矩阵。(2)假设三元组表 A的空间足够大，将矩阵B加到矩阵A上，不增加A B之外的附加空间，要求算法的时间复杂度为O(m+n),其中m,n为A、B矩阵中非零元素的数目。实验二：设计一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及 其下标的算法。单元六 树(一)【学习要点】熟悉二叉树的各种存储结构的特点及适用范围；掌握建立二叉树的存储结构的方法；熟练掌握二叉树的前序、中序、后序遍历的递归及非递归算法；灵活运用递归的遍历算法实现二叉树的其它各种运算。实验一：以二叉链表作存储结构，设计求二叉树高度的算法。实验二：一棵

6、n 个结点的完全二叉树用向量作存储结构，用非递归算法实现对该二叉树进行前序遍历。实验三 :以二叉链表作存储结构，编写非递归的前序、中序、后序遍历算法。单元八七 树（二）【学习要点】灵活运用非递归的遍历算法实现二叉树的其它各种运算；掌握按层次顺序遍历二叉树的方法；熟练掌握在中序线索二叉树上找给定结点的指定顺序下的前驱和后继的方法。* 实验一：以二叉链表作存储结构，设计按层次顺序（同一层自左向右）遍历二叉树的算法。* 实验二：在二叉树中查找值为 x 的结点，编写算法打印值为 x 的结点的所有祖先。假设值为 x 的结点不多于1 个。单元八 图（一）【学习要点】熟练掌握图的两种存储结构的实现方法；熟练

7、掌握遍历图的递归和非递归算法。实验一：设计算法，构造图的邻接链表，并递归地实现基于邻接链表的图的深度优先搜索遍历。* 实验二：利用基于邻接矩阵的图的深度优先搜索算法，判别有向图中是否存在由顶点Vi到顶点Vj的路径（i wj ）。单元十 排序（一）【学习要点】熟练掌握在顺序表上实现排序的各种方法；深刻理解各种排序方法的特点，并能灵活运用。实验一：编写双向起泡排序算法。实验二：编写算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字的前面。单元十一排序（二）【学习要点】熟练掌握在动态链表及静态链表上实现各种排序算法; 掌握基数排序的实现方法。实验一：以单链表为存储结构实现直接选择排序。实验二：用先查找插入位置， 后插入的方法， 在静态链表上实现直接插入排序。单元十二查找（一）【学习要点】熟练掌握顺序查找、二分查找、分块查找的递归及非递归算法；熟练掌握散列表上的各种操作。实验一：给出递归的二分查找算法。实验二：设计用拉链法解决冲突