第二学期的数据结构C语言代码
-
数据：描述客观失误的数值、字符、以及能输入机器且能被储存的各种符号集合
-
数据元素：组成数据的基本单位，是数据集合的个体
-
数据对象：数据对象是性质相同的数据元素的集合,是数据的一个子集。
-
数据结构：数据结构是指相互之间存在一种或多种特定关系的数据元素集合
-
数据类型：数据类型是一-组性质相同的值集合以及定义在这个值集合上的--组操作的总称。
-
抽象数据类型
-
数据的抽象
-
抽象数据类型ADT（abstract data type），包括数据对象、数据元素间的结构关系、操作三部分
-
最重要的特点：数据抽象和信息隐蔽
-
特征：使用与实现分离,实现封装和信息隐蔽,也就是说,在抽象数据类型设计时,类型的定义与其实现分离。
-
-
逻辑结构：
- 集合结构
- 线性结构
- 树状结构
- 图状/网状结构
-
存储结构：
- 顺序存储（顺序映像）
- 非顺序存储（非顺序映像）
-
特征：
- 有限性
- 确定性
- 可行性
- 输入
- 输出
-
（1，2，3为最基本）
-
要求：
- 正确性
- 可读性
- 健壮性（鲁棒性）
- 高效率，低存储
-
语句频度：一个语句重复执行的次数。一个算法的时间耗费就是算法中所有语句频度之和
-
时间复杂度：算法中语句总执行次数f(n)和问题规模n的关系（仅关注数量级）
-
渐进时间复杂度：和时间复杂度往往不加区分
-
常见时间复杂度：
$O(1), O(n) , O(n^2), O(n^3) , O(2^n) , O(log_{2}n), O(log_{2}n)$ -
最坏时间复杂度：时间复杂度一般指最坏时间复杂度
- 结构化程序设计
-
目的：以程序良好的静态结构来保证程序动态执行的正确性
-
方法：
- 自顶向下，逐步求精
- 独立功能，一个入口，一个出口
- 仅用三种基本控制结构
-
-
面向对象 = 对象 + 类 + 继承 + 通信
-
面向对象的概念
-
对象：在应用事件中出现的各种实体、事件、规格说明，由一组属性和这组值上的一组服务构成的,其中属性值确定了对象的状态。
-
类:把具有相同属性和服务的对象归到同一类,而把一个类中的每一个对象称为该类的一个实例,它们具有相同的服务。
-
继承:面向对象方法的最有特色的方面。
-
各个类的对象间通过消息进行通信。
-
-
面向对象程序设计的特点是封装性(Encapsulation),继承性(Inheritance)和多态性( Polymorphism)。可以看出,与数据结构密切相关的是定义在数据结构上的一组操作。操作的种类和数目不同,即使逻辑结构相同,这个数据结构的用途也可能大不相同。定义在数据结构上的操作的种类是没有限制的,可以根据具体需要而定义。
-
基本操作主要为：插入，删除，更新，查找，排序。操作可以分为两类：加工型（改变结构的值），引用型（不改变值）
-
面向对象的开发方法首先着眼于应用问题所涉及的对象，包括对象、对象属性、要求的操作，从而建立对象结构和为解决问题需要执行的事件序列,据此建立类的继承层次结构,通过各个类的实例之间的消息连接实现所需的功能。类的定义充分体现了抽象数据类型的思想,基于类的体系结构可以把对程序的修改局部化,如果系统功能的需求发生变化，只需修改类中的服务即可,此时类所代表的对象基本不变,从而确保系统不致因修改而退化。
-
基本原则：分解，抽象，信息隐藏
-
一个抽象数据类型确定了一个模型，但是隐藏实现细节
定义一组运算，但是隐藏运算的实现过程
-
特点：一个前驱，一个后继，一对一的关系
-
单链表
- 插入可头插法/尾插法
-
循环链表
- 判断是否尾节点：p!=L或p->next!=L
-
双向链表
-
静态链表：
- 每个节点有两个域：data域和cursor域。其中，cursor存放游标而不是指针，游标存放后继节点的标号
-
基于时间、空间的需求，灵活选择
-
一维
- Loc( A[ i ] ) = Loc( A[ 1 ]) + ( i - 1 ) * size
-
二维
- Loc( A[ i ] [ j ]) = Loc( A[ 1 ] [ 1 ]) + ( ( i - 1 ) * n + j - 1 ) * size
-
三维
- Loc( A[ i ] [ j ] [ k ]) = Loc( A[ 1 ] [ 1 ] [ k ]) + ( ( i - 1 ) * m * n + ( j - 1 ) * n + k -1) * size
-
三角矩阵
- 只存储上/下三角
-
带状矩阵
- 所有非零元都在以主对角线的为中心的带状区域
- 压缩存储原则：计算位置，将非零元按照行序存储
-
稀疏矩阵
- 大多数元素为0
- 三元组表示法
- 存储行、列、值
-
二维数组，略
-
列序递增转置
-
【算法思想】采用按照被转置矩阵三元组表A的列序(即转置后三元组表B的行序)递增的顺序进行转置,并依次送入转置后矩阵的三元组表B中,这样一来,转置后矩阵的三元组表B恰好是以“行序为主序”的。
-
【具体做法】
找出第一行全部元素:第一遍从头至尾扫描三元组表A,找出其中所有col找出第1行全部元素:第一遍从头至尾扫描三元组表A,找出其中所有col
找出第二行全部元素:第二遍从头至尾扫描三元组表A,找出其中所有col为2的三元组,转置后按顺序送到三元组表B中。
以此类推,找出第k行全部元素:第k遍扫描三元组表A,找出其中所有col为h的三元组,转置后按顺序送到三元组表B中。
k的取值:1≤k≤A.n。
为实现处理附设一个当前存放位置计数器j,用于指向当前转置后元素应放入三元组表B中的位置下标。j初值为1,当处理完一个元素后, j加1。 -
时间复杂度：O( A.len * A.n )
-
-
一次定位快速转置法。
-
【算法思想】 在列序递增转置中,为了使转置后矩阵的三元组表B仍按行序递增存放,必须多次扫描被转置矩阵的三元组表A,以保证按被转置矩阵列序递增形式进行转置,因此要通过双重循环来完成。要改善算法的时间性能,必须去掉双重循环,使整个转置过程通过一重循环来完成,即只对被转置矩阵的三元组表A扫描一次,就使A中所有非零元的三元组"1次定位",直接放到三元组表B的正确位置上。为了能将被转置三元组表A中的元素一次定位到三元组表B的正确位置上,需要预先计算以下数据:
1. 待转置矩阵三元组表A每一-列中非零元素的总个数,即转置后矩阵三元组表B的每一行中非零元素的总个数。
2. 待转置矩阵每-.列中第一个非零元素在三元组表B中的正确位置，即转置后矩阵每一行中第-1个非零元素在三元组表B中的正确位置。
为此,需要设两个数组分别为num[ ]和position[ ],其中num[col]用来存放三元组表A第col列中非零元素总个数(三元组表B第col行中非零元素的总个数), position[col]用来存放转置前三元组表A中第col列(转置后三元组表B中第col行)中第一个非零元素在三元组表B中的存储位置(下标值)。num[col]的计算方法是,将三元组表A扫描一遍,对于其中列号为col的元素，给相应的num数组中下标为col的元素加1。
说明:在num[col]的计算中,采用了“数组下标计数法”。
position[col]的计算方法如下:
position[1]=1,表示三元组表A中,列值为1的第一个非零元素在三元组表B中的下标值。
position[col] = position[col-1] +num[col-1],其中2≤col≤A.n。 -
【具体做法】position[ col ]的初值为三元组表A中第col列(三元组表B的第col行)中第一个非零元素的正确位置,当三元组表A中第col列有一个元素加人到三元组表B时,则position[ col] = position[ col]+1,即令position[ col ]始终指向三元组表A中第col列中下一个非零元素在三元组表B中的正确存放位置(下标值)。
-
时间复杂度：O(A.len + A.n)
-
略
-
后进先出（LIFO），last_in_first_out
-
顺序栈：
- top == -1表示空
- 双端栈：栈底不变，栈顶相互正对（底在两边，顶在中间）
-
链栈
-
栈和递归
-
递归进层(i->i+1层)系统需要做三件事:
-
保留本层参数与返回地址
-
为被调用函数的局部变量分配存储区,给下层参数赋值
-
将程序转移到被调函数的人口。
-
-
而从被调用函数返回调用函数之前，递归退层(i<-i+1层)系统也应完成三件工作:
-
保存被调丽数的计算结果
-
释放被调函数的数据区,恢复上层参数。
-
依照被调函数保存的返回地址,将控制转移回调用函数。
-
-
当递归函数调用时,应按照“后调用先返回”的原则处理调用过程,因此上述函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时,就为它在栈顶分配-一个存储区,而每当从一个函数退出时,就释放它的存储区。显然,当前正在运行的函数的数据区必在栈顶。
-
一个递归函数的运行过程中,调用函数和被调用函数是同一个函数,因此,与每次调用时相关的一个重要的概念就是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层,则从主函数调用递归函数为进入第1层;从第i层递归调用本函数为进入“下一层”,即第i+1层。反之,退出第i层递归应返回至“上一层”,即第i-1层。为了保证递归函数正确执行,系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个工作记录,其中包括所有的实在参数、所有的局部变量以及上-一层的返回地址。每进入一层递归,就产生一个新的工作记录压人栈顶。每退出一层递归,就从栈顶弹出一个工作记录。因此当前执行层的工作记录必为递归工作栈栈顶的工作记录,称这个记录为活动记录,并称指示活动记录的栈顶指针为当前环境指针。由于递归工作栈是由系统来管理的，无须用户操心,所以用递归法编制程序非常方便。
-
递归转换非递归
-
单向递归：
单向递归是指递归函数中虽然有一处以上的递归调用语句,但各次递归调用语句的参数只和主调用函数有关,相互之间参数无关,并且这些递归调用语句处于算法的最后。 -
尾递归：
尾递归是指递归调用语句只有一个,而且是处于算法的最后,尾递归是单向递归的特例。
-
-
-
先进先出（FIFO），first_in_first_out
-
允许插入的一端：队尾
允许删除的一端：队头 -
链队列：
-
队头：front
队尾rear -
入队关键代码：
NewNode->data= x ; NewNode->next= NULL; Q->rear->next= NewNode; Q->rear= NewNode;
- 出队关键代码：
p=Q->front-> next; Q->front->next=p->next; / *队头元素p出队*/ if( Q->rear==p) / *如果队中只有一个元素p,则p出队后成为空队*/ Q->rear=Q->front; * x=p->data; free(p);
-
-
循环队列：
- 初始化：front=rear=0
- 入队
rear = (rear+1) mod MAXSIZE;
- 出队
front = (front+1) mod MAXSIZE;
- 队满
(rear+1) mod MAXSIZE == frontc
- 队空
rear == front
-
结点的度:一个结点的子树个数称为此结点的度。
-
叶结点:度为0的结点,即无后继的结点,也称为终端结点。
-
分支结点:度不为0的结点,也称为非终端结点。
-
结点的层次:从根结点开始定义,根结点的层次为1, 根的直接后继的层次为2,以此类推。
-
结点的层序编号:将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列,依次给它们编以连续的自然数。
-
树的度:树中所有结点的度的最大值。
-
树的高度(深度):树中所有结点的层次的最大值。
-
有序树:在树T中,如果各子树T之间是有先后次序的，则称为有序树。
-
森林:m(m≥0)棵互不相交的树的集合。将一棵非空树的根结点删去,树就变成一个森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。
-
同构:对两棵树,通过对结点适当地重命名,就可以使两棵树完全相等(结点对应相等,对应结点的相关关系也相等) ,则称这两棵树同构。
-
兄弟结点:同一双亲结点的孩子结点之间互称兄弟结点。
-
堂兄弟:父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。
-
祖先结点:一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。
-
子孙结点:一个结点的直接后继和间接后继称为该结点的子孙结点。
-
前辈:层号比该结点小的结点,都称为该结点的前辈。
-
后辈:层号比该结点大的结点,都称为该结点的后辈。
-
二叉树的第i层至多有
$2^{i-1}$ 个节点（i≥1） -
深度为k的二叉树至多有
$2^k-1$ 个节点（k≥1） -
若终端节点树为
$n_{0}$ ,而度数为2的节点数为$n_{2}$ ,则$n_{0} = n_{2} + 1$ -
由遍历序列唯一确定一颗二叉树，必须为中序遍历和先/后序遍历共同确定，先序和后序不行
-
树的先根遍历<-->对应二叉树的前序遍历
-
书的后根遍历<-->对应二叉树的中序遍历
- 定义：深度为k的二叉树，且有
$2^k-1$ 个节点 - 顺序表示：从根开始，层次贱从上至下、层次内从左到右编号
- 定义：深度为k，节点数为n的二叉树，其节点1
n的位置序号分别于等高的满二叉树的节点1n的序号一一对应 - 性质：对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号,则对于任意的序号为i的结点有:
-
如 i=1 ,则序号为 i 的结点是根结点, 无双亲结点; 如 i>1 ,则序号为i的结点的双亲结点序号为 i/2
-
如 2i>n ,则序号为 i 的结点无左孩子; 如 2i≤n ,则序号为i的结点的左孩子结点的序号为 2i。
-
如 2i+1>n ,则序号为 i 的结点无右孩子; 如 2i+1≤n ,则序号为i的结点的右孩子结点的序号为 2i+1。
-
- 存储结构
- 顺序存储（仅针对完全二叉树）
- 链式存储
- 存储方法（教材P181-182）
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
-
Ltag/Rtag = 0 ：指针域指向左/右孩子
-
Ltag = 1 ：指针域指向节点的遍历前驱
-
Rtag = 1 ：指针域指向节点的遍历后继
注：遍历前驱/后继，指的是在遍历（打印）时该节点的前/后一个节点，而非逻辑结构上的前驱/后继
-
节点的带权路径长度：从树根到某节点的路径长度乘上节点的权重。
-
树的带权节点权重：所以 叶子 节点的带权路径和
-
霍夫曼树：n个带权叶子节点的构成的所有二叉树中带权路径长度最短的二叉树（也称最优二叉树）
-
构建过程：
-
初始化:用给定的n个权值{w1,w2,... ,wn}构造n棵二叉树并构成的森林F={T1,T2,T3,Tn},其中每棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点,其左、右子树为空。
-
找最小树:在森林F中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左、右子树的根结点权值之和。
-
删除与加入:从F中删除被选中的那两棵二叉树,同时把新构成的二叉树加人到森林F中。
-
重复，直到森林只有一棵树
- 简而言之，先选择权小的,所以权小的结点被放置在树的较深层,而权较大的离根较近,故在哈夫曼树中权越大叶子离根越近，这样一来,在计算树的带权路径长度时,自然会具有最小带权路径长度,这种生成算法就是一种典型的贪心法。
-
-
前缀编码：任何一个编码不是另一个编码的前缀
-
哈夫曼编码：
- 创建Huffman编码:左子树为1, 右子树为0, 从根节点到该节点的数字连起来(二进制)就是对应的编码.
- 哈夫曼编码是前缀编码
- 编码中1的个数等于路过的路径数
-
顶点 Vertex
-
弧 Arc <u , v> ：从u到v的弧。u：弧尾；v：弧头
-
边 Edge
-
入度：ID(v) ; 出度：OD(v) ; 度：TD(v)
-
邻接矩阵
-
无向图只用压缩存储一个三角矩阵即可
-
有向图要全部存储
-
-
邻接表P219
-
表头结点表：由所有表头结点以顺序结构(向量)的形式存储,以便可以随机访问任一顶点的边链表。表头结点由两部分构成,其中数据域vexdata用于存储顶点的名或其他有关信息;链域firstarc用于指向链表中第一个顶点(即与顶点$v_{i}$邻接的第一个邻接点)
-
边表：由表示图中顶点间邻接关系的n个边链表组成。边链表中结点的结构由三部分组成,其中邻接点域adjvex用于存放与顶点$v_{i}$相邻接的顶点在图中的位置;链域nextarc用于指向与顶点$v_{i}$相关联的下一条边或弧的结点;数据域info用于存放与边或弧相关的信息(如赋权图中每条边或弧的权值等)。
-
-
十字链表(OrthogonalList)P221
- 有向图的另一种链式存储结构,可以把它看成是将有向图的邻接表和逆邻接表结合起来的一种链表。有向图中的每一条弧对应十字链表中的一个弧结点,同时有向图中的每个顶点在十字链表中对应有一个结点,称为顶点结点。
-
简单路径
-
遍历 P225-231
-
广度优先（队列）
-
深度优先（栈）
-
-
生成树和最小生成树
-
概念：
-
生成树：一个连通图的生成树是指一个极小连通子图,它含有图中的全部顶点,但只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边,必定构成一个环,这是因为该条边使得它依附的两个顶点之间有了第二条路径
-
最小生成树：各边的代价之和最小的生成树（MST)
-
-
算法：
-
Prim普里姆算法(最小生成树，加点法)
-
假设N=(V,{E})是连通网，TE是最小生成树中边的集合
-
初始U={u0}（u0属于V），TE为空集
-
在所有的u属于U，v属于V-U的边中选一条代价最小的边放进TE，v0放进U
-
重复(2)直到U=V
- 此时，TE中有n-1条边，则T必然是N的最小生成树
-
-
算法步骤：
-
初始顶点u加入集合U，剩余的每个顶点i，将CloseEdge[i]初始化为i到u的边信息
-
循环n-1次：
-
从各组最小边CloseEdge[]里选择最小的最小边ClodeEdge[v]（v属于V-U）
-
v加入U
-
更新剩余节点的最小边信息CloseEdge[i]（i属于V-U）
-
-
-
-
kruskal克鲁斯卡尔算法（加边法）：
-
找最小生成树（各边代价之和最小的生成树（连通子图））
-
将n个顶点看成n个集合
-
按照权值由小到大选择边，满足：边的两端点在不同集合中。将该边放到生成树的边集合里，合并该边的端点集合
-
重复(2)。直到只有一个顶点集
-
（注意：加边不能形成回）
-
更适合于稀疏的连通图
-
-
-
-
-
有向无环图的应用：《数据结构》P243-249
-
拓扑排序：
-
概念：
-
AOV-网：用顶点表示活动的网。用顶点表示活动，弧表示活动间优先关系
-
拓扑序列：先后关系的序列（可能不唯一）
-
-
思想：
-
选取无前驱的节点并记录此节点
-
删除此节点和相连的边
-
重复，直到不存在没有前驱的节点
-
若此时记录的节点小于总节点数，说明有环。否则记录的是一个拓扑排序
-
-
基于邻接矩阵G的算法：
-
第一个序号k=1
-
找一个未新编号且值全为0的列。若找到，继续(3);否则，若所有列都已经编号，排序结束，若还有列没有编号，则存在回路
-
输出(2)找到的列对应的顶点j，把新序号k赋给(2)中找到的列
-
j对应的行全部置为0
-
序号k++，转(2)
-
-
基于邻接表G的算法：
-
查找indegree[i]为0的顶点i
-
对链在i后面的所有邻接顶点j，对应的indegree[j]减一
-
为避免重复检测入度为0的点，设一辅助栈S，将入度为0的顶点入栈。
-
只要栈不空，重复：{栈顶元素i出栈并打印 -> i的每个邻接点k的入度减1，若k入度变为0，k入栈}
-
-
-
关键路径
-
概念：
-
AOE-网：边表示活动的网。用顶点表示时间，边的权值表示所需时间（记顶点为v，边为a，即通常事件为v，活动为a）
-
源点：唯一的、入度为0的节点
-
汇点：唯一的、出度为0的节点
-
关键路径：从源点到汇点的最长路径长度即是完成活动所需的总时间
-
关键活动：关键路径上的活动
-
事件v的最早发生时间：源点到v的最长路径长度
-
事件v的最晚发生时间（在保证汇点最早发生的前提下）：从汇点开始，逆拓扑顺序向源点递推
-
活动a开始的最早时间：从源点到弧a的始点最长路径
-
活动a开始的最晚时间：倒推
-
活动a松弛时间（时间余量）：a的最早开始时间与最晚开始时间之差
-
-
关键路径步骤：
-
进行拓扑排序，排序时按照拓扑序列求出每个事件的最早发生时间ve(i)（程序如上）
-
按照逆拓扑序列求出事件最晚发生时间vl(i)
-
求出每个活动a(i)的最早开始时间e(i)和最晚发生时间l(i)
-
e(i)=l(i)为所求
-
-
算法思想：(部分功能已在TopOrder实现)
-
求出各个顶点入度，入度为0则入栈S
-
初始化各顶点最早发生时间为ve[i]=0
-
当栈S不空，重复：
-
S栈顶元素j出栈，并压入T（生成逆拓扑序列）
-
对链在j后面的所有邻接顶点k，对应的indegree[k]减一。若此时入度为0，则对应节点入栈S
-
根据顶点j的最早发生时间和ve[j]和弧<j,k>的权值，更新k的最早发生时间
-
-
-
-
-
最短路径
-
迪杰斯特拉算法
-
求给定顶点到其他顶点的最短路径
-
时间复杂度：O(
$n^3$ ) -
空间复杂度：O(n)
-
操作：
-
对图G={V,|E|}，将顶点分为两组：
第一组S：已经求出的最短路径的终点集合（开始为{v0}）；
第二组V-S：尚未求出最短路径的集合（开始为V-{v0}的全部节点） -
按照长度递增顺序，把第二组的加进第一组，即先把最短的加进第一组，直到加完
-
-
-
弗洛伊德算法
- 从任意顶点到其他顶点的最短路径
- 时间复杂度：O(
$n^3$ ) - 空间复杂度：O(
$n^2$ ) //用了一个二维数组 - 操作：
- 将
$v_{i}$ 到$v_{j}$ 的最短的路径长度初始化为g.arcs[i][j].adj,然后进行如下n次比较和修正:-
$v_{i}$ 与$v_{j}$ 间加入顶点$v_{0}$,比较($v_{i}$ ,$v_{0}$ ,$v_{j}$ )的路径长度,取其中较短的路径作为$v_{i}$到$v_{j}$的且中间顶点号不大于0的最短路径。 - 在
$v_{i}$ 与$v_{j}$ 间加入顶点$v_{1}$,得到($v_{i}$ , ... ,$v_{1}$ ) 和 ($v_{1}$ ,...,$v_{j}$),其中($v_{i}$ , ... ,$v_{1}$ )是$v_{i}$ 到$v_{1}$ 的且中间顶点号不大于0的最短路径,($v_{1}$ , ... ,$v_{j}$ )是$v_{1}$ 到$v_{j}$ 的且中间顶点号不大于0的最短路径,这两条路径在上一步中已求出。将($v_{i}$ , ... ,$v_{1}$ , ...,$v_{j}$)与上一步已求出的$v_{i}$到$v_{j}$中间顶点号不大于0的最短路径比较,取其中较短的路径作为$v_{i}$到$v_{j}$的且中间顶点号不大于1的最短路径。 - 在n,与v,间加人顶点$v_{2}$得(
$v_{i},...v_{2}$ )和($v_{2}$ , ...$v_{j}$ ), 其中($v_{i},...v_{2}$ )是$v_{i}到v_{2}$的且中间顶点号不大于1的最短路径, ($v_{2}$ , ...$v_{j}$ )是$v_{2}$到$v_{j}$的且中间顶点号不大于1的最短路径,这两条路径在上一步中已求出。将(v_{i}, .... v_{2}, ... v_{j})与上一步已求出的$v_{i}$ 与$v_{j}$ 且中间顶点号不大于1的最短路径比较,取其中较短的路径作为$v_{i}$ 到$v_{j}$ 的且中间顶点号不大于2的最短路径。 - 以此类推，经过n次比较和修正,在第n-1步,将求得$v_{i}$ 到
$v_{j}$ 的且中间顶点号不大于n-1的最短路径,这必是从$v_{i}$ 到$v_{j}$ 的最短路径。
-
- 图g中所有顶点偶对$v_{i}$ 与
$v_{j}$ 间的最短路径长度对应一个n阶方阵D。在上述n+1步中,D的值不断变化,对应一个n阶方阵序列。 - 定义:n阶方阵序列$D^{-1}, D^0, D^1, ... D^n$, 其中，
$D^{-1}$ [i][j]=g.arcs[i][j].adj$D^k$ [i][j]=Min{$D^{k-1}$ [i][j],$D^{k-1}$ [i][k] +$D^{k-1}$ [k][j] } ,0≤k≤n-1 - 显然,$D^{N-1}$中为所有顶点偶对
$v_{i}$ 与$v_{j}$ 间的最终最短路径长度。
- 将
-
注：本文内容是以流行的观点（特别是C++的STL）来看的。
- 简而言之，容器是存储、管理数据（集合）的一种机制。
- 容器相关的常见操作（接口）有：
- 容器的建立（初始化） initialization
- 插入元素 insertion
- 删除元素 deletion
- 查询 find
- 遍历 traverse
- 统计元素个数 count
- 检查容器是否为空 empty
- 常用的容器有：
- 双向链表（链式存储） list
- 双端队列（顺序存储） deque //Double Ended Queue的非正规缩写
- 向量 vector
- 数组（经过包装而非原生的） array
- 集合 set
- 映射 map
-
简而言之，容器适配器是依附于别的容器、能转换该容器接口的、适用于特殊场合的“容器”。
-
容器适配器不是一种容器的实现，而是对已有容器的包装。即是说，容器适配器的内部有一个容器对象（称为“基础容器”，underlying container），适配器使用这个容器来管理数据集合。
-
容器适配器的接口是对对应基础容器接口的包装（wrapper），即容器适配器要将操作转发给容器。反过来，为达到次目的，容器必须提供足够的接口。
-
常见的容器适配器有这些：
-
栈 stack
-
队列 queue
以上两种适配器的默认基础容器是双端队列deque。
-
-
适配器依赖的容器是可以替换的。你可以用自己编写的、符合规范的容器取替换默认的基础容器。例如，你可以用一个链表代替双端队列。
-
这里以stack为例来说明情况。
- stack的基础容器默认为双端队列deque。“双端”意味着，deque可以在前、后两端插入和删除数据。
- deque的接口
- push_front()：在队列前端插入数据
- push_back()：在队列后端插入数据
- pop_front()：删除队列最前端的数据
- pop_back()：删除队列最后端的数据
- front()：获取队列最前端的数据
- back()：获取队列最后端的数据
- empty()：判断队列是否为空
- stack的接口
- 内部有一个deque对象，既定为c
- push()：压栈，一般调用c的push_back()
- pop()：弹栈，一般调用c的pop_back()
- top()：取栈顶数据，一般调用c的back()
- empty()：调用c的empty()
- 子串在主串中的位置以子串的第一个字符在主串位置表示
-
Brute-Force算法（暴力匹配） 略
-
KMP算法
-
堆串存储方法
- 以一组地址连续的存储单元顺序存放串中的字符,但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间,每当建立一个新串时,系统就从这个空间中分配一个大小和字符串长度相同的空间用于存储新串的串值。
-
串名符号表:
- 所有串名的存储映像构成一个符号表。借助此结构可以在串名和串值之间建立一个对应关系,称为串名的存储映像。
- 结点大于1：当BLOCK_SIZE大于1时,每个结点存放多个字符,当最后一个结点未存满时，不足处可用特定字符(如#)补齐。虽然存储密度相对结点大小等于Ⅰ的存储方法来说,存储密度较高,但此时插人﹑删除的处理方法比较复杂,需要考虑结点的分拆和合并。
-
列表:由同- -类型的数据元素(或记录)构成的集合，可利用任意数据结构实现。
-
关键字:数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯-标识列表中的一一个数据元素,则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时,数据元素的值就是关键字。
-
查找:根据给定的关键字值,在特定的列表中确定-一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素,则称查找是成功的,否则称查找是失败的，此时应返回空地址及失败信息,并可根据要求插人这个不存在的数据元素。
-
对于表的查找，一般有两种情况,一种是静态查找,指在查找过程中只是对数据元素进行查找;另一种是动态查找,指在实施查找的同时,插人找不到的元素,或从查找表中删除已查到的某个元素,即允许表中元素变化。
-
查找算法中涉及的三类参量:
- 查找对象K(找什么)
- 查找范围L(在哪找)
- K在L中的位置(查找结果)。
- 其中1，2为输人参量,3为输出参量,在函数中，输人参量必不可少,输出参量也可用函数返回值表示。
-
平均查找长度:为确定数据元素在列表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度。对于长度为n的列表,查找成功时的平均查找长度为（P：访查找某元素的概率；C：查找到该元素时已经比较的次数）$$ASL = \Sigma P_{i}*C_{i}$$
-
比较查找法
- 基于线性表
- 顺序查找法
- 折半查找法
- 分块查找法
- 基于树
- 基于线性表
-
计算查找法
- 也称哈希查找法
-
顺序查找法：
-
常常设置监视哨 r[0] 存放要查找的关键字，从表的另一端开始查找，可以起到防止越界的作用
-
ASL =
$\dfrac{n+1}{2}$
-
-
折半查找法（二分查找）
-
条件：
- 顺序存储结构
- 关键字有序排列
-
用平均查找长度(ASL)分析折半查找算法的性能。半查找过程可用二叉判定树的描述,判定树中每- -结点对应表中一个记录，但结点值不是记录的关键字,而是记录在表中的位置序号。根结点对应当前区间的中间记录,左子树对应前一子表,右子树对应后一子表。显然,找到有序表中任一记录的过程,对应判定树中从根结点到与该记录相应的结点的路径,而所做比较的次数恰为该结点在判定树上的层次数。因此,折半查找成功时,关键字比较次数最多不超过判定树的深度。查找成功时平均查找长度为：$$ASL_{bs} = \dfrac{n+1}{n}log_{2}(n+1) - 1$$$$\approx log_{2}(n+1)-1$$
-
-
分块查找：
-
准备步骤：
-
首先将列表分成若千个块(子表)。一般情况下，块的长度均匀,最后一块可以不满。每块中元素任意排列,即块内无序,但块与块之间有序。
-
构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置,以及每块中的最大关键字(或最小关键字)。索引表按关键字有序排列。
-
-
过程：
-
将待查关键字k与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。
-
进一步用顺序查找法,在相应块内查找关键字为k的元素。
-
-
分块查找的平均查找长度由两部分构成,即查找索引表时的平均查找长度为$L_{B}$,以及在相应块内进行顺序查找的平均查找长度$L_{W}$$$ASL_{bs} = L_{B} + L_{W}$$假设表长为n，分为b块，每块含s个元素，查找每个元素的概率相等，则$$ASL_{bs} = log_{2}(b+1) -1+\dfrac{s+1}{2}$$$$\approx log_{2}(\dfrac{n}{s} + 1) + \dfrac{s}{2}$$
-
-
二叉排序树
-
概念：
- 二叉排序树又称为二叉查找树,它是一种特殊的二叉树。其定义为:二叉树排序树或者是一棵空树,或者是具有如下性质的二叉树：
-
若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
-
若它的右子树非空,则右子树上所有结点的值均大于(或大于等于)根结点的值;
-
它的左右子树也分别为二叉排序树.
-
- 二叉排序树又称为二叉查找树,它是一种特殊的二叉树。其定义为:二叉树排序树或者是一棵空树,或者是具有如下性质的二叉树：
-
创建二叉排序树的时间复杂度：$O(nlog_{2}n)$
-
二叉排序树平均查找长度：$O(log_{2}n)$
-
删除二叉排序树：
- 删除操作首先查找要删除的结点,看是否在二叉排序树中,若不在则不做任何操作;否则,假设要删除的结点为p,结点p的双亲结点为f,并假设结点p是结点f的左孩子(右孩子的情况类似)。下面分三种情况讨论。
- 若p为叶结点,则可直接将其删:f->lchild=NULL;free(p)。
- 若ρ结点只有左子树,或只有右子树,则可将p的左子树或右子树,直接改为其双亲结点f的左子树。即:f->lchild = p->lchild(或f->lchild =p->rchild) ;free(p)。
- 若p既有左子树,又有右子树,如图8.8 (a)所示。此时有以下两种处理方法：
-
方法1:首先找到p结点在中序序列中的直接前驱s结点，然后将p的左子树改为f的左子树,而将p的右子树改为s的右子树:f->lchild = p->lchild;s->rchild= p->rchild;free(p)
-
方法2:首先找到p结点在中序序列中的直接前驱s结点,然后用s结点的值替代p结点的值,再将s结点删除,原s结点的左子树改为s的双亲结点q的右子树:p->data= s->data;q->rchild = s->lchild;free(s)
-
-
-
平衡二叉排序树：
-
概念：
- 平衡二叉排序树又称AVL树。一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树:
- 左子树与右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉排序树。
- 平衡二叉排序树又称AVL树。一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树:
-
引人平衡二叉排序树的目的,是为了提高查找效率,其平均查找长度为$O(log_{2}n)$
-
结点的平衡因子( Balance Factor)定义为:结点的左子树深度与右子树深度之差。显然,对一棵平衡二叉排序树而言,其所有结点的平衡因子只能是-1、0或1. 当在一个平衡二叉排序树上插入一个结点时,有可能导致失衡,即出现绝对值大于1的平衡因子,如2.-2。
-
失衡的调整：通常，只有新插入节点的祖先节点平衡因子会受影响。这里假设最低层失衡节点为A，A_L, A_R, A_LR, A_RL分别为A的左子树，右子树，左子树的右子树，右子树的左子树, bf为平衡因子,FA为A的父指针.(教材P282-286)
-
LL型:A_L插入新节点后失衡。记B=A_L
-
特征：A->bf = 2, B->bf = 1
A->lchild = B->lchild; B->lchild = A; A->bf = B->bf = 0; if (FA==NULL) t=B; else if(A == FA->lchild) FA->lchild= B; else FA->rchild= B;
-
-
LR型:A_LR插入新节点后失衡。记B=A_L, C=A_LR
-
特征：A->bf = 2, B->bf = -1
B->rchild = C->lchild ; A->lchild = C->rchild; C->lchild = B; C->rchild = A; if (S->key<C->key){/在C下插入S A->bf=-1; B->bf=0; C->bf=0; } else if (S->key>C->key){//在Cp下插入S A->bf=0; B->bf=1; C->bf=0; } else if(S->key==C->key){//C本身就是插入的新结点S A->bf=0; B->bf=0; } if (FA==NULL) t = C; else if(A == FA->lchild) FA->lchild = C; else FA->rchild = C;
-
-
RR型:A_RR插入新节点后失衡。记B = A_R
-
特征：A->bf = -2, B->bf = -1
A->rchild = B->lchild; B->lchild = A; A->bf = 0; B->bf = 0; if (FA == NULL) t = B; else if(A == FA->lchild) FA->lchild = B; else FA->rchild = B;
-
-
RL型:A_RL插入新节点后失衡。记B = A_R, C = A_RL
-
特征：A->bf = -2, B->bf = 1
B->lchild = C->rchild ; A->rchild = C->lchild; C->lchild = A; C->rchild = B ; if(S->key < C->key){//在C下插入S A->bf=0; B->bf=-1; C->bf=0; } else if(S->key > C->key){//在C下插入S A->bf=1; B->bf=0; C->bf=0; } else(S->key==C->key){//C本身就是插入的新结点S A->bf=0; B->bf=0; } if(FA == NULL) t=C; else if(A == FA->lchild) FA->lchild = C; else FA->rchild = C;
-
-
-
-
即哈希查找法。基本思想:首先在元素的关键字h和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为h的元素直接存人地址为H(k)的单元;以后当查找关键字为hi的元素时,再利用哈希函数计算出该元素的存储位置p=H(k),从而达到按关键字直接存取元素的目的
-
构造哈希函数：教材P300-302
- 原则：函数便于计算；计算得到地址分布均匀，冲突少
- 常用方法：
- 数字分析法
- 平方取中法
- 分段叠加法
- 折叠法
- 移位法
- 除留余数法
- 伪随机数法
-
解决冲突：教材P302-304
- 开放定址法（再散列法）
-
$h_{i} = (H(key) + d_{i}) % m , i = 1,2,...,n$
亦即$h_{i} = (h_{0} + d_{i}) % m , i = 1,2,...,n$
- 增量序列d的取法：
- 线性探测再散列:
$d_{i} = 1,2,3...,m-1$ - 二次探测再散列:
$d_{i} = 1^2,-1^2,2^2,-2^2,...k^2,-k^2(k\leq\dfrac{m}{2})$ - 伪随机探测再散列
- 线性探测再散列:
-
- 再哈希法：同时构造多个哈希函数，一个不行换下一个
- 链地址法：构成同义词链的单链表，将表头存储再哈希表的
- 建立公共溢出区：将哈希表分为基本表和溢出表
- 开放定址法（再散列法）
-
装填因子
$\alpha = \dfrac{哈希表中元素个数}{哈希表长度}$
显然，$\alpha$越小，发生冲突的可能越小， -
平均查找长度
方法 线性探测再散列 伪随机探测、二次探测、哈希法 链址法 成功时的ASL $\dfrac{1}{2}(1+\dfrac{1}{1-\alpha})$ $-\dfrac{1}{\alpha}ln(1-\alpha)$ $1+\dfrac{\alpha}{2}$ 失败时的ASL $\dfrac{1}{2}(1+\dfrac{1}{(1-\alpha)^2})$ $\dfrac{1}{1-\alpha}$ $\alpha+e^{-\alpha}$ 哈希表的平均查找长度ASL是装填因子
$\alpha$ 的函数，和待散列元素数目n无关
装填因子通常取0.7-0.8
-
排序：P317
-
内部排序和外部排序
根据排序时数据所占用存储器的不同，可将排序分为两类。一-类是整个排序过程完全在内存中进行,称为内部排序;另一类是由于待排序记录数据量太大,内存无法容纳全部数据,排序需要借助外部存储设备才能完成,称为外部排序。 -
主关键字与次关键字
-
排序的稳定性：排序前后，具有相同关键字值的元素的相对位置不变（即只要值相同，那么若排序A前在B前面，排序后A也在B前面）
-
待排序的记录序列：
- 向量结构
- 链表结构
- 记录向量与地址向量结合（地址排序）
- 基本思想：在一个已排好序的记录子集的基础上，每一步将下一-个待排序的记录有序插入到已排好序的记录子集中,直到将所有待排记录全部插入为止。
-
算法思想：
直接插人排序是一种最基本的插人排序方法,其基本操作是将第i个记录插人到前面i-1个已排好序的记录中； -
直接插入排序法，在待排序的关键字序列基本有序且关键字个数n较少时,其算法的性能最佳。
-
具体过程为：
将第i个记录的关键字$K_{i}$顺次与其前面记录的关键字$K_{i-1},K_{i-2},..., K_{1}$进行比较,将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于$K_{i}$的记录$K_{j}$,此时$K_{j}$后面必为空位置,将第i个记录插入空位置即可。完整的直接插人排序是从i=2开始的，也就是说,将第一个记录视为已排好序的单元素子集合,然后将第二个记录插入到单元素子集合中。i从2循环到n,即可实现完整的直接插入排序。 -
时间复杂度
$O(n^2)$
空间复杂度$O(1)$
-
对于有序表进行折半查找，其性能优于顺序查找。所以,可以将折半查找思想用于在有序记录r[1..i-1]中确定应插人位置,相应的排序法称为折半插人排序法。
-
时间复杂度
$O(n^2)$
空间复杂度$O(nlog_{2}n)$
-
又称缩小增量排序法,是一种基于插入思想的排序方法,它利用了直接插入排序的最佳性质，首先，将待排序的关键字序列分成若干个较小的子序列,对子序列进行直接插入排序,使整个待排序序列排好序。在时间耗费上,较直接插人排序法的性能有较大的改进。然后，在进行直接插人排序时,若待排序记录序列已经有序,直接插人排序的时间复杂度可以提高到O(n)。若待排序记录序列基本有序,即序列中具有下列特性的记录较少时: r[i].key < Max{r[j].key},(1 ≤ j < i),直接插人排序的效率会大大提高。希尔排序正是基于以上两点对直接插人排序进行了改进。
-
算法思想：先将待排序记录序列分割成若干个“较稀疏的"子序列,分别进行直接插人排序。经过上述粗略调整,整个序列中的记录已经基本有序,最后再对全部记录进行一次直接插入排序。
- 首先选定记录间的距离为d,(i=1),在整个待排序记录序列中将所有间隔为$d_{i}$的记录分成一组,进行组内直接插入排序。
- 然后取i=i+1,记录间的距离为
$d_{i} , (d_{i}<d_{i-1})$ ,在整个待排序记录序列中，将所有间隔为$d_{i}$的记录分成一组,进行组内直接插入排序。 - 重复步骤2多次,直至记录间的距离$d_{i}$=1,此时整个只有一个子序列,对该序列进行直接插入排序,完成整个排序过程。
-
时间复杂度
$O(n^{1.5})$ -
不稳定的排序
- 反复扫描，顺次比较，逆序则交换
-
算法思想：从待排序记录序列中选取一一个记录(通常选取第一个记录)为枢轴,其关键字设为$K_{i}$,然后将其余关键字小于$K_{i}$的记录移到前面,而将关键字大于或等于$K_{i}$的记录移到后面,结果将待排序记录序列分成两个子表,最后将关键字为$K_{i}$的记录插到其分界线的位置处。将这个过程称为一趟快速排序。通过一-次划分后,就以关键字为$K_{i}$的记录为界,将待排序序列分成了两个子表，且前面子表中所有记录的关键字均小于$K_{i}$而后面子表中的所有记录的关键字均大于或等于$K_{i}$。对分割后的子表继续按上述原则进行分割,直到所有子表，的表长不超过1为止,此时待排序记录序列就变成了一个有序表。
-
算法步骤：
- 假设待划分序列为r[low], r[low+1], ... ,r[high]。首先将基准记录r[low]移至变量x中,使r[low]相当于空单元,然后反复进行如下两个扫描过程,直到low和high相遇。
- high从右向左扫描,直到r[high].key < x.key时,将r[high]移至空单元r[low], 此时τ[high]相当于空单元。
- low从左向右扫描,直到r[low].key ≥ x.key时,将r[low]移至空单元r[high] ,此时r[low]相当于空单元。
- 当low和high相遇时，r[low] (或r[high])相当于空单元,且r[low]左边所有记录的关键字均小于基准记录的关键字,而r[low]右边所有记录的关键字均大于或等于基准记录的关键字。最后将基准记录移至r[low]中,就完成了一次划分过程。对于r[low]左边的子表和r[low]右边的子表可采用同样的方法进行进一步划分。
- 假设待划分序列为r[low], r[low+1], ... ,r[high]。首先将基准记录r[low]移至变量x中,使r[low]相当于空单元,然后反复进行如下两个扫描过程,直到low和high相遇。
-
第i趟简单选择排序时,从第i个记录开始,通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。
-
如此反复,经过n-1趟简单选择排序,将把n-1个记录排到位,剩下一-个最小记录直接在最后,所以共需进行n-1趟简单选择排序。
- 算法思想：树形选择排序也称作锦标赛排序。基本思想是先把待排序的n个记录的关键字两两进行比较，取出较小者,然后再在
$\dfrac{n}{2}$ 个较小者中，采用同样的方法进行比较,选出每两个中的较小者，如此反复,直至选出最小关键字记录为止。这个过程可以用一棵满二叉树来表示，不满时用关键字为∞的结点补满,选出的最小关键字记录就是这棵树的根结点。在输出最小关键字之后,为选出次小关键字,将最小关键字记录所对应的叶子结点的关键字值置为∞，然后从该叶结点开始和其兄弟结点的关键字比较,修改从该叶结点到根结点路径上各结点的值，则根结点的值即为次小关键字。重复进行上述过程,直到所有的记录全部输出
-
概念：
- 大根堆：称各结点的关键字值满足条件:r[i].key ≥ r[2i].key 并且 r[i].key ≥ r[2i+1].key (i=1,2,..,n/2)的完全二叉树
- 小根堆：这棵完全二叉树中任意结点的关键字小于或者等于其左孩子和右孩子的关键字(当有左孩子或右孩子时)
-
算法思想：把待排序的记录的关键字存放在数组r[1..n]之中,将r看成是一棵完全二叉树的顺序表示,每个结点表示一个记录,第一个记录r[1]作为二叉树的根,以下各记录 r[2] ~ r[n] 依次逐层从左到右顺序排列,任意结点r[i]的左孩子是r[2i],右孩子是r[2i+1], 双亲是r[$/dfrac{i}{2}$]。对这棵完全二叉树进行调整建堆。
-
关键步骤
-
重建堆-- 当堆顶记录改变时，重建堆
-
首先将与堆相应的完全二叉树根结点中的记录移出，该记录称为待调整记录。此时根结点相当于空结点,从空结点的左、右子树中选出一个关键字较大的记录,如果该记录的关键字大于待调整记录的关键字，则将该记录上移至空结点中。
-
此时,原来那个关键字较大的子结点相当于空结点，从空结点的左、右子树中选出一个关键字较大的记录,如果该记录的关键字仍大于待调整记录的关键字,则将该记录上移至空结点中。
-
重复上述移动过程，直到空结点左、右子树的关键字均小于待调整记录的关键字。此时,将待调整记录放人空结点即可。
- 上述调整方法相当于把待调整记录逐步向下“筛”的过程,所以一般称其为“筛选”法。
-
-
建初堆-- 由任意序列建初堆
- 将一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆,因而可以反复利用上述调整堆算法(“筛选”法),自底向上逐层把所有子树调整为堆,直到将整个完全二叉树调整为堆。
- 可以证明，上述完全二叉树中,最后一个非叶结点位于第$/dfrac{i}{2}$个位置,n为二叉树结点数目。因此,“筛选”需从第$/dfrac{i}{2}$个结点开始,逐层向上倒退,直到根结点。
-
具体操作
- 将待排序记录按照堆的定义建初堆,并输出堆顶元素。
- 调整剩余的记录序列,利用筛选法将前n-i个元素重新筛选建成为一个新堆，再输出堆顶元素。
- 重复(2),进行n-1次筛选，新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多,最后使待排序记录序列成为一个有序的序列,这个过程称之为堆排序。
-
-
思想：基于合并，将两个及以上的子表合并成一个新的有序表
-
以2-路归并为例介绍
-
算法思想：假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到$\dfrac{n}{2}$个长度为2(n为奇数时,最后一个序列的长度为1)的有序子序列。在此基础.上,再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。如此重复,直至得到一个长度为n的有序序列为止。
-
递归解决：
- 将 r1[ ]中的记录用归并法排序后放到r3[]中,可以分为下面三个步骤。
- 首先将rI[ ]前半段的记录用归并法排序后放到r2[ ]的前半段中。
- 将r1[ ]后半段的记录用归并法排序后放到r2[ ]的后半段中。
- 将r2[ ]的前半段和后半段合并到r3[ ]中。
-
- 桶排序
- 低位优先的排序。例如对扑克按照花色和点数排序
- 算法思想：基数排序属于上述“低位优先"排序法,通过反复进行分配与收集操作完成排序。假设记录r[i]的关键字为$key_{i}$,
$key_{i}$ 是由d位十进制数字构成的,即$key_{i}$ =$K^1_{i}K^2_{i}K^3_{i}...K^i_{i}$ ,则每一位可以视为一个子关键字,其中$K^1_{i}$是最高位,$K^i_{i}$是最低位,每一位的值都在0~9的范围内,此时基数rd=10。
排序时先按最低位的值对记录进行初步排序,在此基础上再按次低位的值进行进一.步排序。以此类推，由低位到高位,每一趟都是在前一趟的基础上，根据关键字的某一位对所有记录进行排序,直至最高位,这样就完成了基数排序的全过程。
需要辅助空间大小为待排序序列中最大元素的值，因此适合密集型的且元素非负序列进行排序
-
步骤：
-
开辟新数组helper，其大小为原数组中元素的最大值，每个元素默认为-1
-
扫描原数组
for(int i = 0; i < arr_length; i++){ helper[arr[i]]++; }
-
扫描helper中不是-1的元素
int j = 0 for(int i = 0; i < helper_length; i++){ if(helper[i] == -1)continue; else{ while(helper[i] > 0){ arr[j] = i; j++; }}}
-
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | 是 | |||
| 冒泡 | 是 | |||
| 简单选择 | 否 | |||
| 希尔 | 否 | |||
| 快速 | 否 | |||
| 堆 | 否 | |||
| 归并 | 是 | |||
| 基数 | 是 |