new

静态实现是利用两个数组配合来模拟链表。

一个表示数据域另一个表示指针域它的运行速度很快。

下面演示的也都是单链表的静态实现。

2.定义

两个足够大的数组elem数组e用来存数据next数组ne用来存下一个结点的位置变量

const

{id;e[id]x;mp[x]id;ne[id]ne[h];ne[h]id;

4.遍历链表

i;for(ine[h];i;ine[i]){if(e[i]x)return

}return

第一种方式就是遍历链表如果存储的值数据范围不大就可以用哈希表优化就是第二种方式。

当然第二种方式是有局限性的一是存的数据过大会导致崩溃二是不能存在相同的数据否则这个数组中的部分数据会进行刷新。

6.在任意位置之后插入元素

{id;e[id]x;mp[x]id;ne[id]ne[p];ne[p]id;

void

{if(ne[p]){mp[e[ne[p]]]0;ne[p]ne[ne[p]];}

在单链表的模拟实现中我们可以发现虽然一个节点是由其数据域和指针域组成的但真正代表该节点信息的是数据域和下标指针域只是为了连接下一个节点的工具其实就是下一个节点的下标本质上是属于下一个节点的。

有了这个工具我们就能通过elem数组找到下一个节点的数据域也能通过next数组找到下一个节点的指针域。

以上就是单链表的内容了。

那我们为什么不像顺序表一样实现一个尾插、尾删、删除任意位置的元素等操作呢

1.实现方式

依旧采用静态实现的方式。

双向链表无非就是在单链表的基础上加上一个指向前驱的指针那就再来一个数组充当指向前驱的指针域即可。

2.定义

id;e[id]x;mp[x]id;pre[id]h;ne[id]ne[h];pre[ne[h]]id;ne[h]id;

4.遍历链表

{id;e[id]x;mp[x]id;pre[id]p;ne[id]ne[p];pre[ne[p]]id;ne[p]id;

7.在任意位置之前插入元素

{id;e[id]x;mp[x]id;pre[id]pre[p];ne[id]p;ne[pre[p]]id;pre[p]id;

void

{mp[e[p]]0;ne[pre[p]]ne[p];pre[ne[p]]pre[p];

我们可以看出双向链表只是在单链表的基础上加了pre这个前驱指针数组本质和单链表无异就是清楚指针域之间的关系。

回看之前实现的带头单向链表。

我们定义0表示空指针但其实哨兵位就在0位置所有的结构正好成环。

因此循环链表就是在原有的基础上让最后一个元素指向表头即可。

在这里就用一道算法题来说明循环链表。

因为报数一直绕着圈进行所以我们可以使用循环链表。

操作的次数比较明显因为要使所有人出圈所有要操作总人数的次数也就是n。

在进行每一步操作时要数m个人但是如果数到第m个的话我们改变其前面元素的指针域就会很困难了所以我们可以数m-1次再使用指针域找到第m个人的信息。

#include

是非常耗时的操作效率不高在竞赛中一般不会使用。

因为和vector都是STL的容器使用操作也差不多只要正常使用接口就能实现。

list