数据结构的一些复习点

数据结构知识点总结


概论
1：数据的结构直接影响算法的选择和效力。
2：数据->数据元素（元素，结点，记录）数据的基本单位->数据项（字段，域）数据不可分割的最小单位
3：数据类型：原子数据类型：值不可分（整型，字符型，实型）和结构数据类型：值可分解（数组类型，结构类型）用户自己定义的
4：数据结构：逻辑结构，物理结构：存储结构（数据结构在计算机中的表示），运算特点。
逻辑结构：集合，线性结构（1对1），树型结构（1对多），图状结构（多对多）
运算：插入，删除，查找，排序。
数据结构定义：按某种逻辑关系组织起来的1批数据，利用计算机语言，按1定的存储表示方法把它们存储在
计算机的存储器中，并在这些数据上定义了1个运算的集合。
数据的4种基本存储方法：
顺序存储方法：逻辑上相邻的节点存储在物理位置相邻的存储单位中，结点之间的逻辑关系由存储单元的邻接关系来体现。
该方法主要利用于线性的数据结构。
链接存储方法：不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针来表示的。
索引存储方法：存储结点信息的同时，建立附加的索引表。索引表中的每项称为索引项。索引项的1般情势：（关键字，地址）
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
例子：线性结构+顺序存储方法+栈=顺序栈，线性结构+链接存储方法+队列=链队列。
5：算法特性：有穷性，肯定性，可行性，输入，输出。
6：算法好坏的判断根据：正确性，硬朗性，可读性，履行耗费时间，履行耗费空间。
7：经常使用函数关系排序：c < log2n 8：算法是通过数据结构求解问题的步骤，程序是用数据类型描写的算法。
9：数据结构：
基础数据结构：
线性结构：线性表，栈，队列，串
非线性结构：数组，广义表，树，2叉树，图
利用数据结构：查找，内部排序，外部排序，文件。


线性表
1：线性表特点：
有且只有1个“第1元素”
有且只有1个“最后元素”
除第1个元素以外，其他元素都有唯1的直接前趋
除最后元素以外，其他元素都有唯1的直接后继
2：线性表的基本操作：初始化，清除，求表长，插入数据，删除数据，
取得后继结点，取得前趋结点，取得位置i的节点，定位（按值查找）
在插入数据，删除数据，定位中平均移动比较次数是n/2，这3个操作的时间复杂度是O（n）。
3：线性表的存储结构用数组来实现
4：顺序表：顺序存储结构的线性表
特点：元素在计算机内部存储的物理位置相邻来表示线性表中数据元素之间的逻辑相邻关系。
1段连续的内存空间来保存线性表结点的值。
5：在顺序存储中，能够方便的查找指定位置的结点值，但是，插入和删除结点比较麻烦。
5：链表：链式存储结构的线性表
6：单链表：1个结点只包括1个指针域，1个结点结构=数据域+指针域。指针域保存地址信息。
用单链表来表示线性表时，结点之间的逻辑关系是由结点中的指针来唆使的。
7：为了方便判断空表，插入和删除结点，我们在单链表的第1个结点前面加上1个头结点。
单链表的头指针L指向头结点，如果L->next=null,表示链表为空表。
8：单链表中，任何两个结点的存储位置之间没有固定的联系，要寻觅某1个结点，必须从头指针动身，
   1个1个结点地向后寻觅。
9：线性表的链式存储方式利用不连续的内存空间来保存结点的信息，因此，在结点中，不但需要保存结点
本身的数据值，还需要利用指针域保存指向直接后继的指针。
10：单链表的操作：清除链表，求表长，定位查找，插入数据，删除数据时间复杂度为O（n）
11：在链式存储中，插入或删除结点不需要大量的移动结点；但是在定位时，却需要遍历全部链表。
12：单循环链表：如果把单链表的最后1个节点的指针域指向第1个结点（头结点）。则构成1个首尾相连的循环链表。
13：循环链表中判断1个链表是不是为空，需要看头结点的next域是不是等于本身。
14：循环链表建立和判断的时间复杂度为O（1），插入和删除的时间复杂度为O（n）
15：双向链表：两个指针域，1个指向直接前趋，1个指向直接后继。
16：双向链表中结点的特点，结点的next的prior是结点本身，结点的prior的next是结点本身。
17：判断双向链表为空表：看是不是两个指针域都为NULL。
18：双向链表的建立和判断时间复杂度为O（1），插入和删除的时间复杂度为O（n）
19：双向循环链表：双向链表中的头结点和尾结点连接起来。
20：判断双向循环链表为空表：看是不是两个指针域都指向本身。
21：线性表顺序存储与链式存储的比较
时间角度：当线性表的操作操作主要是进行查找，而很少进行插入和删除时，应当采取顺序表进行存储
当对频繁的插入和删除操作的线性表，则应当采取链表作为为存储结构
空间角度：顺序表的存储空间是静态分配的，在程序引入前必须规定其存储闺蜜，如果估计过大，会造成空间的浪费。估计太小，会造成空间的溢出。
动态链表是动态分配的，只要内存空间有空闲，就不会产生溢出。
线性表的长度变化比较大时，应当采取动态链表为存储结构。
22：顺序表是采取数组实现的，链表是采取指针（动态链表）或游标（静态链表）来实现的。


