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

（2013版）

 

 

 

 

 

课程编码：0611100504

课程名称：算法与数据结构

学时/学分：64/4

先修课程：《计算机导论》、《程序设计基础》

适用专业：计算机科学与技术

开课教研室：软件工程教研室

 

 

 

 

 

 

 

 

 

 

 

 

执笔：

审定：

 

一、课程性质与任务

1．课程性质：算法与数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，算法与数据结构不仅是一般程序设计（特别是非数值计算程序设计）的基础，而且是设计和实现编译程序、操作系统、以及其它系统程序和大型应用程序的重要基础。因此算法与数据结构课程是计算机科学与技术专业的专业基础课。

2．课程任务

通过本课程的学习，应使学生掌握线性表、栈、队列、串、数组、二叉树、图等典型数据结构的设计方法；了解各种抽象数据类型的性质；掌握处理各种抽象数据类型的基本算法；重点掌握各种典型数据结构的应用；了解各种典型排序和查找算法的性能和设计方法；重点掌握程序设计的基本原理和方法；初步掌握算法的时间分析和空间分析的技术。

二、课程教学基本要求

学生通过学习该课程后能够针对不同数据对象的特性，选择适当的数据结构和存储结构以及相应的算法，去解决实际应用问题。学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护，为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。

本课程共计学时：64，理论学时48，实践学时16。

成绩考核形式：末考成绩（闭卷考试）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30%)。成绩评定采用百分制，60分为及格。

三、课程教学内容

第一章    绪  论

1.教学基本要求

了解数据的逻辑结构和物理结构；了解算法对于程序设计的重要性；掌握算法时间复杂度的分析方法 。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生了解数据结构的基本概念，主要包括数据、数据元素、数据项、数据结构、四种逻辑结构、四种存储结构、时间复杂度等基本概念；掌握时间复杂度和空间复杂度来评价算法效率的基本分析方法。

3.教学重点和难点

教学重点是数据结构的基本概念。教学难点是抽象数据类型和算法分析技术。

4.教学内容

（1）什么是数据结构

主要知识点：从数据结构实验演示认识数据结构；数据结构研究的内容。

（2）数据的逻辑结构

主要知识点：基本概念：数据、数据元素、数据项、数据对象、数据的逻辑结构。

（3）数据的存储结构

主要知识点：顺序存储；链式存储；索引存储；散列存储。

（4）算法和算法分析

主要知识点：算法特性；算法的效率；算法效率的评价。

第二章    线性表

1.教学基本要求

掌握线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握线性表的逻辑结构特征，线性表上定义的基本运算，掌握顺序表的定义及特点，顺序表上的插入删除操作及其平均时间性能；掌握单链表、双链表、循环链表链式存储方式上的区别、基本运算算法和平均时间性能分析。通过本章学习，使学生能够针对具体应用问题的要求和性质，选择合适的存诸结构设计出相应的有效算法，解决与线性表相关的实际问题。

3.教学重点和难点

教学重点是顺序表的插入运算、删除运算，链表的创建、插入、删除运算。教学难点是双链表插入、删除运算的算法；利用链表结构的特点设计算法。

4.教学内容

（1）线性表的定义与运算

主要知识点：线性表的定义；线性表的基本操作。

（2）线性表的顺序存储

主要知识点：线性表的顺序存储特点；顺序表结构体类型的定义；顺序表上基本运算的实现：顺序表的空间分配及初始化、插入、删除等基本运算及其平均时间性能分析。

（3）线性表的链式存储结构

主要知识点：线性表的链式存储的特点；线性表的链式存储的基本运算：头部尾部建立线性链表、带头指针和不带头指针求表长、插入、删除等基本运算；循环链表特点及基本运算、尾指针取代头指针；存储密度；双链表的特点及基本运算。

第三章    栈

1.教学基本要求

掌握栈的逻辑结构以及在两种存储结构上如何实现栈的基本运算。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握栈的逻辑结构特点，栈与线性表的异同。顺序栈和链栈上实现的入栈、出栈等基本算法。栈的"上溢"和"下溢"的概念及其判别条件，利用栈设计算法解决简单的应用问题。

3.教学重点和难点

