数据结构实验教学大纲(教育技术).doc

《数据结构》实验教学大纲课程总学时：64＋32 学分：5 实验学时：32 实验个数： 实验学分： 1 课程性质：必做 适用专业： 计算机科学与技术、软件工程、网络工程 教材及参考书：数据结构（C 语言版） ，严蔚敏 吴伟民，清华大学出版社，2002 年 9 月第 1 版 ；数据结构题集（C 语言版）实习题部分，清华大学出版社；数据结构实验教程，王玲 刘芳 贺春林等，四川大学出版社，2002 年 10 月， 大纲执笔人：刘芳 大纲审定人： 一、实验课的性质与任务计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写 计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法， 这是数据结构课程中学习和研究的内容由于数据结构的原理和算法较抽象，而该课程一 般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得 较为困难 《数据结构》实验课程着眼于原理和应用的结合点，使读者学会如何将书上学到的知 识用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活” ，起到深化理解和灵活掌握教学内容的目的。

平时练习较偏重于如何编写功能单一的“小” 算法，而实习题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、 程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养 此外，还有很重要的一点是：机器是比任何老师更严厉的检查者 训练的重点在于基本的数据结构，而不是强调面面俱到各实习单元与教科书的各章 只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容 二、实验课程目的与要求 1. 实验目的 根据《数据结构》课程的任务与要求，帮助学生拓宽知识面并达到以下教学要求： 1)学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适 当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空 间分析的技术；掌握各种基本数据结构的逻辑结构和存储结构及相应算法 2)本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构 清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力； 3)通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面 向对象的程序做一些铺垫 2.实验要求 1)熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧 以及如何根据实际问题设计一个有效的算法。

2)会书写类 C 语言的算法，并将算法转变为程序实现 3)正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较 强的逻辑分析能力 4)针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能三、实验项目及内容提要 数据结构实验课程 （课程编号）实验类型序号实验项目编号实验名称学 时必 做选 做学 分 数基 本 操 作验 证综 合设 计内容提要1抽象数据 类型的表 示与实现2√√√抽象数据类型的表 示与实现2线性表实 验6√√√线性表的存储实现 及有关应用3栈和队列 实验8√√√栈和队列的基本操 作及其实现，以及 典型应用举例4树和二叉 树实验6√√树的两种种存储结 构，及各种操作的 算法实现（建立、 遍历、线索化、最 优二叉树）5图及其应 用实验6√√图的两种基本存储 结构，及各种操作 的算法实现（建立、 遍历）6查找和排 序实验4√√√一种基本的查找和 排序算法及其实现 分析四、实验内容安排： 实验一 抽象数据类型的表示与实现 （ 验证性实验 2 学时） 1.目的要求： 1) 熟悉类 C 语言的描述方法，学会将类 C 语言描述的算法转换为 C 源程序实现； 2)理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组） 。

3)认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结 果，并结合程序进行分析 2.实验内容： 1）编程实现抽象数据类型三元组的定义、存储、基本操作（最大值、最小值、平均值 等的求解） ，并设计一个主菜单完成各个功能的调用 3.主要仪器设备及药品1）PC 机 2）Turbo C 2.0 或 Visual C++ 实验二 线性表实验 （ 验证性实验 6 学时） 1.目的要求： 1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2）以线性表的各种操作（建立、插入、删除等）的实现为重点； 3）通过本次实习帮助学生加深对高级语言 C 语言的使用（特别是函数参数、指针类型、 链表的使用） 4)认真阅读和掌握本实验的参考程序，上机运行本程序， 保存和打印出程序的运行 结果，并结合程序进行分析按照你对线性表的操作需要，重新改写主程序并运 行，打印出文件清单和运行结果 3.实验内容： 1） 编程实现线性表两种存储结构中的基本操作的实现（线性表的创建、插入、删除 和查找） ，并设计一个主菜单完成各个功能的调用 3.主要仪器设备及药品1）PC 机 2）Turbo C 2.0 或 Visual C++ 实验三 栈、队列实验 （ 验证性试验 8 学时） 1.目的要求： 1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运 用它们。

2）本实验训练的要点是“栈”和“队列”的观点； 2.实验内容： 1） 利用栈，实现数制转换 2） 利用栈，实现任一个表达式中的语法检查（选做） 3） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、 出队列） ； 3.主要仪器设备及药品 1)PC 机 2)Turbo C 2.0 或 Visual C++实验四 树及二叉树实验 （ 验证性 、应用性 6 学时） 1.目的要求： 1)树是一种重要的非线性数据结构，要求掌握二叉树的两种基本的存储结构，及各种 操作的算法实现（建立、遍历）以及应用 2)本实验训练的要点是：递归算法的设计方法以及二叉树的应用 2.实验内容： 1)按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，然 后按先序、中序、后序顺序分别遍历这棵二叉树2)编写一个求二叉树叶子结点数的算法 3.主要仪器设备及药品 1)PC 机 2)Turbo C 2.0 或 Visual C++实验五 图及其应用实验 （ 验证性 6 学时） 1.目的要求： 1)图是一种重要的非线性数据结构，要求掌握图的两种基本的存储结构（邻接矩阵、 邻接表） ，以及图的基本算法实现（建立、深度优先遍历、广度优先遍历） ，并能 运用图结构分析解决一些实际问题。

2)本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、 遍历） 2.实验内容： 1)建立无向图和有向图的邻接矩阵存储，计算顶点的度，并按要求输出图的基本信 息 2)建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后按照要 求输出图的基本信息 3.主要仪器设备及药品 1)PC 机 2)Turbo C 2.0 或 Visual C++实验六 查找与排序实验 （ 验证性实验 6 学时） 1.目的要求： 1) 学生在实习中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效 算法的可能性和寻找、构造高效算法的方法 2.实验内容： 1)实现二分查找算法 2)实现插入排序或选择排序算法 3.主要仪器设备及药品 1)PC 机 2)Turbo C 2.0 或 Visual C++。