Discover
IndexIndexIndexAboutAboutAboutEngineeringEngineeringEngineeringJournalJournalJournalFictionFictionFictionCredentialsCredentialsCredentialsDiscoverDiscoverDiscoverFriendsFriendsFriendsXiangqiXiangqiXiangqi
Before the work
AboutFriendsDiscover
The work itself
EngineeringJournalFiction
After the work
CredentialsXiangqiComing Soon
Connect
HHZZHH
© 2024–2026 HZH — PERSONAL ARCHIVE
←INDEX←ENGINEERING

// 02 — DATA-STRUCT数据结构

10 ENTRIESENGINEERING
SORTOLDEST FIRSTNEWEST FIRST

线性表、树、图与经典算法

001算法复杂度:用执行次数给算法定价从旋转数组的超时说起,讲清 T(N) 怎么数、大 O 怎么化简、常见阶的增长速度、最坏/平均/最好的区别,以及递归的空间为什么按峰值算。2025.03.12→002顺序表与链表:连续内存和指针链的代价从顺序表的三段边界讲到单链表的结点、二级指针、反转/找中点/合并/判环,再到带头双向循环链表,并用一张表把两种存储的取舍算清。2025.03.13→003栈与队列:两种受限线性表的边界条件栈只在栈顶进出,队列从队尾进、队头出;数组栈、链式队列、循环队列的判空判满各有一套约定,两个结构还能互相实现。2025.03.26→004二叉树:递归定义、遍历序列与堆从一组对不上的遍历结果切入,讲树的术语、二叉树与完全二叉树的性质、递归和非递归遍历、结点统计、构建销毁,以及堆的上下调整与 O(n) 建堆。2025.04.02→005排序:八种算法的划分、边界与稳定性插入、希尔、选择、冒泡、堆、快排、归并、计数排序的实现与边界;霍尔、挖坑、前后指针三种划分,三数取中与小区间优化,以及稳定性总表。2025.04.07→006B-树:阶、结点分裂与磁盘页,为什么索引用多路平衡树数据大到装不进内存时,查找代价从比较次数变成读盘次数。按课件讲清 m 阶 B 树的六条性质、关键字与孩子指针的数量关系、插入时的连锁分裂、删除时的借位与合并,再对比 B+ 树、B* 树,落回 MyISAM 与 InnoDB 的索引差异。2025.07.01→007并查集:一个数组表示森林,路径压缩与按大小合并并查集只维护“谁和谁在同一集合”,用一个父指针数组就能完成合并和查询。按课件讲清负数编码、Union 两行的顺序、路径压缩的两趟循环、按大小合并与反阿克曼复杂度,再落到省份数量、等式方程和 Kruskal。2025.07.02→008图:邻接矩阵与邻接表、两种遍历、最小生成树和三种最短路图这一讲的主线是“关系怎么存、怎么走、怎么选最便宜的走法”。从顶点集与边集的定义出发,比较邻接矩阵和邻接表的空间与度数计算,写出 BFS/DFS,再用 Kruskal、Prim、Dijkstra、Bellman-Ford、Floyd 覆盖生成树与最短路,补上课件没讲的拓扑排序和连通分量。2025.07.03→009LRU Cache:哈希表存位置,双向链表排新旧LRU 要做到 get 和 put 都是 O(1),靠的是哈希表定位、双向链表排序:命中搬到表头,满了从表尾淘汰。按课件写完整实现,讲清迭代器同步、方向约定和更新已存在 key 的边界,再对比 LFU。2025.07.04→010跳表:随机层数、多层索引与期望对数级查找跳表用多层稀疏链表替代平衡树的旋转:每个结点插入时随机摇一个层数,查找从最高层向右、走不动就下降。按课件讲清 p=1/4 的层数分布、期望 O(logN) 的推导、查找插入删除的三处接线边界,再对比平衡树与哈希表,落到 Redis ZSet 的 span 和 backward。2025.07.05→