数据结构与算法总结_稀疏图nlogn怎么算出来

一：绪论

表示时间复杂度的阶有：

O(1) ：常量时间阶

O (n)：线性时间阶

O(㏒n) ：对数时间阶

O(n㏒n) ：线性对数时间阶

O (nk)： k≥2 ，k次方时间阶

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指数时间的关系为：

O(2n)<O(n!)<O(nn)

 

算法的空间复杂度定义为:S(n) = O(g(n))

表示随着问题规模 n 的增大，算法运行所需存储量S(n)的增长率与 g(n) 的增长率相同，称S(n)(渐近)空间复杂度。

        

二：线性表

顺序线性表：

设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。

总的平均移动次数： Einsert=∑pi*(n-i+1)  (1≦i≦n)

∴ Einsert=n/2 。

链式线性表：

单链表：

例2.1假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。

算法思想：1、扩大La，将存在于Lb中而不存在于La中的数据元素插入到La中去。2、需要从Lb中依次取得每个数据元素，并依值在La中进行查访，若不存在，则插　之。

例2.3 已知线性表LA和LB中的数据元素是按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素也是按值非递减有序排列。

1.初始化 LC 为空表；

2.分别从 LA和LB中取得当前元素 ai 和 bj；

3.若 ai≤bj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中；

4.重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；

5.将 LA 表或 LB 表中剩余元素复制插入到LC 表中。

（双向）循环链表：

约瑟夫问题：

n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,  报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其          出列，…，如此下去,  直到圆圈中只剩一个人为止。此人即为优胜者。

例如  n = 8   m = 3

 

三：栈和队列

括号匹配的检验：（栈）

假设在表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即：

（［］（））或［（［ ］［ ］）］等为正确的格式，

［（ ］）或（［（ ））或 （（）］)均为不正确的格式。

则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

算法设计：

1）  凡出现左括弧，则进栈；

2）  凡出现右括弧，首先检查栈是否空

若栈空，则表明该“右括弧”多余，

   否则和栈顶元素比较，

     若相匹配，则“左括弧出栈” ，

     否则表明不匹配。

3）表达式检验结束时，

   若栈空，则表明表达式中匹配正确，

   否则表明“左括弧”有余。

 

表达式求值：（栈）

迷宫求解：（栈）

求迷宫路径算法的基本思想是：从入口出发，按某一方向向未走过的前方探索

若当前位置“可通”，则纳入路径，继续前进

若当前位置“不可通”，则后退，换方向继续探索;

若四周“均无通路”，则将当前位置从路径中删除出去。

 

                            算法：

