企业官网建设流程全解析

1.链表的概念

1.1链表的定义

链表：用链式存储实现的线性表

链式存储：在内存中，不仅存储当前元素的信息，还存储前继或后继结点的地址

通过地址实现元素与元素之间的关系

1.2链表的分类

将各种类型的链表排列组合，总共有8种不同链表结构：

虽然链表种类较多，我们只需要掌握单向链表、双向链表和循环链表即可

2.链表的模拟实现

2.1单链表的模拟实现

2.1.1 实现方式

链表的实现方式分为动态实现和静态实现两种

动态实现：通过new申请结点，通过delete释放结点的形式构造链表

特点：

1.动态实现特别能体现链表的特性，代码编写也很清晰

2.但是，频繁的调用new和delete会有很大的时间开销

静态实现：

两个足够大的数组：其中一个数组elem存储数据，充当数据域；另一个数组next存储下一个元素的下标，充当指针域

两个变量：其中一个变量h标记头结点的下标；另一个变量id标记新来结点的存储位置

2.1.2 定义-创建-初始化

1.两个足够大的数组，一个用来存数据，一个用来存下一个结点的位置

2.变量h，充当头指针，表示头结点的位置

3.变量id，为新来的结点分位置

#include <iostream> using namespace std; const int N = 1e5+10; //创建 int e[N],ne[N],h,id; int main() { return 0; }

2.1.3头插

头插：在链表的头部插入一个元素

细节问题：修改指针的顺序是②->①；一定要先修改②再修改①

代码编写：

1.id++，标记新结点的位置；同时储存新结点的值：e[id]=x

2.修改新结点的指针域，让其指向哨兵位的下一个位置：ne[id]=ne[h]

3.修改哨兵位的指针域，让其指向新结点：ne[h]=id

//头插 void push_front(int x) { //先把x放在一个格子里面 id++; e[id] = x; //修改指针，顺序不能颠倒 //1.x的右指针指向哨兵位的后继 //2.哨兵位的右指针指向x ne[id] = ne[h]; ne[h] = id; }

2.1.4遍历链表

遍历链表：通过指针域，访问链表中的所有元素

//打印链表 void print() { //定义一个指针从头结点开始 //通过ne数组逐渐向后移动 //直到遇到空指针 for(int i = ne[h];i;i = ne[i]) { cout << e[i] << " "; } cout << endl << endl; }

2.1.5按值查找

按值查找：查询链表中是否存在元素x，如果存在，返回该元素存储的下标

策略一：遍历整个链表，一个一个对比

策略二：重新创建一个数组mp，标记每一个元素存储的下标。此时 mp[i] 表示：i 这个元素存储的位置

局限性：1.数据的值不能过大；2.链表中不能存重复的数，不然无法标记位置

//按值查找 int find(int x) { //解法一：遍历链表 for(int i= ne[h];i;i = ne[i]) { if(e[i] == x) return i; } return 0; //解法二：用mp数组优化 return mp[x]; }

2.1.6在任意位置之后插入元素

定义：在存储位置为p的元素后面，插入新的元素x

完成步骤：

1. id++,标记新结点的位置；同时存储新结点的值：e[id] = x
2. 修改新结点的指针域，让其指向p的下一个位置：ne[id] = ne[p]
3. 修改p位置的指针域，让其指向新结点：ne[p] = id

//在存储位置p的元素后面，插入一个元素x void insert(int p,int x) //一定要注意，这里的p是位置，不是元素 { id++; //x这个元素分配的位置 e[id] = x; //将x放在id位置处 ne[id] = ne[p]; //x指向p的后面 ne[p] = id; //p指向x }

2.1.7 删除任意位置之后的元素

定义：删除存储位置为p后面的元素

直接让p指向下一个元素的下一个元素即可：ne[p] = ne[ne[p]]

当我们删除的是链表中的最后一个元素后面的元素时：

ne[ne[p]]会找到哨兵位的下一个结点，此时再去赋值就会让链表成环，破坏了实际的结构

//删除存储位置为p后面的元素 void erase(int p) //注意p表示元素的位置 { if(ne[p]) { mp[e[ne[p]]] = 0; //将p后面的元素从mp中删除 ne[p] = ne[ne[p]]; //指向下一个元素的下一个元素 } }

