课程编号:131516

课程名称:数据结构

学时/学分:96/5

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

适用专业:网络工程

开课系或教研室:计算机与信息工程系

一、课程性质与任务

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

2课程任务:本课程主要介绍在解决非数值计算的问题中如何合理地组织和表示数据、有效地存储和处理数据、正确地设计算法以及对算法进行分析和评价。通过本课程的学习，使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法。掌握各种数据结构的基本操作在不同存储方式下的算法实现，以及算法分析，进而培养基本的、良好的程序设计技能，编制正确高效可靠和易读易懂的程序。并为学习操作系统、编译原理、数据库和人工智能等后续课程奠定良好的基础。

二、课程教学基本要求

本门课以课堂讲授为主。理论课时64学时，试验课时32学时。

考核形式:本课程为考试课。期末笔试占总成绩的80％，平时作业、试验共占总成绩的20％。

三、课程教学内容

（一）算法与数据结构绪论

1．教学要求

（1）熟悉各名词、术语的含义

（2）掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系；

（3）掌握算法描述与算法分析，包括算法的时间复杂度和空间复杂度，最坏和平均的时间复杂度。

2．教学内容

（1）数据结构主要研究内容

（2）基本概念和术语

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

（4）算法与算法分析

3．重点与难点

（1）理解算法五个要素的确切含义

（2）抽象数据类型的定义、表示和实现方法

（3）计算语句频度和估算算法时间复杂度的方法

（二）线性表

1. 教学要求

（1）理解线性表的定义及其运算

（2）理解顺序表和链表的定义、组织形式、结构特性和类型说明

（3）掌握在顺序表和链表上实现的插入、删除和按值查找等算法

（4）了解循环链表、双链表的结构特点和在其上施加的插入、删除等操作。

2．教学内容

（1）线性表的类型定义

（2）线性表的顺序表示和实现

（3）线性表的链式表示和实现

（4）一元多项式的表示及相加

3．重点与难点

（1）顺序表的表示及基本操作的实现

（2）单链表的表示及基本操作的实现

（3）线性表基本操作在两种存储方式下不同实现算法的时间复杂度的分析

（三）栈和队列

1．教学要求

（1）理解栈和队列的逻辑结构特性、基本操作

（2）掌握栈和队列在两种存储结构上基本操作的实现

（3）理解栈和队列的应用

（4）掌握递归算法的设计方法，理解栈与递归之间的关系

2．教学内容

（1）栈的定义和实现

（2）栈的应用若干实例

（3）栈与递归的实现

（4）队列的表示和实现

3．重点与难点

（1）栈的表示方法和基本操作的实现

（2）循环队列及基本操作的实现

（3）栈与递归之间的关系

（四）字符串

1．教学要求

（1）了解串的逻辑结构定义，理解串的各种存储方式

（2）掌握在串的定长顺序存储结构上实现串的各种操作的方法。

（3）掌握串的堆存储结构以及在其上实现串操作的基本方法。

（4）理解串匹配的KMP算法，熟悉NEXT函数的定义；

2．教学内容

（1）串的类型定义

（2）串的表示和实现

（3）串的模式匹配算法

3．重点与难点

（1）串的三种不同的存储方式

（2）串匹配的KMP算法

（五）数组和广义表

1．教学要求

（1）理解多维数组的结构特点和在内存中的两种存储方式

（2）理解并掌握矩阵和特殊矩阵元素在存储区中的地址计算，领会稀疏矩阵的压缩方式和简单运算

（3）了解广义表的定义和存储结构，掌握广义表的基本运算

2．教学内容

（1）数组的定义及顺序表示和实现

（2）矩阵的压缩存储

（3）广义表的定义及存储结构

（4）广义表的各种递归算法

3．重点与难点

（1）数组的顺序表示存储结构中地址的计算方法

（2）稀疏矩阵的两种压缩存储的方法

（六）树和二叉树

1．教学要求

（1）理解树的定义、基本概念，二叉树的定义

（2）掌握二叉树的性质和存储表示

（3）熟练掌握二叉树的遍历算法，并会利用二叉树的遍历算法解决相关的应用问题

（4）掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法

（5）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法

（6）熟练掌握哈夫曼树及哈夫曼编码方法

2．教学内容

（1）树的定义和基本术语

（2）二叉树

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

（4）树和森林

（5）哈夫曼树及其应用

（6）回溯法与树的遍历

3．重点与难点

（1）二叉树性质

（2）二叉树的遍历操作及其递归算法

（3）哈夫曼树及哈夫曼编码

（七）图

1．教学要求

（1）理解图的基本概念、掌握图的两种存储结构（邻接矩阵、邻接表）

（2）熟练掌握图的两种遍历的算法思想、步骤

（3）理解最小生成树的概念，能按普利姆算法和克鲁斯卡尔算法构造最小生成树

（4）领会并掌握拓扑排序、关键路径、最短路径的算法思想

（5）一般了解有向图的强连通分量问题，了解关节点和重连通分量的概念

2．教学内容

（1）图的定义和术语

（2）图的存储结构

（3）图的遍历

（4）图的连通性问题

（5）有向无环图及其应用

（6）最短路径

3．重点与难点

（1）图的两种遍历算法

（2）最小生成树的两种构造方法

（3）拓扑排序和最短路径

（八）查找

1．教学要求

（1）了解查找的基本思想及查找成功和不成功的概念

（2）熟练掌握在顺序表、有序表、散列表上的查找方法和算法，并能求出相应的平均查找长度

（3）掌握在二叉排序树上的查找、插入和删除算法

（4）了解平衡二叉树、B-树和B⁺树定义及查找方法。

2．教学内容

（1）静态查找表

（2）动态查找表

（3）哈希表

3．重点与难点

（1）折半查找树的构造及查找分析

（2）二叉排序树的插入删除算法及查找分析

（3）如何按照开放定址法和链地址法处理冲突构造散列表及查找分析

（九）排序

1．教学要求

（1）领会排序的基本思想和基本概念

（2）理解并掌握插入排序、冒泡排序、快速排序、直接选择选择排序、堆排序、归并排序和基数排序的基本思想、步骤及算法

（3）掌握各种排序方法的时间复杂度的分析方法

（4）理解排序方法“稳定”或“不稳定”的含义

2．教学内容

（1）排序概述

（2）插入排序

（3）交换排序

（4）选择排序

（5）归并排序

（6）基数排序

3．重点与难点

（1）理解各种内部排序方法的特点

（2）shell排序、快速排序、堆排序和基数排序等的算法及时空复杂度的分析。

四、学时分配表

五、教材及参考书

教材:《数据结构 （C语言版）》 严蔚敏等编著 清华大学出版社

参考书:

1 A.V.Aho,J.E.Hopcroft and J.D.Ullman,Data Structures and Algorithms,by Addison——Wesley Publishing Company,Inc.,1983

2 《数据结构（用面向对象方法与C++描述）》 殷人昆 陶永雷 谢若阳 盛绚华 编著 清华大学出版社

3 《算法与数据结构》 傅清祥 王晓东 编著 电子工业出版社

执笔:李艳平

审定:张秀爱 日期: