对数时间阶,图形)和情理构造(顺序储存

一:绪论

表示时间复杂度的阶有:

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.数码:数据实际上就是标志,它可以输入到电脑,并且可以被电脑程序处理

三:栈和队列

括号匹配的检查:(栈)

假如在表达式中允许包含二种括号:圆括号和方括号,其嵌套的逐一随意,即:

([]())或[([ ][ ])]等为不易的格式,

[( ])或([( ))或 (()])均为不科学的格式。

则 检验括号是否配合的法子可用“期望的迫切程度”那么些定义来描述。

算法设计:

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 (n1);  //归纳项}

2.数据结构:是相互存在一种或多种特定关系的数据元素的集纳

四:串

 

 简单字符串格局匹配算法(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起和形式再一次开头匹配。

 

3.逻辑结构(集合,线性,树形,图形)和大体构造(顺序储存,链式储存)

五:数组和广义表:

数组,广义表是线性表的推广;

出色矩阵:

对称矩阵:

上三角:

下三角:

 

对角矩阵:对角矩阵可按行优先顺序或对角线的次第,将其缩减存储到

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

疏散矩阵:

疏散因子: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层至多有2i-1个结点
  2. 深度为k的二叉树至多有2k-1个结点
  3. 对于其余一颗二叉树,假使其叶子数为n0,度为2的结点数为n2,则n0=n2+1
  4. 负有n个结点的完全二叉树的深度为(log2n)+1

满二叉树的概念:

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

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

 

二叉树的存储:

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

         链式:二叉链表,三叉链表

特征:n个结点,有n+1个空指针域

二叉树的遍历:前序遍历,中序遍历,后序遍历(前中后是指根结点)

         实现:递归方法

                            非递归方法:用栈

 

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

 

线索二叉树:

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

         先序线索二叉树

         中序线索二叉树

         后续线索二叉树

 

365体育官网,树的存储:

         双亲表示法

         孩子表示法

         孩子兄弟表示法(常用)

 

树转二叉树:哥俩相连留长子

         特点:其右子树一定为空

 

二叉树变树:左孩右右连父母,去掉原来右孩线

 

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

 

二叉树变森林:去掉所有右孩线,孤立二叉再过来

 

树的遍历与二叉树遍历对应的关联:

 

树:先序遍历,后序遍历

密林:先序遍历,中序遍历

二叉树:先序遍历,中序遍历

 

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的结点

 

 

1.算法:解决特定问题求解步骤的叙说,在电脑中表现为命令的蝇头连串,并且一个指令表示一个或者三个操作

七:图

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

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

 

         稀疏图:边数或弧数远点儿nlogn

         连通:无向图中,顶点到极点之间有途径

        

 

        
图的生成树:一个连通图(无向图),生成树是一个极小连通子图,有图中全体n个顶点,n-1条边

 

         对于非连通图,每个连通分量可以社团一颗生成树,从而结成森林

        
图结合森林:由若干棵有向树组成,会有图中全体顶点,但唯有能够构成若干棵不相交的有向树的弧

 

         图的积存:邻接矩阵,邻接链表,十字链表,邻接多重表,边表

 

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

 

         无向树的邻接矩阵:终极的度 = 第i行的要素 1 的个数

 

                   优点:容易实现图的操作 
缺点:空间效用为o(n2

 

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

 

图的遍历:

         深度优先DFS:(Depth_First Search)

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

         广度优先BFS:(Breadth First Search)

                   基本思维:仿树的层系遍历

 

         图的最小生成树

                  
生成树的代价:一旦连通图是一个带权图,则其生成树中的边也带权,生成树中所有边的权值之和称为生成树的代价

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

 

                   布局最小生成树的不二法门:

①   Prim算法(以终端为目标),时间复杂度o(n2),适合稠密图

②   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(n3)

                            方法二:Floyd算法:

考虑:逐个顶点试探,从vi到vj的拥有可能存在路线中,选出一条长度最短的

                                     实现:

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

(2)逐渐试着在原一向途径中扩大中间顶点,若出席中间点后路径变短,则修改之;否则,维持原值。

(3)所有终端试探完毕,算法为止。      

 

 

2.算法设计的渴求:正确性 可读性 健壮性 时间效用高和储存量低

八:查找

3.广阔的刻钟复杂度:0(1)

静态表查找

平均查找长度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 = 12 -12
22 -22

c)  为随意探测再散列(双散列函数探测再散列)

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

②  链地址开方法(开域法):将具有哈希值相同的笔录都接连在平等链表中

 

 

 

1.线性表:零个或四个数据元素的少数体系

九:排序

评价标准:执行时间,协理空间,算法稳定性

 

里面排序:

①   插入排序

a) 直接插入排序

b) Hill排序

  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(n2):直接插入排序、起泡排序和简单采纳排序

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

