《数据结构》课程教学大纲一、课程基本信息二、课程教学目标本课程介绍软件设计中常用的线性表、栈、队列、串、数组、广义表、树、二叉树、图结构等几种基本的数据结构及其存储结构和所施加的运算与实现等。

另外，还介绍软件设计中常用的几种查找和排序算法，以及递归技术等，在介绍各项内容的同时，还涉及到算法设计与分析的基本技术和面向对象程序设计的理论与技术等内容。

通过本课程的学习，达到以下目标：熟练掌握上述结构及其运算的实现和性能特点，掌握各种排序和查找运算以及递归技术，能对给定的实际问题，建立准确的问题模型，设计有效的问题求解方法，选择合理的数据结构及其运算集，设计有效的算法。

三、教学学时分配《数据结构》课程理论教学学时分配表＊理论学时包括讨论、习题课等学时。

《数据结构》课程实验内容设置与教学要求一览表四、教学内容和教学要求第一章绪论（2学时）（一）教学要求1．了解数据结构的各种基本概念和术语；2．了解数据类型和抽象数据类型的概念；3．理解算法的设计目标；4．掌握算法的时间复杂度概念和算法的时间复杂度分析方法。

（二）教学重点与难点教学重点：数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系教学难点：算法复杂度的分析方法。

（三）教学内容第一节什么是数据结构1．数据结构的定义2．逻辑结构类型3．存储结构类型4．数据结构和数据类型第二节算法及其描述1．什么是算法2．算法描述第三节算法分析1．算法设计的目标2．算法效率分析3．算法存储空间分析本章习题要点：基本概念、算法复杂度的分析方法第二章线性表（10学时）（一）教学要求1．理解线性表的逻辑结构和基本操作；2．理解线性表的顺序存储结构和实现方法；3．理解线性表的链式存储结构和实现方法；4．了解单循环链表和双向链表的概念和插入、删除等操作方法。

（二）教学重点与难点教学重点：顺序表和单链表上实现的各种基本算法及相关的时间性能分析。

教学难点：链表本质及其操作的实现算法、线性表相关的应用。

（三）教学内容第一节线性表1．线性表的定义2．线性表的抽象数据类型描述第二节线性表的顺序存储结构1．线性表的顺序存储结构——顺序表2．顺序表基本运算的实现第三节线性表的链式存储结构1．线性表的链式存储结构——链表2．单链表基本运算的实现3．双链表4．循环链表本章习题要点：第三章栈和队列（12学时）（一）教学要求1．理解栈的定义、特征及在其上所定义的基本运算；2．掌握在两种存储结构上对栈所施加的基本运算的实现；3．了解数制转换、括号匹配、表达式运算、迷宫等几种栈的典型应用；4．理解队列的定义、特征及在其上所定义的基本运算；5．掌握在两种存储结构上对队列所施加的基本运算的实现。

（二）教学重点与难点教学重点：栈和队列在两种存储结构上实现的基本运算。

教学难点：栈与递归过程的实现，循环队列中对边界条件的处理。

（三）教学内容第一节栈1．栈的定义2．栈的顺序存储结构及其基本运算实现3．栈的链式存储结构及其基本运算的实现4．栈的应用举例第二节队列1．队列的定义2．队列的顺序存储结构及其基本运算的实现3．队列的链式存储结构及其基本运算的实现4．队列的应用举例本章习题要点：栈和队列的基本运算的实现第四章串（5学时）（一）教学要求1．掌握串的定义、存储及串的比较、求子串、连接、赋值等基本运算；2．了解基本的串模式匹配算法和KMP匹配算法。

（二）教学重点与难点教学重点：串的定义及基本运算，串的模式匹配算法。

教学难点：KMP模式匹配方法。

（三）教学内容第一节串的基本概念第二节串的存储结构1．串的顺序存储结构——顺序串2．串的链式存储结构——链串第三节串的模式匹配1．Brute Force算法2．KMP算法本章习题要点：第五章数组和广义表（3学时）（一）教学要求1．掌握数组的定义及数组元素的存储方式；2．掌握特殊矩阵的压缩存储及运算；3．了解稀疏矩阵的三元组表、理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；4．了解广义表的定义、存储和基本运算。

（二）教学重点与难点教学重点：多维数组的存储方式、矩阵的压缩存储方式。

教学难点：稀疏矩阵的压缩存储表示下实现的算法。

（三）教学内容第一节数组1．数组的基本概念2．数组的存储结构3．特殊矩阵的压缩存储第二节稀疏矩阵1．稀疏矩阵的三元组表示2．稀疏矩阵的十字链表表示第三节广义表1．广义表的定义2．广义表的存储结构3．广义表的运算本章习题要点：特殊矩阵的压缩存储及运算第六章树（12学时）（一）教学要求1．掌握树和二叉树的定义及基本运算；2．掌握二叉树的性质、存储结构和操作的实现方法；3．掌握二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；4．了解二叉树的线索化处理过程；5．了解树的孩子表示法和双亲表示法，了解树的孩子－兄弟表示法；6．掌握树与二叉树的相互转化方法；7．掌握哈夫曼树的概念和哈夫曼树在编码方面的应用方法。