栈和队列
1：栈和队列：操作受限的线性表，称为限定性的线性表结构。
2：栈：仅允许在1端进行插入和删除运算线性表。落后先出（LIFO）线性表
栈顶：允许进行插入和删除的那1端。
栈底：不可以进行插入和删除的那1端（线性表的表头）
进栈，入栈，压栈：在1个栈中插入新元素，成为新的栈顶元素
出站，退栈：在1个栈中删除1个元素，删除栈顶元素，使下1个成为新的栈顶元素。
3：栈的基本操作：构造空栈，清除所有元素，判断栈是不是为空，返回栈顶元素，入栈，出栈。
4：根据存储结构：顺序栈，链栈
顺序栈：利用地址连续的存储单元顺次寄存从栈底到栈顶的数组元素，数组0位置的元素作为栈底元素
top=⑴，表示栈空；top=maxsize⑴，表示栈满，就相当于1维数组
在做入栈操作前，首先要判定栈是不是满（满了叫上溢）；入栈指针top先加1，然后入栈。
在做出栈操作前，先要判定栈是不是为空（空的为下溢）；出栈指针top先减1，然后出栈（指针+1）。
链栈：相当于结点构成的单链表。
栈顶元素为单链表的第1个结点，由于栈顶元素操作频繁，所以常常用没有头结点的单链表。
链栈是动态分配结点空间的，所以操作时无需斟酌上溢问题。
链栈的优点：可以使多个栈同享空间；在栈中元素变化的数量较大，且存在多个栈的情况下，链栈是栈的首选存储方式。
5：栈的利用：数值进制转换，括号匹配问题，子程序的调用，递归实现
6：队列：限定在表的1段进行插入而在另外一端进行删除的线性表。先进先出线性表（FIFO）
队头：允许删除的1端
队尾：允许插入的1端
入队：向队列中插入新元素，成为新的队尾元素
出队：从队列中删除元素，其后继元素成为新的队头元素。
7：队列的基本操作：构造空队列，判断队列为空，求队列长度，返回队头元素，插入队尾元素，删除队头元素，清除队列元素。
8：根据存储结构：链队列，顺序队列
链队列：限制仅在表头进行删除和在表尾进行插入的单链表。具有两个指针（头指针，尾指针）
头指针指向头结点，队尾指针指向真实的队尾元素结点。
判断链队列为空：头指针和尾指针全部指向头结点。
入队：先将尾指针指向的元素的指针指向入队元素，然后尾指针指向入队元素。
出队：修改头指针中的指针，指向后继结点，但是当删除的元素是最后1个元素时，尾指针需要指向回头结点。
顺序队列：用1组地址连续的存储单元顺次寄存从队列头到队列尾的元素。
这里除定义1维数组还需要两个指针指向队头和队尾。
初始化空队列：front=rear=0；
入队：元素插入到rear所指向的空单元内，rear+1；
出队：删除数组头结点，front+1
在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下1个位置。
假溢出：当产生了若干次出队入队操作后，尾指针到了最后，没法插入了，但是队列元素<队列的单元数。
避免假溢出现象：使用循环队列。
循环队列：数组大小maxsize，数组所表示的循环队列最多允许有maxsize⑴个结点，rear所指的单元始终为空。
循环队列队满条件：(rear+1)%maxsize==front
循环队列队空条件：rear==front
9：队列的利用：打印杨辉3角，迷宫问题。
10：递归：如果1个函数直接调用自己或通过1系列调用间接地调用自己。
直接递归：在函数体内直接调用本身
间接调用：1个函数通过调用其他函数并由其他函数反过来又调用该函数
11:用到递归方法的情况：
第1种情况：定义是递归的。比如阶乘，Fibonacci数列
第2种情况：数据结构时递归的。比如链表就是1种递归的数据结构
第3种情况：有些问题本身没有明显的递归结构，但用递归方法求解更简单。
12：递归消除：由于递归程序运行时要花费较多的时间和空间，效力较低，有时需要消去1个程序中最常常履行部份的递归调用。
经常使用的是用迭代和栈进行递归消除。

串
1：串（字符串）：是1种特殊的线性表，它的每一个节点仅由1个字符组成。通经常使用双引号把串中字符括起来。
2：空串：长度为0的串
3：空格串：串中都是空格字符，它有长度。
4：子串：串中任意个连续字符组成的子序列。
5：串：串变量（值可以改变），串常量（只能被援用不能改变其值）
6：顺序串：串的顺序存储结构，用1组地址连续的存储单元来顺次寄存串中的字符序列。字符数组表示。
串结束标志：1般使用“\0”来肯定串是不是结束。也能够把串长度放在ch[0]中。
基本操作：求串长，串复制，串联接，求子串，串删除。
缺点：事前定义了串长，这在程序运行前是很难估计的
定义了串的最大长度，串值空间被肯定，是静态的，插入，连接操作被限制。
7：串的堆存储结构：仍然是1组空间足够大的，地址连续的存储单元寄存串值字符序列，不同的是
存储空间的大小不是预先定义的，而是在程序履行进程中动态分配的。
指向字符串存储空间的是字符指针而非数组，若为空串，则指针为null。
8：链串：串的链式存储结构：每一个结点仅存储1个字符。便于插入和删除。
9：块链：由于链串每一个结点的指针域所占空间比字符域大，存储空间利用率低，
所以在链串的每一个结点寄存多个字符，这样的结点叫做块。块的大小就是结点所容纳字符的个数。
当结点大小大于1时，串的长度不1定正好是结点大小的整数倍，因此用特殊字符“#”填充。
10：串的模式匹配：子串定位操作。
两种方法：n是主串长度，m是模式串长度
第1种：时间复杂度O（mn）
KMP算法：时间复杂度O（m+n）

