数据结构与算法计算,数据结构

对数时间阶,4.算法的度量

一:绪论

代表时间复杂度的阶有:

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)(渐近)空间复杂度。

        

第1章 绪论

1.常用的数据结构类型:集合、线性、树形、图状。

2.数据结构:

  • 逻辑结构:数据成分之间的涉及
  • 仓库储存结构:数据结构在处理器中的表示。存款和储蓄结构分为:顺序存储结构和链式存款和储蓄结构。

3.算法是对一定难题求解步骤的一种描述,算法具有如下特征:有穷性、分明性、可行性、输入、输出。

4.算法的心胸:

  • 时光复杂度
  • 空中复杂度

二:线性表

顺序线性表:

设在线性表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。

算法思想:壹 、扩充La,将存在于Lb中而不设有于La中的数据成分插入到La中去。② 、必要从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 表中。

(双向)循环链表:

Joseph难题:

n 个人围成一个圆形,首先第③民用从1开端一人一人顺时针报数, 
报到第m私家,令其出列。然后再从下1人开头,从1顺时针报数,报到第m私有,再令其
         出列,…,如此下来,  直到圆圈中只剩一个人甘休。这厮即为优胜者。

例如  n = 8   m = 3

 

第二章 线性表

1.线性表的概念:

  • 留存唯一1个“第③个”元素
  • 留存唯一一个“最终2个”成分
  • 除第三个要素外,每二个要素都有且只有1个前任
  • 除最终二个要素外,每一种成分都有且唯有几个后继

2.线性表合并的办法:

  • 将表A中的成分各种和B中的相比,不一致就进入到B中。时间复杂度为O*len
  • AB是严守原地排列的前提下,使用多个指针分别指向A和B,将二者较小的要素插入到C中,然后移动较小的指针,直到整个插入到C。时间复杂度为O+len

3.线性表的各类达成:满意LOC=LOC+l,LOC表示成分地址。特点:下标读取快O,插入删除O。

#include <stdlib.h>#ifndef SEQUENCE_LINER_LIST_H#define SEQUENCE_LINER_LIST_H/* 线性表的顺序实现*/#define LIST_INIT_SIZE 100 //初始分配量#define LIST_INCREMENT 10 //增量#define LIST_TYPE int //存储类型typedef struct strSequenceLinerList{ LIST_TYPE *elem; //存储空间基址 unsigned int length; //当前长度 unsigned int listSize; //当前存储容量}SequnceLinerList;static enum Status{ OK, FAILED, OVERFLOW};/* 线性表初始化 */Status initSequenceLinerList(SequnceLinerList& list){ list.elem = (LIST_TYPE *)malloc(sizeof(LIST_TYPE)*LIST_INIT_SIZE); if (!list.elem) { return OVERFLOW; } list.length = 0; list.listSize = LIST_INIT_SIZE; return OK;}/* 扩展 */Status resizeSequenceLinerList(SequnceLinerList& list){ printf("Resize...\n"); list.elem = (LIST_TYPE*)realloc(list.elem, sizeof(LIST_TYPE)*(list.listSize + LIST_INCREMENT)); if (!list.elem) { return OVERFLOW; } list.listSize += LIST_INCREMENT; return OK;}/* 打印 */void printSequnceLinerList(SequnceLinerList& list){ printf("Begin print list...\n"); printf("length=%d,listSize=%d.\n",list.length,list.listSize); unsigned int i = 0; for (; i < list.length-1;++i) { printf("%d,",list.elem[i]); } printf("%d\n", list.elem[i]); printf("End print list.\n");}/* 线性表插入:position表示插入的位置,从1开始。第一个元素是list.elem[0] */Status insertSequenceLinerList(SequnceLinerList& list, unsigned int position, LIST_TYPE value){ if (position<1 || position>list.length+1) { return FAILED; } if (list.length >= list.listSize) { Status res = resizeSequenceLinerList; if (OK != res) { return FAILED; } } LIST_TYPE* p = &list.elem[position -1]; LIST_TYPE* q = &list.elem[list.length]; for (; p != q; --q) { * = *p; } list.length++; *p = value; return OK;}/* 删除元素 */Status deleteSequenceLinerList(SequnceLinerList& list, unsigned int position){ if (position<1 || position>list.length) { return FAILED; } LIST_TYPE* p = &list.elem[position - 1]; LIST_TYPE* q = &list.elem[list.length - 1]; for (; p != q; ++p) { *p = *; } --list.length; return OK;}/* 查找:第一个值的下标 */unsigned int findSequenceLinerList(SequnceLinerList& list, int value){ for (unsigned int i = 0; i < list.length;++i) { if (value == list.elem[i]) { return i; } } return -1;}/* 排序 */void sortSequeceLinerList(SequnceLinerList& list){ unsigned int i = 0; unsigned int j = 0; for (; i < list.length-1;++i) { for (j = i + 1; j < list.length; ++j) { if (list.elem[i]>list.elem[j]) { LIST_TYPE tmp = list.elem[i]; list.elem[i] = list.elem[j]; list.elem[j] = tmp; } } }}/* 销毁 */void destroySequenceLincerList(SequnceLinerList& list){ delete list.elem; list.elem = NULL;}#endif

