手机如何使用wordpress,爱站seo工具包官网,网页设计是什么意思,网站建设教程学习嵌入式Day13 一段话总结
文档主要介绍带有头指针和尾指针的单链表的实现及操作#xff0c;涵盖创建、销毁、头插、尾插、按索引/数据增删查、遍历等核心操作#xff0c;强调头插/尾插时间复杂度为O(1)#xff0c;按索引/数据操作需遍历链表、时间复杂度为O(n)#xff0c;并…嵌入式Day13 一段话总结
文档主要介绍带有头指针和尾指针的单链表的实现及操作涵盖创建、销毁、头插、尾插、按索引/数据增删查、遍历等核心操作强调头插/尾插时间复杂度为O(1)按索引/数据操作需遍历链表、时间复杂度为O(n)并对比提及双向链表因存储前后指针、操作更高效是典型的空间换时间策略。 思维导图
## **单链表结构**
- 头指针(head)
- 尾指针(tail)
- 节点(Node)datanext指针
- 链表结构体(LinkedList)包含head、tail、size
## **核心操作**
- 创建calloc分配LinkedList结构体
- 销毁先释放所有节点再释放结构体
- 遍历按x-y-z-NULL格式打印
- 新增- 头插(add_before_head)更新head首个节点时更新tail- 尾插(add_behind_tail)有节点时尾节点next指向新节点否则更新head- 按索引(idx)idx0头插idxsize尾插中间需找idx-1前驱节点
- 查询- 按索引(search_by_idx)遍历找idx节点- 按数据遍历找匹配data节点
- 删除- 按索引(delete_by_idx)idx0删头节点其他找前驱节点删尾节点需更新tail- 按数据(delete_by_data)遍历找节点及前驱删头/尾节点特殊处理
## **时间复杂度**
- O(1)头插、尾插、删头节点
- O(n)按索引/数据增删查、删非头节点
## **双向链表对比**
- 节点增加前驱指针
- 操作更灵活附近操作O(1)
- 空间换时间如C list/Java LinkedList底层实现详细总结
一、单链表结构与核心操作概述
结构组成由LinkedList结构体管理head头指针、tail尾指针、size节点数每个Node包含data数据和next后继指针。核心操作涵盖创建、销毁、遍历、增删查等操作时需注意头/尾节点特殊情况如首个节点需同时更新head和tail。
二、具体操作实现要点
创建与销毁 创建使用calloc分配LinkedList结构体初始headtailNULLsize0。销毁先遍历释放所有Node节点再释放LinkedList结构体。 新增操作 头插法新节点直接指向原head更新head若为首个节点同时更新tail。尾插法若链表非空原tail-next指向新节点更新tail若为空直接更新head和tail。按索引插入索引范围[0, size]idx0头插idxsize尾插中间需遍历找到idx-1前驱节点时间复杂度O(n)。 查询操作 按索引查询索引范围[0, size-1]遍历找到对应节点时间复杂度O(n)。按数据查询遍历全链表匹配数据时间复杂度O(n)。 删除操作 按索引删除idx0直接删头节点更新head若为尾节点idxsize-1需更新tail为前驱节点其他情况遍历找前驱节点时间复杂度O(n)除删头节点为O(1)。按数据删除遍历找到节点及其前驱删头节点时更新head删尾节点时更新tail时间复杂度O(n)除删头节点为O(1)。
三、时间复杂度对比表
操作类型具体操作时间复杂度是否需遍历新增头插/尾插O(1)否按索引插入O(n)是中间查询按索引/数据查询O(n)是删除删头节点O(1)否删非头节点含尾O(n)是
四、双向链表对比
优势节点增加前驱指针prev可直接访问前后节点附近操作如删除当前节点时间复杂度为O(1)性能更优。应用C list、Java LinkedList底层均为双向链表体现空间换时间策略。 关键问题 为什么头插法和尾插法的时间复杂度是O(1) 答头插法直接通过头指针操作首个节点尾插法通过尾指针直接定位最后一个节点无需遍历链表因此时间复杂度为O(1)。 删除单链表尾节点的时间复杂度为什么是O(n) 答删除尾节点需先遍历找到其前驱节点需O(n)时间才能更新前驱节点的next指针为NULL因此整体时间复杂度为O(n)。 双向链表相比单链表的核心优化点是什么 答双向链表每个节点增加前驱指针prev可直接访问前后节点使在确定节点附近的操作如删除当前节点时间复杂度从O(n)降至O(1)以空间换时间提升性能。
文档主要介绍了单链表常见的五道经典面试题及解法包括求中间结点、判断是否有环、反转链表、合并两条有序链表两种方法具体如下
六、求链表中间结点
问题给定单链表找到中间结点奇数长度取中间结点偶数长度取中间偏右结点。 解法
遍历统计法 先遍历链表统计长度 list_len再计算中间索引 mid_idx list_len / 2再次遍历找到对应结点。时间复杂度O(n)两次遍历。 快慢指针法双指针法 思路定义两个指针 slow每次走1步和 fast每次走2步。当 fast 到达链表末尾fast NULL 或 fast-next NULL时slow 指向中间结点。代码逻辑int find_mid_ele2(Node *head) {Node *fast head, *slow head;while (fast ! NULL fast-next ! NULL) { // 循环条件确保快慢指针有效移动slow slow-next;fast fast-next-next;}return slow-data; // 直接返回中间结点数据
}时间复杂度O(n)单次遍历效率更高。
七、判断单链表是否有环
问题判断单链表是否存在环尾结点 next 指向链表中任意结点。 解法快慢指针法
思路若链表有环快慢指针最终会在环内相遇若无环fast 会先到达 NULL循环结束。代码逻辑bool has_circle(Node *head) {Node *fast head, *slow head;while (fast ! NULL fast-next ! NULL) {slow slow-next;fast fast-next-next;if (slow fast) return true; // 相遇即有环}return false; // 循环正常结束无环
}关键点 环的形成尾结点 next 指向头结点、中间结点或自身。快慢指针速度差确保在环内必然相遇数学证明快指针每次比慢指针多走1步环长有限最终会追上。
八、单链表反转循环迭代法
问题反转单链表返回新链表的头指针原尾结点。 解法三指针法prev、curr、succ
思路 初始化 prev NULL前驱指针指向反转后的尾部curr head当前结点succ head-next后继结点防止链表断开。遍历链表每次将 curr-next 指向 prev然后 prev、curr、succ 依次后移。遍历结束后prev 指向新链表的头结点原尾结点。 代码实现Node *reverse(Node *head) {Node *prev NULL, *curr head, *succ head ? head-next : NULL; // 处理头结点为空的情况while (curr ! NULL) {curr-next prev; // 反转当前结点指向prev curr;curr succ;succ (succ ! NULL) ? succ-next : NULL; // 避免空指针访问}return prev; // 返回新头指针
}变种通过二级指针直接修改原头指针reverse2 函数适用于需要修改原始链表头指针的场景。
九、合并两条有序单链表循环迭代法
问题合并两条升序单链表返回合并后的升序链表头指针。 解法1无虚拟头结点需处理头部特殊情况
步骤 校验空链表直接返回非空链表。找到两条链表的最小结点作为新链表的头指针 head 和尾指针 tail并移动对应链表指针list1 或 list2。循环比较 list1 和 list2 的当前结点将较小结点接入 tail-next更新 tail 和对应链表指针。循环结束后将剩余非空链表接入 tail。 代码逻辑Node *merge_lists(Node *list1, Node *list2) {if (!list1 || !list2) return list1 ? list1 : list2; // 处理空链表Node *head, *tail;if (list1-data list2-data) {head tail list1;list1 list1-next;} else {head tail list2;list2 list2-next;}while (list1 list2) { // 合并剩余结点if (list1-data list2-data) {tail-next list1;tail list1;list1 list1-next;} else {tail-next list2;tail list2;list2 list2-next;}}tail-next (list1 ! NULL) ? list1 : list2; // 接入剩余链表return head;
}解法2使用虚拟头结点简化头部处理
优化点在链表头部添加一个虚拟结点 dummy_node避免单独处理头指针初始化统一逻辑。代码逻辑Node *merge_lists2(Node *list1, Node *list2) {if (!list1 || !list2) return list1 ? list1 : list2;Node dummy_node {0, NULL}; // 栈上创建虚拟头结点Node *tail dummy_node; // tail指向虚拟结点作为初始尾结点while (list1 list2) { // 直接合并所有结点无需头部特殊处理if (list1-data list2-data) {tail-next list1;tail list1;list1 list1-next;} else {tail-next list2;tail list2;list2 list2-next;}}tail-next (list1 ! NULL) ? list1 : list2;return dummy_node.next; // 返回虚拟结点的下一个结点真正的头结点
}优势虚拟头结点使头部和后续结点的处理逻辑一致代码更简洁减少边界条件判断。
十、核心算法总结
面试题关键思路时间复杂度空间复杂度求中间结点快慢指针法单次遍历O(n)O(1)判断是否有环快慢指针法相遇即有环O(n)O(1)反转链表三指针迭代反转prev、curr、succO(n)O(1)合并有序链表无虚拟头比较结点尾插法处理头部特殊情况O(nm)O(1)合并有序链表有虚拟头虚拟头结点统一逻辑O(nm)O(1)
注意事项
指针操作需避免空指针访问如判断 succ ! NULL 再取值。处理边界条件如空链表、单结点链表、环的特殊情况。虚拟头结点常用于简化链表操作的头部逻辑提高代码鲁棒性。
文档主要介绍单链表反转与合并的递归实现方法包括递归思路、代码实现及复杂度分析以下是详细总结
十一、单链表反转递归实现
核心思路通过递归分解问题将长链表反转拆解为短链表反转逐步构建反转后的链表。
递归分解逻辑 问题分解反转 n 个结点的链表 反转第 1 个结点 反转后续 n-1 个结点。递归出口当链表为空或只剩一个结点时直接返回头结点无需反转。关键操作 先递归反转后续结点从第 2 个结点开始得到新链表头指针 new_head。修改第 2 个结点的指针使其指向第 1 个结点head-next-next head。将第 1 个结点的指针置为 NULL使其成为新链表的尾结点。 代码实现Node *reverse_recursion(Node *head) {// 递归出口空链表或单结点链表if (head NULL || head-next NULL) {return head;}// 递归反转后续结点得到新链表头指针Node *new_head reverse_recursion(head-next);// 让第 2 个结点指向第 1 个结点head-next-next head;// 第 1 个结点置为尾结点指针域为 NULLhead-next NULL;return new_head; // 返回新链表头指针
}复杂度分析 时间复杂度O(n)每个结点递归处理一次。空间复杂度O(n)递归栈深度最多为 n链表长度存在栈溢出风险。
十二、合并两条有序单链表递归实现
核心思路通过递归逐层比较两条链表的当前结点将较小结点作为当前层结果并递归合并剩余结点。
递归分解逻辑 问题分解合并链表 list1 和 list2 选择当前较小结点 递归合并剩余结点。递归出口当任一链表为空时直接返回另一链表已处理完所有结点。关键操作 比较 list1 和 list2 的当前结点选择较小者作为当前层合并结果。将较小结点的 next 指针指向递归合并剩余结点的结果形成链式合并。 代码实现Node *merge_lists3(Node *list1, Node *list2) {// 递归出口处理空链表if (list1 NULL) return list2;if (list2 NULL) return list1;// 选择较小结点并递归合并剩余结点if (list1-data list2-data) {list1-next merge_lists3(list1-next, list2); // 递归合并 list1 剩余结点和 list2return list1; // 返回当前较小结点} else {list2-next merge_lists3(list1, list2-next); // 递归合并 list1 和 list2 剩余结点return list2; // 返回当前较小结点}
}复杂度分析 时间复杂度O(mn)每条链表的每个结点递归处理一次m、n 为链表长度。空间复杂度O(mn)递归栈深度最多为 mn大链表场景下可能导致栈溢出。
十三、递归与迭代实现对比
操作实现方式时间复杂度空间复杂度优缺点对比单链表反转迭代O(n)O(1)原地算法无额外空间效率高适合大链表逻辑较直观需维护三指针prev、curr、succ。递归O(n)O(n)递归栈代码简洁利用递归分解问题但存在栈溢出风险大链表场景下不推荐。合并有序链表迭代O(mn)O(1)原地算法需处理头部特殊情况或用虚拟头结点简化逻辑稍复杂无栈风险。递归O(mn)O(mn)递归栈代码更简洁递归分解自然但栈空间占用随链表长度增长大链表易栈溢出。
十四、注意事项与扩展
递归的局限性 递归深度受系统栈空间限制处理长链表如上万结点时可能引发栈溢出错误。迭代实现更适合生产环境尤其对性能和稳定性要求高的场景。 虚拟头结点的应用 迭代合并链表时虚拟头结点可统一头部和后续结点的处理逻辑减少边界条件判断如 merge_lists2 函数。 其他反转思路 复制头插法遍历原链表复制每个结点并采用头插法构建新链表。时间复杂度 O(n)但需额外空间且涉及内存分配效率较低。
十五、总结
递归的核心思想将大问题分解为同类型小问题通过递归出口终止分解逐层构建结果。适用场景递归适合逻辑简洁、链表长度较小的场景迭代更适合长链表或对性能敏感的场景。指针操作要点递归实现中需注意指针指向的正确性如反转时避免链表断开确保每一步递归调用后链表结构有效。
文档主要介绍七种基于比较的排序算法包括简单排序冒泡、选择、插入、希尔排序及高级排序归并、快速、堆排序以下是从第十六条开始的详细总结
十六、插入排序重点
核心思想将未排序元素逐个插入到已排序序列的合适位置类似扑克牌整理。操作流程 从第二个元素开始视为未排序元素与前序已排序元素比较。若未排序元素小于前序元素则前序元素后移直至找到合适位置插入。 代码逻辑伪代码for (i 1; i n; i) { temp arr[i]; j i - 1; while (j 0 arr[j] temp) { arr[j1] arr[j]; j--; } arr[j1] temp;
}复杂度 时间复杂度O(n²)最坏/平均但常数项和系数优于冒泡、选择排序实际性能更好。空间复杂度O(1)原地排序。 稳定性稳定相邻交换不改变相同元素相对顺序。适用场景小规模数据排序的首选算法。
十七、希尔排序了解
核心思想插入排序的改进版通过增量递减将数组分组对每组进行插入排序逐步缩小增量至1。操作流程 选择初始增量如 gap n/2将数组分为 gap 组每组元素下标差为 gap。对每组进行插入排序缩小增量如 gap gap/2重复直至 gap1此时退化为插入排序。 复杂度 时间复杂度依赖增量选择介于 O(nlogn) 到 O(n²) 之间通常优于插入排序。空间复杂度O(1)原地排序。 稳定性不稳定跨组交换可能改变相同元素相对顺序。评价适用场景有限大数据集下不如高级排序小数据集下牺牲稳定性但性能提升不明显。
十八、归并排序高级排序
核心思想分治策略递归将数组分成两半分别排序后合并有序子数组。关键步骤 分解将数组从中间分成左右两部分直至子数组长度为1有序。合并将两个有序子数组合并为一个有序数组需额外空间存储临时合并结果。 代码逻辑伪代码void merge_sort(int arr[], int left, int right) { if (left right) { mid (left right)/2; merge_sort(arr, left, mid); merge_sort(arr, mid1, right); merge(arr, left, mid, right); // 合并两个有序子数组 }
}复杂度 时间复杂度O(nlogn)所有情况均稳定。空间复杂度O(n)需额外数组存储合并结果。 稳定性稳定合并时保留相同元素顺序。适用场景需要稳定排序的大数据集如外部排序磁盘数据排序。
十九、快速排序高级排序重点
核心思想分治策略选择基准值pivot将数组分为小于/大于基准值的左右两部分递归排序子数组。关键步骤 分区选择基准值通过交换将数组分为左 pivot、中 pivot、右 pivot三部分。递归对左右子数组重复分区操作直至子数组长度为1。 优化点 基准值选择随机选、三数取中避免最坏情况O(n²)。双向分区从两端向中间扫描减少交换次数。 复杂度 时间复杂度平均 O(nlogn)最坏 O(n²)可通过基准值优化规避。空间复杂度O(logn)递归栈深度平均情况最坏 O(n)退化为链表递归。 稳定性不稳定跨区交换可能改变相同元素顺序。适用场景大数据集排序的首选性能最优但需注意栈溢出风险大递归深度。
二十、堆排序高级排序
核心思想基于堆大顶堆/小顶堆结构每次将堆顶元素最大值/最小值与末尾元素交换逐步构建有序数组。关键步骤 建堆将数组转换为大顶堆父节点≥子节点。排序交换堆顶最大值与末尾元素对前 n-1 个元素重新建堆重复直至排序完成。 复杂度 时间复杂度O(nlogn)建堆 O(n)每次调整堆 O(logn)。空间复杂度O(1)原地排序仅利用数组本身空间。 稳定性不稳定堆顶交换可能破坏相同元素顺序。适用场景无需递归、空间受限的大数据集排序如操作系统进程调度。
二十一、七种排序算法对比表
算法时间复杂度最坏时间复杂度平均空间复杂度稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定玩具算法仅学习用途选择排序O(n²)O(n²)O(1)不稳定玩具算法仅学习用途插入排序O(n²)O(n²)O(1)稳定小规模数据首选希尔排序O(n²)O(nlogn)~O(n²)O(1)不稳定了解即可实际应用少归并排序O(nlogn)O(nlogn)O(n)稳定大数据集稳定排序快速排序O(n²)O(nlogn)O(logn)不稳定大数据集首选性能最优堆排序O(nlogn)O(nlogn)O(1)不稳定无需递归、空间受限场景
二十二、总结与建议
简单排序选择 小规模数据优先使用插入排序性能最佳稳定。学习用途了解冒泡、选择排序逻辑但无需用于实际项目。 高级排序选择 需要稳定性选归并排序如数据库排序、物流订单排序。性能优先选快速排序默认场景需注意基准值优化。空间受限/禁止递归选堆排序如嵌入式系统、内核排序。 算法实现建议 必学插入排序简单高效、快速排序工业级应用。扩展学习归并排序分治思想、堆排序数据结构应用。 复杂度注意点 时间复杂度是趋势描述O(n²) 算法在小规模下可能比 O(nlogn) 更快如插入排序 vs 快排。空间复杂度需关注额外堆空间如归并排序栈空间如递归快排可能导致栈溢出。
