Competency Training of Data Structure and Algorithm
前修课程：高级语言程序设计、离散数学
一、实验技能训练的目的与要求
通过本课程的实践，学生应掌握链表等复杂的数据结构及相关的性质和算法，熟练使用C++语言的基本语法编写应用程序。
二、相关课程
本课程为“数据结构与算法”配套实验课程。
三、实验技能训练的主要内容和学时安排
本技能训练是《数据结构与算法》课程的配套实践课程，内容为各种数据结构及相关算法，包括顺序表、链表、堆栈、树、图、排序、查找等内容。
序号 1 2 3 4 合 计 总 计 实验 一 二 三 四 顺序表 单链表 二叉树 排序 学 时 数 内 容 实验 时数 2 2 2 2 8 8学时 其他 环节 四、各项技能训练的目的、内容
1、顺序表
实验目的：
掌握顺序表的定位、插入、删除等操作。 实验内容：
（1） 编写一个逐个输出顺序表中所有数据元素的成员函数。并编写主函数测试结果。 （2） 编写顺序表定位操作的成员函数顺序表中查找是否存在数据元素x，如果存在，
返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。并编写主函数测试结果。
（3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 （4） 删除顺序表中所有等于X的数据元素。
2学时
2、单链表
实验目的：
掌握单链表的定位、插入、删除等操作。 实验内容：
2学时
（1） 编写一个逐个输出单链表中所有数据元素的成员函数。并编写主函数测试结果。 （2） 在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 （3） 编写实现带头结点单链表就地逆置的成员函数，并编写主函数测试结果。
3、堆栈和队列
实验目的：
a) 掌握应用栈解决问题的方法。 b) 掌握利用栈进行表达式求和的算法。 实验内容：
（1） 判断一个算术表达式中开括号和闭括号是否配对。
2学时
（2） 假设算术表达式仅由加减乘除运算符组成，编写一个函数对用后缀表达式表示的
算术表达式求值。要求使用顺序堆栈。
4、串、递归算法
实验目的：
a) 掌握串的应用。
b) 掌握递归算法的设计方法。 实验内容：（4选2）
2学时
（1） 设字符串采用静态数组存储结构。编写输出字符串s中值等于字符ch的第一个字
符的函数，并用主函数测试结果。
（2） 设字符串采用静态数组存储结构。编写输出字符串s中值等于字符ch的所有字符
的函数，并用主函数测试结果。
（3） 设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 （4） 测试“汉诺塔”问题。
5、二叉树
实验目的：
a) 掌握二叉树的生成，以及前、中、后序遍历算法。 b) 掌握应用二叉树递归遍历思想解决问题的方法。 实验内容：
2学时
（1） 建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2） 求二叉树中叶结点的个数。
6、图
实验目的：
2学时
a) 熟练掌握图的基本概念、构造及其存储结构。
b) 熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 实验内容：
构造一个无向图（用邻接矩阵表示存储结构），并对此图进行深度优先遍历和广度优先遍历，输出遍历序列。
7、排序
实验目的：
2学时
a) 熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。
b) 掌握以上各种排序的算法。 c) 区分以上不同排序的优、缺点。 实验内容：
用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。
8、查找
实验目的：
a) 掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。 b) 掌握哈希表设计。 实验内容：
（1） 在一个递增有序的线性表中利用二分查找法查找数据元素X。
2学时
（2） 构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。
设计一个测试程序进行测试。
五、实验要求及方法
1． 根据题目，编写程序。 2． 上机调试通过。
3． 按照学院实验报告格式，撰写各实验报告。
六、技能考核
根据要求完成每一个实验内容，根据程序修改和调试的情况决定成绩等次。在规定时间内完成顺利调试通过结果正确为优秀。最后，根据每一个实验的成绩，综合评分。
因篇幅问题不能全部显示，请点此查看更多更全内容