Elian's blog page

单链表的定义与头结点 定义单链表是用链式存储方式实现的 线性表。每个结点通常包含数据域和指针域： 1234typedef struct LNode { ElemType data; struct LNode *next;} LNode, *LinkList; data 存放数据元素。 next 存放后继结点地址。 LinkList 强调这是一个单链表。 LNode * 强调这是一个结点指针。 不带头结点头指针 L 直接指向第一个数据结点。空表时 L == NULL。 缺点：对第一个结点的插入、删除需要特殊处理，代码边界情况较多。 带头结点头指针 L 指向头结点，头结点不存储有效数据，只用于统一操作。空表时 L->next == NULL。 优点： 第一个数据结点之前也有一个“前驱”，便于统一插入、删除逻辑。 空表和非空表的很多操作形式一致。 考试代码题中常见，需注意题目是否说明带头结点。 初始化带头结点单链表： 123456bool InitList(LinkList *L) { *L = (LNode...

单链表的插入与删除按位序插入：带头结点ListInsert(&L, i, e) 在第 i 个位置插入元素 e。 核心思路：找到第 i - 1 个结点 prev，将新结点 newNode 插入到 prev 之后。 ↻ + − 基本步骤： 检查 i 是否合法。 从头结点开始寻找第 i - 1 个结点。 申请新结点 newNode，令 newNode->data = e。 令 newNode->next = prev->next，先接住原后继。 令 prev->next = newNode，再让前驱指向新结点。 时间复杂度：查找前驱结点需要 O(n)，真正修改指针为 O(1)。 123456789101112131415161718bool ListInsert(LinkList head, int index, ElemType value) { if (index < 1) return false; LNode *prev = head; int position = 0; while...

空间复杂度定义空间复杂度 S(n) 表示算法所需存储空间与问题规模 n 的增长关系。分析时重点关注随 n 增长而变化的额外空间。 常量空间如果算法运行所需额外空间不随问题规模变化，例如只使用少量局部变量，则 S(n) = O(1)。这种算法也称原地工作。 数组带来的空间 一维数组 flag[n] 通常带来 O(n) 空间。 二维数组 flag[n][n] 通常带来 O(n^2) 空间。 若同时有 flag[n][n] 和 other[n]，总空间为 O(n^2) + O(n) + O(1) = O(n^2)。 递归调用带来的空间递归会产生调用栈。每一层递归调用都需要保存参数、局部变量、返回地址等信息。 若递归深度为 n，每层只使用常量空间，则递归调用的深度决定空间复杂度，S(n) = O(n)。 若第 k 层还申请与 k 相关的空间，总空间要累加各层空间。例如每层使用规模依次为 1, 2, ..., n 的数组，则总空间为 O(n^2)，也可写成...

单链表的查找与建立按位查找带头结点单链表中，GetElem(L, i) 获取第 i 个数据结点。 基本思路：从头结点开始，沿 next 指针向后移动，直到第 i 个数据结点。 ↻ + − 边界： i < 1 非法。 遍历到 NULL 仍未到第 i 个位置，说明位序越界。 时间复杂度：O(n)。 12345678910LNode *GetElem(LinkList head, int index) { if (index < 1) return NULL; LNode *current = head->next; int position = 1; while (current != NULL && position < index) { current = current->next; position++; } return current;} 返回 NULL 表示位序非法或越界。注意这里 position =...

静态链表定义静态链表是用数组实现的链表。它分配一整片连续空间，但元素之间的逻辑顺序不由数组下标相邻体现，而由游标 next 表示。 每个数组元素通常包含： 数据域 data：存储数据元素。 游标 next：存储下一个结点的数组下标。 游标相当于指针，但它存的是数组下标而不是内存地址。 结构示例12345#define MaxSize 10typedef struct { ElemType data; int next;} SLinkList[MaxSize]; SLinkList a 相当于定义了一个长度为 MaxSize 的结点数组。 常用约定 a[0] 可充当头结点。 next == -1 表示已经到达表尾。 可用特殊值如 -2 表示结点空闲。 具体特殊值不是固定标准，关键是题目或代码中约定一致。 基本操作思路初始化： 令头结点游标指向 -1，表示空表。 将其他空闲结点标记为特殊值。 查找： 从头结点出发，根据游标依次访问后继结点。 插入第 i 个位置： 找到一个空闲结点并写入数据。 从头结点出发找到第 i - 1...

存储结构类型存储结构说明如何在计算机中表示数据元素及其逻辑关系。 顺序存储逻辑上相邻的元素，物理存储位置也相邻，元素关系由存储单元的邻接关系体现。典型例子是 顺序表。 特点：支持按地址公式快速访问；要求分配连续存储空间；插入删除常需要移动元素。 链式存储逻辑上相邻的元素，物理位置可以不相邻，通过指针表示元素之间的关系。典型例子是 单链表 和 双链表。 特点：不要求连续空间；扩容灵活；查找前通常需要沿指针遍历；指针域会带来额外空间开销。 索引存储在存储元素信息的同时建立附加索引表。索引项通常形如“关键字 + 地址”，通过索引帮助定位元素。 特点：可提高查找效率；需要额外索引空间；维护索引会增加插入、删除时的成本。 散列存储根据元素关键字直接计算存储地址，也称哈希存储。 特点：理想情况下查找、插入、删除很快；需要处理冲突；性能受散列函数和冲突处理方法影响。 考点提示顺序存储要求物理连续，非顺序存储可以物理离散。存储结构会影响空间分配、插入删除、查找等运算效率，因此分析数据结构题时要同时看逻辑关系和实现方式。

时间复杂度为什么不用运行时间直接评价算法事后统计运行时间会受机器性能、编程语言、编译器质量、运行环境等因素影响，并且有些场景无法先运行再统计。因此通常事前估计算法时间开销 T(n) 与问题规模 n 的增长关系。 渐进时间复杂度时间复杂度通常用大 O 表示，只关心当 n 足够大时增长最快的部分。 常见化简规则： 只保留最高阶项：3n + 3 = O(n)，n^2 + 3n + 1000 = O(n^2)。 忽略常数系数：9999n = O(n)。 加法规则：O(f(n)) + O(g(n)) = O(max(f(n), g(n)))。 乘法规则：O(f(n)) * O(g(n)) = O(f(n)g(n))。 常见阶数从低到高： O(1) < O(log_2 n) < O(n) < O(n log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) <...

Bash Shell Scripting Notes快速索引 主题 关键词 脚本文件 shebang、chmod +x、./script.sh 输出与变量 echo、环境变量、用户变量、命令替换 重定向与管道 >, >>, <, <<, | 算术与退出码 $((...)), $?, exit 条件结构 if, test, [ ], [[ ]], (( )), case 循环 for, C 风格 for, while, break, continue 用户输入 位置参数、shift、getopts、read 文件描述符 exec, 2>, &>, 自定义 fd 脚本控制 信号、后台运行、作业控制、定时任务 1. Bash 空格 / 引号 / 符号速查 用途 语法示例 是否留空 是否加引号 说明 条件判断 [ ... ] [ $a = $b ] ✅ 必须左右留空 ✅ 通常加 =...

[!TODO][x] JS[ ] html[ ] css[ ] framework: React as example Frontend Learning IndexJavaScript JavaScript-Basics：脚本引入、变量、基本类型、类型转换、控制流、函数基础、函数表达式、回调、箭头函数基础。 JavaScript-Objects-and-Data-Structures：对象、拷贝、构造函数、可选链、Symbol、数组、迭代器、Map/Set、WeakMap/WeakSet、Date、JSON。 JavaScript-Advanced-Functions：Rest、Spread、定时器、bind、this 与箭头函数。 HTML目标笔记： HTML Semantic Structure Notes.md 主题范围： 主题 内容 文档结构 <!doctype...

JavaScript Advanced Functions1. rest-parameters-spread1.1. Rest在函数定义中声明一个数组来收集参数。语法是这样的：...变量名，这将会声明一个数组并指定其名称，其中存有剩余的参数。这三个点的语义就是“收集剩余的参数并存进指定数组中”。 1234567function sumAll(...args) { // 数组名为 args let sum = 0; for (let arg of args) sum += arg; return sum; } Rest 参数会收集剩余的所有参数，所以Rest 参数必须放到参数列表的末尾。 1.2. SpreadSpread 语法 看起来和 rest 参数很像，也使用 ...，但是二者的用途完全相反。 当在函数调用中使用 ...arr 时，它会把可迭代对象 arr “展开”到参数列表中。 123let arr = [3, 5, 1]; alert( Math.max(...arr) ); // 5（spread...