4.线性表的链式完毕:通过p=p.next查找具体地方的链表。特点:插入、删除快O。

#include <stdio.h>#include <stdio.h>#ifndef LINK_LINER_LIST_H#define LINK_lINER_LIST_H#define LINK_LIST_TYPE int/* 线性表的链表实现*/typedef struct strLinkLinerList{ LINK_LIST_TYPE data; struct strLinkLinerList* pNext;}LinkLinerList;LinkLinerList* head = NULL;/* 链表初始化 */Status initLinkLinerList(){ if (NULL == head) { head = (LinkLinerList*)malloc(sizeof(LinkLinerList)); if  { return OVERFLOW; } head->pNext = NULL; return OK; } else { return FAILED; }}/* 添加元素 */Status insertLinkLinerList(LINK_LIST_TYPE value){ if (NULL == head) { return FAILED; } LinkLinerList* p = head; while (p->pNext) { p = p->pNext; } LinkLinerList* tmp = (LinkLinerList*)malloc(sizeof(LinkLinerList)); if  { return OVERFLOW; } tmp->data = value; tmp->pNext = NULL; p->pNext = tmp; return OK;}/*打印*/void printLinkLinerList(){ printf("Begin print...\n"); if (NULL == head || NULL == head->pNext) { printf("List is null."); } LinkLinerList* p = head->pNext; while (p->pNext) { printf("%d,",p->data); p = p->pNext; } printf("%d\n", p->data); printf("End print.\n");}/* 排序 */Status sortLinkLinerList(){ if (NULL == head || NULL == head->pNext) { return FAILED; } LinkLinerList* p = head->pNext; LinkLinerList* q = p->pNext; while  { q = p->pNext; while  { if (p->data > q->data) { LINK_LIST_TYPE tmp = p->data; p->data = q->data; q->data = tmp; } q = q->pNext; } p = p->pNext; } return OK;}/* 长度 */unsigned int lengthLinkLinerList(){ if (head == NULL || head->pNext == NULL) { return 0; } LinkLinerList* p = head->pNext; unsigned int length = 0; while  { p = p->pNext; length++; } return length;}/* 删除 */Status deleteLinkLinerList(unsigned int position){ if (position > lengthLinkLinerList() || position < 1) { return FAILED; } else { LinkLinerList* p = head; LinkLinerList* q = p->pNext; if (NULL == p || NULL == q) { return FAILED; } while (--position) { p = p->pNext; q = p->pNext; } p->pNext = q->pNext; free; return OK; }}/* 销毁 */void destroyLinkLinerList(){ if (NULL == head) { return; } else { LinkLinerList* p = head->pNext; LinkLinerList* q = p; while  { p = p->pNext; free; q = p; } }}#endif

地点完结的是线性表的链式结构。其它,线性表通过链表还足以兑现:

  • 循环列表:表最后的1个节点的指针指向表头
  • 双列表:指针能够针对下三个成分或然上二个因素

5.线性表的用处:

  • 一元多项式的意味和相加

三:栈和队列

括号匹配的检验:(栈)

如若在表达式中允许包蕴三种括号:圆括号和方括号,其嵌套的依次随意,即:

([]())或[([ ][ ])]等为正确的格式,

[( ])或([( ))或 (()])均为不得法的格式。

则 检验括号是还是不是匹配的艺术可用“企望的殷切程度”那些定义来讲述。

算法设计:

1)  凡出现左括弧,则进栈;

2)  凡出现右括弧,首先检查栈是不是空

