数据结构要点复习

一 基本概念
1.数据：可以被计算机识别，存储和加工处理的符号的总称。
2.数据元素：数据的基本单位，有时，一个数据元素可由若干个数据项组成。
3.数据项：数据不可分割的最小单位。
4.数据对象：性质相同的数据元素的集合，是数据的一个子集
5.数据结构：数据之间的相互关系，包含3个方面的内容：
  ===>数据的逻辑结构，也就是数据元素之间的逻辑关系。数据的逻辑结构可以分为线性结构和非线性结构。
  ===>数据的存储结构：数据及其逻辑结构载存储器中的实现方式。
  ===>对数据可进行的操作：主要包括：查找，插入，删除，修改和排序等。
 

一 基本概念
1.数据：可以被计算机识别，存储和加工处理的符号的总称。
2.数据元素：数据的基本单位，有时，一个数据元素可由若干个数据项组成。
3.数据项：数据不可分割的最小单位。
4.数据对象：性质相同的数据元素的集合，是数据的一个子集
5.数据结构：数据之间的相互关系，包含3个方面的内容：
  ===>数据的逻辑结构，也就是数据元素之间的逻辑关系。数据的逻辑结构可以分为线性结构和非线性结构。
  ===>数据的存储结构：数据及其逻辑结构载存储器中的实现方式。
  ===>对数据可进行的操作：主要包括：查找，插入，删除，修改和排序等。
 

二 算法的描述和分析
1.算法：由有限条指令组成，规定了解决特定问题的一系列操作。
2.算法特性：算法具有有限性，确定性，输入，输出和可行性五个特性
===>有限性：任何一条指令都只能执行有限次，即算法必须载执行有限步后结束。
===>确定性：算法中每条指令的含义必须明确，不允许由二义性
===>输入：一个算法的输入可以包含零个或多个数据。
===>输出：算法有一个或多个输出
===>可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。
3.算法评价：一个好的算法应该考虑以下5条准则：
===>正确性：对一切合法的输入数据，该算法经过有限时间（算法意义上的有限）的执行都能产生正确的结果
===>时间复杂性：算法执行的实际时间是随着所用的计算机系统而改变的；而算法所执行的语句条数又依赖于算法设计者采用

的算法描述语言和算法的设计风格。所以，用一个算法的基本（！！）运算次数来作为算法的时间复杂度并以此来衡量算法的

时间效率。要注意的是，一个算法所执行的基本运算次数常常因输入不同而异，与输入规模和输入数据的性质有关。
===>空间复杂度：一个算法执行所需要的存储空间，用于存储语句，常数，变量，中间结果等。
在算法执行的不同时间，其空间复杂度也是不同的。注意：降低算法的时间复杂度和空间复杂度有时是冲突的，需要在这两者

之间进行衡量。但算法的时间复杂度往往比算法的空间复杂度更加重要。
===>可读性：可读性好的算法有助于设计者和他人阅读，理解，修改和重用。
===>坚固性：在输入非法数据时，算法能适当地作出合适的反应。
4.算法时间复杂度的分析：一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为算法的不同输入

往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。一种可行的方法是计算算法的平均运算次数。

这样的结果在实际中可能不是特别有用，因为某些输入较其他输入可能更经常出现，所以对数目足够的不同输入的加权平均将

会给出更有意义的结果。

三 数组和字符串
1.稀疏矩阵
===>设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。
===>稀疏矩阵的压缩存储
    为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存

储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能

。其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
    稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。
===>三元组表
    将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵

的顺序存储结构称为三元组表。
===>稀疏矩阵的链式结构
    当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构

更为恰当。 稀疏矩阵的链式结构有十字链表等方法
    十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中:
    矩阵的每一行和每一列都设置一个由表头结点引导的循环（！！！）链表
    每一个非零元用一个结点表示，结点中除了表示非零元所在的行(row)、列(col)和值(val)的域外，还需增加两个链域：行

指针域(right)，用来指向本行中下一个非零元素；列指针域(down) ，用来指向本列中下一个非零元素。

四 队列和栈
栈是后进先出的，队列是先进先出的；
队列的入队序列=出队序列
栈的入栈序列！=出栈序列，由多种可能性。
例见《全国计算机等级考试应试指导及模拟试题集四级》
P58 例1 P64 例14 P71 45 P76 79
P74 65，69。

五 线性表
===>除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继；线性表可以为空。
===>线性表中的元素不需要按递增（减）的顺序排列
===>线性表的顺序存储：必须占用一片连续的存储单元，便于随即存取表中的任一元素，但不利于插入删除操作。
===>线性表的链式存储：不必占用连续的存储空间，只适于顺序存取，便于插入删除操作