教学重点是栈的定义和特点、栈的基本运算和算法以及栈的典型应用。教学难点是后缀表达式的算法、数制的换算、利用本章的基本知识设计相关的应用问题

4.教学内容

（1）栈的定义与运算

主要知识点：栈的定义；栈的特性；栈的应用实例。

（2）栈的存储和实现

主要知识点：顺序栈的特点、顺序栈结构体类型的定义、顺序栈的基本运算；链栈的特点、链栈结构体类型的定义、链栈的基本运算。

（3）栈的应用举例

主要知识点：数制转换；括号匹配；表达式求值；子程序调用；递归调用。

第四章    队列

1.教学基本要求

掌握队列的逻辑结构以及在两种存储结构上如何实现队列的基本运算。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握队列的逻辑结构特点，队列与线性表的异同，队列的"上溢"和"下溢"的概念及其判别条件，使用数组实现的循环队列取代普通的顺序队列的原因，循环队列中对边界条件的处理方法，利用队列设计算法解决简单的应用问题。

3.教学重点和难点

教学重点是队列的定义和特点、队列的基本运算和算法以及队列的典型应用。教学难点是循环队列的特点及判断溢出的条件；利用队列的特点设计相关的应用问题。

4.教学内容

（1）队列的定义与运算

主要知识点：队列的定义；队列的特性；队列的应用实例。

（2）队列的存储实现及运算的实现

主要知识点：顺序队列的特点、顺序队列结构体类型的定义、顺序队列的基本运算；循环队列的特点、循环队列结构体类型的定义、循环队列的基本运算；链队列的特点、链队列结构体类型的定义、链队列的基本运算。

（3）队列的应用举例

主要知识点：队列在输入、输出管理中的应用；对CPU的分配管理；优先队列。

第五章    串

1.教学基本要求

掌握串的逻辑结构、存储结构及其串上的基本运算，C语言及其它高级语言均已具备了较强的串处理功能，掌握串上实现的模式匹配算法。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握串的有关概念及基本运算。串与线性表的关系，掌握串的两种存储表示。串上实现的模式匹配算法及其时间性能分析，使用高级程序设计语言提供的串操作函数构造与串相关的算法解决简单的应用问题。

3.教学重点和难点

教学重点是串的有关概念和术语、串的基本运算、串的存储方法和串的模式匹配运算算法。教学难点是串的模式匹配运算算法。

4.教学内容

（1）串的定义

主要知识点：串的定义；串的相关术语：长度、空串、空格串、串相等、子串、主串、模式匹配；串的应用；串的输入输出；串的基本运算。

（2）串的表示和实现

主要知识点：定长顺序存储描述、存储方式；链接存储的描述；串的存储密度；大结点结构；串的堆分配存储结构；堆分配存储的方法；带长度索引表的描述。

（3）串的基本运算

主要知识点：串长度、求子串、串连接、串比较、插入子串、删除子串、模式匹配基本算法。

第六章    多维数组和广义表

1.教学基本要求

掌握多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握多维数组的顺序存储结构及地址计算方式，多维数组的存储方式、特殊矩阵的压缩存储方式，稀疏矩阵的三元组表表示方法及有关算法，广义表的定义及其求表头和表尾的运算。

3.教学重点和难点

教学重点是多维数组的逻辑结构和存储结构，特殊矩阵的压缩存储，稀疏矩阵的三元组存储，广义表的逻辑结构、存储结构。教学难点是十字链表存储。

4.教学内容

（1）多维数组

主要知识点：多维数组的逻辑结构；多维数组的存储结构。

（2）特殊矩阵的压缩存储

主要知识点：对称矩阵的特点及压缩存储方式；三角矩阵的特点及压缩存储方式。

（3）稀疏矩阵

主要知识点：稀疏矩阵的三元组存储；稀疏矩阵的带行指针的链表存储；稀疏矩阵的十字链表存储。

（4）广义表

主要知识点：广义表的定义、性质；广义表的首尾存储法。

第七章    树和二叉树

1.教学基本要求

