数据结构复习串讲

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构复习串讲,概论,：主要是概念，算法的计算。,线性表,：基础章节，多数为基本概念题。,栈和队列,：基础章节，基本概念题。栈常与其它章节配合考查，也常与递归等概念相联系进行考查。,串,：基础章节，概念较为简单。,多维数组及广义表,：基础章节，数组常与“查找，排序”等章节结合来作为大题考查。,树和二叉树,：重点难点章节，算法题。,图,：重点难点章节，可与树一章共同构成算法设计大题的题型设计。,查找,：重点难点章节，概念较多，联系较为紧密，容易混淆。分析型题目，基本概念型题目。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。,排序,：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，常与数组结合来考查。,概述,本章主要起到总领作用,数据结构的基本概念，时间和空间复杂度的概念及度量方法,线性表,链式存储概念将是整个数据结构学科的重中之重,1.,线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。,2.,线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。,3.,线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法、判断链表是否为空（在不同的链表中，其判表空的方式是不一样的）等都是较为常见的考查方式。,4.,线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。,栈与队列,1.,栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。,2.,递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：,n!,阶乘问题，,fib,数列问题，,hanoi,问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。,3.,栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解。,4.,循环队列中判队空、队满条件，循环队列中入队与出队算法。,串,1.,串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件,2.,串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。,运用串的基本操作去完成特定的算法,。,3.,顺序串与链串及块链串的区别和联系，实现方式。,数组与广义表,1.,多维数组中某数组元素的,position,求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。,2.,明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解,1,中类型的题。,3.,将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。,4.,广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。,树与二叉树,总体来说，树一章的知识点包括：,二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。,1.,二叉树的概念、性质和存储结构,考查二叉树的定义，说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第,i,层的最多结点数，深度为,k,的二叉树的最多结点数，,n0=n2+1,的性质，,n,个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：,2*i,，右为：,2*i+1,）。,二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。,2.,二叉树的三种遍历算法,二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数）。,3.,可在三种遍历算法的基础上改造完成的其它二叉树算法：,求叶子个数，求二叉树结点总数，求度为,1,或度为,2,的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为,n,的某个指定结点，删除值为,n,的某个指定结点，诸如此类等等等等。,4.,线索二叉树：,线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。,5.,最优二叉树（哈夫曼树）：,最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。给一组数据，要求建立基于这组数据的最优二叉树，并求出其最小权值之和。,6.,树与森林：,二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为,2,以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。,树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。,图,1.,考查有关图的基本概念问题：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。,2.,考查图的几种存储形式：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。,3.,考查图的两种遍历算法：深度遍历和广度遍历,深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为,K,的简单路径问题”，就分别用到了广度遍历和深度遍历算法。,4.,生成树、最小生成树的概念以及最小生成树的构造：,PRIM,算法和,KRUSKAL,算法。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。,图,5.,关键路径问题：,这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。一般要求按照书上的算法描述求解的过程和步骤。,在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为,0,。关键路径问题是工程进度控制的重要方法，具有很强的实用性。,7.,最短路径问题：,与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用,DIJSKTRA,算法，解决第二个问题用,FLOYD,算法。注意区分。,查找,在复习这一章的知识时，,需要先弄清楚以下几个概念,：关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度,ASL,的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的,ASL,值，应该记住。,1.,线性表上的查找：,主要分为两种线性结构：顺序表，有序顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。需要注意这两种表下的,ASL,值以及算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。,2.,树表上的查找：,这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二叉排序树，平衡二叉树，,B,树，键树。其中，尤以前两种结构为重。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密。,查找,二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于,1,。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。,3.,基本哈希表的查找算法：,哈希一词，是外来词，译自“,hash”,一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个,function,，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。,排序,排序的各种算法汇总以及算法复杂度的比较,插入排序,，与线性表的查找结合，有直接插入和折半插入，与链表结合，有表插入，另外要注意希尔排序，是逐趟缩小间隔的方法，要详细了解每一趟的排序算法。,快速排序,，有起泡排序法（思想简单，容易理解）和快速排序，要了解一趟快速排序的思想，知道如何设置枢轴，其他关键字与枢轴的关系，如何调整关键字。,堆排序，利用堆的概念，找出关键字中的最大者（或最小者），依次进行排序。堆的概念是重点，相关的概念是筛选和建堆。可与二叉树的概念相结合,归并排序，思想简单，通过两两合并的方法，将小的有序集合扩大成大的有序集合。,