若栈空,则注脚该“右括弧”多余,

   不然和栈顶元素相比较,

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

     不然注明不协作。

3)表明式检验达成时,

   若栈空,则评释表明式中匹配正确,

   不然表明“左括弧”有余。

 

表明式求值:(栈)

迷宫求解:(栈)

求迷宫路径算法的基本思维是:从入口出发,按某一方向向未度过的火线探索

若当前岗位“可通”,则纳入路径,继续提升

若当前岗位“不可通”,则战败,换方向持续追究;

若四周“均无通路”,则将近来职责从路径中除去出去。

 

                            算法:

设定当前岗位的初值为进口地点;

lovebet爱博, do{

   若当前岗位可通,

   则{将如今地方插入栈顶;

           若该职责是说道地点,则算法结束;           

           不然切换当前位置的东邻方块为

                   新的最近地方;

   }

   否则 {

   }

}while (栈不空);

若栈不空且栈顶地点尚有其余方向未被追究,

则设定新的此时此刻义务为: 沿顺时针方向旋转

            找到的栈顶地点的下一相邻块;

若栈不空但栈顶地点的方圆均不可通,

则{删去栈顶地点;// 从路径中除去该通道块                  

        若栈不空,则另行测试新的栈顶地点,

        直至找到三个可通的相邻块或出栈至栈空;

若栈空,则申明迷宫没有通路。

 

 

栈的别的一个重庆大学的选拔:递归调用

用分治法求解递归难题:

分治法:对于叁个相比较复杂的标题,能够分解成多少个相对简便易行的且解法相同或近乎的子难题来求解

五个规范:

① 、能将3个难题转变成2个新题材,而新题材与原难题的解法相同或类同,分裂的仅是拍卖的目的,且那几个处理目的是生成有规律的

 

二 、能够透过上述转化而使难点简化

 

三 、必须有多少个明显的递归出口,或称递归的边际

 

分治法求解递归难题算法的相似格局:

     void   p (参数表) {

        if   (递归甘休条件)可径直求解步骤;—–基本项

        else  p(较小的参数);——归结项

       }

long Fact ( long n ) {

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

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

第①章 栈和队列

1.栈和队列是出格的线性表。

2.栈是先进后出的线性表,其象征:typedef struct{Type *base;Type *top; int stacksize;}SqStack;当中base始终指向栈底,top随成分的增加直接指向栈顶。可以有各类完成和链表达成。

3.栈的利用举例:

  • 数制转换
  • 括号匹配
  • 行编辑器帮忙处理错误输入
  • 迷宫求解
  • 表明式求解
  • 达成递归

3.队列是先进先出的线性表。可以由链表达成和顺序达成。

四:串

 

 简单字符串方式匹配算法(BF算法):

算法思想:从主串S的第pos个字符起和方式串T的首先个字符相比之,若相等,则继续相比较后续字符;不然从主串的下二个字符起再重复和格局的字符相比较之。依此类推,直至格局T中的每种字符依次和主串S中的3个两次三番的字符体系相等,则称匹配成功,函数值为和方式T中率先个字符相等的字符在主串S中序号,不然称匹配不成事,函数值为零。

首尾字符串匹配算法:

先相比方式串的第四个字符

再相比较形式串的结尾贰个字符

说到底比较形式串中从第二个到第n-三个字符

 

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起和格局再一次初步匹配。

 

第四章 串

1.串是由零到四个字符组成的字符连串。

2.串的格局匹配算法:

  • 找到主串中第一个等于子串首字符的职位,开头稳步遍历子串和主串:时间复杂度O),个中m,n是主串、子串长度
  • kmp算法:关键是有的匹配值的总结(”部分匹配”的精神是,有时候,字符串尾部和尾巴会有重新。比如,”ABCDAB”之中有五个”AB”,那么它的”部分匹配值”就是2。搜索词移动的时候,第③个”AB”向后运动几人(字符串长度-部分匹配值),就能够过来第三个”AB”的岗位)。时间复杂度O。KMP算法仅当子串与主串之间存在诸多”部分匹配”的情景下才快的多。详见http://kb.cnblogs.com/page/176818/

五:数组和广义表:

数组,广义表是线性表的拓宽;

极度矩阵:

对称矩阵:

上三角:

下三角:

 

对角矩阵:对角矩阵可按行优先顺序或对角线的各种,将其缩减存款和储蓄到

一维数组中,且也能找到各类非零成分和向量下标的应和关系。

疏散矩阵:

疏散因子:m行n列t个非零成分

 

 

顺序存款和储蓄:安慕希组(行数,列数,元素值)

转置:

算法的为主考虑:第一回从转置前稀疏矩阵source中取出应该放置到转置后的稀疏矩阵dest中首先个地方的要素,行列号交换后,放于dest中率先个职分;首回从source中选择应该放权dest中的第二个职位的因素,……,如此进行,依次生成dest中的各要素。

艺术一:按m的列序转置

按T.data中伊利组次序依次在M.data中找到呼应的三元组举办转置,即根据矩阵M的列序来展开置换。

为找到M中每一列全部非零元素,需对其三元组表M.data从第二行起扫描1遍。由于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.广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们持有其自个儿结构。

六:树与二叉树

二叉树的习性:

  1. 在二叉树第i层至多有2i-1个结点
  2. 纵深为k的二叉树至多有2k-1个结点
  3. 对此别的一颗二叉树,假使其叶子数为n0,度为2的结点数为n2,则n0=n2+1
  4. 持有n个结点的一点一滴二叉树的深浅为(log2n)+1

满二叉树的定义:

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

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

 

二叉树的蕴藏:

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

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

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

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

         达成:递归方法

                            非递归方法:用栈

 

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

 

线索二叉树:

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

         先序线索二叉树

         中序线索二叉树

         后续线索二叉树

 

树的贮存:

         双亲表示法

         孩子表示法

         孩子兄弟表示法(常用)

 

树转二叉树:手足相连留长子

         特点:其右子树一定为空

 

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

 

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

 

二叉树变森林:去掉全数右孩线,孤立二叉再回复

 

树的遍历与二叉树遍历对应的涉及:

 

树:先序遍历,后序遍历

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

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

 

Haffman树与Haffman编码:

         Haffman树最优树:带权路径长度(WPL)最短的树

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

 

         构造Haffman树:7 5 5 2 4

        

         Haffman编码:依照字符出现频率编码,使电文化总同盟长度最短

 

         八个难题:

n个结点经n-3遍联合,每一趟生成新的结点,总共
n+n-1=2n-3个结点,度为2的结点个数为n-1

 

未曾度为1的结点

 

 

第五章 树和二叉树

1.树的连带概念:

  • 度:节点的子树数目称之为节点的度。度为0的节点称之为叶子。
  • 纵深:树中结点的最大层次。

2.二叉树子节点至多有七个,且有左右之分。二叉树有多样基本造型:空、根、右子树为空、左右子树非空、左子树为空。二叉树的品质:

  • 第i层有2^个节点
  • 深度为k的二叉树至多2^k-二个节点
  • 顶点节点数为n,度为2的节点数为m,则n=m+1
  • 具备n个结点的通通二叉树的吃水是+1

3.二叉树分类:

  • 满二叉树:深度为k且有2^k-三个结点的二叉树
  • 一齐二叉树:深度为k,有n个结点的二叉树,每一个结点的号子与深度为k的满二叉树编号顺序对应

4.二叉树的仓库储存结构:

  • 逐条结构:依据完全二叉树的编号将其存放在一人数组中标有i-1的轻重中。
  • 链表结构:typedef struct BitNode{ElemType data; struct BitNode *lchild,*rchild}BitNode;

5.二叉树的遍历:

  • 先序遍历
  • 中序遍历
  • 后序遍历先根和后根反映的是老人与儿女节点的关系,中根反映的是弟兄节点之间的左右次序。对于表达式而言,那三种遍历分别前缀表达式、中缀表达式和后缀表明式。

6.二叉树的规定:

  • 已知先根和中根遍历能够建立唯一二叉树
  • 已知后根和中根遍历能够成立唯一二叉树
  • 已知先根和后根遍历不得以创建唯一二叉树

7.二叉树的遍历能够利用递归完成,其非递归中根遍历的算法是:

[图表上传失利…(image-5f478f-1524397579659)]

8.二叉树从根伊始分层从左至右遍历算法是:

lovebet爱博 1image

9.线索二叉树:指向前驱可能后继的节点的链成为线索。线索二叉树使用的节点结构为:data、left、right、ltag、rtag。在那之中ltag=0表示子树,=1表示前驱节点。

10.赫夫曼树又称最优树,是一类带权路径长度(子叶到根的门路个数)最短的树。赫夫曼树的组织算法:赫夫曼算法:

  • 以权值分别为W1,W2...Wn的n各结点,构成n棵二叉树T1,T2,...Tn并组成森林F={T1,T2,...Tn},其中每棵二叉树
    Ti仅有多个权值为 Wi的根结点;
  • 在F中选用两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值=左右孩子权值之和,叶结点的权值=
    Wi)
  • 从F中删除那两棵二叉树,同时将新二叉树加入到F中;
  • 、直到F中只含一棵二叉树结束,那棵二叉树正是Huffman树。