掌握二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历、树、森林与二叉树的转换；哈夫曼树及哈夫曼编码等内容，使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。  

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握树的逻辑结构特征，二叉树的递归定义及树与二叉树的差别，二叉树的性质，二叉树的两种存储方法、特点及适用范围；二叉树的三种遍历算法，理解其执行过程，以遍历算法为基础，设计有关算法解决简单的应用问题；二叉树线索化的目的及实质，中序线索树中查找给定结点的中序前趋和中序后继的方法；树和森林与二叉树之间的转换方法，树的各种存储结构及其特点。最优二叉树和最优前缀码的概念及特点，哈夫曼算法的思想。

3.教学重点和难点

教学重点是树的基本概念与术语、二叉树及二叉树的存储结构、二叉树的遍历及线索二叉树、哈夫曼树及哈夫曼编码。教学难点是二叉树遍历算法的设计，利用二叉树遍历算法，解决简单应用问题，哈夫曼树的算法。

4.教学内容

（1）树的定义和术语

主要知识点：树的定义；树的表示法；树的相关术语。

（2）二叉树

主要知识点：叉树的定义；二叉树的性质；二叉树的存储。

（3）遍历二叉树和线索二叉树

主要知识点：二叉树的遍历；二叉树的恢复；线索二叉树方法及优点。

（4）二叉树的转换

主要知识点：一般树转换为二叉树；森林转换为二叉树；二叉树转换为树和森林。

（5）二叉树的应用

主要知识点：二叉树的基本应用；标识符树与表达式。

（6）哈夫曼树及其应用

主要知识点：哈夫曼树相关术语的定义及创建；哈夫曼编码；算法的实现。

第八章    图

1.教学基本要求

掌握图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，要求学生在熟悉这些内容的基础上，掌握在图的两种存储结构上实现的遍历算法，求最小生成树，求最短路径以及拓扑排序，同时要求学生掌握这些算法的基本思想及时间性能。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握图的逻辑结构特征，邻接矩阵和邻接表这两种存储结构的特点及适用范围，根据应用问题的特点和要求选择合适的存储结构；连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法，其执行过程以及时间分析；Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点；单源最短路径的Dijkstra算法的基本思想和时间性能；拓扑排序的基本思想和步骤。

3.教学重点和难点

教学重点是图的逻辑结构及基本术语、邻接矩阵和邻接表的存储结构和特点，深度优先搜索和广度优先搜索两种遍历算法、图的连通性、最小生成树、最短路径的算法。教学难点是图的遍历、最小生成树、最短路径。

4.教学内容

（1）图的定义和术语

主要知识点：图的定义；图的相关术语；图的基本操作。

（2）图的存储表示

主要知识点：邻接矩阵；邻接表。

（3）图的遍历

主要知识点：深度优先搜索；广度优先搜索；有向图的十字链表存储结构。

（4）图的连通性

主要知识点：无向图的连通分量和生成树；普里姆算法求最小生成树；克鲁斯卡尔算法求最小生成树。

（5）最短路径

主要知识点：迪杰斯特拉算法

第九章    查找

1.教学基本要求

掌握顺序查找、二分查找，二叉查找树上查找、二叉平衡树以及散列表上查找的基本思想和算法实现。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握查找在数据处理中的重要性；查找算法效率的评判标准，顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析，顺序查找中哨兵的作用；二分查找对存储结构及关键字的要求，通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法；二叉查找树的特点、用途，二叉查找树的插入、删除、建树和查找算法及时间性能以及二叉平衡树的调整方法，散列函数的选取原则及产生冲突的原因，几种常用的散列函数构造方法，两类解决冲突的方法及其优缺点。

3.教学重点和难点

教学重点是查找的基本概念、二分查找、分块查找、二叉排序树查找、哈希函数和解决冲突的方法。教学难点是二叉排序树查找、平衡二叉树。

4.教学内容

（1）查找的基本概念

主要知识点：查找、静态查找、动态查找、关键字、主关键字、内查找和外查找、平均查找长度ASL等概念。

（2）静态查找表

主要知识点：顺序查找：基本思路、算法、性能分析；二分查找的基本思路、算法、性能分析；分块查找的基本思路、算法、性能分析。

（3）动态查找表

主要知识点：二叉排序树的定义、插入、删除、查找、查找分析；平衡二叉排序树的定义和调整。