②   排元素系列按重要性字顺序有序

a)  直接插入排序能达到O(n)的时刻复杂度, 迅速排序的时日性能蜕化为O(n2)

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

a)  
简单采纳排序、起泡排序、堆排序和合并排序的岁月性能不随元素类别中根本字的遍布而改变

 

安静的排序方法指的是,对于三个关键字相当的因素,它们在连串中的相对地点,在排序以前和通过排序之后,没有更改。

 

 

 

 

 

2.依次储存方法:储存空间的发端地方data  最大储存容量马克斯(Max)Size
 当前长度length

3.线性表的顺序结构再存,取多少时时间复杂度为O(1),而插入或者去除时
时间复杂度为O(n);

4.线性表的逐条结构的优点:无需为表中的逻辑关系而充实额外的囤积空间,可以长足的存取某一岗位的多寡

 
缺点:插入或者去除需要活动大量多少,当线性表长度变化较大时难以确定储存空间的大小
,造成储存空间的”碎片”

5.链式储存结构:n个结点链成一个链表,每个结点只含有一个指针域,成为单链表

6.静态链表:数组描述的链表, 

可取:在插入或者去除时只需要改游标,不需要活动元素,从而改正了在各类储存结构中插入和删除需要活动大量要素的缺点.

缺陷:没有缓解连续储存带来的尺寸难以确定的问题,失去了顺序存储结构的随机存取的特性.

7.将单链表中终端结点的指针端由空指针指向首结点,就使得所有单链表成为一个环.这样的首尾相接的单链表就叫做循环链表.

8.双向链表:在单链表的每个结点上,再设置一个针对其前任结点的指针域.

第四章 栈与队列

1.栈: 限定仅在表尾举行插队和删除的线性表

2.递归函数:把一个从来调用自己仍然经过一多级的调用语句直接地调用自己的函数

3.四则表明式 将中缀表明式转换为后缀表明式  将后缀表明式举行演算拿到结果

4.队列: 只允许在一端举行扦插操作,而在另一端进行删减操作的线性表

第五章 串

1.串:→零个依旧五个字符组成的星星系列,又名字符串

2.朴素匹配      KMP情势匹配算法  时间复杂度 O(n+m)

第六章 树 tree

1.树是由n个结点的有数集  n=0时 称为空树,
在任何一棵非空树中:a.有且仅有一个一定的称为根的结点
b.当n>1时,另外结点可分为m个互不相交的蝇头集T1 T2 …Tm.
其中每个集合的本身又是一棵树,并且称为根的子树.

2.囤积结构的计划是一个异常灵活的过程.一个仓储结构设计的是不是合理,取决于基于该储存结构的演算是否适合,是否便利,时间复杂度好糟糕等

3.老人家表示法 :每个结点中,附设一个提醒器指示其家长结点在数组的职位

4.儿女表示法:每个结点的男女结点排列起来,以单链表作为储存结构,则n个结点有n个儿女链表,如假使纸牌结点则此单链表为空.
然后n个头指针又结合一个线性表,采用顺序储存结构,存放进一个一维数组中   

5.兄弟表示法:任意一棵树,他的结点的率先个孩子只要存在就是绝无仅有的,他的右兄弟如若存在也是绝无仅有的,由此,我们设置多少个指针,分别指向该结点的首先个儿女和他的右兄弟,

