彭长根-数据结构与算法实验教学大纲

1、 数据结构与算法 实验教学大纲理学院贵州大学二OO七年八月 数据结构与算法 实验教学大纲课程名称：数据结构与算法 (Data Structure & Algorithms)课程编号：课程性质：专业基础课课程设置类别：非独立设置课程课程总学时：72实验总学时：18实验总学分：1实验周学时：1适用专业及年级：数学与应用数学、信息与计算科学，第四学期先修课程：计算机应用基础、高级语言程序设计大纲主撰人： 彭长根一、实验教学目的和基本要求数据结构是数学与应用数学、信息与计算科学信息管理与信息系统专业的重要专业基础课，数据结构是研究基本数据结构和算法的学科，因此该课程的实践环节很重要，要求学生在实验中，

2、掌握基本算法的程序实现，并能用其基本算法实现应用问题的解决。课程教学的关键是要求学生掌握算法的设计与实现，通过实验加深对讲授内容的理解和培养软件开发的初步能力。本课程要求学生掌握算法的设计、程序设计和调试运行，能正确阐述设计和实验结果、正确绘制系统和程序框图，注重培养动手能力、知识的综合应用能力，并逐步建立正确的程序编写风格。并对结果进行分析。具体要求如下：1要求学生在上机前准备好本次实验所编写的程序，上机时输入和调试自己所编写的程序，解决程序运行过程中所出现的问题，以深入掌握调试程序的技巧。2每次实验必须按要求的格式撰写实验报告，内容大体包括：实验目的、实验内容、算法原理及流程图、程序清单、

3、程序运行结果分析、总结。3实验成绩作为平时成绩的一部分。二、实验内容及学时分配 实验一 线性表的表示与实现（验证性实验，2学时）内容：线性表的顺序表示与实现、线性表的链式表示与实现，包括线性表的插入、删除等算法，并能对1-2实例进行处理。要求：通过实验，要求学生掌握线性表的存储方法，并基于相应的存储表示，如单链表、双链表上能实现初始化、插入结点、删除结点等算法。实验二 栈与队列的表示与实现（验证性实验，4学时）内容：(1). 栈的顺序存储和链式存储结构实现的方法，基于相应的表示实现栈的初始化，入栈、出栈等操作，并能对一个简单实例进行处理。(2). 队列的顺序存储和单链表存储结构的实现方法，实现

4、队列的初始化，入队、出队等操作，并能对一个简单实例进行处理。(3). 顺序存储结构实现循环队列的方法，并实现队列的初始化，入队、出队、队满队空判断等操作，并能对一个简单实例进行处理。要求：能熟练掌握栈和队列的不同表示，并能基于此实现栈和队列的典型操作，理解栈和队列在软件开发中的重要性。实验三 数组的存储与压缩处理（验证性实验，2学时）内容：(1). 数组的表示与实现，并运用于一个实际问题。(2). 用三元组表和十字链表存储结构实现稀疏矩阵的压缩方法，并能实现压缩后矩阵的基本运算。要求：通过实验，使学生深刻理解数组的实现，进一步体会高级语言中一、二维数组功能；掌握矩压缩的方法。实验四 二叉树的存

5、储与实现（验证性实验，2学时）内容：二叉树的存储和基本操作（2学时）、二叉树的应用（Huffman树和Huffman编码，2学时）。要求：通过实验，要求学生掌握用二叉链表存储结构实现二叉树的表示方法，并能实现其基本运算：二叉链表建立及其它有关处理，在此基础上实现Huffman树和Huffman编码。要求掌握树的编程，加深理解递归的原理。实验五 图的表示与遍历（验证性实验，2学时）内容：(1). 图的表示：邻接矩阵和邻接表存储一个图或网络。(2). 图的遍历：DFS遍历和BFS遍历实现。(3). 图的应用：最小生成树、拓朴排序、关键路径和最短路径应用实现。要求：通过实验，要求学生掌握图的存储与实

6、现，在此基础上实现图的DFS遍历和BFS遍历及图的其它处理；通过实验理解图的应用，包括最小生成树、拓朴排序、关键路径和最短路径应用，理解贪心算法。实验六 查找及排序算法设计（验证性实验，2学时）内容：(1). 顺序查找、二分查找、HASH表查找的算法实现。(2). 典型排序算法实现。要求：通过实验，要求学生掌握基本的查找方法的实现，重点是顺序查找、二分查找、HASH表查找等方法；掌握查找表的特点，并能根据查找方法定义合理的存储结构；针对应用，要能基本写出相应的查找算法，并对算法作出分析。通过实验，熟悉目前典型的排序算法及特点，并能比较各种排序算法效率。实验七 应用实例的数据结构与算法设计（设计

7、性实验，4学时）内容：利用学生所学的程序设计、算法设计和相关数学课程实现一个具实例的综合设计，解决数据结构的选取及算法设计，并用C/C+实现程序设计。在项目的实施过程中，要有需求分析、数据分析、系统设计和系统实施过程。要求：本项目涉及到实验项目需要数据结构课程的知识点有：栈、队列、树、图等数据结构的设计，也涉及到查找、排序基本算法。还需要熟练的C/C+编程技术。本项目重点要解决数据结构和算法。本项目要求具有需求分析、功能分析、算法设计和程序实现，最好能以图形界面进行设计。三、主要仪器设备 计算机，VC+平台。四、实验教学方式 机房实验。五、实验考核方式1、本实验课程考核内容主要考查实验报告完成

8、的质量；2、实验课成绩占课程总成绩的20%。六、推荐实验教材和教学参考书 教材：1. 吴艳等数据结构与算法实验教程北京：科学出版社，2006年 2. 严蔚敏，吴伟民编数据结构（C语言版）北京：清华大学出版，2003年主要参考书：严蔚敏，吴伟民编著数据结构题集清华大学出版社，1999年 七、实验课程与学时分配表序号实验项目名称实验内容提要学时分配实验属性实验类型每组人数实验要求指导教师已开/未开1线性表的表示与实现线性表的顺序链式表示与实现，以及线性表的插入、删除等算法2基础验证1必做彭长根已开2栈与队列的表示与实现栈和队列的二种表示与实现，以及初始化，入栈、出栈等操作4基础验证1必做彭长根已开3数组的存储与压缩处理数组的表示与实现；数组的压缩实现2基础验证1必做彭长根已开4二叉树的存储与实现二叉树的存储、基本操作、应用2基础验证1必做彭长根已开5图