多维数组和广义表
1：多维数组和广义表：非线性结构。
逻辑结构：每一个数据元素可能有多个直接前趋和多个直接后继。
2：数组只有两种基本运算————读和写
读：给定1组下标，读出相应的元素
写：给定1组下标，修改相应的元素
3：数组的存储结构：1般取数组的开始地址作为基准，然后考察其他元素相对此基准的偏移量。因此基准加上该数组元素的偏移量就是该元素的绝对地址。
由于内存是1段连续的1维存储空间，其实不是1个多维的存储空间，因此多维数组中的数据要存储在内存汇总，需要依照1定
的顺序存储在1维空间中。
4：矩阵的紧缩存储：矩阵中有很多值相同的元素或零值元素，为了节省存储空间，需要对他们进行紧缩存储。
对称矩阵，3角矩阵（上3角或下3角是常数），对角矩阵（除主对角线和主对角线相邻两侧的若干条对角线的元素以外，其余元素皆为0）
5：稀疏矩阵：
3元组表：根据原矩阵上非零元素的行号，列号和值来作为3元组中的1个值。
6：广义表：又称为列表，它是线性表的推行。就是放宽了线性表元素是原子项这个限制。允许他们具有本身独立的类型结构。
广义表可以表示为：LS=(a1...ai...an)。LS是广义表的名字，n是广义表的长度，若ai本身就是广义表，则称为它是LS的子表。
空表：不包括任何元素的广义表。
用大写字母表示广义表，小写字母表示原子。
若广义表非空，则a1称为LS的表头，其余元素组成的表(a2...ai...an)称为LS的表尾。明显，表尾1定是子表，表头可以是原子也能够是子表。
广义表结构：广义表是递归定义的。
不斟酌广义表内部的结构，广义表就是1个线性表，反之，线性表就是1个不含子表的广义表。
广义表的深度：该表展开后所含括号的层数。
7：特殊广义表：
（）：长度为0的空表，对其不能求表头和表尾的运算。
（（））：长度为1的非空表，对其进行分解，得到的表头和表尾均是空表。
8：纯表：广义表可以与树对应，没有同享和递归的成份
9：再入表：广义表中的元素存在同享。
10：递归表：广义表中有自己。有递归。
11：广义表独有的运算：取表头和表尾。
在广义表中取某个元素，需要将该元素所在的子表逐渐分离出来，直到所求的元素成为某个子表的表头，再用取表头运算取出。
总的来讲最后1步肯定是取表头。