设定当前位置的初值为入口位置；

 do｛

   若当前位置可通，

   则｛将当前位置插入栈顶；

           若该位置是出口位置，则算法结束；           

           否则切换当前位置的东邻方块为

                   新的当前位置；

   ｝

   否则 {

   ｝

｝while (栈不空）；

若栈不空且栈顶位置尚有其他方向未被探索，

则设定新的当前位置为: 沿顺时针方向旋转

            找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，

则｛删去栈顶位置；// 从路径中删去该通道块                  

        若栈不空，则重新测试新的栈顶位置，

        直至找到一个可通的相邻块或出栈至栈空；

｝

若栈空，则表明迷宫没有通路。

 

 

栈的另外一个重要的应用：递归调用

用分治法求解递归问题：

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

三个条件：

1、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的

 

2、可以通过上述转化而使问题简化

 

3、必须有一个明确的递归出口，或称递归的边界

 

分治法求解递归问题算法的一般形式：

     void   p (参数表) {

        if   （递归结束条件）可直接求解步骤；-----基本项

        else  p（较小的参数）；------归纳项

       }

long Fact ( long n ) {

    if ( n == 0) return 1;  //基本项

    else return n * Fact (n-1);  //归纳项}

四：串

 

 简单字符串模式匹配算法（BF算法）：

算法思想：从主串S的第pos个字符起和模式串T的第一个字符比较之，若相等，则继续比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中序号，否则称匹配不成功，函数值为零。

首尾字符串匹配算法：

先比较模式串的第一个字符

再比较模式串的最后一个字符

最后比较模式串中从第二个到第n-1个字符

 

Kmp算法：（难理解）：复杂度o（m+n）

若设目标串(主串)为s，模式串为p ，并设i指针和j指针分别指示目标串和模式串中正待比较的字符，设i和j的初值均为1。若有si=tj，则i和j分别加1。否则，i不变，j退回到j=next[j]的位置，再比较si和tj，若相等，则i和j分别加1。否则，i不变，j再次退回到j=next[j]的位置，依此类推，直至下列两种可能：

      一种是j退到某个next[…]时字符比较相等，则指针各自增1，继续进行匹配；

     另一种是j退到值为零（即模式的第一个字符“失配），则此时需将模式继续向右滑动一个位置，即从主串的一个字符si+1起和模式重新开始匹配。

 

五：数组和广义表：

数组，广义表是线性表的推广；

特殊矩阵：

对称矩阵：

上三角：

下三角：

 

对角矩阵：对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到

一维数组中，且也能找到每个非零元素和向量下标的对应关系。

稀疏矩阵：

稀疏因子：m行n列t个非零元素

 

 

顺序存储：三元组（行数，列数，元素值）

转置：

算法的基本思想：第一次从转置前稀疏矩阵source中取出应该放置到转置后的稀疏矩阵dest中第一个位置的元素，行列号互换后，放于dest中第一个位置；第二次从source中选取应该放到dest中的第二个位置的元素，……，如此进行，依次生成dest中的各元素。

方法一：按m的列序转置

按T.data中三元组次序依次在M.data中找到相应的三元组进行转置，即按照矩阵M的列序来进行置换。

为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序，所以由此得到的恰是T.data中应有的顺序。

方法二：快速转置

按M.data中三元组次序转置，转置结果放入T.data中恰当位置。

此法关键是要预先确定M中每一列第一个非零元在T.data中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。

链式存储：十字链表

 

 

 

广义表：（人工智能）：

广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。

A=()，B=(x, y, z)，C=(B, y, z)，D=(x,(y, z))，E=(x, E)

 

 

六：树与二叉树

二叉树的性质：

1. 在二叉树第i层至多有2^i-1个结点
2. 深度为k的二叉树至多有2^k-1个结点
3. 对于任何一颗二叉树，如果其叶子数为n₀,度为2的结点数为n₂，则n₀=n₂+1
4. 具有n个结点的完全二叉树的深度为(log₂n)+1

满二叉树的定义：

法一：若二叉树中最多只有最下两层有度小于2的结点,且最下层的结点都依次排列在最左边,则称此二叉树为完全二叉树。

法二：深度为k的二叉树,若第1到第k-1层为深度为k-1的满二叉树,第k层的结点都依次排列在最左边,则称此二叉树为完全二叉树。

 

二叉树的存储：

         顺序：适合满二叉树和完全二叉树

         链式：二叉链表，三叉链表

特点：n个结点，有n+1个空指针域

二叉树的遍历：前序遍历，中序遍历，后序遍历（前中后是指根结点）

         实现：递归方法

                            非递归方法：用栈

 

         已知前序遍历和后序遍历不能求出二叉树

 

线索二叉树：

         目的：非线性结构 –> 线性结构

         先序线索二叉树

         中序线索二叉树

         后续线索二叉树

 

树的存储：

         双亲表示法

         孩子表示法

         孩子兄弟表示法（常用）

 

树转二叉树：兄弟相连留长子

         特点：其右子树一定为空

 

二叉树变树：左孩右右连双亲，去掉原来右孩线

 

森林变二叉树：树变二叉根相连

 

二叉树变森林：去掉全部右孩线，孤立二叉再还原

 

树的遍历与二叉树遍历对应的关系：

 

树：先序遍历，后序遍历

森林：先序遍历，中序遍历

二叉树：先序遍历，中序遍历

 

Haffman树与Haffman编码：

         Haffman树最优树：带权路径长度（WPL）最短的树

         Haffman最优二叉树：WPL最短的二叉树

 

         构造Haffman树：7 5 5 2 4

        

         Haffman编码：根据字符出现频率编码，使电文总长度最短

 

         两个问题：

n个结点经n-1次合并，每次生成新的结点，总共 n+n-1=2n-1个结点，度为2的结点个数为n-1

 

没有度为1的结点

 

 

七：图

         无向图边的取值范围：0<=e<=n(n-1)/2

         有向图弧的取值范围：0<=e<=n(n-1)

 

         稀疏图：边数或弧数远少于nlogn

         连通：无向图中，顶点到顶点之间有路径

        

 

         图的生成树：一个连通图（无向图），生成树是一个极小连通子图，有图中全部n个顶点，n-1条边

 

         对于非连通图，每个连通分量可以构造一颗生成树，从而构成森林

         图构成森林:由若干棵有向树组成，会有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

 

         图的存储：邻接矩阵，邻接链表，十字链表，邻接多重表，边表

 

         有向图的邻接矩阵：顶点的度 = 第i行元素之和 + 第j列元素之和

 

         无向树的邻接矩阵：顶点的度 = 第i行的元素 1 的个数

 

                   优点：容易实现图的操作  缺点：空间效率为o（n²）

 

                   邻接表：效率o(n+e)

 

图的遍历：

         深度优先DFS：（Depth_First Search）

                   基本思想：仿树的中序遍历，分连通图和非连通图两类

         广度优先BFS：（Breadth First Search）

                   基本思想：仿树的层次遍历

 

         图的最小生成树

                   生成树的代价：如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价

                   最小生成树MST（Minimun Spanning Tree）:带权连通图中代价最小的生成树

 

                   构造最小生成树的方法：

①   Prim算法（以顶点为对象），时间复杂度o(n²),适合稠密图

②   Kruskal算法（以边为对象），时间复杂度o(eloge),适合稀疏图

注意：最小生成树可能不唯一

         有向无环图及其应用：

                   有向无环图DAG：（Directed Acycling Graph）

                   拓扑排序：

①   在有向图选一个没有前驱的顶点且输出 （入度为0）

②   从图中删除该顶点及它的所有尾

③   重复以上两步

 

AOV网：顶点表示活动的网（Activity On Vertex network）,不允许有回路，弧表示活动之间的优先制约关系

检测AOV中是否存在环：网中所有顶点拓扑有序序列（拓扑序列不是唯一的）

 

 

 

         关键路径：（Critical Path）

AOE网（Activity On Eage network）：顶点表示时间，弧表示活动，权表示活动持续的时间

        

关键活动：该边上的权值增加将使有向图上的最长路径长度增加，l（i）=e（i）

 

找关键路径：必须找到关键活动

①   向前递推

②   向后递推

③   把l(i)=e(i)的路径连起来

 

 

         最短路径（Short Path）：交通网络问题

 

                   分两种：单源点最短路径，所有顶点最短路径

 

                   单源点最短路径：

 

方法一：将源点到终点所有路径列出来，选最短的。缺点：随路径的增多，效率会降低

                            方法二：Dijkstra算法：按路径长度递增次序产生各顶点的最短路径

 

                  每一对顶点间最短路径：

                            方法一：以一个顶点为源点，重复执行Dijkstra算法N次，T(n)=o(n³)

                            方法二：Floyd算法：

思想：逐个顶点试探，从vi到vj的所有可能存在路径中，选出一条长度最短的

                                     实现：

（1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值，否则为∞。

（2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。

（3）所有顶点试探完毕，算法结束。      

 

 

八：查找

静态表查找

平均查找长度ASL：（Average Search Length）：为了确定记录在表中的位置，需要与给定值进行比较关键字的个数的期望值

评价标准：ASL

顺序查找：（顺序或链式）

思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找不成功。

 

折半查找：（顺序）

                   效率比顺序查找高

 

 

动态查找表

存在关键字为key的记录，则返回，否则插入

 

二叉排序树：（二叉查找树）

特点：

        i.   左子树所有节点<根节点

       ii.   右子树所有节点>根节点

       iii.   左右子树分别是二叉排序树

算法：

①   查找

②   插入：插入位置由查找过程得到

③   删除：（分三种情况，定则：保持中序序列不变）

a)   *p为叶子节点，只需修改*P双亲*f的指针

b)   *P只有左子树或右子树

             i.  只有左子树：用*P的左孩子代替*p

             ii.   只有右子树：用*p的右孩子代替*p

c)         *p左右子树非空

      　　 i.     用*P的直接前驱取代*p

     　　  ii.    用*p的直接后继取代*p

       　　iii.    若*p的左子树无右子树，用*p左子树取代*p

 

