数据结构前言链式存储是一种将数据元素存储在不连续的内存空间中,并通过指针链接每个元素来保持元素间逻辑关系的存储方式.链式存储结构不要求数据存储在连续的空间中,这使得其在动态数据操作方面具有较高的灵活性.索引存储是一种通过为数据元素建立辅助结构(索引表)来提高数据访问效率的存储方式.哈希存储是一种数据结构,用来快速查找,插入和删除数据.其核心原理是使用哈希函数将数据映射到存储位置,使得查找时间可以接近常数时间复杂度O(1)逻辑结构:**集合结构:**元素之间除了同属于一个集合,没有其他任何关系(元素相互独立)1.**线性结构:**一对一2.**树形结构:**一对多3.**网状结构:**多对多物理存储结构:1.**顺序存储:**连续内存空间,比如数组;访问快,增删慢2.**链式存储:**不连续,靠指针相连,比如链表;增删快,随机访问慢3.**索引存储:**数据区索引表,索引记录关键字和地址;查找快,额外占索引空间.4.**散列存储:**根据关键字直接计算存储地址;查找极快,存在哈希冲突问题.涉及到的算法:1.查找算法顺序查找、二分查找、哈希查找等2.排序算法冒泡、快速、归并、堆排序等3.插入删除针对数据结构的增删操作链表 / 数组增删4.分治算法分而治之把大问题拆成多个相同小问题如归并排序、快速排序5.动态规划保存子问题结果避免重复计算解决最优子结构问题6.贪心算法每一步做局部最优选择期望得到全局最优线性表链表节点data和next链表由一个个节点组成每个节点一般包含两部分1.data数据域存放这个节点要保存的有效数据数字、字符等。2.next指针域是一个指向下一个节点的指针存储下一个节点的内存地址。如果是最后一个节点next NULL代表后面没有节点。链表像一串珠子data珠子本身带的信息next连接到下一颗珠子的线简述链表反转的算法步骤初始化三个指针prevcurrentnext,其中prev指向NULLcurrent指向链表的头节点next用来保存节点的下一个元素。遍历链表对于每个节点先保存current的下一个节点到next中。将当前节点的next指向prev然后将prev移动到当前节点current移动到next。重复上述过程直到current为NULL即遍历完整个链表。最后返回prev即新的头节点。简述如何查找链表的倒数第k个节点使用两个指针first和second都初始化为链表的头节点。先将first指针向前移动k步。然后同时移动first和second指针直到first移动到链表的末尾。此时second指针指向链表的倒数第k个节点。简述如何删除链表中的所有值为val的节点创建一个虚拟头节点dummy其next指向链表的头节点。设置一个指针current初始化为dummy。遍历链表若current-next-val,则删除current-next节点并将current-next指向下一个节点否则移动current到下一个节点。返回dummy-next,即删除节点后的新头节点。请简述如何在链表中间插入一个节点查找链表的中间节点使用快慢针方法。快指针每次移动两步慢指针每次移动一步直到快指针到达链表末尾慢指针正好指向中间节点。创建新节点并将其插入到中间节点之后。更新新节点的next指向原中间节点next然后将中间节点的next指向新节点。简述如何合并两个已排序的链表创建一个虚拟节点dummy用于存放合并后的链表。使用两个指针p1和p2分别指向两个链表的头节点。比较p1和p2指向的节点的值将较小的节点连接到dummy链表并移动对应的指针。当其中一个链表遍历完时将另一个链表剩余的部分直接连接到合并链表的末尾。返回dummy-next,即合并后的链表头节点。简述如何删除链表中的第k个节点创建一个虚拟头节点dummy其next指向链表头节点。设置一个指针current初始化为dummy。遍历链表找到第k-1个节点。将第k-1个节点的next指向第k1个节点完成删除操作。返回dummy-next即删除节点后的新头节点栈和队列栈**(先进后出)**是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说表尾端有其特殊含义称为栈顶相应地表头端称为栈底。不含元素的空表称为空栈。栈的基本操作1.initStatck(*S):初始化一个空栈S2.DestroyStatck(*S):销毁栈S3.ClearStatck(*S):清空栈S的所有元素4.StackEmpty(S):检查栈S是否为空。如果为空返回TRUE否则返回FALSE5.StackLength(S):返回栈S中元素的个数6.GetTop(S,*e)返回栈S顶端的元素7.Push(*S,e):将元素e压入栈S的顶端。8.Pop(*S,*e):将栈S顶端的元素弹出并将其赋值给e。9.StackTraverse(S,visit()):从栈顶底部遍历栈S并对每个元素应用visit()函数队列是一种先进先出的线性表它只允许在表的一端进行插入而在另一端删除元素允许插入的一端叫做队尾允许删除的一端叫做队头。EnQueue(*Q,e):入队元素DeQuene(*Q,*e):出队元素特性 循环队列链队列实现方式数组(固定大小链表(动态大小)队列大小固定大小动态大小空间效率高避免空间浪费低使用指针存储额外的内存开销操作复杂度O(1)(入队出队)O(1)(入队出队适用场景Q:固定任务资源分配Q:缓冲区循环缓存L:动态任务调度L:大规模高变动的数据流L:内存灵活的应用缺点Q:固定大小限制队列满时无法扩展L:内存开销较大L需要额外的指针操作和内存管理顺序队列的假溢出顺序队列用数组实现队头front、队尾rear指针不断后移当rear移动到数组末尾但数组前部还有已经出队释放的空闲空间此时看似满了实际还有空位这就是假溢出。循环队列解决假溢出思路与原理循环队列通过取模让队尾指针绕回数组头部复用队头前面已经出队的空闲存储单元消除假溢出。栈的应用场景表达式求值栈可用于中缀表达式转后缀表达式、后缀表达式求值等操作。递归调用栈用于保存函数调用的上下文信息操作系统的调用栈就是利用栈来管理递归调用的。浏览器历史记录浏览器通过栈来管理用户的历史访问记录用户可以通过后退、前进按钮来回溯历史记录。数组顺序表示把多维数组映射到一段连续一维内存空间用公式算出每个元素位置。树和二叉树树是n个节点的有限集n0时称为空树在任意一颗非空树中有且仅有一个特定的称为根的结点书的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度二叉树是一种每个结点最多有两个子结点的树结构在二叉树中前序遍历根节点-左子树-右子树中序遍历:左子树-根节点-右子树后序遍历左子树-右子树-根节点层序遍历按从上到下同一层从左到右依次访问赫夫曼树(哈夫曼树)的特性赫夫曼树哈夫曼树定义就是带权路径长度 WPL 最小的最优二叉树在哈夫曼编码场景里叶子节点权值一般对应字符出现频率内部节点权值 它两个子节点权值之和所以内部节点也有权值哈夫曼树不一定是完全二叉树构造时只合并最小权值节点形态不确定图图(G)是一种数据结构由一组顶点和连接这些顶点的一系列边或弧组成用来描述多对多的数据结构。顶点V节点比如城市人边E:顶点之间的连线代表关系记为G(V,E)有向图/无向图1.无向图边没有箭头双向关系。A连BB连A。2.有向图边带箭头单向。A-B不等于B-A权值(带权图/网边上可以带数字叫权。比如地图顶点是城市边是公路权距离。这种图又叫网其他名词度一个顶点连接多少条边无向图度 相连边数量有向图入度指向自己、出度从自己出去路径从一个顶点沿着边走到另一个顶点的顶点序列环起点和终点是同一个点的路径连通图无向任意两点之间都有路可以到达强连通图有向任意两点互相可达两种存储方式1.邻接矩阵用二维数组存。matrix[i][j]i 到 j 有没有边带权就存权值。优点判断两点有没有边很快 O (1)缺点顶点少边少时很浪费空间。适合稠密图边很多2.邻接表数组 链表。数组下标代表顶点链表存这个点能直接到达的顶点。优点省空间缺点判断两点是否有边要遍历链表。适合稀疏图边很少。两大遍历算法DFS 深度优先搜索一路往深处走走不通再回溯。类似走迷宫一条路走到黑。递归实现栈思想DFS算法及其实现过程BFS 广度优先搜索一层一层向外扩散。类似水波扩散先访问起点所有邻居再访问邻居的邻居。队列实现查找算法动态查找动态查找是指查找过程中数据集会发生变化即数据集在查找过程中可能会有插入删除或更新操作。因此查找方法需要处理这些变化保证在插入删除元素时仍能高效地进行查找。二叉排序树或者是一颗空树或者是具有如下性质的二叉树若左非空左子树所有节点的值均小于根节点的值若右非空右子树所有节点的值均大于根节点的值平衡二叉树也叫AVL树它或者是一颗空树或者是具有以下性质的二叉排序树它的左子树和右子树的高度之差的绝对值不超过1且它左子树和右子树都是一颗平衡二叉树B树定义多路平衡查找树m 阶 B 树m≥3每个节点最多有m-1个关键字m个子节点。性质根节点最少 1 个关键字非叶子除根、叶子外每个节点关键字数量[m/2 ] -1nm-1 子节点数 关键字数 1所有叶子节点在同一层叶子节点不存数据代表查找失败节点内关键字有序升序(K_1K_2…K_n)子树划分(P_0) 存小于(K_1)(P_1) 在(K_1,K_2)之间以此类推。特点关键字和数据记录一起存在节点里找到关键字就拿到数据查找可能在任意节点命中不一定走到叶子用途数据库索引、文件系统早期随机查找优秀插入删除会发生节点分裂 / 合并维持平衡。B树B 树是B 树的变种数据库MySQL InnoDB最常用索引结构。m 阶 B 树性质非叶子节点只存关键字 子节点指针不存真实数据所有数据记录全部放在叶子节点叶子节点之间用双向链表串联有序非叶子节点关键字是其子树内的最大值或最小值作为索引分界关键字数量非叶子节点:[m/2]nm叶子节点:[m/2]nm所有叶子在同一层。特点7.查找不管查什么最终一定走到叶子节点8.范围查询极强找到起点后顺着叶子链表向后遍历即可9. 非叶子节点不含数据一页能放更多索引项 →树高更低IO 次数更少10. 缺点单次等值查找大概率要多一层 IO不如 B 树但数据库场景范围查询更多收益更大。B 树每个节点既有目录又放真实内容查到中间节点就结束。B 树上层全是目录所有真正内容都在最底层一排连续链表上。哈希表数组哈希函数核心目标用key直接定位存储位置实现O(1)查找核心原理有一个底层数组每个位置叫桶bucket哈希函数 hash (key)把任意类型的 key字符串、数字等转换成一个整数这个整数就是数组下标把(key, value)存到数组hash(key)对应的桶里查询对 key 算哈希得到下标直接去数组该位置拿 value不用遍历解决问题的办法链地址法拉链法同一个桶放一条链表 / 红黑树。冲突的数据挂在链表上。Java HashMap 就是这个。开放寻址法冲突就找下一个空桶。比如线性探测C unordered_map 不是这个ThreadLocalMap 使用开放寻址。排序算法插排外层从 i1 开始把arr[i]暂存向前不断移动大于它的元素空出位置插入冒泡排序相邻元素两两比较交换每轮把最大元素 “冒泡” 到尾部快排选基准值分区递归处理左右子区间,快速排序的核心思想是通过一个基准元素将数组分成两个部分并递归地对每个部分进行排序。通过分治法优化排序过程。简单选择排序两层 for记录minIndex/maxIndex一轮找最值下标循环结束才交换一次