前情提要
仅为个人看法/想法，有误请轻喷而非倾盆。
在这篇话题及以后我会尽量遵守Markdown守则。
本人习惯使用C/C++也会一点其他的语言，对于歧视编程语言的比较反感，所以请不要“贴脸开大”。
关于线性的数据结构，大家绝对有所了解。
例如 数组 链表 一类都是线性数据结构。
而数组又与链表有何不同呢？
接下来请让我进行讲解：
数据结构的定义
数据结构，即为能够存储数据的结构。
而 线性数据结构 则是只消耗 O (N) 内存存储原数据的数据结构。
比如 数组 链表 栈 队列 一类都属于线性数据结构。
我要讲的就是其中的 数组 和 链表 。
数组
定义与使用
何为数组？数组即是一块连续的内存。
在 C/C++ 中，数组是这么使用的：
定义：
int a[N];
调用：
a[i];
int 可以替换为任意其他的数据类型，
a 可以替换为其他任意合法的变量名，
N 表示的就是数组的大小，
i 表示当前调用的下标。
时空复杂度
观察数组的相关知识，可以发现数组 占用空间有限，无法变动 。
并且 平均时间复杂度 如下：
| 操作 | 无序数组 | 有序数组 |
|---|---|---|
| 增加 | O (N) | O (N) |
| 删除 | O (N) | O (N) |
| 修改 | O (1) | O (1) |
| 查找 | O (N) | O (log_{2} N) |
注：增加、删除、修改 操作均不包含查找所使用的时间
链表
在学习链表知识之前，要先引入 结构体 与 指针 的相关知识
指针
指针是一种指向一种个变量 地址 的变量。
定义方式如下：
int *p;
用指针新增一个值的方式如下：
int *p = new int;
// 前后的变量类型必须相符
修改指向地址的方式如下：
p = &a;
修改指向值的方式如下：
*p = b;
删除/释放指针的方式如下：
delete p;
// 绝对！绝对！绝对要记住！
// delete 只可以用于局部用 int *p = new int 定义的指针！
p 表示一个指针的名字，可以改成任意合法的变量名，
& 表示对一个变量取地址，
* 是解引用符，在调用指针前放一个 * 可以获取它指向的值，
a b 可以是任意值和变量。
结构体
结构体，即为一个有固定结构（自定义数据类型，在一个节点内可以存储多个变量）的数据类型。
声明方式如下：
struct Node {
Node p;
int a;
char b;
double c;
// ...
};
定义：
Node node;
Node o;
调用内部值：
node -> p;
node.a;
node.b;
node.c;
// ...
单向链表
根据上述信息，不难得出单向链表的写法。
首先是声明一个 Node 节点。
struct Node {
int data;
Node *next;
};
data 表示当前节点储存的值，
next 指向下一个节点的指针。
在写插入之前，还需要定义一下头尾的 哑节点。
哑节点不存储任何值，只在头尾出现，不会被删除、使用。
Node head;
Node end;
再于主函数内调整指向。
signed main (void) {
head.next = &end;
end.next = nullptr;
}
开始写一下 插入节点 的操作吧，我们需要定义一个 New Node，将这个新节点插入到 node 后。
- 我们需要先将新节点指向目标的下一个节点，
- 再将旧节点的下个节点指向新节点。
void insert (Node *node, int val) {
Node *newNode = new Node;
newNode -> data = val;
newNode -> next = node -> next;
node -> next = newNode;
return;
}
删除：
删除目标的下一个节点。
- 使用临时节点指向下一个下标，
- 将
node的指针指向它后面的第二个节点后释放临时节点和需要删除节点的内存。
如果不及时释放，则会出现 野指针 （free pointer），占用不必要的内存。
void dlt (Node *node) {
Node *temp = node -> next;
if (temp != &end) {
node -> next = temp -> next;
delete temp;
}
return;
}
查找：
上述的两种操作都需要查找操作的支持，这里就来讲一下链表的查找。
- 根据位置查找
这里用for循环就极为方便，
我们只需在一路上判断当前节点是否为哑节点end。
Node *findsub (int n) {
Node *newNode = &head;
for (int i = 1; i <= n; ++ i) {
if (newNode -> next == end.next) return nullptr;
if (i == n) return newNode;
newNode = newNode -> next;
}
return nullptr;
}
- 根据值查找
既然是根据值进行查找，那么就不需要其他的多余操作了。
只需要先定义一个新节点指针指向链表中的第一个节点随后一直遍历直到找到了那个节点。
Node *findVal (int val) {
Node *newNode = head.next;
while (newNode -> data != val) {
if (newNode -> next -> data == val) return newNode -> next;
if (newNode -> next == &end) return nullptr;
}
return nullptr;
}
完整代码
#include <stdio.h>
struct Node {
Node *next;
int data;
};
struct Chain {
Node head, end;
Node *findsub (int n) {
Node *newNode = &head;
for (int i = 1; i <= n; ++ i) {
if (newNode -> next == end.next) return nullptr;
if (i == n) return newNode;
newNode = newNode -> next;
}
return nullptr;
}
Node *findVal (int val) {
Node *newNode = head.next;
while (newNode -> data != val) {
if (newNode -> next -> data == val) return newNode -> next;
if (newNode -> next == &end) return nullptr;
}
return nullptr;
}
void insert (Node *node, int val) {
Node *newNode = new Node;
newNode -> data = val;
newNode -> next = node -> next;
node -> next = newNode;
return;
}
void dlt (Node *node) {
Node *temp = node -> next;
if (temp != &end) {
node -> next = temp -> next;
delete temp;
}
return;
}
};
signed main (void) {
Chain chain;
chain.insert (&chain.head, 114514);
chain.insert (&chain.head, 11);
chain.dlt (chain.findVal (11)); // 删除 11 的下一个元素，即删除 114514
return 0;
}
最后总结一下复杂度：
| 操作 | 无序数组 | 有序数组 | 链表 |
|---|---|---|---|
| 增加 | O (N) | O (N) | O (1) |
| 删除 | O (N) | O (N) | O (1) |
| 修改 | O (1) | O (1) | O (1) |
| 查找 | O (N) | O (log_{2} N) | O (N) |
线性数据结构，单向链表篇，完结
下期讲什么（ 7 月 1 日截止）
- 栈
- 队列（简化版）
- 双向链表