数据结构教学大纲.txt

南京工业大学的《数据结构》教学大纲

                     《数据结构》教学大纲
                                 
英文名称：Data Structures
学分：4      学时：72 （其中讲课学时:56  实习学时：16）
先修课程：离散数学、C/C++程序设计
教学对象：计算机专业及相关专业的本科生
教学目的与要求：
　　《数据结构》是计算机专业的专业基础课和专业主干课程之一，是编译技术、操作系统、数据库原理等课程的重要基础。本课程旨在让学生学习、分析和研究计算机加工数据对象的特征、掌握数据的组织方法，以便选择合适的数据的逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示和实现。使学生的算法设计和程序设计能力得以培养和提高。
　　
教学内容：
第一章 绪论（2学时）
1.1 什么是数据结构
1.2 基本概念和术语
1.3 算法的描述和算法分析
基本要求：了解《数据结构》所研究的问题，理解数据结构的基本概念，掌握算法的描述、算法设计的要求和算法效率的度量方法。
　　重点：数据的逻辑结构和存储结构；用类C（C++）语言描述算法。
　　难点：算法的时间复杂性分析和时间复杂度的计算。
第二章 线性表（4学时）
　　2．1    线性表的逻辑结构
　　2．2    线性表的顺序存储结构
　　2．3    线性表的链式存储结构
　　单向链表、循环链表、双向链表
2． 4    一元多项式的表示及相加
基本要求：掌握线性表的逻辑结构、存储结构及描述方式；掌握顺序表和链表的插入、删除等操作。
重点：线性结构的定义和特点；顺序表和单链表的组织方法、特点和算法。
难点：链表中的头结点的引入和链表的算法设计。
第三章 栈和队列（4学时）
3．1 栈的定义、栈的表示和实现
3．2   表达式求值
3．3   队列的定义、队列的链式存储结构（链队列）、队列的顺序存储结构（循环队列）
基本要求：了解栈和队列的定义；理解线性表、栈和队列特点及区别，栈对实现递归过程的作用；掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。
重点：栈和队的特点；顺序栈和链栈上基本运算的实现和简单算法设计；链队上基本运算的实现和简单算法设计，栈与递归。 
     难点：循环队列的组织、队空和队满的条件及算法设计；递归过程及其实现。
第四章 串（3学时）
4．1 串的逻辑结构定义及其基本操作
4．2 串的静态存储结构和动态存储结构
基本要求：了解串的有关定义；理解串的逻辑结构和存储结构；掌握串的模式匹配传统方法和KMP方法。
　　　重点：串的基本运算及串的传统匹配方法和改进的KMP方法。
　　　难点：模式串的next函数值的求法。
第五章 数组和广义表（3学时）
5．1 数组的定义和运算
5．2 数组的顺序存储结构
5．3 矩阵（特殊矩阵、稀疏矩阵）的压缩存储
5．4 广义表的定义
5．5 广义表的存储结构及算法
基本要求：了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念、链表表示和算法；理解矩阵的压缩存储的概念；掌握矩阵的压缩存储的有关计算方法。
　　　重点：特殊矩阵的非零元下标与数组下标的对应关系。
　　　难点：稀疏矩阵的三元组的表示和转置过程及十字链表的表示。 
第六章 树和二叉树（8学时）
6．1 树的结构定义和基本操作
6．2 二叉树
　　　　　　定义与基本操作、性质、存储结构、遍历和线索化
6．3   树和森林。
　　　　　　树的存储结构、森林与二叉树的转换、树的遍历
     6．4   哈夫曼树及其应用
基本要求：了解树的定义和二叉树的定义；理解二叉树的性质、二叉树的存储结构；掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。
重点：利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题；哈夫曼树及其应用。
难点：关于二叉树遍历序列确定二叉树的问题；二叉树遍历算法中栈的使用及非递归算法。
第七章 图（8学时）
7．1 图的定义和术语
7．2 图的存储结构：数组表示法、邻接表
7．3   图的遍历：深度优先搜索、广度优先搜索
7．4   图的连通性问题：无向图的连通分量和生成树、最小生成树
     7．5   最短路经
     7．6   拓扑排序
     7．7   关键路经
