1. 数据结构基础概念与算法分析数据结构是计算机存储、组织数据的方式它研究的是数据的逻辑结构、物理结构以及它们之间的关系。在实际编程中选择合适的数据结构能大幅提升程序效率。记得我第一次写学生管理系统时用错了数据结构查询速度慢得让人崩溃后来改用哈希表才解决问题。算法五大特性必须烂熟于心输入零个或多个输入输出至少有一个输出有穷性执行有限步骤后自动结束确定性相同输入必得相同输出可行性可通过基本操作实现时间复杂度计算有个实用技巧把代码中所有循环的嵌套层次画出来。比如双重循环就是O(n²)递归调用就看递归树深度。常见复杂度排序O(1) O(logn) O(n) O(nlogn) O(n²) O(2ⁿ)。考试常考的是快速排序最坏情况O(n²)归并排序稳定在O(nlogn)这些特例。2. 线性表高频考点精讲2.1 顺序表实战技巧顺序表就像一排连续座位知道第一个人的位置就能算出第n个人的位置。考试最爱考插入删除操作// 在位置i插入元素x int InsertSeqList(SeqList *L, int i, ElemType x) { if (L-length MAXSIZE) return 0; // 表满 if (i 1 || i L-length1) return 0; // 位置非法 for (int j L-length; j i; j--) L-data[j] L-data[j-1]; // 后移元素 L-data[i-1] x; L-length; return 1; }易错点移动元素方向不能反从后往前才能避免数据覆盖。时间复杂度O(n)主要消耗在元素移动上。2.2 链表操作陷阱链表就像寻宝游戏每个线索指向下一个藏宝点。常考头插法和尾插法建链表的区别// 头插法创建链表逆序 void CreateListHead(LinkList *L, int n) { *L (LinkList)malloc(sizeof(Node)); (*L)-next NULL; for (int i0; in; i) { Node *p (Node*)malloc(sizeof(Node)); p-data rand()%100; p-next (*L)-next; // 新节点指向原首节点 (*L)-next p; // 头节点指向新节点 } }踩坑提醒头插法建表后元素顺序与输入顺序相反尾插法需要维护尾指针但能保持原序。链表删除时一定要记得free内存否则会造成内存泄漏。3. 栈与队列经典应用3.1 栈的深度剖析栈是种后进先出的结构就像叠盘子。考试重点括号匹配遇到左括号入栈右括号出栈检查表达式求值中缀转后缀时运算符优先级处理是难点// 括号匹配检测 int bracketCheck(char str[]) { Stack S; InitStack(S); for (int i0; str[i]!\0; i) { if (str[i]( || str[i][) Push(S, str[i]); else { if (StackEmpty(S)) return 0; char topElem; Pop(S, topElem); if (str[i]) topElem!() return 0; if (str[i]] topElem![) return 0; } } return StackEmpty(S); }3.2 队列的循环实现循环队列解决假溢出问题关键点队满条件(rear1)%MAXSIZE front队空条件rear front队列长度(rear-frontMAXSIZE)%MAXSIZE// 循环队列入队 int EnQueue(SqQueue *Q, ElemType x) { if ((Q-rear1)%MAXSIZE Q-front) return 0; // 队满 Q-data[Q-rear] x; Q-rear (Q-rear1)%MAXSIZE; // 循环意义下的加1 return 1; }易混淆点区分栈的top指针和队列的front/rear指针移动方向栈是单向移动队列是双向移动。4. 树与二叉树核心算法4.1 二叉树遍历的三种姿势先序、中序、后序遍历的递归写法必须信手拈来// 中序遍历二叉树 void InOrder(BiTree T) { if (T) { InOrder(T-lchild); visit(T); InOrder(T-rchild); } }非递归写法需要借助栈考试常考中序的非递归实现void InOrder2(BiTree T) { Stack S; InitStack(S); BiTree p T; while (p || !StackEmpty(S)) { if (p) { Push(S, p); p p-lchild; } // 走到最左边 else { Pop(S, p); visit(p); p p-rchild; // 转向右子树 } } }4.2 哈夫曼树构建诀窍构造哈夫曼树的五步法将所有节点视为仅含根节点的二叉树选取权值最小的两棵树合并新树根节点权值为左右子树权值之和将新树放回森林重复步骤2-4直到只剩一棵树WPL计算技巧所有叶节点的权值 × 路径长度层数-1之和。考试常给字符出现频率要求设计编码并计算WPL。5. 图论算法重难点突破5.1 最短路径双雄Dijkstra算法单源最短路径初始化集合S只含源点dist数组记录距离每次选取dist最小的顶点u加入S松弛操作更新u的邻接点v的dist值直到所有顶点都加入Svoid Dijkstra(Graph G, int v) { int dist[G.vexnum]; bool final[G.vexnum]; for (int i0; iG.vexnum; i) { dist[i] G.edges[v][i]; final[i] false; } dist[v] 0; final[v] true; for (int i1; iG.vexnum; i) { int min INFINITY; int k; for (int j0; jG.vexnum; j) if (!final[j] dist[j]min) { min dist[j]; k j; } final[k] true; for (int j0; jG.vexnum; j) if (!final[j] (minG.edges[k][j]dist[j])) dist[j] min G.edges[k][j]; } }Floyd算法多源最短路径三重循环核心for (int k0; kn; k) for (int i0; in; i) for (int j0; jn; j) if (A[i][j] A[i][k] A[k][j]) A[i][j] A[i][k] A[k][j];5.2 最小生成树对决Prim算法顶点扩展初始化任选起点U{u}TE∅选择U到V-U的最小权边(u,v)将v加入U(u,v)加入TE直到UVKruskal算法边收集初始化每个顶点自成连通分量选择权值最小的边如果边的两个顶点在不同连通分量则加入直到所有顶点在同一连通分量6. 排序算法终极对比九大排序算法对比表排序方法平均时间复杂度最坏情况空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n¹·³)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(nlogn)O(n²)O(logn)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定基数排序O(d(nr))O(d(nr))O(r)稳定记忆口诀快选堆希不稳定快速、选择、堆、希尔排序不稳定插冒归基稳如山插入、冒泡、归并、基数排序稳定。实际项目中数据量小用插入基本有序用冒泡随机分布用快排内存受限用堆排。