lovebet爱博 2image

11.赫夫曼树的行使:

  • 区别分数段评定特出中差,可以依照分数出现比例为权值构造赫夫曼数,优化程序判断次序
  • 赫夫曼编码

七:图

         无向图边的取值范围: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)

                   拓扑排序:

①   在有向图选1个并未前人的极限且输出 (入度为0)

②   从图中去除该终端及它的装有尾

③   重复以上两步

 

AOV网:极端表示活动的网(Activity On Vertex
network),不允许有回路,弧表示活动之间的优先制约关系

检查和测试AOV中是或不是留存环:网中保有终端拓扑有序体系(拓扑连串不是唯一的)

 

 

 

         要害路径:(Critical Path)

AOE网(Activity On Eage
network):
顶点表示时间,弧表示活动,权表示活动持续的时刻

        

重在活动:该边上的权值扩大将使有向图上的最长路径长度扩大,l(i)=e(i)

 

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

①   向前递推

②   向后递推

③   把l(i)=e(i)的门道连起来

 

 

         最短路径(Short 帕特h):交通互连网难点

 

                   分二种:单起源最短路径,全部终端最短路径

 

                   单起源最短路径:

 

主意一:将源点到终点全数路径列出来,选最短的。缺点:随路径的增多,功用会下跌

                           
方法二:Dijkstra算法:按路径长度递增次序爆发各顶点的最短路径

 

                  每一对极端间最短路径:

                           
