4 hihello米

尚未进行身份认证

暂无相关简介

等级
TA的排名 2w+

内部排序 ---- 归并排序 、基数排序【按位依次排序】

1、归并排序 》》 “归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。 》》 案例:2-路归并排序 2、基数排序【按位依次排序】 》》基数排序分为:“最高位优先(MSD)”和 “最低位优先(LSD)”。 》》 基数排序的案例:【由 4个 3位数组成的表的过程】--》使用“最低位...

2019-10-25 16:35:05

内部排序 ---- 选择排序 :堆排序(树形选择排序)--借助“完全二叉树顺序存储”

1、 》》堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将 L[1...n]看成是一棵完全二叉树 的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关 键字最大(或最小)的元素。 》》堆的定义如下: n个关键字序列 L[1...n]称为“堆”,当且仅当该序列满足:...

2019-10-25 10:53:06

内部排序 -- 选择排序:简单选择排序

》》选择排序的基本思想:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已经排好序的 子表(有序序列)的最后,直到全部记录排序完毕。 1、简单选择排序图解: 1)、将一段序列分为“有序序列”和“无序序列”两个部分。 说明1:每次都从“无序序列”中找出...

2019-10-25 09:03:50

内部排序 --交换排序:冒泡排序 快速排序

》》所谓交换,就是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。1、冒泡排序 》》冒泡排序算法的基本思想是:假设待排序表长为n ,从后往前(或者从前往后)两两比较 相邻元素的值,若为逆序(即 A[ i-1 ] > A[ i ]),则交换它们,直到序列比较完。执行这样的一次 操作称为“一趟冒泡”。 ...

2019-10-24 13:27:48

内部排序 ----》插入排序:查找待插入位置 + 移动待插入位置之后的元素 + 插入数据

》》插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按其关键字 大小插入到前面已经排好序的子序列中,直到全部记录插入完成。1、直接插入排序 》》直接插入排序进行的两项工作: 1)、从前面有序的子表中查找出待插入元素应该被插入的位置 2)、给插入位置腾出空间,将待插入元素...

2019-10-22 18:59:29

排序的定义

1、 》》排序:就是重新排序列表中的元素,使表中的元素满足按关键字递增或递减的过程。为了 查找方便,通常要求计算机中的表是按关键字有序的。 》》算法的稳定性:如果待排序表中有两个元素 A和 B ,其对应的关键字 A1 = B1 ,且在排序前 A在 B的前面,如果使用某一个算法排序后,A仍然在 B的前面,则称这个排序算法是稳定的...

2019-10-19 16:12:55

字符串模式匹配 ---- 简单的模式匹配算法

1、简单的模式匹配算法 》》串的模式匹配,是求第一个字符串(模式串)在第二个字符串(主串)中的位置。 》》一种简单的模式匹配算法:从主串 S指定的字符开始(一般为第一个)和模式串 T的第一个字符比较, 若相等,则继续逐个比较后续字符,直到 T中的每个字符依次和 S中的一个连续的字符序列相等,则 称匹配成功;如果比...

2019-10-19 13:49:03

散列(hash) 表

1、 》》散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为 Hash(key)=Addr , ###散列函数可能会把两个或者两个以上的不同关键字映射到同一地址,称这种情况为“冲突”, 这些发生碰撞的不同关键字称为同义词。 ###一方面好的散列函数应尽量减少冲突的出现;另一方...

2019-10-19 08:49:33

B+树的基本概念

1、 》》 B+树是应数据库所需而出现的一种 B树的变形树。 》》一棵m阶的 B+树需要满足下列条件: 1)、每个分支结点最多有m棵子树(子结点) 2)、非叶根结点至少有两棵子树,其他每个分支结点至少有棵子树 3)、结点的子树个数与关键字个数相等 4)、所有叶结点...

2019-10-16 19:51:01

B树及其基本操作

1、 》》 B树,又称为“多路平衡查找树 ” , B树中所有结点的孩子结点数的最大值称为 B树的阶, 通常用m表示。 》》一棵m阶B树或为空树,或为满足如下特性的m叉树: 1)、树中每个结点至多有m棵子树(即至多含有 m-1个关键字) 2)、若根结点不是终端结点,则至少有两棵子树 ...