（二）教学重点与难点教学重点：二叉树的性质；二叉树的遍历算法和二叉树遍历算法的应用；哈夫曼树在编码方面的应用方法。

教学难点：二叉树的遍历算法及哈夫曼树的构造算法（三）教学内容第一节树的基本概念1．树的定义2．树的逻辑表示方法3．树的基本术语4．树的存储结构及基本运算第二节二叉树的概念和性质1．二叉树的概念2．二叉树的性质3．二叉树与树、森林之间的转换第三节二叉树存储结构1．二叉树的顺序存储结构2．二叉树的链式存储结构第四节二叉树的基本运算及其实现1．二叉树的基本运算概述2．二叉树的基本运算算法实现第五节二叉树的遍历1．二叉树遍历的概念2．二叉树遍历递归算法3．二叉树遍历非递归算法4．层次遍历算法5．线索二叉树第六节哈夫曼树1．哈夫曼树概述2．哈夫曼树的构造算法3．哈夫曼编码本章习题要点：二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法；第七章图（12学时）（一）教学要求1．掌握图的定义以及顶点的度、连通和强连通、生成树等术语；2．掌握图的邻接矩阵、邻接链表存储，了解图的邻接多重表和十字链表存储；3．掌握图的深度优先遍历和广度优先遍历算法；4．掌握求最小生成树的Prim算法和Kruskal算法；5．掌握拓扑排序算法，了解关键路径求解算法；6．了解求最短路径的迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。

（二）教学重点与难点教学重点：图的数组和邻接表存储方法；图的深度和广度优先搜索算法；图的有关应用问题及算法。

教学难点：深度优先和广度优先遍历算法；最小生成树、关键路径、最短路径的算法思想。

（三）教学内容第一节图的基本概念1．图的定义2．图的基本术语第二节图的存储结构1．邻接矩阵存储方法2．邻接表存储方法第三节图的遍历1．图的遍历的概念2．深度优先搜索遍历3．广度优先搜索遍历第四节生成树和最小生成树1．生成树的概念2．无向图的连通分量和生成树3．普里姆算法4．克鲁斯卡尔算法第五节拓扑排序第六节最短路径1．路径的概念2．从一个顶点到其余各顶点的最短路径3．每对顶点之间的最短路径第七节AOE网与关键路径本章习题要点：图的深度优先遍历和广度优先遍历算法，图的应用。

第八章查找（6学时）教学难点：二叉排序树的插入、删除算法。

（一）教学要求1．掌握查找的基本概念和查找方法的评判标准；2．理解顺序查找和有序查找的算法设计方法，理解索引查找的基本结构；3．掌握二叉排序树定义、创建、插入、删除和查找算法及查找效率分析；4．掌握哈希函数、哈希冲突函数和哈希表的构造方法。

（二）教学重点与难点教学重点：顺序查找、二分查找，二叉排序树上查找以及哈希表上查找的基本思想、算法实现、效率分析。

（三）教学内容第一节查找的基本概念第二节线性表的查找1．顺序查找2．二分查找3．索引存储结构和分块查找第三节树表的查找1．二叉排序树2．平衡二叉树第二节哈希表查找1．哈希表的基本概念2．哈希函数构造方法3．哈希冲突解决方法本章习题要点：各种查找的实现方法。

第九章排序（10学时）教学重点：基本插入排序和希尔排序算法，冒泡排序和快速排序算法，简单选择排序和堆排序算法，归并排序算法，各种排序算法的时间、空间效率分析教学难点：多重循环希尔排序算法、快速排序算法、堆排序算法和归并排序算法（一）教学要求1．掌握基本的插入排序算法、改进算法（希尔排序算法）及算法效率分析；2．掌握冒泡排序、快速排序算法及算法效率分析；3．掌握简单选择排序、堆排序算法及算法效率分析；4．掌握归并排序算法及算法效率分析，了解基数排序方法。

（二）教学重点与难点教学重点：基本插入排序和希尔排序算法，冒泡排序和快速排序算法，简单选择排序和堆排序算法，归并排序算法，各种排序算法的时间、空间效率分析教学难点：多重循环希尔排序算法、快速排序算法、堆排序算法和归并排序算法（三）教学内容第一节排序的基本概念第二节插入排序1．直接插入排序2．希尔排序第三节交换排序1．冒泡排序2．快速排序第四节选择排序1．直接选择排序2．堆排序第五节归并排序第六节基数排序本章习题要点：各种排序的实现方法。

五、教学方法或手段1、教学方法，采用讲授法与自学辅导式相结合的教学方法。

2、教学手段，采用多媒体教学手段。

六、考核方式及评价要求本课程是计算机科学与技术专业基础课，以笔试方式为主进行考试，考试内容应体现教学大纲的基本要求，笔试成绩占60%，上机实验占据20%，平时成绩占据20%。

七、教材及教学主要参考书推荐教材：《数据结构教程》，李春葆主编，清华大学出版社，2013年6月第4版。

《数据结构》，严蔚敏主编，清华大学出版社，2012年7月第5版。