《数据结构》课程教学大纲

1、数据结构课程教学大纲课程编号：课程名称：数据结构英文名称：Data Structure课程类型：专业基础必修课总 学 时：72 讲课学时：56 上机学时：16 学时：72学分：4.5适用对象：计算机科学与技术专业本科生先修课程：计算机导论、C/C+程序设计I、C/C+程序设计II、离散数学一、课程性质、目的和任务数据结构是计算机学科各专业本科学生必修的一门专业基础课，是计算机程序设计的重要理论和实践基础，是培养学生软件设计能力的一门重要课程，在计算机学科的本科教学中，起着非常重要的作用。本课程研究计算机系统中常用的线性表、二叉树、图等典型数据结构的设计方法，研究各种典型排序和查找算法的设计方法

2、和性能指标，并介绍这些数据结构和算法在实际工程中的应用。通过学习本课程，使学生深入理解软件设计的基本要素和基本结构，培养逻辑思维能力，提高程序设计能力。数据结构课程是一门理论和实践相结合的课程，上机实验、课程设计等实践性环节必不可少。二、教学基本要求本课程是理论与实践并重的课程，要求学生既要掌握数据结构的基础理论知识，又要掌握操作计算机和运行、调试程序的基本技能；能够熟练运用C/C+语言或其它计算机语言编制具有中等难度的应用程序，在实践中培养独立分析问题和解决问题的作风和能力。本课程的基本要求如下。理解线性表、栈、队列、串、数组、树、二叉树、图等基本的数据逻辑结构，掌握描述这些数据结构、选择合

3、适的存储结构和实现各种操作的方法。熟练运用C/C+语言或其它计算机语言表达链式存储结构；熟练运用递归函数表达递归定义、递归算法和递归结构。理解插入、交换、选择、归并等多种典型排序算法的思想，掌握在线性表、树等各种不同数据结构中的查找算法。掌握在计算机语言环境中编辑、编译、运行程序的方法，以及单步运行、设置断点、查看变量运行时值等调试程序的方法。三、教学内容及要求1绪论 了解数据结构的基本概念，了解数据的逻辑结构、数据的存储结构和对数据的操作，了解抽象数据类型与数据结构的关系。 了解算法的概念、算法描述的方法、算法设计目标和算法分析方法，掌握算法的时间复杂度分析方法。2线性表 理解线性表的逻辑结

4、构和基本操作。 掌握线性表的顺序存储结构和实现方法。 掌握线性表的链式存储结构和实现方法；比较两种存储结构的特点和性能。 掌握单向链表、单向循环链表、双向链表、双向循环链表的概念和基本设计方法。3串 理解串的概念和串的基本操作，理解串的静态存储结构、动态存储结构和链式存储结构。 掌握串的定义和基本操作的实现方法。 掌握串的模式匹配方法。4栈和队列 理解栈的概念和作用，掌握顺序栈和链式栈的设计方法，掌握使用栈的算法设计方法。理解栈在递归等算法中的应用。 理解队列的概念和作用，掌握顺序循环队列和链式队列的设计方法，掌握使用队列的算法设计方法。5数组和广义表 理解数组的概念，理解一维数组和二维数组的

5、存储结构。 了解特殊矩阵的压缩存储方法。 了解稀疏矩阵的基本压缩存储方法。 了解广义表的概念和存储结构。6树和二叉树 了解树的定义、树的术语、树的表示方法和树的几种典型存储结构。 理解二叉树的定义、二叉树的性质、二叉树的存储结构和二叉树的多种遍历算法的基本概念。 掌握二叉树结点类、二叉树类的设计与实现；掌握多种二叉树遍历算法实现，比较二叉树遍历递归算法与非递归算法的实现和特点。 理解线索二叉树的概念，掌握线索二叉树结点类、中序线索二叉树类的设计与实现，掌握中序线索化二叉树的递归算法。 掌握哈夫曼树的概念、算法实现，理解哈夫曼树在信息论编码中的应用。 理解树与二叉树的转换方法；理解树的遍历方法。

6、7图 了解图的基本概念和术语。 掌握图的邻接矩阵和邻接表存储结构。 理解并实现图的深度优先遍历和广度优先遍历算法。 理解最小生成树的概念，掌握两种构造图的最小生成树算法：普里姆算法和克鲁斯卡尔算法。 了解最短路径问题的基本概念，了解单源最短路径算法。 8查找 理解查找的基本概念和查找方法的评判标准。 掌握线性表的顺序查找、折半查找、分块查找的算法设计方法，理解索引查找的基本结构。 掌握二叉排序树的建立及其查找算法。 理解哈希表、哈希函数、解决冲突方法等哈希查找技术的概念，掌握拉链法哈希表的构造方法、动态插入、删除元素、查找算法等。9排序 理解排序的基本概念和排序算法的评判标准。 掌握顺序存储结

7、构的直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、二路归并排序的算法思想和算法设计方法；比较各种排序方法的特点和性能。 了解链式存储结构的直接插入排序和直接选择排序的算法设计方法。四、实践环节数据结构课程是一门理论和实践相结合的课程，不仅仅要注重理解基本知识，更要注重培养软件设计的基本技能。实践性环节是巩固所学理论知识、使理论与实际相结合、提高程序设计能力和计算机操作能力的一项必不可少的重要环节。因此，课后习题、上机实验和课程设计等都是加强程序设计训练所必需的。本课程安排的上机实验学时为16学时，课内开设的8个实验说明如下。实验1 线性表的顺序存储结构和链式存储结构（设计型

