数据结构拟面试题

1.快排算法void QuickSort(int *arr, int low, int high) { if (low high) { return; } int first low; int last high; int key arr[first]; while (first last) { while (first last arr[last] key) { --last; } arr[first] arr[last]; while (first last arr[first] key) { first; } arr[last] arr[first]; arr[first] key; } QuickSort(arr, low, first - 1); QuickSort(arr, first 1, high); }1. 时间复杂度最好情况O(n log n)每次都能把数组均匀分成两半基准值选得好最坏情况O(n²)数组已经有序 / 逆序基准值选到最大或最小平均情况O(n log n)2. 空间复杂度O(log n)主要是递归调用栈的开销3. 稳定性不稳定排序2.链表反转原地反转// 链表节点定义 struct ListNode { int val; struct ListNode *next; }; // 核心函数三指针反转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL, *curr head, *next NULL; while (curr ! NULL) { next curr-next; // 暂存后继节点 curr-next prev; // 反转当前节点的指向 prev curr; // prev后移 curr next; // curr后移 } return prev; // prev是新的头节点 }可以把curr-next抽象的看成一根有指向的线也就是指针//逆序 /* 从第二个节点开始打断成两个链表 遍历第二个链表依次取出节点头插到第一个链表中 */ void ReverseLinkList(node *head) { if (head NULL || head-next NULL) { return ; } //打断成两个链表 node *tmp head-next-next; //保存第二个链表头的位置 head-next-next NULL; node *p NULL; //遍历第二个链表 while (tmp ! NULL) { p tmp; //保存要头插的节点 tmp tmp-next; //tmp遍历 //头插 p-next head-next; head-next p; } }2.判断链表是否成环//判断链表是否成环 快慢指针int IsLoop(node *head){if (head NULL || head-next NULL) {return 0;}node *quick head;node *slow head;while (quick ! NULL quick-next ! NULL) {slow slow-next;quick quick-next-next;if (slow quick) {return 1;}}return 0;}3.数组与链表的区别是什么各有什么优缺点底层结构数组连续内存空间元素依次紧挨存放通过下标访问。链表非连续内存每个节点包含「数据 下一节点指针」靠指针串联。数组✅ 优点随机访问快下标直接寻址时间复杂度 O(1)内存紧凑无额外指针开销缓存命中率高遍历效率高。实现简单支持下标、位运算等便捷操作。❌ 缺点插入 / 删除效率低中间增删需要移动大量元素O(n)容量固定静态数组大小编译 / 初始化时确定易出现空间浪费或溢出动态数组扩容也伴随拷贝开销。无法灵活碎片化利用内存。链表✅ 优点插入 / 删除极快只需修改指针O(1)找到目标节点后。动态扩容按需申请节点无固定容量限制内存利用灵活。可利用零散内存碎片。❌ 缺点不支持随机访问查找元素必须从头遍历O(n)每个节点额外占用指针内存开销更大链表节点分散缓存效率差。实现相对复杂指针操作易出现野指针、断链问题。适用场景数组频繁查询、遍历元素数量相对固定如查表、矩阵、缓冲区、普通数据存储。链表频繁增删元素数据量动态变化大如 LRU 缓存、哈希表拉链、多项式存储。数组连续内存随机访问快、遍历高效增删慢、容量固定。适合查询多、数据量稳定场景。链表非连续内存增删快、动态扩容不支持随机访问、有指针开销。适合频繁增删、数据动态变化场景。数组的物理结构为顺序存储链表的物理结构为链式存储数组的长度是固定的链表的长度是可变的数组内存占用紧凑链表要存地址有额外开销数组方便任意访问和查找链表方便增和删操作4.栈和队列的区别栈Stack规则后进先出 LIFO只允许在同一端栈顶 做插入、删除、访问。队列Queue规则先进先出 FIFO队尾入队、队头出队两端分别操作。栈✅ 结构简单操作速度快内存开销小函数调用天然依赖栈。❌ 访问受限只能操作栈顶无法随机访问内部元素普通顺序栈存在栈溢出风险。队列✅ 天然实现排队逻辑解耦生产与消费循环队列可高效复用内存。❌ 顺序队列易出现 “假溢出”需实现循环队列优化无法快速访问中间元素。适用场景栈函数调用、递归调用保存返回地址、局部变量、栈帧。表达式求值、括号匹配、语法解析编译器 / 解释器。页面 / 路由后退、浏览器历史记录、撤销操作。深度优先搜索DFS。队列任务排队、消息队列、请求排队服务器处理客户端请求。生产者 - 消费者模型线程 / 进程间数据传递。广度优先搜索BFS。打印机、IO 设备等外设任务调度。限流、削峰缓冲突发流量。栈后进先出仅栈顶操作用于函数调用、递归、括号匹配、撤销功能、DFS。队列先进先出队尾入队、队头出队用于任务排队、生产者消费者、消息队列、BFS、流量削峰。栈是先进后出队列是先进先出栈顶端出入队列是一端进入一端出栈主要应用在函数的调用和递归以及网页和手机的回退队列主要应用在任务排队和消息队列、缓冲区5.链表排序直插void SortLinkList(node *head) { if (head NULL || head-next NULL) { return; } //打断成两个链表 node *tmp head-next-next; //保存第二个链表头的位置 head-next-next NULL; node *p NULL; //虚拟头节点 node *h NULL; //用来遍历第一个链表找插入位置的指针 //遍历第二个链表 while (tmp ! NULL) { p tmp; //拿到当前要插入的结点 tmp tmp-next; //tmp遍历 for (h head; h-next ! NULL h-next-data p-data; h h-next); /* h head; while (1) { if (h-next NULL || h-next-data p-data) { break; } h h-next; } */ //p插入到h后面 p-next h-next; h-next p; } }ListNode* insertionSort(ListNode* head) { if (!head || !head-next) return head; // 1. 初始化哑节点简化操作 ListNode* dummy (ListNode*)malloc(sizeof(ListNode)); dummy-next head; ListNode* lastSorted head; // 已排序部分的最后一个节点 ListNode* curr head-next; // 当前要插入的节点从第二个开始 while (curr ! NULL) { if (curr-val lastSorted-val) { // 情况1当前节点已经比已排序部分大直接扩展 lastSorted curr; } else { // 情况2需要找到插入位置 ListNode* prev dummy; // 找到第一个大于curr-val的节点的前一个位置 while (prev-next-val curr-val) { prev prev-next; } // 执行插入 lastSorted-next curr-next; curr-next prev-next; prev-next curr; } curr lastSorted-next; } ListNode* result dummy-next; free(dummy); return result; }6.哈夫曼树权值计算方法7.合并有序链表/* 1、传参的出错判断 2、释放掉一个头节点 3、创建两个指针p1和p2分别遍历两个链表用于数据大小比较 4、创建tmp指针做链表 */ node *CombineLinkList(node *head1, node *head2) { if (head1 NULL) { return head2; } if (head2 NULL) { return head1; } node *p1 head1-next; node *p2 head2-next; node *tmp head1; //使用tmp做拼接工作 free(head2); //释放多余的头节点 while (1) { if (p1-data p2-data) { tmp-next p2; p2 p2-next; tmp tmp-next; if (p2 NULL) { //当第二个链表没有数据时 tmp-next p1; //tmp直接指向第一个链表的结尾 break; } } else { tmp-next p1; p1 p1-next; tmp tmp-next; if (p1 NULL) { //当第二个链表没有数据时 tmp-next p2; //tmp直接指向第一个链表的结尾 break; } } } return head1; }Node* mergeTwoListsRecursive(Node* l1, Node* l2) { // 1. 终止条件如果有一个为空直接返回另一个 if (l1 NULL) return l2; if (l2 NULL) return l1; // 2. 比较并递归 if (l1-data l2-data) { l1-next mergeTwoListsRecursive(l1-next, l2); return l1; // l1 作为当前的头 } else { l2-next mergeTwoListsRecursive(l1, l2-next); return l2; // l2 作为当前的头 } }8.二分查找int binarySearch(int a[], int n, int key) { int left 0, right n - 1; while (left right) { int mid (left right) / 2; // 中间位置 if (a[mid] key) return mid; else if (a[mid] key) left mid 1; // 去右边 else right mid - 1; // 去左边 } return -1; }9.数据结构物理与逻辑结构速记表分类结构类型核心关键词背这个特性与公式常见对应数据结构物理结构(怎么存)1. 顺序存储连续、相邻、随机访问逻辑相邻 物理相邻访问 O (1)插入删除 O (n)数组、顺序表、顺序栈、堆2. 链式存储指针、不连续、前连后靠指针链接访问 O (n)插入删除 O (1)单 / 双链表、循环链表、二叉树3. 散列存储(哈希)Hash 函数、直接寻址关键字 - 地址冲突解决链地址法、开放定址哈希表 (HashMap)、字典4. 索引存储索引表、关键字 - 地址额外建立索引表以空间换时间B 树索引、数据库索引逻辑结构(怎么关)1. 线性结构一对一、前驱后继有且仅有一个首和尾元素排成一条线数组、链表、栈、队列、串2. 树形结构一对多、层次关系根节点、父节点、子节点非线性层次结构二叉树、BST、红黑树、堆3. 图状结构多对多、网状关系任意两点可连接存在路径与环路无向图、有向图、网4. 集合结构同属集合、无特定关系元素之间无逻辑关联仅属于同一个集合Set (集合)a区分概念顺序存储是物理结构线性表是逻辑结构。数组是 “顺序存储的线性表”。哈希表基于散列存储物理结构不是逻辑结构。b判空 / 判满公式循环队列顺序存储判空front rear循环队列判满(rear 1) % MAXSIZE frontc时间复杂度顺序存储访问最快 O (1)。链式存储遍历慢 O (n)。散列存储查找最快 O (1)平均情况。类别名称主要特点常见应用逻辑结构​集合元素之间无特定关系只属于同一集合集合运算、去重线性结构元素一对一有唯一前驱和后继数组、链表、栈、队列树形结构元素一对多存在层次和分支关系二叉树、堆、B树图形结构元素多对多任意元素可相连社交网络、地图、依赖关系物理结构​顺序存储元素在内存中连续存放支持随机访问数组、顺序表链式存储元素通过指针/引用连接不要求连续链表、树、图的邻接表索引存储建立附加索引结构提高查找效率数据库索引、字典散列存储通过哈希函数直接计算存储位置哈希表、缓存逻辑结构• 集合元素无关系• 线性一对一• 树形一对多• 图形多对多物理结构• 顺序连续存储随机访问快• 链式不连续插入删除方便• 索引额外索引查找快• 散列哈希定位效率高结构大类具体结构名称核心逻辑关系核心特点典型适用场景线性结构元素间一对一的有序关联线性表元素按线性顺序排列除首尾元素外每个元素有唯一前驱和唯一后继1. 元素有序、同类型2. 支持随机访问顺序实现3. 插入 / 删除操作需移动大量元素顺序实现基础数据存储、线性表的基础操作封装栈Stack受限线性表仅允许在栈顶一端进行插入、删除操作1. 核心规则后进先出LIFO2. 操作受限仅栈顶可读写3. 无随机访问能力函数调用栈、表达式求值、括号匹配、深度优先搜索DFS队列Queue受限线性表仅允许在队尾插入、队头删除1. 核心规则先进先出FIFO2. 操作受限仅队头出、队尾入3. 无随机访问能力任务调度、消息队列、广度优先搜索BFS、缓冲区管理数组Arrayn 维线性表元素按行 / 列顺序排列所有元素同类型1. 支持多维索引随机访问效率极高O (1)2. 元素连续存储内存密度高3. 插入 / 删除操作复杂度高需移动大量元素矩阵运算、多维数据存储、批量同类型数据管理非线性结构元素间一对多 / 多对多的复杂关联树Tree一对多的层次结构根节点无父节点其余节点有唯一父节点可有多棵子树无环路1. 严格的层次结构天然适合表达层级关系2. 子树之间相互独立无交叉关联3. 遍历方式多样前 / 中 / 后 / 层序目录结构、组织架构、分类体系、哈夫曼编码二叉树Binary Tree特殊的树结构每个节点最多有 2 棵子树左子树、右子树子树有严格的左右顺序1. 结构规范遍历、查找、插入操作的算法成熟2. 可衍生出二叉搜索树、平衡二叉树、红黑树等高效结构3. 是绝大多数树型算法的基础模型二叉搜索树、AVL 树、红黑树、堆、表达式树图Graph多对多的网状结构由顶点Vertex和边Edge组成顶点间可通过边任意关联允许有环路1. 最灵活的非线性结构可表达任意复杂的关联关系2. 分为有向图 / 无向图、带权图 / 无权图、连通图 / 非连通图3. 核心算法围绕遍历、最短路径、最小生成树、拓扑排序展开社交网络、交通路网、网络拓扑、任务依赖、状态机集合Set元素间无明确逻辑关系仅存在「属于 / 不属于」的归属关系元素唯一、无序1. 元素不可重复无顺序要求2. 核心操作是交集、并集、差集、成员判断3. 是最简单的非线性结构无复杂的关联规则数据去重、集合运算、标签管理、权限控制时间复杂度算法执行基本操作的次数衡量运行快慢。空间复杂度算法额外开辟的内存空间含递归栈、临时数组、辅助变量。10.完全二叉树编码a.数组静态初始化最简单直接用一维数组表示完全二叉树数组顺序就是层序遍历顺序。#include stdio.h // 最大节点数 #define MAX_SIZE 100 // 完全二叉树结构体数组实现 typedef struct { int data[MAX_SIZE]; int size; // 实际节点个数 } CompleteBiTree; // 1. 初始化完全二叉树用给定数组构建 void InitTree(CompleteBiTree *tree, int arr[], int n) { if (tree NULL || n MAX_SIZE) return; // 逐个拷贝数据 for (int i 0; i n; i) { tree-data[i] arr[i]; } tree-size n; } // 2. 层序遍历数组本身就是层序直接遍历即可 void LevelOrder(CompleteBiTree *tree) { if (tree NULL || tree-size 0) { printf(树为空\n); return; } for (int i 0; i tree-size; i) { printf(%d , tree-data[i]); } printf(\n); } // 3. 前序遍历递归 void PreOrder(CompleteBiTree *tree, int idx) { // 下标越界递归终止 if (idx tree-size) return; printf(%d , tree-data[idx]); // 访问根 PreOrder(tree, 2 * idx 1); // 左子树 PreOrder(tree, 2 * idx 2); // 右子树 } int main(void) { // 原始数据按层序给出构建完全二叉树 int arr[] {1, 2, 3, 4, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); CompleteBiTree tree; // 初始化 InitTree(tree, arr, n); printf(层序遍历); LevelOrder(tree); printf(前序遍历); PreOrder(tree, 0); printf(\n); return 0; }b.动态逐个插入初始化动态构建不提前给完整数组逐个节点插入保持完全二叉树形态只能从末尾追加。#include stdio.h #include string.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int size; } CompleteBiTree; // 初始化空树 void CreateEmptyTree(CompleteBiTree *tree) { if (tree NULL) return; memset(tree-data, 0, sizeof(tree-data)); tree-size 0; //memset(起始地址, 填充字节值, 填充总字节数); } // 尾部插入节点完全二叉树只能末尾追加 int InsertNode(CompleteBiTree *tree, int val) { if (tree NULL || tree-size MAX_SIZE) return 0; // 失败 tree-data[tree-size] val; tree-size; return 1; // 成功 } // 层序遍历 void LevelOrder(CompleteBiTree *tree) { if (tree NULL || tree-size 0) { printf(空树\n); return; } for (int i 0; i tree-size; i) { printf(%d , tree-data[i]); } printf(\n); } int main(void) { CompleteBiTree tree; CreateEmptyTree(tree); // 逐个插入节点完成初始化 InsertNode(tree, 1); InsertNode(tree, 2); InsertNode(tree, 3); InsertNode(tree, 4); InsertNode(tree, 5); InsertNode(tree, 6); printf(动态插入后层序遍历); LevelOrder(tree); return 0; }7.顺序表和链表的区别对比维度顺序表 (如 ArrayList)链表 (如 LinkedList)内存布局物理地址连续物理地址不连续节点分散随机访问支持时间复杂度 O(1)不支持需遍历时间复杂度 O(n)插入/删除效率低O(n)效率高O(1)空间管理需预分配可能浪费或溢出动态分配按需申请缓存效率高对CPU缓存友好低缓存命中率低·内存布局连续 vs 分散顺序表它基于数组实现要求所有元素在内存中必须存放在一块连续的区域。这种特性使得它可以通过首地址和元素下标直接计算出任意元素的内存位置这是其高效访问的基础。链表它的节点可以在内存中任意位置动态生成物理上是离散的。每个节点除了存储自身数据还必须包含一个或多个指针用于记录下一个或上一个节点的地址从而将这些分散的节点在逻辑上串联起来。. 访问方式随机访问 vs 顺序访问顺序表支持随机访问。就像数组一样你可以通过下标 arr[i] 在 O(1) 的时间内直接访问到第 i 个元素效率极高。链表只支持顺序访问。如果你想访问第 i 个元素必须从头节点开始沿着指针一个接一个地遍历直到找到目标平均时间复杂度为 O(n)。. 插入与删除移动元素 vs 修改指针顺序表在中间位置插入或删除元素时为了保持内存的连续性需要将该位置之后的所有元素向后或向前移动平均需要移动约一半的元素时间复杂度为 O(n)。链表在已知插入或删除位置的前提下只需要修改相关节点的指针指向即可无需移动任何数据时间复杂度为 O(1)。这也是链表最大的优势所在。. 空间管理与缓存效率顺序表空间管理需要预先分配一块固定大小的内存。分配太小容易溢出分配太大会造成浪费。虽然动态顺序表如 ArrayList可以扩容但扩容操作申请新内存、复制旧数据开销很大。缓存效率由于数据在内存中连续存放非常符合CPU缓存的局部性原理。访问一个元素时CPU会预加载其附近的一整块数据到高速缓存中使得后续访问速度极快。链表空间管理非常灵活用多少申请多少没有空间浪费和扩容问题。但每个节点都需要额外的空间来存储指针导致存储密度低于顺序表。缓存效率由于节点在内存中随机分布CPU无法有效预取数据导致缓存命中率低访问速度相对较慢。8.不同数据结构适用数据结构核心优势核心劣势典型应用场景数组 (Array)随机访问极快 O(1)插入/删除慢 O(n)大小固定矩阵运算、缓存、静态数据列表链表 (Linked List)插入/删除快 O(1)无法随机访问 O(n)额外内存开销频繁增删的列表、底层实现栈/队列哈希表 (Hash Table)查找/插入/删除极快 O(1)无序占用内存较多有冲突风险字典、缓存(Redis)、统计词频、数据库索引栈 (Stack)后进先出 (LIFO)只能访问栈顶函数调用、撤销操作(Undo)、括号匹配队列 (Queue)先进先出 (FIFO)只能访问队头/队尾任务调度、消息队列、广度优先搜索(BFS)二叉搜索树 (BST)有序查找/插入 O(log n)可能退化为链表 O(n)动态查找表平衡树 (AVL/红黑树)严格平衡稳定 O(log n)实现复杂旋转开销数据库索引、C map/set、Java TreeMap堆 (Heap)快速获取最大/最小值 O(1)查找普通元素慢优先队列、Top K 问题、堆排序图 (Graph)表达复杂关系算法复杂空间开销大社交网络、地图导航、推荐系统Trie树 (前缀树)字符串前缀匹配极快空间消耗大搜索自动补全、敏感词过滤8.哈夫曼树编码// 1. 哈夫曼树节点定义 typedef struct HuffmanNode { char ch; // 字符叶子才有 int weight; // 权值频率 int parent; // 父节点下标数组实现方便 int lchild, rchild; } HuffmanNode; // 2. 哈夫曼编码结构体 typedef struct HuffmanCode { char ch; // 字符 char code[100]; // 编码串01串 } HuffmanCode; // 3. 选两个权值最小的节点核心 // 在 0~n-1 中找 parent-1 的两个最小节点 void selectMin(HuffmanNode* HT, int n, int* s1, int* s2) { int i; // 找第一个最小 s1 *s1 -1; for (i 0; i n; i) { if (HT[i].parent -1) { if (*s1 -1 || HT[i].weight HT[*s1].weight) *s1 i; } } // 找第二个最小 s2 *s2 -1; for (i 0; i n; i) { if (HT[i].parent -1 i ! *s1) { if (*s2 -1 || HT[i].weight HT[*s2].weight) *s2 i; } } } // 4. 构造哈夫曼树 // n: 叶子数 void createHuffmanTree(HuffmanNode* HT, int n, int* weights, char* chars) { if (n 1) return; int totalNodes 2 * n - 1; // 总节点数固定叶子n → 2n-1 // 初始化所有节点 for (int i 0; i totalNodes; i) { HT[i].parent HT[i].lchild HT[i].rchild -1; HT[i].weight 0; HT[i].ch 0; } // 初始化叶子节点前n个 for (int i 0; i n; i) { HT[i].weight weights[i]; HT[i].ch chars[i]; } // 开始合并 n-1 次 for (int i n; i totalNodes; i) { int s1, s2; selectMin(HT, i, s1, s2); // 选两个最小 // 建立父子关系 HT[s1].parent i; HT[s2].parent i; HT[i].lchild s1; HT[i].rchild s2; HT[i].weight HT[s1].weight HT[s2].weight; } }把所有权值看成n 棵只有根节点的树构成森林在森林中选两棵权值最小的树作为左右子树构造一棵新树新树根节点权值 两棵子树权值之和把这两棵小树从森林删除加入新树重复 2~4直到森林只剩一棵树→ 就是哈夫曼树特点权值越小的叶子离根越远权值越大的叶子离根越近哈夫曼树没有度为 1 的节点总节点数 2n - 1n 是叶子数9.环型队列一、循环队列顺序存储数组实现默认规则队头front指向第一个元素队尾rear指向最后一个元素的下一个位置数组大小MAXSIZE牺牲一个位置用来区分空和满判空front rear判满(rear 1) % MAXSIZE front二、循环链表链式存储循环链表没有队满一说因为是动态申请结点空间无限。判空带头结点head-next head不带头结点head NULL判满循环链表不存在判满永远不会满三、总结循环队列空front rear满(rear1) % MAXSIZE front循环链表空head-next head满无不存在循环队列不能用 rear front 判满会和空冲突循环链表永远不会满考试问 “循环链表判满条件” 直接答无循环队列是物理结构循环链表是逻辑 存储结构#include stdio.h #define MAXSIZE 5 // 循环队列结构 typedef struct { int data[MAXSIZE]; int front; // 队头指针 int rear; // 队尾指针 } Queue; // 初始化队列 void InitQueue(Queue *q) { q-front q-rear 0; } // 判断队列是否为空 int IsEmpty(Queue *q) { return q-front q-rear; } // 判断队列是否满 // 常用方法牺牲一个位置(rear1)%MAXSIZE front 表示满 int IsFull(Queue *q) { return (q-rear 1) % MAXSIZE q-front; } // 入队 int EnQueue(Queue *q, int val) { if (IsFull(q)) { printf(队列满无法入队\n); return 0; } q-data[q-rear] val; q-rear (q-rear 1) % MAXSIZE; return 1; } // 出队 int DeQueue(Queue *q, int *val) { if (IsEmpty(q)) { printf(队列空无法出队\n); return 0; } *val q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; } // 取队头元素 int GetFront(Queue *q, int *val) { if (IsEmpty(q)) return 0; *val q-data[q-front]; return 1; } // 测试主函数 int main() { Queue q; InitQueue(q); EnQueue(q, 10); EnQueue(q, 20); EnQueue(q, 30); EnQueue(q, 40); EnQueue(q, 50); // 这里会满因为牺牲了一个位置 int x; while (!IsEmpty(q)) { DeQueue(q, x); printf(%d , x); } return 0; }10.各种算法的复杂度11.各种数据结构的用处数据结构核心优势核心劣势典型应用场景数组 (Array)随机访问极快 O(1)插入/删除慢 O(n)大小固定矩阵运算、缓存、静态数据列表链表 (Linked List)插入/删除快 O(1)无法随机访问 O(n)额外内存开销频繁增删的列表、底层实现栈/队列哈希表 (Hash Table)查找/插入/删除极快 O(1)无序占用内存较多有冲突风险字典、缓存(Redis)、统计词频、数据库索引栈 (Stack)后进先出 (LIFO)只能访问栈顶函数调用、撤销操作(Undo)、括号匹配队列 (Queue)先进先出 (FIFO)只能访问队头/队尾任务调度、消息队列、广度优先搜索(BFS)二叉搜索树 (BST)有序查找/插入 O(log n)可能退化为链表 O(n)动态查找表平衡树 (AVL/红黑树)严格平衡稳定 O(log n)实现复杂旋转开销数据库索引、C map/set、Java TreeMap堆 (Heap)快速获取最大/最小值 O(1)查找普通元素慢优先队列、Top K 问题、堆排序图 (Graph)表达复杂关系算法复杂空间开销大社交网络、地图导航、推荐系统Trie树 (前缀树)字符串前缀匹配极快空间消耗大搜索自动补全、敏感词过滤12.顺序表和链表哪个空间利用率高a. 顺序表数组空间利用率较低 / 有浪费原因必须一次性申请连续的一大块内存比如大小 100实际只用了 20 个剩下 80 个空着闲置浪费扩容时通常扩 1.5~2 倍会更浪费每个元素只存数据没有额外开销b.链表动态节点空间利用率较高 / 几乎不浪费原因用一个节点申请一个空间不用提前分配不会闲置但每个节点都多存一个指针域next这部分是额外开销属于 “有效利用率下降”一句话不浪费空位但每个节点都要多带一个指针。顺序表浪费在 “空位置”链表浪费在 “指针域”一般题目问谁空间利用率更高答通常认为链表更高因为它不预留、不闲置。对比项顺序表链表内存连续性连续不连续预分配空间一次性分配易闲置浪费随用随分配无闲置额外开销无只存数据每个节点多一个指针空间利用率较低有空隙浪费较高无空隙但有指针开销适合场景数据稳定、不频繁增删频繁增删、长度变化大13.哈希表初始化、插入、查询代码#include stdio.h #include stdlib.h #include string.h /* 哈希表节点键值对 链表指针 */ typedef struct HashNode { int key; /* 假设键为整数 */ int value; struct HashNode *next; } HashNode; /* 哈希表结构 */ typedef struct HashTable { HashNode **buckets; /* 桶数组每个元素指向链表头 */ int size; /* 桶的数量 */ } HashTable; /* 哈希函数简单的取模 */ static int hash_func(int key, int size) { return key % size; } /* 初始化哈希表 */ HashTable* hash_init(int size) { HashTable *ht (HashTable*)malloc(sizeof(HashTable)); if (!ht) return NULL; ht-size size; ht-buckets (HashNode**)calloc(size, sizeof(HashNode*)); if (!ht-buckets) { free(ht); return NULL; } return ht; } /* 插入键值对若 key 已存在则更新 value */ void hash_insert(HashTable *ht, int key, int value) { int index hash_func(key, ht-size); HashNode *p ht-buckets[index]; /* 查找是否已存在相同 key */ while (p) { if (p-key key) { p-value value; /* 更新值 */ return; } p p-next; } /* 不存在头插法创建新节点 */ HashNode *new_node (HashNode*)malloc(sizeof(HashNode)); new_node-key key; new_node-value value; new_node-next ht-buckets[index]; ht-buckets[index] new_node; } /* 查询 key 对应的 value成功返回 1失败返回 0结果通过 value 指针返回 */ int hash_get(HashTable *ht, int key, int *value) { int index hash_func(key, ht-size); HashNode *p ht-buckets[index]; while (p) { if (p-key key) { *value p-value; return 1; } p p-next; } return 0; } /* 销毁哈希表释放所有内存 */ void hash_destroy(HashTable *ht) { if (!ht) return; for (int i 0; i ht-size; i) { HashNode *p ht-buckets[i]; while (p) { HashNode *temp p; p p-next; free(temp); } } free(ht-buckets); free(ht); } /* 演示示例 */ int main() { HashTable *ht hash_init(10); /* 10 个桶 */ hash_insert(ht, 1, 100); hash_insert(ht, 2, 200); hash_insert(ht, 12, 1200); /* 12 % 10 2与 key2 同桶测试冲突 */ hash_insert(ht, 2, 250); /* 更新 key2 的值 */ int val; if (hash_get(ht, 2, val)) printf(key 2 - value %d\n, val); else printf(key 2 not found\n); if (hash_get(ht, 12, val)) printf(key 12 - value %d\n, val); if (hash_get(ht, 99, val)) printf(key 99 - value %d\n, val); else printf(key 99 not found\n); hash_destroy(ht); return 0; }