2.1.8删除任意位置的元素

定义：删除存储位置为p的元素

实现步骤：

1.让p的前驱结点的后继指针指向p的后继结点：ne[pre[p]] = ne[p]

2.让p的后继结点的前驱指针指向p的前驱结点:pre[ne[p]] = pre[p]

//删除下标为p的元素 void erase(int p) { mp[ne[p]] = 0; //从标记中移除 ne[pre[p]] = ne[p]; pre[ne[p]] = pre[p]; }

2.2双向链表的模拟实现

2.2.1实现方式

静态实现方式，创建三个足够大的数组：

第一个数值存储数据；第二个数组存储前一个元素的存储下标；第三个数组存储下一个元素的存储下标

2.2.2定义

#include <iostream> using namespace std; const int N = 1e5 + 10； //创建双链表 int e[N],ne[N],pre[N],id,h; int main() { return 0; }

2.2.3头插

定义：在链表的头部插入一个元素

修改指针的顺序：

1.先修改新结点x的左右指针②和③；

2.然后修改结点y的左指针④；

3.最后修改哨兵位的右指针①

完成步骤：

1. id++,标记新结点存储的位置；把新的元素存储下来：e[id] = x
2. 修改新结点的前驱指针，让其指向哨兵位：pre[id] = h
3. 修改新结点的后继指针，让其指向哨兵位的下一个位置：ne[id] = ne[h]
4. 修改y结点的前驱指针，让其指向新的结点：pre[ne[h]] = id
5. 修改哨兵位的后继指针，让其指向新的结点：ne[h] = id

//头插 void push_front(int x) { id++; e[id] = x; mp[x] = id; //存一下x这个元素的位置 //左指向哨兵位，右指向哨兵位的下一个位置，也就是头结点 pre[id] = h; ne[id] = ne[h]; //先修改头结点的指针，再修改哨兵位，顺序不能颠倒 pre[ne[h]] = id; ne[h] = id; }

2.2.4 遍历链表

直接无视prev数组，与单链表的遍历方式一致

//打印链表 void print() { for(int i = ne[h];i;i = ne[i]) { cout << e[i] << " "; } cout << endl << endl; }

2.2.5 按值查找

直接用mp数组优化

//查找元素x在链表中存储的位置 int find(int x) { //用mp优化 return mp[x]; }

2.2.6在任意位置之后插入元素

定义：在存储位置为p的元素后面，插入新的元素x

实现步骤：

1. id++,标记新结点存储的位置；把新的元素存储下来：e[id] = x
2. 修改新结点的前驱指针，让其指向p位置：pre[id] = p
3. 修改新结点的后继指针，让其指向p位置的下一个位置：ne[id] = ne[p]
4. 修改p下一个位置的前驱指针，让其指向新的结点：pre[ne[p]] = id
5. 修改p的后继指针，让其指向新的结点：ne[p] = id

//在任意位置p的后面插入新的元素x void insert(int p,int x) { id++; e[id] = x; mp[x] = id; pre[id] = p; ne[id] = ne[p]; pre[ne[p]] = id; ne[p] = id; }

2.2.7在任意位置之前插入元素

定义：在存储位置为p的元素前面，插入新的元素x

修改指针的顺序：

1. 先修改新结点x的左右指针
2. 然后修改结点1的右指针
3. 最后修改p的左指针

实现步骤：

1. id++，标记新结点存储的位置；把新的元素存储下来：e[id] = x
2. 修改新结点的前驱指针，让其指向p的前一个位置：pre[id] = pre[p]
3. 修改新结点的后继指针，让其指向p位置：ne[id] = p
4. 修改p前一个位置的后继指针，让其指向新的结点：ne[pre[p]] = id
5. 修改p的前驱指针，让其指向新的结点：pre[p] = id

//在存储位置p的元素前面，插入一个元素x void insert_front(int p,int x) { id++; e[id] = x; mp[x] = id; //存一下x这个元素的位置 //先左指针指向p的前驱，右指针指向p pre[id] = pre[p]; ne[id] = p; //先让p的前驱的右指针指向id //再让p的左指针指向id ne[pre[p]] = id; pre[p] = id; }