（4）哈希表

主要知识点：哈希表与哈希方法；哈希函数的构造方法：直接定址法、除留余数法、平方取中法；处理冲突的方法：开放定址法、拉链法。

第十章    排序

1.教学基本要求

掌握插入排序、快速排序、堆排序、归并排序这四类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。

2.要求学生掌握的基本概念、理论、技能

通过本章的学习，掌握排序方法的"稳定"性含义，排序方法的分类及算法好坏的评判标准；　　掌握直接插入排序、冒泡排序中的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析；直接插入排序中哨兵的作用，能够针对给定的输入实例，要能写出它们的排序过程；掌握直接选择排序、堆排序、归并排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，写出该排序的排序过程。

3.教学重点和难点

教学重点是排序的基本概念、二分插入排序、快速排序、堆排序。教学难点是堆排序、快速排序。

4.教学内容

（1）概述

主要知识点：排序、内排序、外排序等相关概念。

（2）插入排序

主要知识点：直接插入排序的基本思想、算法、效率分析；二分插入排序的基本思想、算法、效率分析；希尔排序的基本思想、算法、效率分析。

（3）快速排序

主要知识点：冒泡排序的基本思想、算法、效率分析；快速排序的基本思想、算法、效率分析。

（4）选择排序

主要知识点：简单选择排序的基本思想、算法、效率分析；树形选择排序的基本思想、效率分析；堆排序的基本思想、算法、效率分析。

（5）归并排序

主要知识点：归并排序的基本思想、算法、效率分析。

第六节   各种排序方法的比较

主要知识点：各种排序方法时间、空间、稳定度、最坏状况、程序的编写难易程度等比较。

四、学时分配表

1.讲授内容及学时分配

章序

内容

课时

备注

一

绪论

3

 

二

线性表

6

 

三

栈

6

 

四

队列

3

 

五

串

2

 

六

多维数组和广义表

4

 

七

树

7

 

八

图

7

 

九

查找

5

 

十

排序

5

 

合计

48

 

2.实践内容及学时分配

序号

项目名称

内容提要

学时

必/选开

1

学生成绩分析程序

设一个班有10个学生，每个学生有学号，以及数学、物理、英语、语文、体育5门课的成绩信息。

1．求数学的平均成绩。

2．对于有两门以上课程不及格的学生，输出他们的学号、各门课成绩及平均成绩。

3．输出成绩优良的学生

2

必开

2

多项式求和

分别使用线性表的顺序存储结构或链式存储结构实现

2

必开

3

后缀表达式求值

1．从键盘终端输入一个整数表达式的后缀表达式（操作数的范围是0～9，运算符只含+、-、*、/，而且中间不可以有空格），

2．利用栈将该后缀表达式求值。

2

必开

4

字符串分割处理

1．从键盘终端输入一行英文句子，并将该句存入数组，

2．以一行一个单词的方式进行显示。

2

必开

5

二叉树子系统

1．用前序方法建立一棵二叉树

2．编写前序遍历、中序遍历、后序遍历、层次遍历程序。

3．编写求二叉树的叶结点数、总结点数和深度的程序。

2

必开

6

最小生成树

1．输入无向网的邻接矩阵，

2．用Prim算法或Kruskal算法求最小生成树。

4

必开

7

双向冒泡排序

1．设计双向冒泡排序算法（每一趟排序通过相邻的关键字的比较，产生最小和最大的两个元素）。

2．待排序数据可以人机交互输入或用随机函数rand()产生。

3．输出每一趟排序结果。

2

必开

合计

16

 

五、主用教材及参考书

（一）主用教材：

《实用数据结构基础》 主编：陈元春、王中华、张亮、王勇  出版社：中国铁道出版社 出版时间：2011年。

（二）参考书：

1.《数据结构》(C语言版)主编：严蔚敏、吴伟民  出版社：清华大学出版社  出版时间：2011年。

2.《数据结构》(C语言版)主编：崔进平、郭小春、王霞  出版社：清华大学出版社 出版时间：2011年。

3.《数据结构与算法》（C语言版）主编：陈明、王红梅  出版社：中国铁道出版社 出版时间：2011年。