对数时间阶,算法具有如下特点

一:绪论

意味着时间复杂度的阶有:

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.数据结构:

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

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。

算法思想: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 表中。

(双向)循环链表:

Joseph难题:

n 个人围成二个圆形,首先第1私有从1起来一人一个人顺时针报数, 
报到第m民用,令其出列。然后再从下一人初始,从1顺时针报数,报到第m私有,再令其
         出列,…,如此下去,  直到圆圈中只剩壹位结束。这个人即为优胜者。

例如  n = 8   m = 3

 

第二章 线性表

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

地方实现的是线性表的链式结构。此外,线性表通过链表还是能完毕:

  • 循环列表:表最终的二个节点的指针指向表头
  • 双列表:指针能够本着下三个因素或然上一个要素

5.线性表的用处:

  • 一元多项式的象征和相加

三:栈和队列

括号匹配的查检:(栈)

借使在表达式中允许包涵二种括号:圆括号和方括号,其嵌套的相继随意,即:

([]())或[([ ][ ])]等为科学的格式,

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

则 核查括号是或不是相称的法子可用“仰望的迫切程度”那些概念来描述。

算法设计:

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

第3章 栈和队列

1.栈和队列是破例的线性表。

2.栈是先进后出的线性表,其代表:typedef struct{Type *base;Type *top; int stacksize;}SqStack;在那之中base始终指向栈底,top随成分的增进直接指向栈顶。能够有各样实现和链表完成。

3.栈的运用比如:

  • 数制转变
  • 括号相配
  • 行编辑器扶助管理错误输入
  • 迷宫求解
  • 表明式求解
  • 完结递归

3.队列是先进先出的线性表。可以由链表实现和各种完结。

四:串

 

 轻巧字符串格局匹配算法(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起和格局再一次开始相称。

 

第四章 串

1.串是由零到三个字符组成的字符种类。

2.串的格局相称算法:

  • 找到主串中首先个等于子串首字符的岗位,伊始逐年遍历子串和主串:时间复杂度O),个中m,n是主串、子串长度
  • kmp算法:关键是部分相称值的计量(”部分相称”的本色是,不常候,字符串底部和尾部会有双重。比如,”ABCDAB”之中有八个”AB”,那么它的”部分相配值”正是2。搜索词移动的时候,第贰个”AB”向后活动4位(字符串长度-部分相称值),就能够过来第三个”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从第一行起扫描叁遍。由于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的二叉树,若第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的结点

 

 

第六章 树和二叉树

1.树的有关概念:

  • 度:节点的子树数目称之为节点的度。度为0的节点称之为叶子。
  • 纵深:树中结点的最大档期的顺序。

2.二叉树子节点至多有四个,且有左右之分。二叉树有三种为主造型:空、根、右子树为空、左右子树非空、左子树为空。二叉树的性质:

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

3.二叉树分类:

  • 满二叉树:深度为k且有2^k-1个结点的二叉树
  • 全然二叉树:深度为k,有n个结点的二叉树,每种结点的号子与深度为k的满二叉树编号挨个对应

4.二叉树的贮存结构:

  • 次第结构:根据完全二叉树的号码将其存放在一位数组中标有i-1的份量中。
  • 链表结构:typedef struct BitNode{ElemType data; struct BitNode *lchild,*rchild}BitNode;

5.二叉树的遍历:

  • 先序遍历
  • 中序遍历
  • 后序遍历先根和后根反映的是父母亲与子女节点的关系,中根反映的是弟兄节点之间的左右次序。对于表明式来讲,这三种遍历分别前缀表明式、中缀表达式和后缀表达式。

6.二叉树的规定:

  • 已知先根和中根遍历能够创制唯一二叉树
  • 已知后根和中根遍历能够建设构造唯一二叉树
  • 已知先根和后根遍历不得以创设唯一二叉树

7.二叉树的遍历能够行使递归达成,其非递归中根遍历的算法是:

[图形上传战败…(image-5f478f-1524397579659)]

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

图片 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树。

图片 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)

                   拓扑排序:

①   在有向图选三个从未前人的终极且输出 (入度为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)全部终端试探完结,算法停止。      

 

 

第七章 图

1.图的遍历算法:

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

八:查找

第八章 动态管理内部存储器

静态表查找

平均查找长度ASL:(Average Search
Length):
为了明确记录在表中的岗位,须要与给定值进行比较关键字的个数的指望值

评说标准:ASL

梯次查找:(顺序或链式)

寻思:从表中尾数记录起初,每一个实行记录的最主要字和给定值的可比,若某些记录的重中之重字和给定值相比较相等,则查找成功,不然查找不成事。

 

折半寻觅:(顺序)

                   功效比顺序查找高

 

 

第九章 查找

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为轴,顺时针旋转)

                    君越福特Explorer平衡旋转:(B为轴,逆时针旋转)

                    LCR-V平衡旋转:(c为轴,先逆时针旋转,后顺时针旋转)

                    卡宴L平衡旋转:(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+58%改为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. 观念:
首先选一个轴值(即相比较的规则),通过一趟排序将待排序记录分割成单身的两局地,前一部分笔录的主要码均小于或等于轴值,后一部分记录的要紧码均大于或等于轴值,然后分别对这两有个别重新上述格局,直到所有连串有序。

③   慎选排序

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)  
不难采取排序、起泡排序、堆排序和统一排序的年月质量不随成分种类中至关心珍爱要字的分布而改动

 

安静的排序方法指的是,对于四个基本点字非常的因素,它们在系列中的相对地点,在排序此前和经过排序之后,未有退换。

 

 

 

 

 

第十章 第十一章 排序

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):

  • 插入排序:将首先个因素看成是稳步的队列,之后的成分看成是未排序的行列,然后遍历未排序的行列,将其插入到平稳种类中
  • 希尔排序:先将全方位待排序的笔录体系分割成为若干子类别分别开始展览直接插入排序,待一切类别中的记录“基本有序”时,再对全数记录实行依次直接插入排序
  • 选料排序:首先在未排序系列中找到最小成分,存放到排序种类的伊始地方。再从剩余未排序成分中承袭寻找最小成分,然后放到已排序类别的末梢。
  • 冒泡排序:比较相邻成分,倘诺前边的大就调换
  • 归并排序
  • 立刻排序
  • 堆排序
  • 基数排序

图片 3排序算法.jpg

第十二章 文件

相关文章