树和2叉树
1：树是n个结点的有限集T，当n=0时，称为空树，当n>0时，满足以下条件
有且只有1个称为树根的结点
当n>1时，除树根结点之外的其余n⑴个结点可以划分为m个互不相交的有限集，每个集合本身又是1个数。
2：树的特点：
树中有且只有1个结点为树根的结点
树中各子树是互不相交的集合。
3：相干概念：结点的度（结点具有子树的数目）
4：树的基本操作：初始化，求树根，创建1颗树，求双亲结点，求孩子结点， 插入子树，删除子树，树的遍历，清除树，判断树空。
5：2叉树：由n个结点的有限集构成，此集合可能为空集，也可能由1个根结点及两颗互不相交的左，右子树组成，并且左，右子树都是2叉树。
6：2叉树的特点：
2叉树有且唯一1个结点被称为树根的结点
当n>1时，每一个结点最多有两颗子树（即2叉树不存在度大于2的结点）
2叉树的子树有左，右之分，且其次序不能任意颠倒，它是有序树。
7：2叉树的基本操作：基本和树1样，但是在求孩子结点的时候，有左孩子和右孩子之分。
8：满2叉树：1颗深度为k且有2^k⑴个结点的2叉树。
9：完全2叉树：深度为k，有n个结点的2叉树当且仅当其每个结点都与深度为k的满2叉树逐一对应。
特点：
叶子结点只可能在层次最大的两层上出现
对任1结点，若其右分支下子孙最大层次为p，则左分支下子孙的最大层次为p或p+1
10：满2叉树必为完全2叉树，完全2叉树不1定是满2叉树。
11：2叉树的性质：
在2叉树的第i层最多有2^(i⑴)个结点。
深度为k的2叉树最多有2^k⑴个结点。
对任意1颗2叉树BT，如果其叶子结点树为n0，度为2的结点数为n2，则n0=n2+1
推倒进程：n=n0+n1+n2，n=1+n1+2n2
对n个结点的完全2叉树的深度为logN+1，logN取下限，表示不大于logN的最大整数
对具有n个结点的完全2叉树，如果对其结点按层次编号，则对任1结点i，有
如果i=1，则结点i是2叉树的树根，无双亲；如果i>1,则其双亲是i/2取下限
如果2i>n，则结点i无左孩子；如果2i<=n，则其左孩子是2i；
如果2i+1>n，则结点i无右孩子;如果2i+1<=n,则其右孩子是2i+1。
12：2叉树的顺序存储：用1组连续的存储单元来存储2叉树的数据元素。
在存储的时候，对普通2叉树必须修补成完全2叉树进行存储，这也造成了存储空间的浪费。这是顺序存储的最大缺点。
13：2叉树的链式存储：2叉树的结点应由1个数据元素和分别指向其左，右子树的各个分支构成。
因此2叉树的链表中的结点包括3个域：数据域和指向左，右子树的指针域。称为2叉链表。
14：使用链式存储结构来存储2叉树比使用顺序结构存储2叉树更加方便，也更容易反应结点之间的逻辑关系。
15：2叉树的遍历：
先根遍历2叉树：根节点-左子树-右子树
中根遍历2叉树：左子树-根结点-右子树
后根遍历2叉树：左子树-右子树-根结点
16：线索2叉树：加上了指针“线索”的2叉链表组成的2叉树:目的是为了加速遍历进程和充分利用存储空间
线索：在有n个结点的2叉链表中有2n个指针域，但只要n⑴个指针域用来寄存左右指针，其余n+1个指针域均为空。
因此用这n+1个空指针域来寄存遍历进程中的前趋和后继的指针。
规定：
若结点有左子树，则lchild指向左孩子，否则ltag=1，lchild指向直接前趋结点。
若结点有右子树，则rchild指向右孩子，否则rtag=1，rchild指向直接后继结点。
17：线索化：实质是在2叉链表的空链域中填写相应结点在1定遍历次序下的前趋和后继的地址。而这个地址只能在动态的遍历进程中才能得到。
18：在中跟遍历中：
在线索树中查找前趋结点：当ltag=1，lchild就是其前趋结点；当ltag=0时，lchild就是其左子树右链下最后1个结点。
在线索数中查找后继结点：当rtag=1，rchild就是其后继结点；当rtag=0时，rchild就是其右子树左链下最后1个结点。
19：树的存储结构
双亲表示法：用1组连续的存储空间（数组）来存储树中的结点，每一个数组元素不但包括结点本身的信息，
还保存双亲结点的下标号。
好处：查找某个结点的双亲容易
坏处：查找某个结点的孩子结点很困难。
孩子链表表示法：把每一个结点的孩子结点排列起来，构成1个单链表（孩子链表）。
然后将这样的将n个这样的数据元素放在1组连续的存储空间中。
好处：容易求得1个结点的孩子结点。
坏处：求得1个结点的双亲结点就很困难。
孩子兄弟链表表示法：链表中的结点有两个链域，分别指向第1个孩子结点和下1个（右）兄弟结点。
好处：容易实现数的任何操作，在结点上加上双亲域，可以方便双亲的查找。
20：树，森林和2叉树之间的转换
由于树的孩子兄弟链表示法和2叉树的2叉链表表示法完全1样，所以之间很容易实现相互转换
树转换成2叉树：
-加线：在树中所有相邻的兄弟之间加1条线。
-抹线：对树中每一个结点，除其左孩子外抹去该结点与其余孩子之间的连线。
-整理：以树的根结点为轴心，将整树按顺时针旋转45度。
可以证明，树转换所构成的2叉树是唯1的。
转换成的2叉树中，左分支上的各结点在原来的树中是父子关系，右分枝上的各结点在原来的树中是兄弟关系。
森林转换成2叉树：
-将森林中的每棵树转换成相应的2叉树
-第1课树不动，从第2课树开始，顺次把后1颗2叉树的根结点作为前1颗2叉树根的右子树。
树转换成2叉树根结点没有右子树，森林转换成2叉树，根结点有右子树。
2叉树转换成树：
-加线：若某结点是其双亲的左孩子，则把该结点右链上所有的结点都与该结点的双亲结点用线连接起来。
-抹线：抹掉原2叉树中所以双亲结点与其左孩子右链上所有结点的连线。
-整理
能够转换成树的2叉树1定没有右子树
2叉树转换成森林：
-将2叉树中根结点与其右孩子连接，及沿右分支搜索到的所以右孩子间连线全部抹掉，使之成为孤立的2叉树。
-将孤立的2叉树还原成树。
21：树的遍历
先根遍历：
访问根结点
从左到右，顺次先根遍历根结点的每颗树。
后根遍历
从左到右，顺次后根遍历根结点的每颗树
访问根结点。
层次遍历
若树非空，则遍历方法是先访问第1层上的结点，然后顺次遍历第2层到第n层的结点。
22：森林的遍历
先根遍历：
访问森林中第1颗树的根结点
先根遍历第1棵树的根结点的子树森林
先根遍历除去第1颗树以后剩余的树构成的森林。
中根遍历：
中根遍历森林中第1颗树的根结点的子树森林
访问第1颗树的根结点
中根遍历除去第1颗树以后剩余的树构成的森林
后根遍历：
后根遍历森林中第1颗树的根结点的子树森林
后根遍历除去第1课树以后剩余的树构成的森林
访问第1颗树的根结点
23：森林的先根遍历，中根遍历和后根遍历相对转换成的2叉树的先根遍历，中根遍历和后根遍历相对应
24：树的先根遍历，后根遍历分别于森林的先根遍历和中根遍历。
25：哈夫曼树（最好判定树）：由n个带权叶子结点构成的所有2叉树中带权路径长度WPL最小的2叉树。
WPL：树的带权路径长度：结点的权值*结点的路径长度，然后所以结点的带权路径长度相加。
树带权路径长度越小越好。
26：前缀编码：任意1个编码不能成为其他任意编码的前缀。利用哈夫曼算法，可以设计出前缀编码
好处：可以减少定长编码的总位数。
27：哈夫曼树中没有长度为1的结点，1颗n个叶子结点的哈夫曼树共有2n⑴个结点。
可以用1个1维数组来表示各个结点，数组中每一个元素包括4个数据项：结点的权值，结点的双亲下标和结点左右孩子。
28：2叉树的1些结论
1颗2叉树的前根序列和中根遍历可肯定1颗2叉树
1颗2叉树的后根序列和中根遍历可肯定1颗2叉树
但是前和后不能肯定。
含有n个结点的2叉树共有1/(n+1)*C(n|2n);和出栈次数1样
任何1颗2叉树的叶子结点在先根，中根和后根遍历序列中的相对次序不产生改变。

