1、数据结构自学指导一、自学目的使学生掌握计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。本门课程考核要求由低到高共分为“了解” 、 “掌握” 、 “熟练掌握”三个层次。其含义：了解，指学生能懂得所学知识，能在有关问题中认识或再现它们；掌握，指学生清楚地理解所学知识；熟练掌握，指学生能较为深刻理解所学知识，在此基础上能够准确、熟练地分析解决较为简单的实际问题。二、自学内容、要求（一） 数据结构基本概念1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。2、算法的概念和算法的时间复杂度分析要
2、点： 利用大 O 规则计算时间复杂性，对于一般算法能分析出时间复杂度。1、线性表11 线性表的逻辑结构12 线性表的数组实现13 线性表的指针实现链表14 特殊链表要点： 掌握数组实现的特点 掌握链表的实现方法，如单链表的搜索算法与插入、删除算法（二） 栈与队列1、栈：栈的特性、栈的基本运算要点： 栈的数组实现、栈的链表实现 栈满及栈空条件2、队列：队列的特性、队列的基本运算要点： 队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件 队列的链表实现：链式队列中的队头与队尾指针的表示、3、算术表达式计算：用后缀表示计算表达式，中缀表示改后缀表示（三） 树1、树：树的定义、树的基本运算
3、要点： 树的分层定义是递归的 树的一些常用术语，如结点，树根，度，树叶，树的深度等 树中结点个数与高度的关系 树的几种存储形式2、二叉树：二叉树定义、二叉树的基本运算要点： 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数 有序树和二叉树的转化 二叉树的前序 中序后序遍历的递归算法3、二叉排序树：二叉排序树的定义及操作要点： 二叉排序树的查找算法4、穿线二叉树：概念，存储形式要点： 用游标实现穿线二叉排序树5、哈夫曼树：哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算要点： 哈夫曼树是带权路径长度最小的扩充二叉树 构造哈夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，
4、具次小关键码的子树是根的右子树 在构造过程中，新二叉树按根的权值加入到森林的最后6、堆：堆的定义要点： 堆的顺序存储、堆中结点的双亲、子女和兄弟的位置（四） 图1、图：图的定义与图的存储表示要点： 邻接/代价邻接矩阵表示 邻接表表示 邻接多重表表示 边表表示2、深度优先遍历与广度优先遍历要点： 深度优先搜索算法和广度优先搜索算法 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程 为防止重复访问已经访问过的顶点，需要设置一个访问标志数组 visited3、图的连通性要点： 深度优先搜索可以遍历一个连通分量上的所有顶点 对非连通图进行遍历，可以建立一个生成森林4、最小生成树要点： 对于连
5、通网络、可用不会构成环路的权值最小的 n-1 条边构成最小生成树 会画出用 Kruskal 算法及 Prim 算法构造最小生成树的过程（五） 查找1、集合要点： 用位向量实现集合的操作2、查找表要点： 对有序顺序表的顺序搜索算法 对有序顺序表的折半搜索算法3、散列技术要点： 散列的概念 哈希函数的选择 两类解决冲突的方法及其优缺点（六） 排序1、基本概念：关键字、关键字比较次数、数据移动次数、稳定性2、熟悉常用排序算法的稳定性、算法的复杂度3、简单排序方法31 插入排序要点： 直接插入、折半插入算法的原理和实现方法32 选择排序要点： 算法的原理和实现方法33 冒泡排序要点： 算法的原理和实现方法4、分治法排序41 合并排序要点： 算法的原理和实现方法 针对给定的输入实例，写出排序过程42 快速排序要点： 算法的原理和实现方法 快速排序是一个递归的排序方法 当待排序关键码序列已经基本有序时，快速排序显著变慢 针对给定的输入实例，写出排序过程5、比较型排序方法51 堆排序要点： 算法的原理52 希尔排序要点： 算法的原理6、各种排序方法的比较（时间复杂性、稳定性方面）