六 树：
1. 相关概念：
1.)树：树（Tree）是n（n≥0）个结点的有限集。在任意一颗非空树中
 （1）有且仅有一个特定的称为根（Root)的结点
 （2）当n＞1时，其余结点可以分为m（m＞0）个互不相交的有限集，其中每一个集合本身又是一颗树，并且称为根的子树。
2.)结点的度：结点拥有的子树数
3.)叶子：度为0的结点称为叶子或终端结点。
4.)树的度：树内各结点的度的最大值。
5.)孩子和双亲：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲（双亲是一个结点，而不是两个结点！）
5.)兄弟：同一个双亲的孩子之间互称为兄弟。
6.)祖先：从根到该结点所经分支上的所有结点。
7.)子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。
8.)堂兄弟：其双亲在同一层的结点互为堂兄弟。
9.)有序/无序树：如果将树中结点的各子树看成是从左到右有次序的（不能互换），则称该树为有序树，否则为无序树。
10.)森林：森林是m颗互不相交的树的集合。
11.)二叉树：每个结点至多只有二颗子树的有序树。
12.)满二叉树：深度为k且有2的k次方-1个结点的二叉树（具备所有可能的结点）。
13.)完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时

    ，称之为完全二叉树

2. 树的高度（或深度）：
   就是树中结点的最大层次（树最高一层的层次）。
   有两种情况。假设树总共有三层，
       若设根的层次为0，则高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....+P*n.
     叶子结点数=总结点数-叶子结点数。
     例见《全国计算机等级考试应试指导及模拟试题集四级》P63 例8
4. 二叉树：
   1.)定义：二叉树是每个结点至多只有二颗子树的有序树。
   2.)二叉树的性质（设根的层次为1）
    （1）第i层上最多有2的(i-1)次方个结点。
    （2）若二叉树的高度为h，则二叉树最多有2的h次方-1个结点，此时二叉树即为满二叉数。
    （3）对任意一颗二叉树，如果其叶子结点（度为0）的结点数为n0，度为2的结点树为n2，则n0=n2+1
     例见《全国计算机等级考试应试指导及模拟试题集四级》P68 13，23，33，46，81，83。
5 完全二叉树：
   1.)定义：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时    

      ，称之为完全二叉树。
   2.)性质：
     ===>若将最高一层除去，则剩下的二叉树为满二叉树。(若深度为k有n个结点，则n>2的(k-1)次方-1）
     ===>叶子结点只可能出现在层次最大的两层上。
     ===>具有n个结点的完全二叉树的深度为[Log2 n]+1
     ===>对n个结点的完全二叉树编号，则对任一结点i有
         --->结点i的双亲是[i/2] （i>1）
         --->结点i的左孩子是结点2i (2i≤n）
         --->结点i的右孩子是结点2i+1 (2i+1≤n）
6. 树的特性
===>二叉树的度不一定为2；
===>根据同一颗二叉树的两种遍历顺序，可唯一地确定一颗二叉树（也可以得到用另一种遍历方法得到的遍历序列）
===>二叉树的三种遍历方法所得到的遍历序列中，所有叶子结点之间的相对顺序不变。
7. 二叉树的存储
   1.)分为数组存储和链表存储
   2.)顺序存储--数组表示法：采用一组连续存储空间存储二叉树结点中的数据元素。
     仅适用于完全二叉树，当用于存储一般二叉树时，一个主要的问题是空间利用率低。
   3.)链表表示法：链表比较适合存储一般的二叉树；通常将树中的每一个元素用一个结点表示，结点一般包括三个域，即元

素的数值，指向其左孩子结点的指针和指向其右孩子结点的指针，称为二叉链表。
   4.)三叉链表：在二叉链表的基础上，加上一个指向结点的双亲的指针，这样就可以方便的找到一个结点的父结点。
8. 树的遍历
1.)四种方法：先根（序）遍历，中根（序）遍历，后根（序）遍历，层次遍历。
2.)遍历二叉树所得到的遍历序列中：
  --->三种遍历序列中，叶子结点的相对顺序相同。 参见《全国计算机等级考试应试指导及模拟试       题集四级》P64例18
  --->先根遍历序列：根结点+左子树结点群+右子树结点群
      中根遍历序列：左子树结点群+根结点+右子树结点群
      后根遍历序列：左子树结点群+右子树结点群+根结点
      例见《全国计算机等级考试应试指导及模拟试题集四级》P65 例18 P82 140
  --->由任意二种遍历序列可唯一确定一颗二叉树  P77 86，89，141
3.)二叉排序树的中根遍历得到一个递增序列。
4.)层次遍历：从二叉树的第一层（根结点）开始，自上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
            在进行层次遍历时，对一层结点访问完后，再按照它们的访问顺序对各个结点的左孩子和右孩子顺序访问。
