《数据结构》自学指导.doc

《《数据结构》自学指导.doc》由会员分享，可在线阅读，更多相关《《数据结构》自学指导.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构自学指导自学指导一、自学目的一、自学目的使学生掌握计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。本门课程考核要求由低到高共分为“了解” 、 “掌握” 、 “熟练掌握”三个层次。其含义：了解，指学生能懂得所学知识，能在有关问题中认识或再现它们；掌握，指学生清楚地理解所学知识；熟练掌握，指学生能较为深刻理解所学知识，在此基础上能够准确、熟练地分析解决较为简单的实际问题。二、自学内容、要求二、自学内容、要求（一）（一） 数据结构基本概念数据结构基本概念1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与

2、物理结构、数据结构的抽象层次。2、算法的概念和算法的时间复杂度分析要点： 利用大 O 规则计算时间复杂性，对于一般算法能分析出时间复杂度。1、线性表11 线性表的逻辑结构12 线性表的数组实现13 线性表的指针实现链表14 特殊链表要点： 掌握数组实现的特点 掌握链表的实现方法，如单链表的搜索算法与插入、删除算法（二）（二） 栈与队列栈与队列1、栈：栈的特性、栈的基本运算要点：栈的数组实现、栈的链表实现栈满及栈空条件2、队列：队列的特性、队列的基本运算要点：队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件队列的链表实现：链式队列中的队头与队尾指针的表示、3、算术表达式计算：用后缀

3、表示计算表达式，中缀表示改后缀表示（三）（三） 树树1、树：树的定义、树的基本运算要点：树的分层定义是递归的树的一些常用术语，如结点，树根，度，树叶，树的深度等树中结点个数与高度的关系树的几种存储形式2、二叉树：二叉树定义、二叉树的基本运算要点：二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数 有序树和二叉树的转化 二叉树的前序中序后序遍历的递归算法3、二叉排序树：二叉排序树的定义及操作要点： 二叉排序树的查找算法4、穿线二叉树：概念，存储形式要点：用游标实现穿线二叉排序树5、哈夫曼树：哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算要点：哈夫曼树是带权路径长度最小的扩充二叉树

4、 构造哈夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树 在构造过程中，新二叉树按根的权值加入到森林的最后6、堆：堆的定义要点： 堆的顺序存储、堆中结点的双亲、子女和兄弟的位置（四）（四） 图图1、图：图的定义与图的存储表示要点：邻接/代价邻接矩阵表示邻接表表示邻接多重表表示边表表示2、深度优先遍历与广度优先遍历要点：深度优先搜索算法和广度优先搜索算法 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程 为防止重复访问已经访问过的顶点，需要设置一个访问标志数组 visited3、图的连通性要点：深度优先搜索可以遍历一个连通分量上的所有顶点对非连通

5、图进行遍历，可以建立一个生成森林4、最小生成树要点：对于连通网络、可用不会构成环路的权值最小的 n-1 条边构成最小生成树会画出用 Kruskal 算法及 Prim 算法构造最小生成树的过程（五）（五） 查找查找1、集合要点： 用位向量实现集合的操作2、查找表要点： 对有序顺序表的顺序搜索算法 对有序顺序表的折半搜索算法3、散列技术要点：散列的概念 哈希函数的选择 两类解决冲突的方法及其优缺点（六）（六） 排序排序1、基本概念：关键字、关键字比较次数、数据移动次数、稳定性2、熟悉常用排序算法的稳定性、算法的复杂度3、简单排序方法31 插入排序要点：直接插入、折半插入算法的原理和实现方法32 选择排序要点：算法的原理和实现方法33 冒泡排序要点：算法的原理和实现方法4、分治法排序41 合并排序要点：算法的原理和实现方法针对给定的输入实例，写出排序过程42 快速排序要点：算法的原理和实现方法快速排序是一个递归的排序方法当待排序关键码序列已经基本有序时，快速排序显著变慢针对给定的输入实例，写出排序过程5、比较型排序方法51 堆排序要点：算法的原理52 希尔排序要点：算法的原理6、各种排序方法的比较（时间复杂性、稳定性方面）