图
1：线性表：数据元素之间仅存在线性关系，每一个数据元素只有1个直接前趋和1个直接后继；
树：数据元素之间有着明显的层次关系，且每层上的数据元素可能和下1层中多个元素（孩子）相干联，但只能和上1层
中1个元素相干联；
图形结构：结点之间的关系可以是任意的，图中任意两个数据之间都可能相干，每一个结点都可以有多个直接前趋和多个直接后继。
2：树是图的特殊情况。
3：有向边，无向边（v1,v2）
4：无向完全图：n个顶点的无向图，如果任意两个顶点间都有1条直接边相连。
有n(n⑴)/2条边
5：有向完全图：n个顶点的有向图，如果任意两个顶点间都有方向互为相反的两条边相连
有n(n⑴)条边
6：路径长度：这条路径上边的数目。
8：简单路径：除第1个顶点和最后1个顶点以外，其余顶点都不同的路径
9：简单回路：第1个顶点和最后1个顶点相同的简单路径。
10：相干概念：连通图，连通份量（极大连通子图），强连通图，强连通份量，弱连通图（有向图中，最少有单向通路），弱连通份量。
11：度：顶点所具有的边的数目
    出度：以某顶点为尾的边的数目
    入度：以某顶点为终点的边的数目
    1个顶点的度=出度+入度
12：生成树：连通图的G的1个子图如果是1颗包括G的所以顶点的树，
n个顶点的生成树具有n⑴条边。
13：图的存储结构：邻接矩阵，邻接表，邻接多重表，10字链表
14：若图为权图：若不是E(G)中的边，则这条边的权值a12为0或无穷大。
若图为非权图：如果顶点v1，v2之间无边，则a12=0；
如果顶点v1，v2之间有边，则a12=1。
15：无向图的邻接矩阵是对称的，而有向图的邻接矩阵不1定对称。
 用邻接矩阵表示具有n个顶点的有向图时，要用n^2个单元存储邻接矩阵
 用邻接矩阵表示具有n个顶点的无向图时，只需要存入3角矩阵，只需n(n+1)/2个存储单元。
16：邻接矩阵来表示图，易判定图中任意两个顶点之间是不是有边相连，也易求得各个顶点的度数。
对无向图，邻接矩阵第i行元素之和就是图中第i个顶点的度数。
对有向图，第i行元素之和是顶点i的出度，第i列元素之和是顶点i的入度。
17：邻接矩阵并不是图的顺序存储结构，只是借助了数组这1数据类型来表示图中元素间的相干关系。
18：邻接矩阵的事件复杂度为O（n^2）。
19：邻接表表示法：图的链式存储结构，包括两部份：链表和向量
邻接表：在邻接链表中，对图中每一个顶点vi都建立1个单链表，第i个单链表中的结点表示依附于顶点i的边。
邻接表中的每一个结点由两个域组成：顶点域和链域。
表头结点：数据域和链域。所有表头结点寄存在1个顶点表中。
将无向图的邻接表称为边表，将有向图的邻接表称为出边表。
20：若无向图中有n个顶点，e条边，则邻接链表需n个表头结点和2e个表结点，每一个结点有两个域
对边很少的图，用邻接链表比用邻接矩阵更节省存储单元。
21：逆邻接表：为了计算有向图的入度；邻接表可以计算有向图的出度。
22：邻接表的时间复杂度：O（n+e）
23：当边数较少时，邻接表比较好；当边数较多时，邻接矩阵比较好。
24：邻接矩阵是唯1的，邻接表不是唯1的。
25：图的遍历：深度优先搜索法和广度优先搜索法。
26：深度优先搜索法：类似于树的前序遍历。当访问了1个顶点以后，尽可能向纵深方向去访问下1个未被访问的顶点。
遍历的时间复杂度取决于存储结构
邻接表：O（n+e）
邻接矩阵：O（n^2）
27：广度优先搜索遍历：类似于树的层次遍历
遍历的时间复杂度取决于存储结构
邻接表：O（n+e）
邻接矩阵：O（n^2）
遍历的空间复杂度为O（n），辅助空间是队列和标志数组
28：非连通图的遍历：进行屡次DFS或BFS算法，从某个顶点动身进行遍历，履行1次不能保证访问到所以顶点
为此，需要再选择未被访问的顶点作为出发点，再次履行DFS或BFS。
29：生成树是连通图的极小连通子图：由于n个顶点的连通图最少有n⑴条边，而所以包括n⑴条边及n个顶点的连通图都是无回路的树。
30：生成树：连通图G的1个子图如果是1颗包括G的所有顶点的树。
31：构造最小生成树：
尽量选择权值小的边，但不能构成回路
选取n⑴条恰当的边以连接网的n个顶点
32：构造最小生成树的普里姆（prim）算法，从顶点动身寻觅最短边。
算法的时间复杂度为O（n^2）,比较合适构造稠密图的最小生成树，与边数无关。
33：构造最小生成树的克鲁斯卡尔（kruskal）算法，选取n⑴条最小的边
算法的时间复杂度为O（eloge），与网中数目e相干，合适稀疏图的最小生成树。
34：最短路径：
迪杰斯特拉（dijkstra）：提出1个按路径长度递增的次数产生最短路径的算法。
算法的时间复杂度O（n^2）
弗洛伊德（floyd）：求每对顶点之间你的最短路径
算法的时间复杂度O（n^3），比较合适稠密图，需要求A^n和path^n;
35：AOV网：以顶点表示活动，有向边表示活动之间的前后关系的网
36：拓扑排序：构造AOV网的拓扑有序序列的操作。是定义在有向图上的1种操作。AOV网不应当出现回路。
算法时间复杂度O（n+e）
37：对AOV网进行拓扑排序的步骤是：
在AOV当选取1个入度为0的顶点并输出它
从网中删去该顶点，并且删去从该顶点发出的全部有向边
重复上面两个步骤，直到网中全部顶点均已输出，或当前图中不存在入度为0的顶点位置，后1种情况说明有向图有回路。
38：AOV网的拓扑有序序列不唯1。
39：AOE网：顶点表示子工程（事件），边表示活动，边上的权表示活动所需的时间。
40：关键路径：从开始顶点到结束顶点的最长路径长度。1个AOE网可能有多条关键路径，他们的长度是1样的。
41：最早开始时间：1个时间vk能够产生的最早时间取决于从始点v1到顶点vk的最长路径长度。
42：最迟开始时间：1个时间vk允许的最迟产生时间，应当等于结束顶点事件vn的最早产生时间减去vk到vn的最长路径长度。
43：最迟开始时间-最早开始时间
若为0，则活动为关键活动，否则为非关键活动。
44：关键路径的辨认：为了使AOE网所代表的工程尽快完成，要先辨认关键路径，只有缩短关键路径上的关键活动所需时间才能缩短全部工期。
45：关键活动算法：
对AOE网进行拓扑排序，按拓扑排序的次序求出各顶点事件的最早产生时间ve，若有向图中有回路，则算法结束，否则履行下1步
按拓扑序列的逆序求出各顶点事件的最迟产生时间vl
根据求得的各顶点的ve，vl，求出各活动ai的最早开始时间e(i)和最迟开始时间l(i)，若e(i)=l(i)，则ai为关键活动。
46：不论出度还是入度，顶点的度之和等于图边数的两倍。
47：用邻接表表示图进行广度优先遍历，通常采取队列来实现算法。
48：用邻接表表示图进行深度优先遍历，通常采取栈来实现算法。