6.二叉树:是n个结点的蝇头集合,该集合或者为空集,或者由一个根节点和两课互不相交的,分别名叫根节点的左子树和右子树的二叉树组成;

7.二叉树的5种造型:空树,只有一个根节点,唯有一个左子树,只有一个右子树,根节点有左子树和右子树;

8.斜树:
所有的结点都只有左子树的叫左斜树,所有结点都唯有右子树的叫右斜树,统称为斜树

9.满二叉树:在一棵二叉树中,倘若拥有的分支结点都设有左子树和右子树,并且具有的纸牌都在相同层上,这棵树称为二叉树;

10.全然二叉树:对一棵具有n个结点的二叉树按层序编号,假使编号为i的结点与平等深度的满二叉树中编号为i的结点在二叉树中地点完全相同,则这棵树为完全二叉树

11.二叉树的属性:a. 在二叉树的第i层上至多有2^(i-1) 个结点(i>=1);
b.深度为k的二叉树至多有2^k -1 个结点(k>=1);
c.对其它一棵二叉树T,假设其终端结点数为n0,度为2的结点数为n2 则n0=n2+1;

   d.具有n个结点的通通二叉树的吃水为[log2n]+1 ;
e.要是对一棵有n个结点的通通二叉树的结点按层序编号,对任一结点i有:
1.尽管i=1.则结点i是二叉树的根,无大人,i>2,则其家长是结点i/2;2.如

   果
2i>n,则结点i无子女,否则其左孩子是结点2i,3.只要2i+1>n,则结点i无右孩子,否则其右孩子是结点2i+1;

12.二叉树遍历:从根节点出发,依照某种次序依次走访二叉树中享有结点,使得各样结点被访问两次且仅被访问三遍;
前序遍历  中序遍历  后序遍历 层序遍历

13.树转二叉树: 1加线 2去线, 3层次调整,    

14.森林转二叉树: 1 把每个树转换为二叉树,2.
率先棵二叉树不动,从第二棵起始,依次吧后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连起.

第七章  图

1.图: 由顶点的战国非空集合和极端之间边的会见组成,平时标书为 G(V,E),其中
G 表示一个图,V是图G中顶点的汇集,E是图G中边的聚集

2.图根据有无方向分为无向图和有向图,
无向图由顶点和边构成,有向图由顶点和弧构成, 弧有弧头和弧尾之分;

3.图比照边或弧的有些分稀疏图和稠密图; 图中顶点之间有邻接点.依附的概念;
无向图顶点的边数叫度,有向图的顶点分出度和入度;

4.图的边或弧带着权的叫做网; 

5.无向图中连通且n个顶点n-1个边叫生成树.有向图中一顶点入度为0
此外顶点入度为1的叫有向树,一个有向图由若干棵有向树构成生成森林

6.图的邻接矩阵储存方法是用多个数组来代表图.一个一维数组储存图中顶点音信,一个二维数组存储图中边或弧的信息

7.图的任何储存方法: 邻接表储存方法是数组与链表的组成   逆邻接表.
十字链表  邻接多重表 边集数组 

8.图的遍历分 广度和深度优先    

 9.最小生成树 :把结构连通网的蝇头代价生成树   普利姆(prim)算法
 克鲁斯凯尔(Kyle)(Kruskal)算法

10.最短路径:是指两顶点之间通过的边际权值之和最少得路径,并且我们称第一个极端为起点最后一个极端是极端;迪杰Stella算法   弗洛伊德算法

11.AOV网:
在一个意味着工程的有向图中,用极端表示活动,用弧表示活动期间的先期关系,这样的有向图为终点表示活动的网
称为AOV网

12.拓扑连串:设G=(V,E)是一个负有n个顶点的有向图,V中的终端系列V1,v2…vn,满意若从终端vi到vj有一条路子,则在顶点系列中顶点vi必在极端vj在此以前.

13.AOE网:在一个代表工程的带权有向图中,用极端表示时间,用有向边表示活动,用边上的权值表示活动的持续时间,那种有向图的边表示活动的网,称为AOE网

14.至关首要路径:路径上各类活动所持续的时间之和称为路径的长短,从起源到汇点具有最大尺寸的门道叫做关键路径,在显要路径上的活动称之为关键活动