基本要求：了解图的定义和术语，生成树和最小生成树的概念；理解邻接矩阵中元素的含义和邻接表中结点的含义；掌握深度优先搜索和广度优先搜索算法；
　　　　　　　　理解求最小生成树、最短路径、拓扑排序和关键路径等各种图解方法。
　　　重点：图的两种表示，两种遍历；用Prim算法和Kruskal算法构造最小生成树。
难点：图的遍历的唯一性；单源点、多源点的最短路径；用拓扑排序算法求关键路径。

第八章    动态存储管理（2学时）
     8．1  可利用空间表及分配方法
     8．2  边界标识法
     8．3  伙伴系统
     基本要求：了解动态存储管理的含义及分配方法。
     重点：边界标识法中可利用空间表的结构及分配算法和回收算法。
     难点：分配算法和回收算法。
第九章      查找（8学时）
9．1 静态查找表：顺序表的查找、有序表的查找、索引顺序表的查找
9．2 动态查找表：二叉排序树和平衡二叉树、B_树和B+树
9．3 哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找及其分析
基本要求：了解顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找等的概念；理解顺序查找、二分查找和分块查找算法，二叉排序树的性质；掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树的查找、插入和删除操作算法及相关查找方法的成功平均查找长度ASL。
重点：二分查找的基本条件和方法；建立二叉排序树和平衡二叉树的过程；根据散列函数和解决冲突的方法建立散列表及等概率下成功平均查找长度ASL。
     难点：平衡二叉树调整规律的理解和方法掌握；B-树B+树的理解。
第十章      内部排序（8学时）
　　10．1   概述
10．2   插入排序：直接插入排序、希尔排
　　10．3   交换排序：冒泡排序、快速排序
　　10．4   选择排序：简单选择排序、树形选择排序、堆排序
　　10．5   归并排序：二路归并
　　10．6   基数排序
　　10．7   各种内部排序方法的比较讨论
基本要求：了解排序算法的稳定性问题；理解直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想；掌握直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的算法和时间分析。
 重点：对直接插入排序、简单选择排序、快速排序、堆排序、归并排序基本过程的掌握和算法的理解及评价。
    难点：排序方法的选择；对冒泡排序算法和快速排序算法的分析和改进。
第十一章     外部排序（2学时）
11．1   外存信息的存取
11．2   外存排序的方法
11．3   多路平衡归并的实现
       11．4   置换-选择排序
　　　基本要求：了解外排序的基本过程及方法。
      重点：外部排序方法
      难点：利用“败者树”解决K路平衡归并和置换-选择排序问题
第十二章   文件（2学时）
　　　12．1   有关文件的基本概念
　　　12．2   顺序文件
　　　12．3   索引文件
　　　12．4   ISAM文件和VSAM文件
　　　12．5   直接存取文件（散列文件）
　　　12．6   多关键字文件：多重表文件、倒排文件
　　　基本要求：熟悉各类文件的特点及构造方法。
　　　重点：顺序文件、索引文件和散列文件。
      难点：采用静态索引结构的ISAM文件及采用B+树的动态索引结构的VSAM文件。

上机实习（16学时）：
　　　1. 约瑟夫问题
   2．迷宫问题
　　　3．表达式的转换及求值
　　　4．建立词索引表
　　　5．哈夫曼编码及译码
　　　6．关键路径
　　　7．散列函数的应用
　　　8．希尔排序、快速排序、堆排序和归并排序等方法的比较

考核方式：  理论课（闭卷考试）
总评成绩：  平时成绩：20%   考试成绩：80%
参考教材：  1. 严蔚敏、吴伟民《数据结构》（C语言版）清华大学出版社   1997
            2. 殷人昆等编著《数据结构》（用面向对象方法与C++描述）
　　　　　　　　　　　　　　　　　　　　　　　　　　清华大学出版社   1999
            3. 《数据结构与程序设计-C++语言描述》（影印版）
                                                    高等教育出版社   2001