《数据结构》实验讲义.doc

《《数据结构》实验讲义.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

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

7、图的深度优先搜索遍历。6《数据结构》实验讲义*实验二：利用基于邻接矩阵的图的深度优先搜索算法，判别有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。单元十排序（一）【学习要点】熟练掌握在顺序表上实现排序的各种方法；深刻理解各种排序方法的特点，并能灵活运用。实验一：编写双向起泡排序算法。实验二：编写算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字的前面。单元十一排序（二）【