数据结构课程教学大纲1

1、数据结构课程教学大纲课程名称：数据结构英文名称：Data Structures课程编号：学 时 数：80其中实验（实训）学时数：24 课外学时数：0学 分 数：5.0适用专业：计算机科学与技术一、课程的性质和任务数据结构是计算机学科各专业本科学生必修的一门专业基础课，是计算机程序设计的重要理论和实践基础，是培养学生软件设计能力的一门重要课程，在计算机学科的本科教学中，起着非常重要的作用。本课程研究计算机系统中常用的线性表、二叉树、图等典型数据结构的设计方法，研究各种典型排序和查找算法的设计方法和性能指标，并介绍这些数据结构和算法在实际工程中的应用。通过学习本课程，使学生深入理解软件设计的基本要

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

3、储结构；熟练运用递归函数表达递归定义、递归算法和递归结构。理解插入、交换、选择、归并等多种典型排序算法的思想，掌握在线性表、树等各种不同数据结构中的查找算法。掌握在计算机语言环境中编辑、编译、运行程序的方法，以及单步运行、设置断点、查看变量运行时值等调试程序的方法。具体设置如下：（一）绪论了解和掌握数据结构的基本概念，这些概念包括:数据、数据元素、数据类型、抽象数据类型、数据逻辑结构、数据存储结构、数据结构上的操作集合、 算法及算法特点等。了解和掌握算法效率分析的意义和方法。重点：抽象数据类型表示。难点：抽象数据类型的概念和表示形式。（二）线性表了解线性表的逻辑结构和基本操作；理解线性表的顺序

4、存储结构和实现方法；理解线性表的链式存储结构和实现方法；了解单循环链表和双向链表的概念和基本设计方法。重点：顺序存储结构和顺序表的设计方法。难点：单链表的存储结构设计及算法的实现。（三）栈和队列理解栈的概念、顺序栈和链式栈的设计方法；理解队列的概念、顺序循环队列和链式队列的设计方法；了解优先级队列以及优先级队列和一般队列的差别；了解堆栈和队列的应用方法。重点：栈和队列的基本概念及其各种操作算法的设计和实现。难点：栈的应用算法和循环队列的实现。（四）字符串理解串的概念和串的基本操作；理解串的静态存储结构、动态存储结构和链式存储结构；了解串基本操作的实现方法；了解串的BF模式匹配方法和KMP模式匹

5、配方法。重点：字符串操作算法的设计和实现。难点：串的模式匹配算法。（五）广义线性表熟练掌握数组的概念和数组的静态、动态存储结构；了解特殊矩阵的压缩存储方法；了解稀疏矩阵的基本压缩存储方法，包括稀疏矩阵的三元组概念，以及稀疏矩阵三元组的顺序表、单链表和十字链表存储结构。重点：特殊矩阵和稀疏矩阵的压缩存储方法。难点：特殊矩阵和稀疏矩阵的存储结构设计及其算法设计。（六）递归算法正确理解递归的概念、递推公式的归纳方法和递归算法的执行过程；熟练掌握递归算法的问题分析和算法设计方法；了解递归算法时间效率低的原因。重点：递推公式的归纳；递归算法的执行过程；递归算法的设计方法。难点：递归技术的原理、实现和运用

6、。（七）树与二叉树了解树的定义、表示方法及其典型存储结构；理解二叉树的定义、性质、存储结构和操作的实现方法；掌握二叉树的遍历算法及其应用实现；理解哈夫曼树的概念及其应用；了解树与二叉树的关系。重点：二叉树的性质、二叉树的存储结构；二叉树的遍历算法和二叉树遍历算法的应用；哈夫曼树在编码方面的应用方法。难点：有关树和二叉树的各种递归算法。（八）图了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；理解图的深度和广度优先遍历方法和算法设计方法；理解最小生成树的概念以及普里姆算法和单源最短路径的狄克斯特拉算法。重点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历方法；普