方法一:以一个巅峰为起源,重复执行Dijkstra算法N次,T(n)=o(n3)

                            方法二:Floyd算法:

合计:每一个顶点试探,从vi到vj的持有可能存在路线中,选出一条长度最短的

                                     实现:

(1)开首时设置三个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应成分为权值,不然为∞。

(2)逐步试着在原向来途径中加进中间顶点,若参预中间点后路径变短,则修改之;不然,维持原值。

(3)全部终端试探完成,算法甘休。      

 

 

第七章 图

1.图的遍历算法:

  • 纵深优先算法
  • 广度优先算法

八:查找

第玖章 动态管理内部存款和储蓄器

静态表查找

平均查找长度ASL:(Average Search
Length):
为了分明记录在表中的任务,要求与给定值实行相比关键字的个数的梦想值

评价标准:ASL

逐条查找:(顺序或链式)

思想:从表中最终3个记下伊始,各个举行记录的基本点字和给定值的相比,若某些记录的首要字和给定值比较相等,则查找成功,不然查找不成功。

 

折半查找:(顺序)

                   功能比顺序查找高

 

 

第九章 查找

1.寻觅算法(详见https://www.cnblogs.com/yw09041432/p/5908444.html)。平均查找长度(Average
Search

动态查找表

留存注重字为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为轴,顺时针旋转)

                    奥迪Q5途乐平衡旋转:(B为轴,逆时针旋转)

                    L奥迪Q5平衡旋转:(c为轴,先逆时针旋转,后顺时针旋转)

                    奥迪Q7L平衡旋转:(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)

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

 

 

 

Length,ASL):需和钦赐key举行比较的要紧字的个数的想望值,称为查找算法在检索成功时的平均查找长度。对于富含n个数据成分的查找表,查找成功的平分查找长度为:ASL