9. 线索二叉树：对二叉树以某种方式遍历后，得到二叉树中所有结点的一个线性序列。这样，二叉树中的结点就有了唯一直接

   前驱结点和唯一直接后继结点。
   在线索二叉树时，二叉树采用二叉链表作为存储结构，每个结点有五个域leftChild,leftTag,data,rightTag,rightChild
   规定：如果某结点的左指针域为空，令其指向依某种方式遍历时所得到的该结点的前驱结点，否则指向左孩子。
         如果某结点的右指针域为空，令其指向依某种方式遍历时所得到的该结点的后继结点，否则指向右孩子（？？）
   为了区分一个结点的指针是指向左右孩子还是指向前驱，后继结点，可用标志为来区分：
   如果 leftTag/rightTag=0,那么指向左/右孩子。
   如果 leftTag/rightTag=1,那么指向前驱/后继线索。
   对一颗二叉树的遍历方法不同，得到的线索二叉树也不同。通常有前序线索二叉树，中序线索二叉树，后序线索二叉树。
10.哈夫曼树
   1.)路径：在一颗二叉树中由根结点到某个结点所经过的分支序列叫做由根结点到这个结点的路径。
   2.)路径的长度：由根结点到某个结点所经过的分支数称为由根结点到该结点的路径长度。
   3.)二叉树的路径长度：由根结点到所有叶结点（！！）的路径长度之和称为该二叉树的路径长度。！！
   4.)二叉树的带权路径长度：设一颗具有n个带权值叶结点（！！）的二叉树，从根结点到各个叶结点（！！）的路径长度与

      对应叶结点权值的乘积之和叫做二叉树的带权路径长度WPL！！！
   5.)哈夫曼树（最优二叉树）：对于一组确定权值的叶结点，可以构造出多重不同形态的二叉树，它们的带权路径长度也不 

    同 ，把其中带权路径长度最小的二叉树称为最优二叉树，也叫哈夫曼树！！！！
   6.)构造哈夫曼树：要使一颗二叉树的WPL最小，显然必须使权值越大的叶结点越靠近根结点。
      构造哈夫曼树的方法是：
      ===>将给定的n个权值看做是n颗只有一个结点的二叉树，就构成了森林F
      ===>在森林F中选两颗根结点（！！）的权值最小的二叉树Ti,Tj，分别作为左子树，右子树构造一棵新的二叉树Tk，置 

    Tk的根结点的劝止为（Ti根结点的权值+Tj根结点的权值）
      ===>在F中删去二叉树Ti,Tj，将新的Tk加入森林F
      ===>重复步骤（2），（3）直到F中仅剩下一颗树为止。
11. 树,森林和二叉树的转换
   1.)树---->二叉树
     由于二叉树是有序的，所以约定树中每一个结点的孩子结点按从左到右的次序顺序编号。
     树---->二叉树：连线--删线----美化
     ===>连线：树中所有相邻兄弟连线
     ===>删线：对每个结点，只保留它与第一个孩子结点之间的连线。
     ===>美化
    由这个转化过程可知：
    树中任意一个结点P的第一个孩子结点---->二叉树中结点P的左孩子结点
    树中任意一个结点P的第一个右兄弟----->二叉树中结点P的右孩子结点
    树转化成的二叉树根结点没有右子树（因为原树的根结点不可能有兄弟，所以转化后根结点也不可能有右子树，这一个性

质在森林转化为一颗二叉树的过程中得到了体现）

   2.)森林--->二叉树
    （1）森林中的每颗树---->二叉树
    （2）从第二颗二叉树开始，依次把当前的二叉树作为前一颗二叉树结点的右子树
     森林转化成的二叉树是有右子树的。
   3.)二叉树---->树/森林
    （1）连线：P是F的左孩子，那么把P沿右分支找到的所有结点和F连起来
    （2）删线：删除二叉树中所有结点和其右孩子结点之间的连线
    （3）美化
     照这个步骤转化，如果原二叉树有右子树，则会转化为森林，如果没有，则会转化为树。

七 图
图的邻接矩阵：
若图中没有结点到自己的边，那么对角线上全是0；
若为无向图，则邻接矩阵关于对角线对称：A[i,j]和A[j,i]都是表示结点Vi,Vj之间的边。
若为有向图，则邻接矩阵通常不对称，A[i,j]是由Vi到Vj的边，A[j,i]是Vj到Vi的边。

图的遍历：深度遍历和广度遍历
    深度优先遍历DFS：深度遍历是从图中的任一个结点V1出发，访问V1的一个邻接点V2，再访问V2的邻接点V3，再访问V3的邻

接点V4.....直到访问到Vn，而Vn的所有邻接点都已被访问过了，这时开始回溯，访问V（n-1)结点的未被访问过的邻接点，如

果V(n-1)的邻接点都已被访问过了，则回溯到V(n-2)结点，访问它的邻接点......（！！？？？？）
    广度优先遍历BFS：略