7、里姆算法和狄克斯特拉算法。难点：图的两种遍历算法以及各应用问题的求解算法。（九）排序了解排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择排序、堆排序、快速排序、二路归并排序、基数排序的算法思想和算法设计方法；理解各种排序方法的性能特点。重点：希尔排序、堆排序、快速排序、二路归并排序和基数排序的算法思想。难点：堆排序、快速排序、二路归并排序和基数排序的算法设计方法。（十）查找了解查找的基本概念和查找方法的评判标准；理解顺序查找，掌握有序查找的算法设计方法，理解索引查找的基本结构；了解二叉排序树和B-树的基本结构和插入、删除方法；掌握哈希函数、哈希冲突函数和哈希表的构造方法

8、。重点：二叉排序树和二叉排序树的插入和删除方法；哈希函数、哈希冲突函数和哈希表的构造方法。难点：二分查找，二叉排序树的构造，哈希表的冲突处理。三、教学方式及学时分配序号主要内容主要教学方式学时分配辅导答疑比例一绪论讲授42：1二线性表讲授+实验12+42：1三栈和队列讲授+实验6+22：1四字符串讲授22：1五广义线性表讲授+实验4+22：1六递归算法讲授22：1七树与二叉树讲授+实验8+42：1八图讲授+实验10+42：1七排序讲授+实验6+22：1十查找讲授+实验6+22：1四、课程其他教学环节要求数据结构课程是一门理论和实践相结合的课程，不仅仅要注重理解基本知识，更要注重培养软件设计的基

9、本技能。实践性环节是巩固所学理论知识、使理论与实际相结合、提高程序设计能力和计算机操作能力的一项必不可少的重要环节。因此，课后习题、上机实验和课程设计等都是加强程序设计训练所必需的。本课程安排的上机实验学时为24学时，课内开设的12个实验说明如下。实验一：线性表操作（一） 要求：掌握顺序存储结构的特点和常见算法。实验二：线性表操作（二） 要求：掌握链式存储结构的特点和常见算法。实验三：栈和队列操作 要求：掌握栈和队列操作，设计新的成员函数，并进行测试。实验四：多维数组和广义表操作 要求：掌握这两种操作、及新的成员函数，并测试。实验五：树和二叉树（一） 要求：掌握二叉树的存储实现、二叉树的遍历思

10、想。实验六：树和二叉树（二） 要求：掌握二叉树的常见算法的程序实现。实验七：图的有关操作（一） 要求：掌握图的存储思想及其存储实现、图的深度、广度优先遍历算法思想及其程序实现。实验八：图的有关操作（二） 要求：掌握图的常见应用算法的思想及其程序实现。实验九：查找 要求：掌握顺序查找，折半查找，二快速排序，堆排序等二叉排序树算法。实验十：排序 要求：掌握常见的排序算法的思想及其适用条件、常见的排序算法的程序实现。实验十一：综合实验（一） 要求：使用数据结构中各种算法编写系统类结构。实验十二：综合实验（二） 要求：结合实验十一的设计，完成综合系统的实现和调试。本课程通过课堂讲授例题、课堂练习、课后

11、习题、上机实验以及课程设计等各个实践环节，对学生进行系统的程序设计训练。所有例题、课堂练习题、课后习题、上机实验题都是精心挑选的，由浅入深，环环相扣，步步推进，调动学生的主动性和自觉性并培养学生写程序的兴趣。除了课内安排的习题课、课堂讨论、期中测验、复习课以外，每次课后都要求学生做至少2个完整的程序，并定期检查学生做作业的情况，作业的数量和质量占平时成绩的一部分。考核方式说明：本课程为考试课程，期末考试为闭卷笔试。学生的课程总评成绩由平时成绩（占30%）和期末考试成绩(70%)两部分构成，平时成绩中实验成绩占20%，出勤、作业、课堂测验、学习主动性等占10%。实验成绩根据实验报告质量评定，作业成绩根据习题的数量和质量评定。五、本课程与其他课程的联系本课程是计算机专业基础课，其先修课程是程序设计语言、离散数学，后续课程包括算法设计与分析、编译技术、操作系统等课程。六、教学参考书目数据结构（C+版），王红梅编著，清华大学出版社，2008年。数据结构（C+版），叶核亚编著，机械工业出版社，2004年。数据结构及应用算法教程，严蔚敏等编著，清华大学出版社，2001年。数据结构（用面向对象方法与C+描述），殷人昆等编著，清华大学出版社，1999年。数据结构教程