《数据结构要点复习》由会员分享，可在线阅读，更多相关《数据结构要点复习（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构要点复习一 基本概念1. 数据：可以被计算机识别，存储和加工处理的符号的总称。2. 数据元素：数据的基本单位，有时，一个数据元素可由若干个数据项组成。3. 数据项：数据不可分割的最小单位。4. 数据对象：性质相同的数据元素的集合，是数据的一个子集5. 数据结构：数据之间的相互关系，包含3个方面的内容：=数据的逻辑结构，也就是数据元素之间的逻辑关系。数据的逻辑结构可以分为线性结构和非线性结构。=数据的存储结构：数据及其逻辑结构载存储器中的实现方式。=对数据可进行的操作：主要包括：查找，插入，删除，修改和排序等。二 算法的描述和分析1. 算法：由有限条指令组成，规定了解决特定问题的一系列操
2、作。2. 算法特性：算法具有有限性，确定性，输入，输出和可行性五个特性=有限性：任何一条指令都只能执行有限次，即算法必须载执行有限步后结束。=确定性：算法中每条指令的含义必须明确，不允许由二义性=输入：一个算法的输入可以包含零个或多个数据。=输出：算法有一个或多个输出=可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。3. 算法评价：一个好的算法应该考虑以下5条准则：=正确性：对一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确的结果=时间复杂性：算法执行的实际时间是随着所用的计算机系统而改变的；而算法所执行的语句条数又依赖于算法设计者采用的算法描述
3、语言和算法的设计风格。所以，用一个算法的基本运算次数来作为算法的时间复杂度并以此来衡量算法的时间效率。要注意的是，一个算法所执行的基本运算次数常常因输入不同而异，与输入规模和输入数据的性质有关。=空间复杂度：一个算法执行所需要的存储空间，用于存储语句，常数，变量，中间结果等。在算法执行的不同时间，其空间复杂度也是不同的。注意：降低算法的时间复杂度和空间复杂度有时是冲突的，需要在这两者之间进行衡量。但算法的时间复杂度往往比算法的空间复杂度更加重要。=可读性：可读性好的算法有助于设计者和他人阅读，理解，修改和重用。=坚固性：在输入非法数据时，算法能适当地作出合适的反应。4. 算法时间复杂度的分析：
4、一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为算法的不同输入往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。一种可行的方法是计算算法的平均运算次数。这样的结果在实际中可能不是特别有用，因为某些输入较其他输入可能更经常出现，所以对数目足够的不同输入的加权平均将会给出更有意义的结果。三 线性表作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。总体来说，线性表这一章的知识点有以下几个方
5、面：1. 线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。2. 线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。3. 线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。4. 线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是
6、不一样的，大家要注意。5. 线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。记住：=除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继；线性表可以为空。=线性表中的元素不需要按递增（减）的顺序排列=线性表的顺序存储：必须占用一片连续的存储单元，便于随即存取表中的任一元素，但不利于插入删除操作。=线性表的链式存储：不必占用连续的存储空间，只适于顺序存取，便于插入删除操作四 队列和栈1. 栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，循环队列，链队等。
7、栈与队列存取数据（请注意包括：存和取两部分）的特点。递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。2. 栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。3. 循环队列中判队空、队满条件，循环队列中入队与出队算法。记住：?栈是后进先出的，队列是先进先出的；?队列的入队序列=出队序列?栈的入栈序列！=出栈序列，由多种可能性。五 树：1. 相关概念：1.
8、）树：树（Tree）是n（n0）个结点的有限集。在任意一颗非空树中（1）有且仅有一个特定的称为根（Root）的结点（2）当n1时，其余结点可以分为m（m0）个互不相交的有限集，其中每一个集合本身又是一颗树，并且称为根的子树。2. ）结点的度：结点拥有的子树数3. ）叶子：度为0的结点称为叶子或终端结点。4. ）树的度：树内各结点的度的最大值。）孩子和双亲：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲（双亲是一个结点，而不是两个结点！）5. ）兄弟：同一个双亲的孩子之间互称为兄弟。6. ）祖先：从根到该结点所经分支上的所有结点。7. ）子孙：以某结点为根的子树中的任一结点都称为该
9、结点的子孙。8. ）堂兄弟：其双亲在同一层的结点互为堂兄弟。）有序/无序树：如果将树中结点的各子树看成是从左到右有次序的（不能互换），则称该树为有序树，否则为无序树。11.）森林：森林是m颗互不相交的树的集合。12.）二叉树：每个结点至多只有二颗子树的有序树。13.）满二叉树：深度为k且有2的k次方-1个结点的二叉树（具备所有可能的结点）。14.）完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树2. 树的高度（或深度）：就是树中结点的最大层次（树最高一层的层次）。有两种情况。假设树总共有三层，若设根的层次为0，则
10、高h为2若设根的层次为1，则高h为3。无特别声明的时候，通常认为根的层次为1（解题时特别要注意这一点）。3. 树的结点的相关计算1. ）对所有的树均有：叶子结点=度为0的结点非叶子结点=度0的结点叶子结点+非叶子结点=总结点2. ）对任意一棵树，若度为n,且度为m的结点树为Pm（m=1,2,3,4.）则有：总结点数=1+1*P1+2*P2+3*P3+4*P4+.+n*Pn（力卩1是表示根结点）非叶子结点数=P1+P2+P3+Pn.叶子结点数=总结点数-非叶子结点数。4. 二叉树：1. ）定义：二叉树是每个结点至多只有二颗子树的有序树。）二叉树的性质（设根的层次为1）（1）第i层上最多有2的（i
11、-1）次方个结点。（2）若二叉树的高度为h，则二叉树最多有2的h次方-1个结点，此时二叉树即为满二叉数。（3）对任意一颗二叉树，如果其叶子结点（度为0）的结点数为n0,度为2的结点树为n2，则n0=n2+15完全二叉树：1.）定义：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。2. ）性质：=若将最高一层除去，则剩下的二叉树为满二叉树。（若深度为k有n个结点，则n2的（k-1）次方-1）=叶子结点只可能出现在层次最大的两层上。=具有n个结点的完全二叉树的深度为Log2n+1=对n个结点的完全二叉树编号，则对任一结点i有-
12、结点i的双亲是i/2（i1）-结点i的左孩子是结点2i（2i书n-结点i的右孩子是结点2i+1（2i+1菊n6. 树的特性=二叉树的度不一定为2；=根据同一颗二叉树的两种遍历顺序，可唯一地确定一颗二叉树（也可以得到用另一种遍历方法得到的遍历序列）=二叉树的三种遍历方法所得到的遍历序列中，所有叶子结点之间的相对顺序不变。7. 二叉树的存储1. ）分为数组存储和链表存储2. ）顺序存储-数组表示法：采用一组连续存储空间存储二叉树结点中的数据元素。仅适用于完全二叉树，当用于存储一般二叉树时，一个主要的问题是空间利用率低。3. ）链表表示法：链表比较适合存储一般的二叉树；通常将树中的每一个元素用一个结
13、点表示，结点一般包括三个域，即元素的数值，指向其左孩子结点的指针和指向其右孩子结点的指针，称为二叉链表。）三叉链表：在二叉链表的基础上，加上一个指向结点的双亲的指针，这样就可以方便的找到一个结点的父结点。8. 树的遍历1. ）四种方法：先根（序）遍历，中根（序）遍历，后根（序）遍历，层次遍历。2. ）遍历二叉树所得到的遍历序列中：-三种遍历序列中，叶子结点的相对顺序相同。-先根遍历序列：根结点+左子树结点群+右子树结点群中根遍历序列：左子树结点群+根结点+右子树结点群后根遍历序列：左子树结点群+右子树结点群+根结点-由任意二种遍历序列可唯一确定一颗二叉树3. ）二叉排序树的中根遍历得到一个递增
14、序列。4. ）层次遍历：从二叉树的第一层（根结点）开始，自上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。在进行层次遍历时，对一层结点访问完后，再按照它们的访问顺序对各个结点的左孩子和右孩子顺序访问。线索二叉树：对二叉树以某种方式遍历后，得到二叉树中所有结点的一个线性序列。这样，二叉树中的结点就有了唯一直接前驱结点和唯一直接后继结点。在线索二叉树时，二叉树采用二叉链表作为存储结构，每个结点有五个域leftChild,leftTag,data,rightTag,rightChild，规定：如果某结点的左指针域为空，令其指向依某种方式遍历时所得到的该结点的前驱结点，否则指向左孩子。如
15、果某结点的右指针域为空，令其指向依某种方式遍历时所得到的该结点的后继结点，否则指向右孩子。为了区分一个结点的指针是指向左右孩子还是指向前驱，后继结点，可用标志为来区分：如果leftTag/rightTag=0,那么指向左/右孩子。如果leftTag/rightTag=1,那么指向前驱/后继线索。对一颗二叉树的遍历方法不同，得到的线索二叉树也不同。通常有前序线索二叉树，中序线索二叉树，后序线索二叉树。9. 哈夫曼树1. ）路径：在一颗二叉树中由根结点到某个结点所经过的分支序列叫做由根结点到这个结点的路径。2. ）路径的长度：由根结点到某个结点所经过的分支数称为由根结点到该结点的路径长度。3. ）二叉树的路径长度：由根结点到所有叶结点的路径长度之和称为该二叉树的路径长度。4. ）二叉树的带权路径长度：设一颗具有n个带权值叶结点的二叉树，从根结点到各个叶结点的路径长度与对应叶结点权值的乘积之和叫做二叉树的带权路径长度WPL。5. ）哈夫曼树（最优二叉树）：对于一组确定权值的叶结点，可以构造出多重