含有 n 个结点的二叉排序树的平均查找长度和树的形态有关 

最好情况： ASL=log 2(n + 1) – 1;   
             树的深度为：log 2n  + 1;  
             与折半查找中的判定树相同。
           （形态比较均衡）。 

最坏情况：插入的 n 个元素从一开始就有序，

            —— 变成单支树的形态！

            此时树的深度为 n;   ASL = (n + 1) / 2  

             查找效率与顺序查找情况相同。

                  

 

平衡二叉树（AVL树）：

性质：

①   左右子树是平衡二叉树

②   所有节点的左右子树深度之差的绝对值小于等于1

 

节点平衡因子：该节点左子树和右子树的深度差

 

构造平衡二叉树：

         LL平衡旋转：（B为轴，顺时针旋转）

                    RR平衡旋转：（B为轴，逆时针旋转）

                    LR平衡旋转：（c为轴，先逆时针旋转，后顺时针旋转）

                    RL平衡旋转：（c为轴，先顺时针旋转，后逆时针旋转）

 

B-树：

 

 B+树：

 

 

  散列表：

 特点：ASL=0，不需要经过比较

 

哈希表：根据设定的哈希函数H（key）和所选中的处理冲突的方法建立的查找表

 

思想：以记录的关键字为自变量，根据哈希函数计算出对应的哈希地址，并在此存储该记录的内容

 

