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 1e510; //创建 int e[N],ne[N],h,id; int main() { return 0; }2.1.3头插头插在链表的头部插入一个元素细节问题修改指针的顺序是②-①一定要先修改②再修改①代码编写1.id标记新结点的位置同时储存新结点的值e[id]x2.修改新结点的指针域让其指向哨兵位的下一个位置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完成步骤id,标记新结点的位置同时存储新结点的值e[id] x修改新结点的指针域让其指向p的下一个位置ne[id] ne[p]修改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.最后修改哨兵位的右指针①完成步骤id,标记新结点存储的位置把新的元素存储下来e[id] x修改新结点的前驱指针让其指向哨兵位pre[id] h修改新结点的后继指针让其指向哨兵位的下一个位置ne[id] ne[h]修改y结点的前驱指针让其指向新的结点pre[ne[h]] id修改哨兵位的后继指针让其指向新的结点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实现步骤id,标记新结点存储的位置把新的元素存储下来e[id] x修改新结点的前驱指针让其指向p位置pre[id] p修改新结点的后继指针让其指向p位置的下一个位置ne[id] ne[p]修改p下一个位置的前驱指针让其指向新的结点pre[ne[p]] id修改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修改指针的顺序先修改新结点x的左右指针然后修改结点1的右指针最后修改p的左指针实现步骤id标记新结点存储的位置把新的元素存储下来e[id] x修改新结点的前驱指针让其指向p的前一个位置pre[id] pre[p]修改新结点的后继指针让其指向p位置ne[id] p修改p前一个位置的后继指针让其指向新的结点ne[pre[p]] id修改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; }