最短路径：略（？？？？）

例见《全国计算机等级考试应试指导及模拟试题集四级》P60例4

八 排序
1. 稳定和不稳定的排序方法
   排序可以按照主关键字来排，也可以按次关键字来排
   如果按次关键字来排序，且关键字Ki=Kj，且排序前记录Ri领先于Rj，那么如果在排序后的序列中Ri还是领先于Rj，那么称

所用的排序方法是稳定的；反之，若可能（！！）使排序后的序列中Rj领先于Ri，那么称排序方法是不稳定的。
2. 内部排序和外部排序
   根据待排序的记录数量和排序过程中涉及的存储器的不同，可将排序方法分为两大类：
   内部排序：待排序记录存放在计算机随机存储器中进行的排序
   外部排序：因为待排序的记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。
3. 内部排序：
   1.)分类：按照排序过程依照的原则可分为：插入排序，交换排序，选择排序，归并排序和基数排序。
   2.)排序操作：在排序过程中需进行以下两种基本操作
    （1）比较两个关键字的大小。
    （2）将记录从一个位置移动到另一个位置。
   3.)插入排序：有直接插入排序，折半插入排序，2-路插入排序，表插入排序等。
    （1）直接插入排序：排序思想是将一个记录插入到已排好序的有序表中，得到一个新的有序表。
         空间复杂度：需要一个记录的辅助空间；
         时间复杂度：O（n*n);
     (2) 折半插入排序：由于直接插入排序的基本操作是在一个有序表中进行查找和插入，因此，这个“查找”可以用“折半

         查找”来实现，由此进行的插入排序称之为折半插入排序。
         空间复杂度和时间复杂度不变。
    （3）2-路插入排序：参见课本P267；
    （4）表插入排序：参见课本P268
   4.)希尔（Shell）排序：由直接插入算法改进而来；
    （1）排序思想：先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”

         时，再对全体记录进行一次直接插入排序。
    （2）优点：对子序列进行直接插入排序使整个序列“基本有序”后，只要做记录的少量比较和移动即可完成排序，因此降

         低了时间复杂度
    （3）希尔排序的分析是一个复杂的问题，究竟时间复杂度为多少还没有一个定论。
   5.)快速（交换）排序：借助“交换”进行排序的方法。
    （1）冒泡排序：
         排序思想：将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过了n-1次比较后，将确定 

                   出最大（或最小）元素的位置，称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。
         时间复杂度：O（n*n)
    （2）快速排序：
         排序思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小

                  ，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
         一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别low和high，设枢轴记录（任选一个关键字，

                                  通常可选第一个记录）的关键字为pivotkey，则首先从high所指位置起向前搜索找到第 

                                 一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索 

      ，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换重复这两步直到low=high  

     位置。这是一趟排序。接着对这两个部分重复这样排序（要用到递归算法）
         注意，在一趟排序过程中，pivotkey是始终不变的。
    6.)选择排序：
     （1）简单选择排序：一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录 

        ，并和第i个记录交换。
          简单选择排序所需进行记录移动的操作次数比较少，最小伪，最大为3(n-1)
          无论记录的初始排列如何，所需进行的关键字的比较次数相同，均为n(n-1)/2;
          时间复杂度为O(n*n);
     （2）树形选择排序：选择排序的主要操作是进行关键字之间的比较，因此改进简单选择排序应该从如何减少“比较”出 

          发考虑。
          树形选择排序的思想：首先对n个记录的关键字两两比较，然后在其中[n/2]个较小者之间再两两比较，如此重复， 

          直到选出最小关键字的记录为止。
          时间复杂度：O（n*log2 n)
          缺点：需要较多辅助存储空间，进行多余的比较等。
     （3）堆排序（Heap Sort)
          堆的定义：n个元素的序列,当且仅当满足下面关系时，称为堆。
             ki≤k2i && ki≤k(2i+1)
           或ki≥k2i && ki≥k(2i+1)
          若将和此序列对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大 

          于（或不小于）其左右孩子结点的值。，由此，若序列是堆，那么堆顶元素（完全二叉树

          的根）必为序列中n个元素的最小值（或最大值）。
          若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重右建成一个堆，则得到n个元素中的次小值，如此反复执 

          行，便能得到一个有序序列，这个过程称为堆排序。
          堆排序对记录数较大的文件比较有效。
    7.)归并排序：“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表，
      排序思想：将初始序列看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序

     子序列，再两两归并.....如此重复，直至得到一个长度为n的有序序列为。这种排序方法称为2-路归并排序。
      2-路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
      归并排序的最大特点是：它是一种稳定的排序方法。
    8.)基数排序：实现基数排序不需要进行记录关键字之间的比较。
      基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法

原文转自：http://www.ltesting.net