《数据结构与算法》教学大纲(本科)

 院(系)：计算机与信息

          教 研 室：软件

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

          课程代号：

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

上 海 第 二 工 业 大 学

计算机科学与技术专业

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

一、课程的性质和任务

性质：本课程是计算机科学与技术专业的一门主要专业技术基础课程。

任务：学会分析研究计算机的数据对象的特性，以便选择适当的数据结构和存贮结构以及相应的算法，并初步掌握算法的时间分析及空间分析的方法。

二、课程的基本要求（通过本课程学习应使学生了解、理解、掌握、熟练掌握的知识和技能）

熟练掌握几种典型的数据结构：（表、树、图），熟炼掌握各类数据结构的基本操作及其应用。在此基础上，着重理解查找和内部排序。初步掌握算法的时间分析及空间分析的方法。进一步提高程序设计和实现能力。

三、课程内容（含实验内容和各章的教学要求、重点、难点和教学建议）

1.绪论

了解数据结构的发展及所处的地位，并掌握数据结构的基本概念和术语、算法的描述及算法分析的方法。

2.线性表

熟练掌握线性数据结构的基本操作所对应的算法并能灵活使用线性表这类基本数据结构。

线性表及其基本操作。线性表的顺序存贮结构

顺序存贮结构、类型描述、插入、删除、查找操作的实现算法描述。

线性表的链式存贮结构

顺序存贮的优缺点，线性链表、循环链表、双向链表、静态链表及其基本操作的算法。

重点：单链表

实验：单链表的建立、插入及删除等基本操作的算法

3.堆栈和队列

掌握栈和队列的基本概念及其应用。注意这类数据结构与线性表的异同点。

栈：定义及其在两种存贮结构下的进栈出栈算法

栈的应用：进制转换、表达式的求值

队列：定义及进队出队算法，链队列、循环队列

重点：栈及其操作

4.串

了解串的概念、定义及存贮结构

5.数组和广义表

掌握数组的定义及地址公式，掌握特殊矩阵的存贮方式，了解广义表的概念

数组的定义及运算

存贮结构：地址计算公式矩阵的压缩存贮：

特殊矩阵：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵、三元组表、十字链表广义表的基本概念

重点：特殊矩阵的存贮方式

难点：矩阵转置

6.树和二叉树

掌握树及二叉树的基本概念，掌握二叉树的遍历、线索化及其应用

树的定义

二叉树：定义、性质、存贮结构

遍历二叉树及线索二叉树：先序、中序、后序遍历，线索二叉树    

树和森林：存贮结构、森林与二叉树的转换、树的遍历、哈夫曼树、哈夫曼编码

重点：二叉树的遍历及其应用

难点：线索二叉树、哈夫曼树的算法

7.图

掌握图的有关术语、存贮结构、及图的各类应用

图的定义及术语

存贮结构：数组表示法、邻接表

图的遍历：深度优先搜索、广度优先搜索

最小生成树：掌握普里姆算法

有向无环图及其应用：拓扑排序、关键路径、最短路径（Dijkstra, Floyd算法）

重点：存贮结构

难点：无向图的遍历、最短路径、拓扑排序算法

8.查找

掌握各类查找方法，掌握一般查找方法及树表查找的概念及算法，了解哈希表的特点

顺序表的查找：顺序、折半及分块查找

树表查找：二叉排序树

哈希表：定义、函数构造、冲突处理方法

重点：一般查找方法及树表查找的概念及算法

难点：二叉排序树算法

9.排序

掌握内排序的概念，掌握内部排序各种方法的算法思想，了解各种不同排序方法的适用场合。

概述

内部排序：掌握插入排序、快速排序、选择排序、归并排序、基数排序的算法。

重点：插入排序、快速排序、选择排序及基数排序的算法。

难点：快速排序、堆排序、归并排序算法

四、本课程与其它课程关系（写明先修后续的课程与本课程的关系）：

本课程是一门综合的专业基础课。它的研究不仅涉及到计算机硬件的研究范围，而且与计算机软件的研究有密切的关系。

本课程中的“线性链表”等内容与“C语言”课程中的有关内容有联系，而无论是“编译原理”还是“操作系统”都涉及到数据元素在存贮器中的分配问题。在研究信息检索时也必须考虑如何组织数据以便查找和存取更为方便。它是介于数学、计算机硬件、软件三者之间的一门核心课程。

先修课程：C语言程序设计、离散数学

后续课程：编译原理、操作系统、软件工程、数据库原理等课程

五、学时分配

《数据结构》（C语言版）    严蔚敏、吴伟民  编著  

 清华大学出版社　1997年4月第1版