8、） 2学时实验2 顺序串类及串的模式匹配算法 2学时实验3 栈和队列及其应用 2学时实验4 建立及遍历二叉树（设计型） 2学时实验5 线索二叉树，哈夫曼算法 2学时实验6 顺序查找，折半查找，二叉排序树（设计型） 2学时实验7 排序算法比较及性能评价 2学时实验8 图的建立与遍历，最小代价生成树 2学时每次实验后均要求学生写出实验报告，实验报告内容包括：题目、题意解释、题意分析、设计方案、流程描述、源程序清单、程序运行结果、程序存在问题和改进意见等。五、课外习题及课程讨论本课程通过课堂讲授例题、课堂练习、课后习题、上机实验以及课程设计等各个实践环节，对学生进行系统的程序设计训练。所有例题、课堂

9、练习题、课后习题、上机实验题都是精心挑选的，由浅入深，环环相扣，步步推进，调动学生的主动性和自觉性并培养学生写程序的兴趣。除了课内安排的习题课、课堂讨论、期中测验、复习课以外，每次课后都要求学生做至少2个完整的程序，并定期检查学生做作业的情况，作业的数量和质量占平时成绩的一部分。六、教学方法与手段本课程的课堂教学采用板书与多媒体相结合的方式进行，以板书教学为主，多媒体教学为辅。其中，课程主要内容采用板书教学，计算机语言环境的使用和程序运行需要采用多媒体的方式进行演示。七、各教学环节学时分配章节（或内容）讲课习题课讨论课实验其它合计绪论44线性表8210串426栈和队列628数组和广义表44树和

10、二叉树8412图628查找628排序8210复习22合 计5421672八、考核方式本课程为考试课程，期末考试为闭卷笔试。学生的课程总评成绩由平时成绩（占30%）和期末考试成绩两部分构成，平时成绩中实验成绩占20%，出勤、作业、课堂测验、学习主动性等占10%。实验成绩根据实验报告质量评定，作业成绩根据习题的数量和质量评定。九、推荐教材和教学参考书教 材：数据结构（C+版），叶核亚编著，机械工业出版社，2004年。参考书：数据结构及应用算法教程，严蔚敏等编著，清华大学出版社，2001年。数据结构（用面向对象方法与C+描述），殷人昆等编著，清华大学出版社，1999年。十、说明另设一周课程设计。大纲

11、制订人：叶核亚大纲审定人：黄纬制订日期：2010年5月数据结构课程实验教学大纲一、实验教学目标与基本要求数据结构是计算机学科各专业本科学生必修的一门专业基础课。数据结构课程是一门理论和实践相结合的课程，不仅仅要注重理解基本知识，更要注重培养软件设计的基本技能。实践性环节是巩固所学理论知识、使理论与实际相结合、提高程序设计能力和计算机操作能力的一项必不可少的重要环节。其中，上机实验是加强程序设计训练所必需的一个重要环节。实验基本要求如下：验证教材中已设计好的算法，给出多种运行结果并分析比较，进一步理解和巩固数据结构基本原理和算法设计原则，积累软件设计经验。熟练运用C/C+语言或其它计算机语言，综

12、合数据结构基本原理和算法设计原则，独立设计出具有中等难度的应用程序，编译、运行程序，获得正确的结果；分析算法性能并给出总结，进一步提高算法性能并降低算法复杂度。掌握在计算机语言环境中编辑、编译、运行程序的方法，以及单步运行、设置断点、查看变量运行时值等调试程序的方法。具备操作计算机和运行、调试程序的基本技能。二、本实验课程的基本理论与实验技术知识数据结构的基本理论，根据数据的逻辑结构，选择合适的数据存储结构，设计对数据进行各种操作的算法。算法的基本设计原则，算法必须达到正确性、可读性、健壮性、高时间效率、高空间效率等基本目标。熟悉在计算机语言环境中编辑、编译、运行和调试程序的方法。三、实验方法

13、、特点与基本要求掌握计算机系统的基本操作，掌握在计算机语言环境中编辑、编译、运行和调试程序的多种方法，具备运行和调试程序的基本技能，发现程序有错时，能够找到错误所在并改正错误。四、实验主要仪器设备计算机。五、实验项目的设置与内容提要总实验学时为 16 学时。序号实验项目内 容 提 要实验学时实验类型每组人数实验要求1线性表掌握线性表的概念，实现线性表的顺序存储结构和链式存储结构下的基本操作，实现单链表复制等操作。2设计1必做3串顺序串类的算法实现及串的模式匹配算法。2验证1必做4栈和队列使用栈和队列结构实现表达式计算等算法。2验证1必做5二叉树验证建立及遍历二叉树算法，设计复制二叉树的算法。2设计1必做6线索二叉树及哈夫曼算法建立并线索化中序线索二叉树；验证哈夫曼算法。2验证1必做8图验证图的建立与遍历算法，最小代价生成树算法2验证1必做7查找顺序查找，折半查找，二叉排序树2设计1必做2排序多个排序算法比较及性能评价。2验证1必做六、实验报告要求每次实验后均要求学生写出实验报告，实验报告内容包括：题目、题意解释、题意分析、设计方案、流程描述、源程序清单