数据结构知识点整理(清华大学出版社)

第一章绪论010609172230061.数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。2.逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义。分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多)形成一个树形数据结构，城市间据通路(多对多)形成图状结构，此外还有集合结构(除同属一个集合外，无其它关联)，共四类3.数据结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。4.顺序存储结构：关系采取顺序映像表示，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5.度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。6.时间复杂度：频度函数的增长率基本与函数中“关键项”(去掉低次项和常数项)的增长率相同，故可用“关键项”反映算法效率。假设关键项为f(n)，用T(n)=O(f(n))表示算法时间增长率与f(n)增长率同阶。称O(f(n))为算法的渐近时间复杂度，简称时间复杂度。f(n)的增长率为f(n+1)/f(n)，如对复杂度为O(n)的算法其运行时间随问题规模增长率为1+1/n,复杂度为O(1)的算法时间增长率为1。7.按增长率由小至大的顺序排列下列各函数(2/3)n-2100-㏒2n-n1/2-n-n㏒2n-n3/2-2n-n!-nn第二章线性表1.顺序表：借助元素在存储器中位置上的”相邻”关系表示数据元素间具有的关系，如此存储的线性表称为顺序表。顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动(表尾除外)；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。2.线性链表:采用链式存储结构的线性表对应一个链表。结点包含数据域和指针域两部分。链表名指向第一个结点(头指针)，尾结点指针域值为NULL。链表优点是空间利用好,插入删除不移动数据,表头表尾操作快(改进的单链表),位置概念强；缺点是需要顺序访问各元素，位序概念弱。3.注意链表中next指针的应用，如插入，删除等操作各个元素的链接。1.队列类似线性表和栈,也是定义在线性结构上的ADT,与线性表和栈的区别在于，元素的插入和删除分别在表的两端进行。类似日常生活中排队,允许插入的一端为队尾(rear),允许删除端称队头(front)。特性:FirstInFirstOut先进先出，如操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。1.初始化一个“空”的稀疏矩阵，按照目标矩阵中的出现次序对原矩阵中的元素逐个转置，列号col从1变到n，每次从头至尾扫描M.data，对列标等于col的三元组，将其行标、列标互换后依次放入T.data[]中。第三章树和二叉树1.树的结构特点：树是一个层次结构，“有且仅有一个根结点无前驱(第一层)；有一或多个叶结点无后继；其余结点有唯一前驱和若干后继”。递归定义：树由根结点(唯一)及该根结点的若干(零或多个)“子树”组成。不含任何结点也是树，称为空树（1）结点(node)：一个数据元素及其若干指向其子树的分支。（2）结点的度(degree)、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。（3）叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。（4）孩子结点、双亲结点、兄弟结点：一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。2.性质1:在二叉树的第i层上最多有2i-1个结点（i≥1）性质2:深度为K的二叉树最多有2K-1个结点（K≥1）性质3:对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证:二叉树上结点总数n=n0+n1+n2。二叉树上边的总数e=n1+2n2。根结点外每个结点都有且仅有一条边(分支)”进入”，故e=n-1。由此n-1=n0+n1+n2-1，进而n0=n2+1。性质4：含n个结点的完全二叉树深度为log2n+1。性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子，否则，编号为2i+1的结点为其右孩子结点。3.含n个结点的树中，只有度为k的分支结点和度为0的叶子结点,试求该树含有的叶子结点数提示:n0+nk=n;e=knk=k(n-n0)=n-1故：n0=(nk-n+1)/k4.二叉树是度不大于2的有序树(每个结点最多两棵子树,子树有左右之分)。5.满二叉树：设深度为k,含2k-1个结点的二叉树。结点数达最大。6.完全二叉树：设树中含n个结点,它们和满二叉树中编号为1至n的结点位置上一一对应(编号规则为由上到下，从左到右）。相比满二叉树仅少“最后的”若干个，不能少中间的。完全二叉树特点：(1)叶子结点出现在最后2层或多或1层。(2)对于任意结点，若其右分支下的子孙的最大层次为L,则左分支下的子孙的最大层次为L或L+1。7.二叉树顺序存储：将二叉树映射到完全二叉树上，不存在的结点以空标记，之后用地址连续的存储单元(一维数组)依次自上而下、自左而右存储完全二叉树上的各元素.(将一般二叉树以完全二叉树形式存储),最坏情况下k个结点需2k-1个单元。但适合完全二叉树的存储，操作简单方便。8.二叉树链表存储：二叉链表包含内容，左孩子及右孩子的指针。三叉链表多了一个指向双亲结点的指针。9.先(根)序遍历：树非空则访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树；空则无操作。中(根)序遍历：树非空则递归地中序遍历根左子树；后访问根结点,再递归地中序遍历右子树；空则无操作。后(根)序遍历：树非空则递归地后序遍历根右子树；后递归地后序遍历右子树，再访问根结点；空则无操作层次遍历：由上到下,由左到右，不宜递归10.由遍历序列确定二叉树：先序序列+中序序列：先序序列中第1个元素X为根，中序序列中唯有遍历完X的左子树后方访问X，故X之前的abc…必构成X的左子树，X之后的def…必构成X的右子树。对于子树类似处理，第1个在先序序列中出现的元素Y为该左子树的根，中序序列中Y左侧的元素构成Y的左子树，右侧构成右子树，依此类推，最终可定。中序序列+后序序列：后序序列中最后一个元素为根，中序序列中该结点前的元素为左子树，后的元素为右子树。对于左/右子树，最后一个在后序序列中出现的元素为子树的根结点，再看中序序列，依此类推。先序输出+后序输出不能确定。如AB和BA。11.二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，增加两个标志位LTag与RTag：其为0是表示域指向孩子，为1时表示指向其前驱或者后继。（详细见课本P132）12.二叉树的线索化：设一棵二叉树有n个结点，则有n-1条边(指针连线)，而n个结点共有2n个指针域(Lchild和Rchild)，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。增设头结点，左标记为Link，左指针指根结点，右标记为Thread，右指针指向最后被访问的结点，树空则均指向头结点。又称双向线索链表，先写出遍历序列，后添加头结点，再据序列增加线索即可。用这种结点结构构成的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；按照某种次序遍历，加上线索的二叉树称之为线索二叉树。13.树的双亲表示法：以一组连续空间存储结点，各结点附设指示器指示其双亲结点的位置(数据域+双亲下标域)。14.树的孩子表示法：结点中为其每个孩子附设一个指针。具体定义时各结点指针的个数可取最大，也可根据各自的度不同而不同。前者同构，实现简单；后者需动态开辟指针域，实现复杂但空间省。15.孩子双亲表示法：链式存储与顺序存储结合,将各结点存储在一个数组中,每个数组元素附加一指针域指向结点的孩子形成的链表。若经常进行访问双亲结点的操作则可向数组元素追加双亲位置域。16.树的孩子兄弟表示法（二叉链表存储）：链式存储,每个结点包括数据域和两个指针域，左指针指向第一个孩子结点，右指针指向兄弟结点.又称二叉链表存储法。（表示法能画出来应该就可以，各个存储结构应该不会考吧，有兴趣的自己找找书P135）17.森林的孩子兄弟表示法（二叉链表存储）：单颗树的二叉链表存储结构中根结点的右指针必为空，若要存储多颗树组成的森林，可将后一颗树的根结点看成前一颗树根结点的兄弟，即将后一颗树对应的二叉链表拼接到前一颗树根结点的右指针上，这称为森林的孩子兄弟表示法或二叉链表存储法。18.树、森林与二叉树的转换：以二叉链表存储结构为转换依据，将左右指针所指结点理解为左右孩子结点则得到二叉树；将左指针所指结点理解为孩子,右指针所指结点理解为当前结点的兄弟则得树或森林。19.树采用二叉链表存储，对树进行遍历即对二叉链表进行遍历。先序遍历二叉链表（先根结点后左子树再右子树），对应到树上是“先根，后自左到右递归遍历各子树”，称为树的先根序遍历。对二叉链表进行中序遍历(先左子树中根再右子树)对应到树上是“先从左到右各子树，后根”，称为树的后根序遍历。20.森林采用二叉链表存储(孩子兄弟表示法)，先序遍历二叉链表(先根结点后左子树再右子树)，对应到树上为“从左到右依次先根遍历各颗树”，称为森林的先序遍历。森林采用二叉链表存储(孩子兄弟表示法)，对二叉链表“先左子树中根再右子树”中序遍历，对应到森林为“从左到右依次后根遍历各颗树”，称为森林的中序遍历。21.由树的先根和后根遍历序列确定树：方法一(间接法，借助二叉链表)：树的先根序列对应二叉链表的先序序列、后根序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的树。方法二(直接法，根据先根后根)：先根序列中第1个X一定是整颗树的根结点，而后根序列中唯有遍历完X的所有子树后方访问X，故X必然出现在最后；先根序列中第二个顶点必然是第一个子树的根结点，后根序列中该结点前的结点为此子树中各结点；除去第一颗子树中的结点后，先根序列中第一个结点必为第二颗子树的根结点，而后根序列中此结点前的结点构成第二颗子树，以此类推，最终可确定。22.由森林的先序和中序遍历序列确定森林：方法一(间接法，借助二叉链表):森林的先序序列对应二叉链表的先序序列、中序序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的森林方法二(直接法，根据先根后根)：先序序列中第1个X一定是第一颗树的根结点,而中序序列中在遍历完第一颗树的最后访问X,故中序序列中X之前的结点构成森林的第