查找
1：查找表：同1类型的数据元素（或记录，结点）构成的集合。
2：关键字：数据元素中某个数据项的值，用它可以标识或辨认1个数据元素。
3：查找：给定1个关键字K，在含有n个结点的查找表中找出关键字等于给定值K的结点。
若查找成功，返回结点的信息或该结点在表中的信息。
若查找失败，返回相干的唆使信息。
4：动态查找表：若在查找的同时需要对表进行修改操作（如插入，删除等）。
5：静态查找表：若对表只进行查找操作（查询，检索等）。
6：内查找：如果查询进程都在内存中进行。
7：外查找：如果查询进程需要访问外存。
8：平均查找长度（ASL）：查找进程中对关键字需要履行的平均比较次数。
衡量1个查找算法效力高低的标准。
9：线性表的查找
顺序查找：从表的1端开始，顺序扫描线性表，顺次将扫描到的结点关键字和给定值K相比较。
R[0]作哨兵，从后往前判断
顺序查找的存储结构：适用于线性表的顺序存储结构，也使用也链式存储结构（使用单链表，扫描从表头开始）
顺序查找的平均查找长度：（n+1）/2
顺序查找改进：每当查找成功时，就将找到的结点和后继结点交换，减少查找几率大的结点的比较次数。
顺序查找的优点：算法简单，对表结构无任何要求，不关注关键字是不是有序。
顺序查找的缺点：查找效力低，当n特别大时，不宜用顺序查找。
2分查找（折半查找）：效力较高的查找算法，要求线性表是有序表，并且要用向量作为表的存储结构。
2分查找的基本思想：
首先肯定该区间内的中点位置
然后将待查的K值与中点位置进行比较：若相等，查找成功返回位置；否则肯定新的区间差找
如果中间位置大于k，则新的区间则是左子表
如果中间位置小与K，则新的区间则是右子表
重复上面这个进程，直至找到关键字为K的结点。
2分查找判定树：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。
2分查找成功时的平均查找长度：log（n+1）⑴
2分查找失败时的平均查找长度：log（n+1）取上限
2分查找的平均查找长度：logn
2分查找的优点：查找效力高，但是要排序关键字，最高效的排序需要花费O（nlogn）
2分查找的缺点：只合适顺序存储结构，合适1经建立就很少改动而又常常需要查找的线性表。
分块查找（索引查找）：性能介于顺序查找和2分查找之间
分块查找表的索引结构：
分块有序的线性表：前1块的最大关键字小于后1块的最小关键字
索引表：抽取各块中最大关键字及其起始位置构成1个索引表，索引表是递增有序表。
分块查找的基本思想:
首先查找索引表，可采取2分查找或顺序查找看看结点在哪1块。
然后在已确认的块中进行顺序查找。
分块查找的平均查找长度
2分查找肯定块：log(n/s+1)+s/2
顺序查找肯定块：(s^2+2s+n)/(2s)
s=n取根号
分块查找的优点：在表中插入或删除1个记录时，只要找到该记录所属的块，便可在该块内进行插入和删除运算。
由于块中的记录的寄存是任意的，所以插入或删除的时候不需要移动大量的结点。
分块查找的缺点：增加1个辅助数组的存储空间和将初始表分块排序的运算。
在这3种查找方式中，2分查找效力最高，但是只适用于静态查找表。
10：树表
2叉排序树（2叉查找树）：
若它的左子树非空，则左子树上所有的结点的值小于根结点的值
若它的右子树非空，则右子树上所有的结点的值大于根结点的值
左右子树本身又个数1颗2叉排序树
树排序：2叉排序树的中序遍历是1个有序遍历，平均履行时间O（nlogn）
对相同的实力，树排序是堆排序的2⑶倍，因此在1般情况下构造2叉排序树是为了查找，其实不是为了排序。
2叉排序树的插入：
若2叉排序树为空，则为待插入的关键字申请1个新结点，并令其为根；
若2叉树不为空，则将key和根的关键字比较：
若2者相等，说明树中已有此关键字，不必插入
若key小于根关键字，则插入左子树
若key大于根关键字，则插入右子树
2叉排序树的删除：
p为叶子结点，只需将p的双亲parent中指向p的指针域置为空；
p只有1个孩子，只需将child和p的双亲直接连接就能够，然后删除p；
p有两个孩子，替换p为p右子树下最左侧的点，删除该点。
2叉排序树上的查找：2叉排序树构建不唯1，2分查找树是唯1的
2叉排序树的查找的平均查找长度与2叉树的形态有关
最坏情况查找长度：构成1颗单树，（n+1）/2
最好情况查找长度，构成1颗形态与2分查找树相似的排序树，logn
插入，删除和查找算法的时间复杂度均为O（logn）
2叉排序树和2分查找的比较：
平均时间差不多，
如果有序表是静态查找表，用2分查找
如果有序表是动态查找表，用2叉排序树
平衡2叉树：指树中任1结点的左右子树的高度大致相同，为了保证2叉排序树的高度为logn
满2叉树是完全平衡的，只要2叉树的高度O（logn），可以看成是平衡的。
AVL树中任1结点的左右子树的高度之差的绝对值不超过1
最坏情况下，n个结点的AVL树高度为1.44logn
完全平衡的2叉树高度为log2n，AVL树是接近最优的。
B-树：查询的文件较大，且文件寄存在磁盘等直接存取装备中，为了减少查询进程中对磁盘的读写次数。
特性：
每一个结点最少包括以下数据域(n,p0,k1,p1,k2,...,ki,pi)k表示关键字（关键字序列递增有序），p表示指针
所有叶子结点都在同1层，叶子的层数为树的高度h
每一个非根结点中所含关键字个数j为(m/2⑴)<=j<=m⑴（m为树的阶树）
由于内部结点的度数正好是关键字总数+1，所以每一个非根结点最少有m/2颗子树，最多有m颗子树
高度为n的3阶B-树的结点最少是2^n⑴
1颗高度为h的B-树，任1叶子结点所处的层数为h，当向B-树插入1个新关键字时，为检索插入位置所需读取h个结点。
11：散列表的查询：不同于顺序查找，2分查找，2叉排序树，不以关键字的比较为基本操作，而是采取直接寻址技术。
12：散列的基本思想：以结点的关键字K为自变量，通过1个肯定的函数关系h，计算出对的函数值，然后把这个值解释为结点
的存储地址，将结点存入函数值所指的存储位置上。在查找时，根据要查找的关键字用同1函数计算出地址
再到相应的单元里去取出要找的结点。
13：散列表冲突问题：两个不同的关键字，由于散列函数值相同，因此被映照到同1表位置上。
冲突不可能完全避免。
避免冲突的办法：
关键字的个数小于或等于散列表的长度
选择适合的散列函数
14：装填因子：a=填入的结点n/表长m。a越大，表越满，冲突的机会也越大，通常去a<=1。
15：散列函数的选择：
平方取中法：先通过求关键字的平方值扩大相近数之间的差别，然后根据表长度取中间的几位数作为散列函数值。
除留余数法：最简单经常使用的1种方法。就是用表长m去除关键字，取其余数作为散列地址。m最好取素数。
相乘取整法：
首先用关键字key乘上某个常数A（0 然后用m乘以该小数后取整。
随机函数法：保证随机函数值在0-（m⑴）之间。通常，当关键字长度不等时采取此方法来构造散列函数。
16：处理冲突的方法
开放地址法：冲突产生时，使用某种探查技术在散列表中构成1个探查序列，沿此序列逐一单元查找，直到找到给定的关键字
或碰到1个开放的地址为止。hi=（h（key）+ di）% m  0<=i<=m⑴
装填因子：0.5-0.9
探测序列的方法：
线性探查法：探查序列：hi=（h（key）+ i）% m  0<=i<=m⑴ 即di=i
缺点：堆积现象严重。
2次探查法：跳跃式探查。hi=（h（key）+ i*i）% m  0<=i<=m⑴ 即di=i^2
缺点：可以减少堆积现象，但是不容易探查到全部散列空间。
两重散列法：开放地址法中最好的方法之1。hi=（h（key）+ i * h1（key））% m  0<=i<=m⑴ 即di=i * h1（key）
用了两个散列函数。h1（key）=key%(m⑴)+1
m为素数，则h1（key）取1-（m⑴）之间的任何数均与m互素。
m为2的方幂，则h1（key）取1-（m⑴）之间的任何奇数。
拉链法：将所有关键字为同义词的结点链接到同1个单链表中。
拉链法的优点：
拉链法处理冲突简单，没有堆积现象
拉链法结点空间动态申请，合适造表前没法确认表长的情况
拉链法可以a>=1
删除结点比较容易，直接在链表上删除；而对开放地址表来讲，只能在被删结点上做标记，不能真实的删除结点
拉链法的缺点：
指针需要额外的空间，当结点范围小，与拉链法相比，开放地址发更省空间。
17：性能分析
查找：散列表的平均查找长度比顺序查找，2分查找等完全依赖与关键字比较的查找要小很多。
查找成功ASL：查找次数之和/关键字个数
查找失败ASL：查找不成功时对关键字需要履行的平均比较次数。
直接找关键字到第1个地址上关键字为空的距离便可，初始位置只能是MODn的0-n⑴；
18：总结：
由同1个散列函数，不同的解决冲突方法构造的散列表，其平均查找长度是不同的
散列表的平均查找长度不是结点个数n的函数，而是装填因子a的函数。
顺序查找O（n），其他查找O（logn），散列法查找O（1）

