自学指导书编写格式
课程名称：数据结构 编写者： 自学时间安排：
适用范围：函授（专升本）
一、 学习目的和要求
?学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析技术。
?本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。为今后的程序设计作一些铺垫。
二、 学习方法
《数据结构》这门课程对于学好计算机应用专业的其他后续课程起着非常关键的作用。但是由于课程内容繁多，许多内容有着相当的难度。所以学好它并不是一件很容易的事情。所以一个好的学习方法就显得尤其重要。判断一个学习方法好坏的标准关键看这种学习方法是否适合于自己。所以大家在学习这么课程的过程中，应该不断吸收、总结、归纳，结合自己的特点，找出一种对自己来说行之有效的学习方法，这样学习起来就可以达到事半功倍。
本课程的算法是用类C语言来描述的。类C语言是一种伪语言，其语法与C语言在很大程度上是相似的。所以我们需要掌握C语言和类C语言是学好数据结构的先决条件，所以事先应该对C语言和类C语言有所了解。
对于课程中讲授的各种数据结构，学员们在学习的过程中，要注意总结它们的特点（优缺点），比较它们之间的联系和不同点。
这门课程，学员们要利用尽可能的机会上机编写程序，实践教材中提到的算法，提高自己设计数据结构和算法的思路，理论指导实践，实践中总结经验，加深对理知识的理解。循序渐进的提高程序设计的水平
三、 学习进度表
课程主要内容 1．绪论 2．算法分析 3．线性表、栈和队列 4．二叉树 5．树 学习学时 2 4 12 12 4 作业 √ √ √ √ 实验 √ √
6．内排序 7．检索 8．图 8 8 12 √ √ √ √ √
四、 各章节的内容、重点、难点和作业题、思考题（分章节列出）
第1章 绪论
(1) 了解数据类型、抽象数据类型、数据结构的概念以及它们之间的关系 (2) 了解问题、算法、程序、算法的代价等概念 第3章 算法分析
(1) 了解渐近算法分析、算法代价的增长率等概念 (2) 了解算法的最佳情况、最差情况和平均情况
(3*) 掌握上限、下限的概念以及大Ｏ、大Ω和大Θ表示法 (4**) 掌握渐进分析的化简法则
(5) 掌握简单程序运行时间的计算方法 (6) 了解问题的代价与算法的代价的区别
(7) 了解多参数问题、空间代价、空间/时间权衡原则和实际操作中的一些因素 第4章 线性表、栈和队列
(1*) 了解线性表的基本概念和抽象数据类型 (2**) 掌握顺序表的实现方法
(3**) 掌握带表头结点的单链表的实现方法 (4*) 了解线性表的两种实现方法的优点和缺点 (5) 掌握带表头结点的双链表的实现方法 (7) 了解单循环链表和双循环链表的结构 (8*) 了解栈的基本概念 (9) 掌握顺序栈的实现方法 (10) 掌握链式栈的实现方法 (11) 了解顺序栈与链式栈的比较 (12*) 了解队列的基本概念 (13) 掌握顺序队列的实现方法 (14) 掌握链式队列的实现方法
(15) 了解顺序队列与链式队列的比较 第5章 二叉树
(1) 了解二叉树的定义与术语
(2) 掌握满二叉树与完全二叉树的定义 (3*) 掌握满二叉树定理及其推论 (4) 了解二叉树结点的抽象数据类型
(5*) 掌握前序、中序和后序周游二叉树的方法 (6*) 掌握用指针实现二叉树的方法
(7) 了解二叉树实现的结构性开销的计算 (8*) 掌握用数组实现完全二叉树的方法 (9**) 掌握二叉检索树的实现方法
(10**) 掌握实现堆以及利用堆实现优先队列的方法
(11*) 掌握Huffman编码树的建立以及利用它进行编码/反编码的方法 第6章 树
(1) 了解树的定义与术语
(2) 了解树结点的抽象数据类型及树的周游方法
(3) 掌握树的父指针表示法以及利用UNION/FIND算法解决等价类问题的方法 (4*) 了解树的子结点表表示法、动态和静态的左子结点/右兄弟结点表示法 (5) 了解K叉树和树的顺序表示法 第7章 内排序
(1*) 掌握冒泡排序、选择排序和插入排序算法 (2) 了解Shell排序算法 (3**) 掌握快速排序算法 (4*) 掌握归并排序算法 (5*) 掌握堆排序算法 (6) 了解基数排序算法
(7) 了解各种排序算法的实验比较和排序问题的下限 第9章 检索
(1**) 了解已排序数组的检索方法 (2**) 了解自组织线性表的检索方法 (3) 了解集合的检索方法
(4**) 掌握散列函数的设计方法
(5**) 掌握两种冲突解决策略: 开散列方法和闭散列方法 第11章 图
(1*) 了解图的术语和邻接矩阵、邻接表表示法 (2) 了解图的抽象数据类型
(3*) 掌握图的邻接矩阵和邻接表实现方法
(4**) 掌握图的两种周游算法: 深度优先和广度优先算法 (5*) 掌握图的两种拓扑排序算法 (6) 了解关键路径算法
(7**) 掌握求单源最短路径的Dijkstra算法 (8**) 掌握求每对顶点间最短路径的Floyd算法
(9**) 掌握求最小支撑树的Prim算法和Kruskal算法
注：（*）表示重点，（**）表示既是重点也是难点，作业和实验分别见作业和实验附件
五、 课程的教材和主要参考书
教材：
数据结构与算法分析 （C++版）（第二版）[美] Clifford A. Shaffer 著张 铭 刘晓丹 等译 电子工业出版社2002年6月第1版