第八章  查找

1.招来:依据给定的某个值,在查找表中规定一个其关键字等于给定值的多寡元素

2.静态查找表是只做查找操作的查找表;动态查找表示在搜寻的过程中并且插入不设有的因素或者去除已存在的某个元素

3.顺序查找表:又称线性查找,从表的第一个元素开端,逐个举行记录的重点字和给定值的可比,若相等,则查找成功,若直到最终一个都不等于的话,则查找未果;O(n)

4.有序表查找:折半追寻,O(logn)
插值查找公式:(key-a[low])/(a[high]-a[low])   O(logn)  
 斐波那契查找 O(logn)

5.线性索引查找:索引就是把一个重中之重字与它对应的笔录相关联的长河
 稠密索引:指在线性索引中,将数据汇总的每一个记下对应一个索引项;分块索引:
是吧数据集的笔录分成了多少块,块内无序,块间有序
倒排索引:其中记录号表储存具备相同关键字的有着记录的记录号

6.二叉排序树 : 又称二叉查找树
它仍然是空树或者有以下性质:若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
它的左右子树也独家是二叉排序树

7.平衡二叉树是一种二叉排序树,其中每个结点的左子树和右子树的莫大差至多等于1
;
 将二叉树上结点的左子树深度减去右子树的深浅的值称为平衡因子BF;距离插入结点目前的
且平衡因子的相对值超出1的结点为根的子树,我们誉为最小不平衡子树

8.多路摸索树
每一个结点的儿女数可以多于多少个,且每一个结点处可以储存多少个要素 2-3树
 2-3-4树  b树  b+树

9.散列表(哈希表)是在笔录的储存位置和她的机要字中间确立一个创设的附和关系f,使得各种首要字key可以对应一个存储地方f
,这种对应关系f称为散列函数或哈希函数,

第九章 排序

1.排序:假使含有n个记录的队列为[r1,r2,r3……rn],其相应的重中之重字分别为[k1,k2,….kn],需确定1,2,….,n
的一种排列p1,p2….pn,使其响应的重要字满意kp1<=kp2<=…<=kpn关系,即便得体系称为一个按首要性字有序的队列[rp1,rp2,…rpn],这种操作叫做排序;

2.内排序是在排序过程中,待排序的拥有记录整个被放置在内存中,外排序是由于排序的记录个数太多,不可以同时停放在内存,整个排序的历程需要在内外存之间多次换成数据才能开展

3.排序的特性  时间性能,匡助空间,算法的纷繁

4.冒泡排序:
两两相比较相邻的笔录的重要字,如若返序则交流,直到没有返序的记录截止

5.粗略拔取排序:通过n-i次重要字间的相比较,从n-i+1个记录中精选关键字不大的笔录,并和第i个记录交换

6.直接插入排序:将一个记录插入到曾经排好序的稳步表中,从而得到一个新的.记录数增1的有序表;

7.希尔(Hill)排序:把原本大量记下举办分组,然后这个子连串进行插入排序当全体连串基本不变时,再对全部记录举办五回插入排序

8.堆:具有下列性质的通通二叉树:每个结点的值都大于或等于其左右子女结点的值,称为大顶堆;或者每个结点的值都低于或等于其子女结点的值,称为小顶堆;

9.堆排序:
将待排序的连串构造成一个大顶堆.此时,整个体系的最大值就是锥顶的根结点.将它移走,然后将余下的n-1个体系重新社团一个堆,这样就会赢得n个元素中的次大值,反复实践,得到稳步系列;

10.归并排序:尽管起初连串有n个记录,则足以当作是n个有序的子连串,每个子系列的长短为1,然后两两合并,得到[n/2]个长度为2或1的有序子体系,再两两联结,如此重复,知道拿到一个尺寸为n的静止系列

11.高速排序:通过一趟排序将待排记录分割成独立的两部分,其中部分记录的显要字均比另一有些记录的重要字小,则可各自对这两有的记录举办排序,以达到任何连串的稳步

12.

365体育官网 1

13.

365体育官网 2

相关文章