网站角色管理,中石油企业邮箱怎么注册,金融网站 改版方案,兰州设计公司有哪些1、单链表、循环链表、双向链表#xff0c;存储、逻辑结构
单链表、循环链表和双向链表都是线性表的链式存储结构#xff0c;它们在存储和逻辑结构上有一些共同点和不同点。
存储结构
单链表#xff1a;每个节点包含一个数据域和一个指针域#xff0c;指针域指向下一个节…1、单链表、循环链表、双向链表存储、逻辑结构
单链表、循环链表和双向链表都是线性表的链式存储结构它们在存储和逻辑结构上有一些共同点和不同点。
存储结构
单链表每个节点包含一个数据域和一个指针域指针域指向下一个节点。最后一个节点的指针域为空NULL表示链表的结束。循环链表与单链表类似每个节点包含一个数据域和一个指针域但最后一个节点的指针域指向链表的头节点形成一个闭环。双向链表每个节点包含一个数据域和两个指针域一个指向前驱节点一个指向后继节点。头节点的前驱指针为空尾节点的后继指针为空。
逻辑结构
单链表 优点插入和删除操作只需要修改指针不需要移动元素时间复杂度为 (O(1))。缺点只能从头节点开始遍历查找某个节点需要 (O(n)) 的时间复杂度。 循环链表 优点可以方便地从任意节点开始遍历整个链表适合某些需要循环操作的场景如循环队列。缺点查找某个节点的时间复杂度仍然是 (O(n))但可以避免链表为空时的特殊情况处理。 双向链表 优点可以从任意节点向前或向后遍历插入和删除操作更加灵活时间复杂度为 (O(1))。缺点每个节点需要额外的指针空间占用更多的内存。
应用场景
单链表适用于需要频繁插入和删除操作且不需要频繁查找的场景。循环链表适用于需要循环操作的场景如循环队列、圆形游戏等。双向链表适用于需要频繁双向遍历的场景如浏览器的前进后退功能、某些双向队列等。
2、栈、循环队列元素个数判断、空/非空判断、多次进出后存储情况
栈和循环队列也都是线性数据结构但它们在元素的进出顺序和存储方式上有所不同。
栈
元素个数判断栈的元素个数可以通过一个计数器来记录每次入栈时计数器加1出栈时计数器减1。空/非空判断 空判断如果计数器为0则栈为空。非空判断如果计数器大于0则栈非空。 多次进出后的存储情况 栈遵循后进先出LIFO的原则即最后进入的元素最先被取出。多次进出后栈顶元素始终是最近一次入栈且未被取出的元素。如果栈的容量有限多次进出时需要注意栈满的情况防止溢出。
循环队列
元素个数判断循环队列的元素个数可以通过队尾指针和队首指针的差值来计算但需要注意循环的情况。 如果队尾指针大于队首指针元素个数为 rear - front。如果队尾指针小于队首指针元素个数为 rear - front capacity其中 capacity 是队列的容量。 空/非空判断 空判断如果队首指针等于队尾指针则队列为空。非空判断如果队首指针不等于队尾指针则队列非空。 多次进出后的存储情况 循环队列遵循先进先出FIFO的原则即先进入的元素最先被取出。多次进出后队首指针始终指向队列的第一个元素队尾指针指向队列最后一个元素的下一个位置。为了避免队列满时的判断错误通常会牺牲一个存储空间来区分队列满和队列空的情况。例如当 (rear 1) % capacity front 时队列满。
应用场景
栈适用于需要回溯或撤销操作的场景如函数调用的堆栈、浏览器的后退功能、括号匹配等。循环队列适用于需要循环操作的场景如任务调度、缓冲区管理等。
注意事项
栈在使用栈时需要注意栈溢出的情况尤其是在递归调用深度较大的情况下。循环队列在使用循环队列时需要注意队列满和队列空的判断条件避免误判。
3、串next求取、BF及KMP模式匹配过程
串的next数组求取
KMP算法中的next数组用于记录模式串中每个字符的前缀和后缀的最大相同长度。具体求取过程如下 初始化 next[0] -1表示第一个字符没有前缀和后缀可以比较。初始化两个指针 j 和 k其中 j 用于遍历模式串k 用于记录前缀的长度。 计算next数组 当 k -1 或者模式串的第 j 个字符与第 k 个字符相等时next[j] k然后 j 和 k 都加1。如果不相等则 k 更新为 next[k]继续比较。 循环结束 当 j 遍历完整个模式串时next数组计算完成。
BF模式匹配过程
BF算法暴力匹配算法是最简单的字符串匹配算法 初始化 设置两个指针 i 和 j分别指向文本串和模式串的起始位置。 匹配过程 如果 text[i] 和 pattern[j] 相等则 i 和 j 都向后移动一位。如果不相等则将模式串向后移动一位即 j 重置为0i 指向下一个字符。 匹配成功 当 j 达到模式串的末尾时表示匹配成功返回 i - j 作为匹配位置的起始索引。 匹配失败 如果 i 遍历完文本串则表示没有匹配到模式串。
KMP模式匹配过程
KMP算法利用next数组来优化匹配过程 初始化 设置两个指针 i 和 j分别指向文本串和模式串的起始位置。计算模式串的next数组。 匹配过程 如果 text[i] 和 pattern[j] 相等则 i 和 j 都向后移动一位。如果不相等则 j 更新为 next[j]i 保持不变。 匹配成功 当 j 达到模式串的末尾时表示匹配成功返回 i - j 作为匹配位置的起始索引。 匹配失败 如果 i 遍历完文本串则表示没有匹配到模式串。
KMP算法通过next数组减少了不必要的比较从而提高了匹配效率。
4、二维数组存储计算
二维数组在计算机中通常以一维数组的形式存储主要有两种存储方式按行存储和按列存储。不同的存储方式会影响元素的访问和计算方式。以下是对这两种存储方式的详细说明
按行存储Row-major Order
存储方式二维数组的元素按行顺序存储在一维数组中。首先存储第一行的所有元素然后是第二行的所有元素依此类推。地址计算假设二维数组 A 的大小为 m x n每个元素占用 size 个字节基地址为 base则元素 A[i][j] 的地址可以通过以下公式计算 Address(A[i][j])base(i×nj)×size 其中i 是行索引j 是列索引。
按列存储Column-major Order
存储方式二维数组的元素按列顺序存储在一维数组中。首先存储第一列的所有元素然后是第二列的所有元素依此类推。地址计算同样假设二维数组 A 的大小为 m x n每个元素占用 size 个字节基地址为 base则元素 A[i][j] 的地址可以通过以下公式计算 Address(A[i][j])base(j×mi)×size 其中i 是行索引j 是列索引.
示例
假设有一个二维数组 A大小为 3 x 4每个元素占用 4 个字节基地址为 1000。按行存储和按列存储的地址计算如下 按行存储 A[1][2] 的地址 Address(A[1][2])1000(1×42)×41000241024 按列存储 A[1][2] 的地址 Address(A[1][2])1000(2×31)×41000281028
树的遍历
树的遍历主要有三种方式先序遍历、中序遍历和后序遍历。这些遍历方式通常用于二叉树但也可以扩展到多叉树。
先序遍历
定义先访问根节点然后递归地先序遍历左子树最后递归地先序遍历右子树。过程 访问根节点。先序遍历左子树。先序遍历右子树。
中序遍历
定义先递归地中序遍历左子树然后访问根节点最后递归地中序遍历右子树。过程 中序遍历左子树。访问根节点。中序遍历右子树。
后序遍历
定义先递归地后序遍历左子树然后递归地后序遍历右子树最后访问根节点。过程 后序遍历左子树。后序遍历右子树。访问根节点.
二叉树的顺序存储
二叉树的顺序存储是将二叉树的节点存储在一个一维数组中按照从上到下、从左到右的顺序排列。这种存储方式适用于完全二叉树和满二叉树但对于一般的二叉树可能会浪费空间。
存储规则
根节点存储在数组的第一个位置索引为0。左子节点对于索引为 i 的节点其左子节点的索引为 2i 1。右子节点对于索引为 i 的节点其右子节点的索引为 2i 2。父节点对于索引为 i 的节点其父节点的索引为 (i - 1) / 2向下取整.
示例
假设有一个二叉树其节点值如下 1/ \2 3/ \ \4 5 6其顺序存储的数组为 [1, 2, 3, 4, 5, 6]。
应用场景
先序遍历常用于复制树结构、打印树结构等。中序遍历对于二叉搜索树中序遍历可以得到节点值的有序序列。后序遍历常用于计算树的大小、删除树等。顺序存储适用于完全二叉树和满二叉树如堆的实现.
注意事项
遍历递归实现递归实现简单直观但可能会导致栈溢出尤其是在树的深度较大时。非递归实现可以使用栈来实现非递归遍历避免递归调用的开销。顺序存储空间浪费对于一般的二叉树顺序存储可能会浪费大量空间因为需要为不存在的节点预留位置。
哈夫曼树的构建
哈夫曼树是一种用于数据压缩的无损编码方法其构建过程如下 初始化 将每个字符及其出现的频率视为一个节点初始化一个优先队列最小堆将所有节点加入队列。 构建过程 从优先队列中取出两个权值最小的节点。创建一个新的节点其权值为两个取出节点的权值之和。将新节点的左子节点和右子节点分别设置为取出的两个节点。将新节点重新加入优先队列。重复上述步骤直到优先队列中只剩下一个节点该节点即为哈夫曼树的根节点。
哈夫曼编码的求取
哈夫曼编码是通过哈夫曼树来确定每个字符的编码具体步骤如下 初始化 从哈夫曼树的根节点开始初始化一个空字符串作为编码路径。 编码过程 从根节点向叶子节点遍历 如果向左子节点移动则在编码路径上添加“0”。如果向右子节点移动则在编码路径上添加“1”。 当到达叶子节点时该叶子节点对应的字符的编码即为当前的编码路径。 编码结果 每个字符的哈夫曼编码是唯一的且通常较短的编码分配给出现频率较高的字符。
示例
假设有一组字符及其频率A(5), B(9), C(12), D(13), E(16), F(45)构建哈夫曼树并求取编码的过程如下 构建哈夫曼树 初始优先队列A(5), B(9), C(12), D(13), E(16), F(45)取出 A(5) 和 B(9)创建新节点 AB(14)加入队列AB(14), C(12), D(13), E(16), F(45)继续合并直到构建完整棵树。 求取编码 从根节点开始遍历最终得到每个字符的编码 F: 0C: 100D: 101A: 1100B: 1101E: 111
邻接矩阵和邻接表
邻接矩阵
定义邻接矩阵是一个二维数组用于表示图中顶点之间的连接关系。存储方式 对于无向图邻接矩阵是对称的。A[i][j] 表示顶点 i 和顶点 j 之间的边的权重。如果 i 和 j 之间没有边则 A[i][j] 为无穷大或一个特定的值如0。对于有向图邻接矩阵不一定对称。A[i][j] 表示从顶点 i 到顶点 j 的边的权重。 优点 可以快速判断两个顶点之间是否存在边。 缺点 空间复杂度高尤其是对于稀疏图会浪费大量空间。
邻接表
定义邻接表是一个数组每个数组元素是一个链表用于存储与该顶点相邻的所有顶点。存储方式 对于无向图每个顶点的邻接表中存储与其相连的所有顶点。对于有向图每个顶点的邻接表中存储其所有出边的目标顶点。 优点 空间复杂度低适合稀疏图。 缺点 判断两个顶点之间是否存在边需要遍历链表时间复杂度较高。
深度优先遍历DFS和广度优先遍历BFS
深度优先遍历DFS
过程 从一个顶点开始沿着一条路径尽可能深地搜索直到无法继续前进。回溯到上一个顶点继续搜索其他未访问的路径。 实现 使用递归或栈来实现。标记已访问的顶点避免重复访问。 应用 用于寻找路径、检测图的连通性等。
广度优先遍历BFS
过程 从一个顶点开始逐层访问其所有邻接顶点。访问完一层的所有顶点后再访问下一层的顶点。 实现 使用队列来实现。标记已访问的顶点避免重复访问。 应用 用于寻找最短路径、检测图的连通性等。
最小生成树求取
Prim算法
过程 从任意一个顶点开始将其加入生成树。在生成树的顶点集合中选择一条连接生成树和非生成树顶点的最小权值边将该边的非生成树顶点加入生成树。重复上述步骤直到所有顶点都加入生成树。 实现 使用优先队列最小堆来优化选择最小权值边的过程。 应用 适用于稠密图因为每次只需要选择一个顶点。
Kruskal算法
过程 将图中的所有边按权值从小到大排序。依次选择权值最小的边如果该边的两个顶点不在同一个连通分量中则将其加入生成树。重复上述步骤直到生成树包含所有顶点。 实现 使用并查集来检测连通分量。 应用 适用于稀疏图因为每次只需要选择一条边.
这两种算法都可以有效地求取无向图的最小生成树选择哪种算法取决于图的稠密程度和具体的应用场景。
二叉排序树也称为二叉查找树或二叉搜索树是一种特殊的二叉树其中每个节点的值大于其左子树中所有节点的值小于其右子树中所有节点的值。以下是关于二叉排序树的生成和查找的详细说明
二叉排序树的生成
插入过程
步骤 初始化从根节点开始。比较将要插入的值与当前节点的值进行比较。 如果要插入的值小于当前节点的值则移动到当前节点的左子节点。如果要插入的值大于当前节点的值则移动到当前节点的右子节点。 递归重复上述比较和移动过程直到找到一个空的子节点位置。插入在找到的空位置插入新节点。
示例
假设我们要将以下值依次插入到一个空的二叉排序树中50, 30, 20, 40, 70, 60, 80。
插入 50作为根节点。插入 30小于 50插入到 50 的左子节点。插入 20小于 30插入到 30 的左子节点。插入 40大于 30插入到 30 的右子节点。插入 70大于 50插入到 50 的右子节点。插入 60小于 70插入到 70 的左子节点。插入 80大于 70插入到 70 的右子节点。
最终生成的二叉排序树如下 50/ \30 70/ \ / \20 40 60 80二叉排序树的查找
查找过程
步骤 初始化从根节点开始。比较将要查找的值与当前节点的值进行比较。 如果要查找的值等于当前节点的值则查找成功返回当前节点。如果要查找的值小于当前节点的值则移动到当前节点的左子节点。如果要查找的值大于当前节点的值则移动到当前节点的右子节点。 递归重复上述比较和移动过程直到找到目标节点或到达空节点。查找失败如果到达空节点则表示查找失败返回空。
示例
假设我们要在上述生成的二叉排序树中查找值 40。
从根节点 50 开始。40 小于 50移动到左子节点 30。40 大于 30移动到右子节点 40。找到目标节点 40查找成功。
如果要查找值 45则
从根节点 50 开始。45 小于 50移动到左子节点 30。45 大于 30移动到右子节点 40。45 大于 40但 40 的右子节点为空查找失败.
冒泡排序Bubble Sort
过程 比较相邻的元素如果第一个元素大于第二个元素就交换它们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
选择排序Selection Sort
过程 在未排序序列中找到最小或最大元素存放到排序序列的起始位置。从剩余未排序元素中继续寻找最小或最大元素然后放到已排序序列的末尾。重复第二步直到所有元素均排序完毕。
插入排序Insertion Sort
过程 从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已经排序的元素序列中从后向前扫描。如果该元素已排序大于新元素将该元素移到下一位置。重复步骤3直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5。
希尔排序Shell Sort 过程 1.选择一个增量序列 t1,t2,….,tk其中 t ti1且 tk 1。 2.按增量序列个数 k对序列进行 k 趟插入排序。 3.每趟排序根据对应的增量 t将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为1时整个序列作为一个表来处理表长度即为整个序列的长度
快速排序Quick Sort
过程 选择一个基准值pivot通常选择序列的第一个元素或最后一个元素。将所有比基准值小的元素放到基准前面所有比基准值大的元素放到基准后面相同的数可以到任一边。在这个分区退出之后该基准就处于数组的中间位置。递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。
归并排序Merge Sort
过程 将序列每相邻两个数字进行归并操作形成 [n/2] 个序列排序后每个序列包含两个元素。将上述序列再次归并形成[n/4]个序列每个序列大概包含四个元素。重复上述操作直到所有元素排序完毕。
堆排序Heap Sort
过程 将待排序序列构建成一个大顶堆此时整个序列的最大值就是堆顶元素。将堆顶元素与末尾元素交换将最大元素“沉”到数组末端。重新调整结构使其满足堆定义然后继续交换堆顶元素与当前末尾元素反复执行直至整个序列有序。
基数排序Radix Sort
过程 将所有待比较数值统一为同样的数位长度数位较短的数前面补零。从最低位开始依次进行稳定排序通常使用计数排序。重复上述过程直到最高位排序完成。
桶排序Bucket Sort
过程 设置一个定量的数组当作空桶。遍历输入数据并且把数据根据其特征值放入对应的桶中。对每个不为空的桶进行排序可以使用其他排序算法或者递归地使用桶排序。按顺序把桶中的数据拼起来。
哈希表是一种通过哈希函数将键key映射到值value的数据结构具有高效的查找、插入和删除操作。当哈希冲突发生时需要采用一定的解决方法。线性探测法和二次探测法是两种常用的解决哈希冲突的方法。
哈希表求取 选择哈希函数 哈希函数将键映射到哈希表中的一个索引位置。常见的哈希函数包括除法哈希、乘法哈希等。例如除法哈希函数hash(key) key % table_size其中 table_size 是哈希表的大小。 处理哈希冲突 当两个不同的键映射到同一个索引位置时发生哈希冲突。需要采用一定的方法解决冲突如链表法、线性探测法、二次探测法等。
线性探测法 基本思想 当发生哈希冲突时线性探测法从冲突位置开始线性地向后探测直到找到一个空的槽位。探测序列是线性的即 h(key) i其中 i 是探测次数从0开始递增。 插入过程 计算键的哈希值 h(key)。如果 h(key) 位置为空则直接插入。如果 h(key) 位置已被占用则从 h(key) 开始线性探测直到找到一个空的槽位插入。 查找过程 计算键的哈希值 h(key)。从 h(key) 开始线性探测直到找到目标键或探测到一个空槽位表示查找失败。
二次探测法 基本思想 当发生哈希冲突时二次探测法从冲突位置开始按照二次方的步长进行探测直到找到一个空的槽位。探测序列是二次的即 h(key) i^2其中 i 是探测次数从1开始递增。 插入过程 计算键的哈希值 h(key)。如果 h(key) 位置为空则直接插入。如果 h(key) 位置已被占用则从 h(key) 开始二次探测直到找到一个空的槽位插入。 查找过程 计算键的哈希值 h(key)。从 h(key) 开始二次探测直到找到目标键或探测到一个空槽位表示查找失败。
优缺点比较 线性探测法 优点实现简单。缺点容易产生聚集现象即多个键聚集在连续的槽位中导致探测长度增加性能下降。 二次探测法 优点可以减少聚集现象探测序列更加分散。缺点实现相对复杂且在某些情况下可能会探测到重复的位置如当 i 和 j 的平方模 table_size 相等时。
应用场景
线性探测法适用于哈希表较小且负载因子较低的情况因为聚集现象对性能的影响较小。二次探测法适用于哈希表较大且负载因子较高的情况可以更好地分散键的分布提高性能。
