《数据结构实验》教学大纲.docVIP

《数据结构实验》教学大纲 课程名称：数据结构实验 课程编码：084300507 总 学 时：36学时 适用对象：电子信息科学与技术 一、教学目的与任务 《数据结构》是计算机几相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。 二、教学基本要求 《数据结构》在计算机科学中是一门综合性的专业基础课，是计算机专业的核心课程。它不仅是一般程序设计的基础，而且也是设计和实现编译程序、操作系统及其他系统程序和大型应用程序的重要基础。随着计算机在非数值计算领域的应用的不断壮大，数据结构的研究与实际应用也显得越来越重要。由于数据结构中有大量的复杂算法，因此数据结构实验课在数据结构教学中占有重要的地位。通过实验要求学生更好的巩固和掌握所学的内容。 三、教学内容及要求 实验一 抽象数据的学习 实验目的： ⑴ 掌握抽象数据的表示和实现方法。 ⑵ 熟悉高级语言的实现方法。 ⑶ 掌握抽象数据常见算法。 实验仪器：计算机，打印机 实验内容： ⑴ 编写复数四则运算程序。 ⑵ 编写有理数四则运算程序。 ⑶ 编写简单的作图程序。 实验二 线性表的顺序存储结构 实验目的： ⑴ 掌握顺序存储结构的特点。 ⑵ 掌握顺序存储结构的常见算法 实验仪器：计算机，打印机 实验内容： ⑴ 输入一组整型元素序列，建立顺序表。 ⑵ 实现该顺序表的遍历。 ⑶ 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 ⑷ 判断该顺序表中元素是否对称,对称返回1,否则返回0。 ⑸ 实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 ⑹ 输入整型元素序列利用有序表插入算法建立一个有序表。 ⑺ 利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 ⑻ 编写一个主函数,调试上述算法。 *⑼ 综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。 实验三 单向链表的有关操作 实验目的： ⑴ 掌握单向链表的存储特点及其实现。 ⑵ 掌握单向链表的插入、删除算法及其应用算法的程序实现。 实验仪器：计算机，打印机 实验内容： ⑴ 随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 ⑵ 遍历单向链表。 ⑶ 把单向链表中元素逆置（不允许申请新的结点空间）。 ⑷ 在单向链表中删除所有的偶数元素结点。 ⑸ 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 ⑹ 利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 ⑺ 利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。 ⑻ 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。 *⑼ 采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。 ⑽ 在主函数中设计一个简单的菜单，分别调试上述算法。 *⑾ 综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中） 实验四 栈和队列及其应用 实验目的： ⑴ 掌握栈、队列的思想及其存储实现。 ⑵ 掌握栈、队列的常见算法的程序实现。 实验仪器：计算机，打印机 实验内容： ⑴ 采用链式存储实现栈的初始化、入栈、出栈操作。 ⑵ 采用顺序存储实现栈的初始化、入栈、出栈操作。 ⑶ 采用链式存储实现队列的初始化、入队、出队操作。 ⑷ 采用顺序存储实现循环队列的初始化、入队、出队操作。 ⑸ 在主函数中设计一个简单的菜单，分别测试上述算法。 *⑹ 综合训练:1)利用栈实现表达式求值算法。 2)利用栈实现迷宫求解。 实验五 串及其应用 实验目的： ⑴ 熟悉串类型的实现方法。 ⑵ 熟悉文本模式匹配方法。 ⑶ 掌握一般文字处理软件的设计方法。 实验仪器：计算机，打印机 实验内容： ⑴ 设计简单的文本处理软件。 ⑵ 设计文本格式化程序。 ⑶ 设计简单的行编辑程序。 ⑷ 串基本操作的演示。 实验六 二叉树的常见操作 实验目的： ⑴ 掌握二叉树的存储实现。 ⑵ 掌握二叉树的遍历思想。 ⑶ 掌握二叉树的常见算法的程序实现。 实验仪器：计算机，打印机 实验内容： ⑴ 输入字符序列，建立二叉链表。 ⑵ 中序遍历二叉树:递归算法。 ⑶ 中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法） ⑷ 求二叉树的高度 。 ⑸ 求二叉树的叶子个数。 *⑹ 将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。 *⑺ 建立中序线索二叉树，并实现中序遍历。 ⑻ 借助队列实现二叉树的层次遍历。 ⑼ 在主函