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