Pi*Ci的和。Pi:查找表中第i个数据成分的可能率。Ci:找到第i个数据成分时已经相比较过的次数。

  • 依次表查找:顺序查找:
    • 务求:存款和储蓄结构为顺序存储也许链表存款和储蓄
    • 思想:顺序依次查找
    • ASL:*(1+2+…+n)=/2
    • 时间复杂度:O
  • 二分查找、折半追寻:
    • 渴求:有序顺序存款和储蓄列表
    • 思考:先将查找值与中间值相比较,查找不成事折半找寻区间
    • ASL:log2
    • 光阴复杂度:O
  • 插值查找:
    • 务求:有序顺序存款和储蓄列表
    • 心想:基于二分查找算法,将查找点的抉择革新为自适应选取(由mid=low+百分之五十改为mid=low+(key-a[low])/(a[high]-a[low]),),能够提升查找功能。
    • 日子复杂度:O
  • 斐波那契额查找:
    • 务求:有序顺序存款和储蓄列表
    • 思考:依然是对查找点的优化,采纳Fibonacci数组,找到对于当下长度的有序表的黄金分割点,作为每回的中间值。
    • 时刻复杂度:O。平均品质,菲波那切查找优于折半追寻,最坏情形低于折半物色。
  • 二叉查找树:
    • 须求:需求首先二叉查找树(左子树<根<右子树)
    • 合计:先对待查找的多寡开始展览生成树,确定保障树的左分支的值稍差于右分支的值,然后在就行和每一个节点的父节点相比大小,查找最契合的范围
    • 时光复杂度:O,最坏O,原因是绝非保证平衡,形成单支树
  • 平衡二叉树AVL:
    • 供给:二叉查找树的根基上,须要开展树的平衡
    • 时间复杂度:平昔是O
    • 除此以外,在此基础上还有2-3树,2-3-4树,B+树,红黑树等。

2.上述算法中:

  • 依次表查找:
    • 优点:简单
    • 缺点:效率低O
  • 一如既往表查找:/
    • 可取:时间复杂度低O
    • 缺点:有序表的插入和删除品质是相比较差的

九:排序

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

 

个中排序:

①   插入排序

a) 直接插入排序

b) 希尔排序

  i.  
 思想:将全体待排序记录分割成几何个子类别,在子系列内分别展开间接插入排序,待全体类别中的记录基本铁钉铁铆时,对全体记录举行直接插入排序。

②   换到排序

a)  冒泡排序

b)  火速排序

 i. 思想:
首先选3个轴值(即比较的尺度),通过一趟排序将待排序记录分割成单身的两有的,前一部分笔录的重点码均小于或等于轴值,后一片段记录的根本码均大于或等于轴值,然后分别对那两部分重新上述办法,直到全数体系有序。

③   慎选排序

a)不难选拔排序(直接选拔排序)

b)堆排序(创新:查找最小码的还要,找出较小值,分大根堆,小根堆)

④   归并排序

a)
二路归并排序:将二个拥有n个待排序记录的连串看成是n个长度为1的不变系列,然后进行两两归并,获得n/三个长度为2的静止序列,再拓展两两归并,获得n/八个长度为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)  
简单选用排序、起泡排序、堆排序和归并排序的年华性能不随成分体系中关键字的遍布而变更

 

安居的排序方法指的是,对于七个第1字十分的要素,它们在种类中的相对地点,在排序在此以前和透过排序之后,没有更改。

 

 

 

 

 

第8章 第九一章 排序

1.排序算法的平安:经过排序,那么些记录的相对次序保持不变,即在原系列中,ri=rj,且ri在rj在此之前,而在排序后的行列中,ri仍在rj在此之前,则称这种排序算法是政通人和的;不然称为不平静的。例如冒泡排序是平稳的,不过若是交流条件改为a[j].key>=a[j+1].key,就是不安定的。

2.排序算法能够分成内部排序和表面排序,内部排序是数量记录在内部存款和储蓄器中展开排序,而外部排序是因排序的数码相当大,贰遍无法包容全部的排序记录,在排序进程中供给拜访外部存款和储蓄器。

3.常见的8种个中排序算法有(详见https://www.cnblogs.com/RainyBear/p/5258483.html):

  • 插入排序:将第三个成分看成是不变的连串,之后的因素看成是未排序的行列,然后遍历未排序的队列,将其插入到平稳体系中
  • 希尔排序:先将一切待排序的笔录连串分割成为若干子类别分别进行直接插入排序,待一切连串中的记录“基本不变”时,再对总体记录举办逐一直接插入排序
  • 分选排序:首先在未排序类别中找到最小元素,存放到排序类别的原初位置。再从剩余未排序成分中持续查找最小元素,然后放到已排序系列的末尾。
  • 冒泡排序:相比较相邻元素,假诺眼下的大就沟通
  • 归并排序
  • 登时排序
  • 堆排序
  • 基数排序

lovebet爱博 3排序算法.jpg

第⑧二章 文件