构造哈希函数的方法：

对数字：直接定值法，数字分析法，随机数法

平方取中法（常用），折叠法，除留与余数法（最常用H(key)=key MOD p p<=m,p为<m的素数或不含20以下质因子的合数）

非数字：先进行数字化处理

 

处理冲突的方法：

①   开放定址法：当发生冲突，在冲突位置前后附近寻找可以存放记录的空闲单元

H0=H(key)

Hi=(H(key)+di) MOD m i=1,2….

Di有三种取法：

a)  线性探测再散列  ，di = 1,2,….

b)  二次探测再散列（平方），di = 1² -1² 2² -2²

c)  为随机探测再散列（双散列函数探测再散列）

 i.  Di=伪随机数列 或者 di = i×H2(key)

②  链地址开方法（开域法）：将所有哈希值相同的记录都连接在同一链表中

 

 

 

九：排序

评价标准：执行时间，辅助空间，算法稳定性

 

内部排序：

①   插入排序

a) 直接插入排序

b) 希尔排序

  i.    思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

②   交换排序

a)  冒泡排序

b)  快速排序

 i. 思想: 首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。

③   选择排序

a)简单选择排序（直接选择排序）

b)堆排序（改进：查找最小码的同时，找出较小值，分大根堆，小根堆）

④   归并排序

a) 二路归并排序：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。

⑤   基数排序

a) 多关键字排序

  i.  最高位优先MSD法

  ii.  最低位优先MSD法

b) 链式基数排序

c)基数排序的时间复杂度为O(d(2n+r))

其中：分配为O(n)

收集为O(n+r)(r为“基”)

 d为“分配-收集”的趟数

 

 

外部排序：外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间

 

讨论：

时间复杂度：

①   平均时间性能：

a)时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序

b) 时间复杂度为 O(n²)：直接插入排序、起泡排序和简单选择排序

c)时间复杂度为 O(n):基数排序

②   排元素序列按关键字顺序有序

a)  直接插入排序能达到O(n)的时间复杂度， 快速排序的时间性能蜕化为O(n2) 。

③   排序的时间性能不随关键字分布而改变的排序

a)   简单选择排序、起泡排序、堆排序和归并排序的时间性能不随元素序列中关键字的分布而改变

 

稳定的排序方法指的是，对于两个关键字相等的元素，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。