“数据结构”课程大纲
一、 课程简介
课程名称：《数据结构》
学时：72/36 学分：4 开课学期：3
开课对象：计算机科学与技术、信息管理与信息系统、信息与计算科学等本科专业。
先修课程：计算科学导论、高级语言程序设计。
教学目的与要求：
《数据结构》是计算机科学技术专业本科教育的重要专业基础课。本课程的主要目的是：一方面训练学生理解掌握各种基本数据结构的要领，以便能够编写出各种典型算法，另一方面，培养学生应用各种典型算法解决具体应用问题的能力。本课程在讲述过程中将适当掌握面向对象的思想和技术，以解决C语言本身在描述和解决客观世界能力方面的不足。
同时为学生进一步学习OO方面打下一定的基础。本课程将始终坚持理论和实际相结合的原则，布置足够多的习题和较大型的上机实践题，以提高学生的动手能力。实践环节采用两种形式，一是集中形式中的上机训练（每周两机时），主要目的是为是巩固基本算法；二是课后以小组为单位的大型课程设计，通过同学之间的相互协作，共同完成较大的课程设计，以达到工程训练的目的。
二、教学大纲
第1章 概论
数据结构讨论的是数据的逻辑结构、存储方式以及相关操作的实现等问题，为学习后续专业课程打下基础。本章讲述数据结构的基本概念及相关术语，介绍数据结构、数据类型和抽象数据类型之间的联系，介绍了算法的特点及算法的时间与空间复杂性。
本章的主要内容包括：
1.1数据结构
1.1.1数据结构
1.1.2数据的逻辑结构
1.1.3数据的存储结构
1.1. 4数据的运算集合
1.2数据类型和抽象数据类型
1.2. 1数据类型
1.2.2数据结构
1.2.3抽象数据类型
1.2.4抽象数据类型的描述和实现
1.3算法和算法分析
1.3.1算法
1.3.2算法的时间和空间复杂性
习题1
第2章 线性表及其顺序存储
线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。
本章的主要内容包括：
2.1线性表
2.2顺序表
2.2.1顺序表
2.2.2顺序表的实现
2.3栈
2.3.1顺序栈
2.3.2顺序栈及其实现
2.3.3栈的应用之一------括号匹配
2.3.4栈的应用之二------算术表达式求值
2.4队列
2.4.1队列
2.4.2顺序队列及其实现
2.4.3顺序循环队列及其实现
习题2
第3章 线性表的链式存储
线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表------栈和队列的链式存储实现。
本章的主要内容包括：
3.1链式存储
3.2单链表
3.2.1单链表
3.2.2单链表的实现
3.3带头结点单链表
3.3.1带头结点单链表
3.3.2带头结点单链表的实现
3.4循环单链表
3.4.1循环单链表
3.4.2循环单链表的实现
3.5双链表
3.5.1双链表
3.5.2双链表的实现
3.6链式栈
3.6.1链式栈
3.6.2链式栈的实现
3.7链式队列
3.7.1链式队列
3.7.2链式队列的实现
习题3
第4章 字符串、数组和特殊矩阵
字符串是一种特殊的线性表，它是许多非数值计算问题的一种重要处理对象；而数组可以看作是线性表的推广。本章主要介绍字符串和数组的基本概念和存储结构、字符串的模式匹配算法、特殊矩阵和稀疏矩阵的压缩存储方式及其实现。
本章的主要内容包括：
4.1字符串
4.1.1 字符串的基本概念
4.1.2 字符串类的定义
4.1.3 字符串的存储及其实现
4.2 字符串的模式匹配
4.2.1 朴素的模式匹配算法
4.2.2 快速模式匹配算法
4.3 数组
4.3.1 数组和数组元素
4.3.2 数组类的定义
4.3.3 数组的顺序存储及实现
4.4 特殊矩阵
4.4.1 对称矩阵的压缩存储
4.4.2 三角矩阵的压缩存储
4.4.3 带状矩阵的压缩存储
4.5 稀疏矩阵
4.5.1稀疏矩阵类的定义
4.5.2稀疏矩阵的顺序存储及其实现
4.5.3稀疏矩阵的链式存储及实现
习题4
第5章 递 归
在计算机科学中，许多数据结构，如广义表、树、二叉树等，都是通过递归方式加以定义的。由于其本身固有的递归性质，因而关于它们的许多问题的算法，均可以采用递归技术加以实现。采用递归技术设计出来的算法程序，具有结构清晰、可读性强、便于理解等优点，但由于递归程序在执行过程中，伴随着函数自身的多次调用，因而其执行效率较低，在追求执行效率的场合下，人们又往往希望采用非递归方式实现问题的算法程序。本章主要介绍递归程序设计的特点、递归程序的执行过程及递归程序转换成非递归程序的方法。
本章的主要内容包括：
5.1 递归与递归程序设计
5.2 递归程序执行过程的分析
5.3 递归程序到非递归程序的转换
5.3.1 简单递归程序到非递归程序的转换
5.3.2 复杂递归程序到非递归程序的转换
5.4 递归程序设计的应用实例
习题5
第6章 树型结构
树型结构是区别于线性结构的另一大类数据结构，它具有分支性和层次性，在计算机科学的许多领域和日常生活中均具有十分广泛的应用，是数据表示、信息组织和程序设计的基础和有力工具。本章主要介绍树的基本概念、树类的定义、树的存储结构及树遍历算法的实现。
本章的主要内容包括：
6.1 树的基本概念
6.2 树类的定义
6.3 树的存储结构
6.3.1 双亲表示法
6.3.2 孩子表示法
6.3.3 孩子兄弟表示法
6.4 树的遍历
6.5 树的线性表示
6.5.1 树的括号表示
6.5.2 树的层号表示
习题6
第7章 二叉树
二叉树是不同于一般树型结构的另一种重要的非线性数据结构，它与第6章介绍的树型结构有着许多相同之处，树型结构中介绍的大多数术语在二叉树中仍然可以使用，同时一般树型结构与二叉树之间可以进行相互转换；但二叉树并非一般树型结构的特殊形式，它们是两种不同的数据结构，许多涉及树的算法采用二叉树表示和处理时更加简洁和方便。本章在介绍二叉树的定义和存储结构的基础上，讨论二叉树遍历问题算法的实现、二叉树与一般树型结构的转换以及穿线二叉树的定义和实现。
本章的主要内容包括：
7.1二叉树的基本概念
7.2二叉树的基本运算
7.3二叉树的存储结构
7.3.1 顺序存储结构
7.3.2 链接存储结构
7.4二叉树的遍历
7.4.1二叉树遍历的定义
7.4.2二叉树遍历的递归实现
7.4.3二叉树遍历的非递归实现
7.5 二叉树其它运算的实现
7.6 穿线二叉树
7.6.1 穿线二叉树的定义
7.6.2 中序穿线二叉树的基本运算
7.6.3 中序穿线二叉树的存储结构及其实现
7.7 树、森林和二叉树的转换
7.7.1 树、森林到二叉树的转换
7.7.2 二叉树到树、森林的转换
习题7
第8章 图
图是一种复杂的非线性结构，在人工智能、网络工程、数学、并行计算、工业设计等领域中，图结构有着广泛的应用。在图结构中，顶点之间的有关联是任意的，图中每个顶点都可以和其它顶点相关联，即数据元素之间存在多对多的关系。相应地，图的存储及其运算也较为复杂。本章先介绍图的概念，再介绍图的存储结构及其应用。
本章的主要内容包括：
8.1图的基本概念
8.2图的基本运算
8.3图的基本存储结构
8.3.1邻接矩阵及其实现
8.3.2邻接表及其实现
8.3.3邻接多重表
8.4图的遍历
8.4.1 深度优先遍历
8.4.2广度优先遍历
8.5生成树与最小生成树
8.5.1最小生成树的定义
8.5.2最小生成树的普里姆算法
8.5.3最小生成树的克鲁斯卡尔算法
8.6最短路径
8.6.1单源最短路径
8.6.2所有点顶点对的最短路径
8.7拓扑排序
8.8关键路径
习题8
第9章 检索
检索又称为查找，就是从一个数据元素集合中找出某个特定的数据元素或者找出满足某类特征的数据元素的过程。本章将系统地讨论各种检索方法，主要包括线性表的检索、树表的检索和哈希表的检索等。
本章的主要内容包括：
9.1检索的基本概念
9.2线性表的检索
9.2.1顺序检索
9.2.2二分法检索
9.2.3分块检索
9.3二叉排序树
9.4丰满树和平衡树
9.4.1丰满树
9.4.2平衡二叉排序树
9.5最佳二叉排序树和Huffman树
9.5.1扩充二叉树
9.5.2最佳二叉排序树
9.5.3 Huffman树
9.6 B-树
9.6.1B-树的定义
9.6.2B-树的基本操作
9.7散列表检索
9.7.1散列存储
9.7.2散列函数的构造
9.7.2冲突处理
习题9
第10章 内排序
排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。
本章的主要内容包括：
10.1排序的基本概念
10.2插入排序
10.2.1直接插入排序
10.2.2二分法插入排序
10.2.3表插入排序
10.2.4Shell插入排序
10.3选择排序
10.3.1直接选择排序
10.3.2树型选择排序
10.3.3堆排序
10.4交换排序
10.4.1冒泡排序
10.4.2快速排序
10.5归并排序
10.6基数排序
10.6.1多排序码的排序
10.6.2静态链式基数排序
习题10
第11章 外排序
在排序操作中，当待排序数据量很大而内存中无法存储所有的数据时，仅仅使用内排序是无法完成排序任务的，此时需要使用外存储器进行外排序。本章概要介绍外存储器及文件的基本知识，并讨论磁盘排序和磁带排序两种外排序的基本思路。
本章的主要内容包括：
11.1外存储器简介
11.1.1磁盘存储器
11.1.2磁带存储器
11.2文件简介
11.2.1文件的逻辑结构
11.2.2文件的存储结构
11.3外排序------磁盘排序
11.3.1磁盘排序
11.3.2多路归并
11.3.3初始有序串的生成
11.4外排序------磁带排序
11.4.1磁带排序
11.4.2非平衡归并
习题11
第12章 动态存储管理
存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、边界标识法、无用单元的收集和压缩存储等内容。
本章的主要内容包括：
12.1概述
12.2可利用空间表及分配方法
12.3边界标识法
12.3.1可利用空间表的结构
12.3.2分配算法
12.3.3回收算法
12.4无用单元的收集
12.5存储压缩
习题12
三、考试和计分方法
平时成绩占30%，理论考试40%，实践性环节考核占30%。
四、教材
《数据结构》(C语言版) ISBN7-115-12221-0/TP.3938
李云清 杨庆红 揭安全 编著
人民邮电出版社 定价：26.00元
五、时间安排
讲授72学时(每周4学时)，上机32学时(每周一次，每次2小时)。
各知识模块及对应的学时：
第1章 概述 2学时
第2章 线性表及其顺序存储 8学时
第3章 线性表的链式存储 8学时
第4章 字符串、数组和特殊矩阵 4学时
第5章 递归 4学时
第6章 树型结构 4学时
第7章 二叉树 8学时
第8章 图 10学时
第9章 检索 10学时
第10章 内排序 8学时
第11章 外排序 2学时
第12章 动态存储管理 2学时
|
