《算法与数据结构》教学大纲

发布时间：2020-03-02 07:38:34 来源：范文大全收藏本文下载本文手机版

《算法与数据结构》教学大纲

一、使用说明

（一）课程性质

《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为C程序设计或C++程序设计。

（二）教学目的

学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。

（三）教学时数

课堂讲授每周4学时，18周，共72学时。

（四）教学方法

本课程将采用课堂讲授及课堂讨论相结合的交互式教学法，同时辅以必要的上机操作实践。

（五）面向专业

计算机科学与技术专业。

二、教学内容

第一章绪论

（一）教学目的要求

介绍数据结构的一些基本概念，算法的时间复杂度和空间复杂度的分析方法，抽象数据类型的定义和使用以及算法的描述方法。掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。

（二）教学内容

主要内容：数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。抽象数据类型。算法时间复杂度和空间复杂度的分析。

教学重点：有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。

教学难点：算法时间复杂度和空间复杂度的分析。

第一节

一、非数值计算

二、数据结构课程内容的历史演变

三、数据结构研究范围

第二节

一、数据

二、数据结构

三、数据类型

四、抽象数据类型

五、多型数据类型

第三节

一、固有数据类型

抽象数据类型的表示与实现

基本概念和术语什么是数据结构

二、数据抽象

三、抽象数据类型的描述语言

第四节

一、算法

二、算法设计的要求

三、算法效率的度量

四、算法的存储空间需求

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

第二章线性表

（一）教学目的与要求

介绍线性表的基本概念和类型定义，对顺序表和单链表的常用操作方法及其程序实现，循环链表和双向链表的定义和它的插入、删除等操作方法。掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。

（二）教学内容

主要内容：线性表的基本概念和类型定义，线性表的顺序存储结构，线性表的链接存储结构：（1）单链表的查找、插入和删除；（2）循环链表；（3）双向链表。

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

教学难点：用所学的基本知识设计有效算法解决与线性表相关的应用问题。链表要分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针以及循环链表、双向链表的特点等。

第一节

一、线性表的定义

二、线性表的基本操作

第二节

一、顺序表

二、顺序表上基本运算的实现

三、顺序表应用举例

第三节

一、线性链表

二、循环链表

三、双向链表

四、静态链表

第四节

一、一元多项式的数学表示

二、一元多项式的计算机表示

三、抽象数据类型：一元多项式的定义

四、抽象数据类型：一元多项式的存储结构

五、抽象数据类型：一元多项式的基本操作算法实现

（三）教学方法与形式

一元多项式的表示及相加线性表的链式存储表示和实现线性表的顺序存储表示和实现

线性表的类型定义算法和算法分析课堂讲授、多媒体课件。

（四）教学时数

8学时。

第三章栈和队列

（一）教学目的与要求

介绍栈和队列的定义，顺序和链接存储的栈和队列的各种运算的方法及其程序实现。掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现。

（二）教学内容

主要内容：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法，栈的应用举例，队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

教学重点：栈和队列在两种存储结构上实现的基本运算。教学难点：递归的实现、循环队列中对边界条件的处理。

第一节

一、抽象数据类型栈的定义

二、栈的表示和实现

第二节

一、数制转换

二、括号匹配的检验

三、表达式求值

第三节

一、函数调用与栈

二、递归调用栈的变化

第四节

一、抽象数据类型队列的定义

二、链队列--队列的链式表示和实现

三、循环队列--队列的顺序表示和实现

第五节

一、优先级队列的概念

二、优先级队列的存储表示和实现

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

第四章串

（一）教学目的与要求

介绍串的基本概念和操作，串的存储结构以及基本操作的算法实现。掌握串的基本概念和操作，掌握串的存储结构以及基本操作的算法实现。

（二）教学内容

主要内容：串的类型定义，串的表示和实现，正文模式匹配，正文编辑——串操作应用举例串的类型定义。

教学重点：串类型定义中各基本操作的定义以及串的实现方法。教学难点：利用串的基本操作来实现串的其它操作。

优先级队列队列栈与递归的实现栈的应用举例

栈

第一节

一、串的定义

二、串的基本操作

第二节

一、定长顺序存储表示

二、堆分配存储表示

三、串的块链存储表示

四、字符串操作的实现

第三节

二、模式匹配的一种改进算法

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

4学时。

串的类型定义

串的表示和实现

字符串的模式匹配

一、求子串位置的定位函数Index（S，T，pos）

第五章数组和广义表

（一）教学目的

介绍数组的基本概念和基本操作的算法实现；稀疏矩阵的定义和各种存储结构，稀疏矩阵的转置和相加的方法并了解其算法；广义表的定义、存储结构和求广义表的长度及深度的算法，建立广义表和输出广义表的方法并了解其算法。掌握数组的基本概念和基本操作的算法实现；掌握稀疏矩阵的定义和各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法；掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握建立广义表和输出广义表的方法并了解其算法。

（二）教学内容

主要内容：稀疏矩阵的定义、存储和运算，广义表的定义、存储和运算串的类型定义。教学重点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。教学难点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。

第一节第二节

一、数组的存储方式

二、数组元素存储位置的计算

三、基本操作的实现

第三节

一、特殊矩阵

二、稀疏矩阵

第四节

一、广义表的基本概念

二、广义表的三个重要结论

第五节

一、头尾链表存储表示

二、扩展线性链表存储表示

第六节

广义表的递归算法广义表的存储表示广义表的定义矩阵的压缩存储数组类型数组的顺序表示和实现

一、求广义表的深度

二、复制广义表

三、建立广义表的存储结构

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

6学时。

第六章树和二叉树

（一）教学目的与要求

介绍树的定义、性质、存储结构及遍历算法，握二叉树的各种遍历方法及其实现，二叉树的其他操作方法及实现，树、森林和二叉树的转换方法，哈夫曼树的定义和构造哈夫曼树的方法，哈夫曼树编码的方法。掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，掌握树、森林和二叉树的转换方法，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解哈夫曼树编码的方法。

（二）教学内容

主要内容：树的定义、性质和表示方法，二叉树的定义、性质和存储结构，二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法，哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法。

教学重点：二叉树和树的遍历及其应用。

教学难点：实现二叉树和树的各种操作的递归算法。

第一节

一、树的定义

二、森林的定义

三、树的抽象数据类型定义

第二节

一、二叉树的定义

二、二叉树的性质

三、二叉树的存储结构

第三节

一、遍历二叉树

二、线索二叉树

第四节

一、树的存储结构

二、森林与二叉树的转换

三、树和森林的遍历

第五节

一、最优二叉树（赫夫曼树）

二、赫夫曼编码

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

10学时。

最优树和赫夫曼编码

树和森林

遍历二叉树和线索二叉树

二叉树

树的定义和基本术语

第七章图

（一）教学目的与要求

介绍图的定义和术语；图的存储结构及深度和广度优先搜索方法及其实现；图的生成树的概念，求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；拓扑排序的方法并了解其实现算法；计算关键路径的方法及其实现算法。掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法；了解计算关键路径的方法并了解其实现算法。

（二）教学内容

主要内容：图的定义和术语，图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，拓扑排序。

教学重点：图在邻接矩阵与邻接表上实现的遍历算法(DFS和BFS)。教学难点：基于遍历算法的应用。

第一节

一、图的定义

二、无向图

三、有向图

四、连通图

五、生成树

第二节

一、数组表示法

二、邻接表

三、十字链表

四、邻接多重表

第三节

一、深度优先搜索

二、广度优先搜索

三、连通分量

第四节

一、Kruskal算法

二、Prim算法

第五节

一、拓扑排序

二、关键路径

第六节

一、从某个源点到其余各项点的最短路径

二、每一对顶点之间的最短路径

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

12学时。

最短路径有向无环图及其应用

最小生成树图的遍历图的存储表示图的定义和术语

第八章查找表

（一）教学目的与要求

介绍顺序表查找和有序表查找的方法及实现；二叉排序树和平衡二叉树的定义、对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；B树的定义，查找、插入和删除元素的方法。熟练掌握顺序表查找和有序表查找的方法及实现；掌握二叉排序树和平衡二叉树的定义、熟练掌握对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。掌握哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；了解B树的定义，查找、插入和删除元素的方法。

（二）教学内容

主要内容：顺序查找和二分查找，索引查找和分块查找，散列查找，动态查找树表。教学重点：顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。

教学难点：二叉排序树的删除算法。

第一节

一、顺序表的查找

二、有序表的查找

三、静态树表的查找

四、索引顺序表的查找

第二节

一、二叉排序树

二、平衡二叉树

三、动态的m路搜索树

四、B树和B+树基本概念

第三节

一、什么是哈希表

二、哈希函数的构造方法

三、处理冲突的方法

四、哈希表的查找及其分析

（三）教学方法与形式

课堂讲授、多媒体课件。

（四）教学时数

10学时。

第九章内部排序

（一）教学目的与要求

介绍插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，快速排序、堆排序、二路归并排序的方法及其实现，各种排序方法的稳定性、时间复杂度和空间复杂度。掌握插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，熟练掌握快速排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。

（二）教学内容

主要内容：排序的概念，直接插入排序，冒泡排序和快排序，直接选择排序和堆排序，归并排序。

哈希表动态查找表静态查找表教学重点：插入排序(直接插入、折半插入)、交换排序（冒泡、快速排序）、选择排序（直接选择、堆）、2 -路归并排序。

教学难点：快速排序partition算法的应用和堆的调整。

第一节

一、稳定的排序方法

二、内部/外部排序

三、内部排序种类

四、排序中的基本操作

五、排序数据的存储方式

第二节

一、直接插入排序