排序：
1：排序方法的稳定性：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些相同的关键字的记录之间的相对次序
保持不变。反之，则是排序方法是不稳定的。
2：内部排序：排序进程中全部文件都在寄存在内存中进行处理的。
1般适用于记录个数不多的小文件
插入排序，选择排序，交换排序，归并排序，基数排序
3：外部排序：排序进程中需要进行数据的内，外存之间的交换。
1般使用于记录个数太多，不能1次性将全部记录放入内存的大文件
4：排序算法的性能评价：
履行算法所需的时间
履行算法所需的辅助空间：O(1)是就地排序，非就地排序1般是O(n)
算法本身的复杂程度
5：不同存储方式的排序进程：顺序表，链表，索引表。
6：插入排序：每次将1个待排序的记录，按其关键字大小插入已排序好的文件中的适当位置，直到全部记录插入完位置
（就像打牌1样，边抓边整理）。
直接插入排序：在排序中，引入哨兵这个概念，作用是：
在进入循环之前，保存了r[i]的副本，使得不致于由于记录后移而丢失r[i]中内容
在while循环中监视下标j是不是越界，1旦越界，直接退出
引入哨兵后使得测试查找循环条件的时间大约减少了1半
算法分析：
时间复杂度：
关键词递增有序（正序）：O（n）
关键词递减有序（反序）：O（n^2）
关键词无序（平均）：O（n^2）
空间复杂度：
辅助空间1个监视哨，O（1），就地排序
直接插入排序是1个稳定的排序
希尔排序：直接插入排序的改进，先取1个小与n的整数d作为第1个增量，把文件分成d组，然后排序，然后减少增量
的值进行排序，最后增量变成1进行排序。
算法分析:
希尔排序的履行时间依赖于增量序列：
最后1个增量必须是1
应当避免序列中的值为倍数
当n较大时，希尔排序比较和移动的次数约为n^1.3
希尔排序时间性能上明显优于直接插入排序
希尔排序是不稳定的。
7：交换排序：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录出现
冒泡排序：从下往上扫描数组，1旦违背轻气泡不能再重气泡之下的原则，就让其调换，直到最后任何两个气泡都是轻者在上，重者在下。
算法分析：
时间复杂度：
关键词递增有序（正序）：O（n）
关键词递减有序（反序）：O（n^2）
关键词无序（平均）：O（n^2）
空间复杂度：
辅助空间1个监视哨，O（1），就地排序
冒泡排序是1个稳定的排序
快速排序(霍尔排序)：采取分治法的思想，将原问题分解成若干个范围更小但结构与原问题相似的子问题，递归解决子问题
然后将这些子问题的解组合为原问题的解。
3个步骤：
分解：在数组中任选1个基准，顺次划分左右两个较小的子区间，最后使得左区间的值<基准值<右区间值
求解；递归对左右区间进行快速排序
组合：求解后已有序了，排序好了，实际上是个空操作。
算法分析：
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需进行k⑴次关键字的比较。
在无序数组当选择划分的基准关键字是决定算法性能的关键。
时间复杂度：
最坏：划分后基准是在最左侧或最右侧O（n^2）
最好：划分基准是中值O（nlogn）
平均：O（nlogn）
空间复杂度：快速排序需要1个栈来实现
最好：O（logn）
最坏：O（n）
快速排序是非稳定的。
8：选择排序：每趟从待排序的记录当选出关键字最小的记录，顺序寄存在已排序好的子文件的后面，直到全部记录排序终了。
直接选择排序：n个记录经过n⑴此直接选择排序得到有序结果
第1趟，在无序区当选择最小的值和第1个元素交换，
第2趟，在2-n当选择最小的值和第2个元素交换。。。
算法分析：
时间复杂度：O（n^2）
空间复杂度：
辅助空间1个监视哨，O（1），就地排序
直接选择排序是不稳定排序。
堆排序：是1树型选择排序，其特点是：在排序进程中，将序列看成是1颗完全2叉树的顺序存储结构，利用完全2叉树
中双亲结点和孩子结点之间的内在关系，在当前无序区当选择关键字最大（或最小）的记录。
堆的定义：n个关键字序列k1，k2，。。。kn称为堆，当且仅当满足以下关系ki<=k2i且ki<=k(2i+1)
或ki>=k2i且ki>=k(2i+1),存储序列可以看作是1颗完全2叉树的存储结构
堆的实质：是满足1下性质的完全2叉树：树中任1非叶结点的关键字均不大于（或不小于）其左右孩子结点的关键字。
大根堆：根结点的关键字是堆里所有结点关键字中最大者
小根堆：根结点的关键字是堆里所有结点关键字中最小者
注意：堆中任意子树也是堆。
堆排序与直接选择排序的区分：在直接选择排序中，会出现重复的比较次数，由于堆排序可以通过树型结构保存
部份比较结果，因此能够减少比较次数。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