21.12.27 第一次复习
折腾了快一个小时,查博客翻书总算是把静态链表彻底搞懂了
没系统学过数据结构还是吃亏啊唉
个人总结,静态链表对比动态链表最大的一个问题就是多了一个维度,也就是数组下标i
动态链表
p是一个节点(二元),有数据域p->data
和地址域p->next
两个
注意,这里的
p->next
虽然名义上是p这个节点的地址域,但实际含义是链表的下一个节点,也就是p->next
是二元的,可以取值或继续取地址
静态链表
Y总所讲e[i]
对应p->data
,ne[i]
对应p->next
。
但是在这里有一个困惑了我很久的点,就是这个i,因为动态链表中,p
直接从头节点开始遍历,并没有i
的存在,这也让我一直搞不清出e[N],ne[N]和数组
是怎么对应起来的
其实这个
i
就是插入数组的顺序下标,在静态链表中,每个节点的ne[i]
指针对应的就是在插入数组中,下一个插入的数的下标
所以在模拟静态链表时,应该在链表的旁边再画一个顺序输入的数组,标明其顺序数组下标i
以及对应的指向下标ne[i]
上边的是两数组:描述了一个链表的性质;下面是这两个数组表现出的行为,长得是个链表
总结
动态链表的指针就是一个节点,是二元的既有数据也还有指针
静态链表的指针就是ne[i]
,i
是输入数组的顺序读入,我们相当于把i从0到n
改写成了一个符合链表顺序的i下标数组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
// head 表示头节点下标
// e[i] 该节点的值
// ne[i] 该节点的指针
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 将x插入到头节点
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head; // head:头节点的指针
head = idx;
idx ++ ;
}
// 将x插入到下标是k的节点的后面
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++ ;
}
// 将k点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
// 不能k++,ne[ne[k]]不一定等于k++,也许是尾节点-1
}
int main()
{
int m;
cin >> m;
init();
while (m -- )
{
int k, x;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
if (!k) head = ne[head];
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}