2019-10-16 14:45:31

分块查找(索引顺序查找)

1、 》》分块查找,又称为“索引顺序查找 ” ,吸取了“ 顺序查找 ”和 “ 折半查找 ”各自的优点,既有 动态结构,又适合于快速查找。 》》分块查找的基本思想:将查找表分为若干个子块。块内的元素可以无序,但是块之间是有序的, 即第一个块中的最大关键字小于第二个块中的所有记录的关键字,第二个块中的最大关键字小于 第三...

2019-10-16 12:30:23

折半查找(二分查找)

1、 》》折半查找,又称为“二分查找 ” ,它仅适用于 “有序的顺序表” 。 》》基本思想:首先将给定值 key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该 元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分中 (例如,在查找表升序排列时,若给定值 key大于中间元素的关键字,则所...

2019-10-16 11:53:48

顺序查找

1、一般线性表的顺序查找 》》基本思想:从线性表的一端开始,逐个检查关键字是否满足给定的条件。若查找到 某个元素的关键字满足给定条件,则查找成功,返回该元素在线性表中的位置; 若已经查找到表的另一端,还没有查找到符合给定条件的元素,则返回查找失败 的信息。 》》下面的简单的...

2019-10-16 09:46:03

查找的基本概念

1、 》》查找:在数据集合中寻找满足某种条件的数据元素的过程称为查找。 》》查找的结果一般分为两种:查找成功,即在数据集合中找到了满足条件的数据元素; 查找失败 》》查找表(查找结构):用于查找的数据集合称为查找表,它由同一类型的数据元素 (...

2019-10-16 09:09:49

图的应用 --- 关键路径

1、 》》在带权有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销, 则称这种有向图为用边表示活动的网络,简称为 AOE网。 》》 AOE网具有以下两种性质: 1)、只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表活动才能开始 2)、只有在进入某一顶点...

2019-10-13 21:24:30

图的应用 ---- 拓扑排序【有向无环图的顶点组成的序列】

1、 》》有向无环图【DAG图】:一个有向图中不存在环,则称为有向无环图。 》》 AOV网:如果用 DAG图表示一个工程,其顶点表示活动,用有向边 < Vi , Vj > 表示活动 Vi必须先于活动 Vj进行,将这个种有向图称为顶点表示活动的 网络,记为 AOV网。 在 AOV 网...

2019-10-13 20:56:51

图的应用 ---- 最短路径

1、 》》广度优先搜索查找最短路径只是对无权图而言的,若图是带权图,则把从一个顶点 V0到图中 其余任一个顶点 Vi的一条路径(可能不止一条)上所经过边上的权值之和定义为该路径的带权 路径长度,把带权路径长度最短的那条路径称作最短路径。 》》求解最短路径的算法通常都依赖于一种性质:两点之间的最短路径也包含了路径上其他顶点间 ...

2019-10-13 18:41:31

图的应用 ---- 最小生成树(Minimum-Spanning-Tree,MST)--- prim + Kruskal

1、 》》一个连通图的生成树:图的极小连通图,它包含图中的所有顶点,并且只含尽可能少的边。 这意味着对于生成树来说,若砍去边的一条边,就会使生成树变成非连通图;若给它增加一条边, 就会形成图中的一条回路。 》》对于一个带权连通无向图 G = ( V , E ) ,生成树不同,每棵树的权(即树中所有边上的权值 ...

2019-10-13 15:31:15

图的遍历 --- 广度优先搜索【借助队列实现】 + 深度优先搜索【借助递归栈】

1、 》》图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问 一次且仅访问一次。 注意:树是一种特殊的图,所以树的遍历实际上也可以看作是一种特殊的图的遍历。 》》 图的遍历是图的一种最基本的操作,其他许多操作都是建立在图的遍历操作基础之上。 》》图的遍历主要有两种算法:广度优先搜...

2019-10-09 14:51:17

图的存储及基本操作 ---- 邻接多重表【无向图的一种链式存储结构】

1、 》》邻接多重表是无向图的另一种链式存储结构。 》》 在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或者 需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。 》》在邻接多重表中,每一条边用一个结点表示,其结构如下图: 说明1: 边的结点 ...

2019-10-09 10:59:35

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。