单链表(数组模拟法)
对于链表这个数据结构,它是很抽象的,不太好理解因为它用到了我们不太熟系的内容-指针,可是万物皆可模拟;
那我们怎么用数组去模拟呢?
例如我们在做 树 图等题目时,我们会采取数组模拟的方式来建立邻接表,这个效率会比链表来建立邻接表高一点
第一步(确定所需要的东西)
我们在链表中需要用节点来存储数据域,所以我们需要一个 e[];
其次我们需要存储每个节点的下一个节点,来把整个节点来串起来, 我们需要一个 ne[];
头结点存储第一个点的下标 head;
以及每次串起来的下标 idx;
第二步(定义第一步所需要的东西)
我们将这些东西定义在堆中,也就是所有函数的外面,他会自动初始化为零
const int N = 1e5+10;
int idx,e[N],ne[N],head;
第三步(初始化)
我们把各个功能用函数表示出来
void init()//初始化函数
{
head=-1;
idx=0;
}
第四步(写函数)
头插法
void add_to_head(int x)//x是我们想存储的date
{
e[idx]=x;
ne[idx]=head;
head=idx++;
}
在某个节点号后面插数据
void add_to_k(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
删除某个节点号后面的节点
void remove(int k)
{
ne[k]=ne[ne[k]];
}
整体代码组合如下(题库搜 826单链表)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int head,idx,e[N],ne[N];
void init()
{
head=-1;
idx=0;
}
void add_to_head(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void add_k(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k)
{
ne[k]=ne[ne[k]];
}
int main()
{
init();
int m;
cin>>m;
while(m--)
{
char op;
cin>>op;
if(op=='H')
{
int x;
cin>>x;
add_to_head(x);
}
else if(op=='D')
{
int k;
cin>>k;
if(k==0) head=ne[head];
else remove(k-1);
}
else if(op=='I')
{
int k,x;
cin>>k>>x;
add_k(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
{
cout<<e[i]<<" ";
}
return 0;
}
学习建议,对于有些算法我们要去寻找它的规律,考虑如何简化代码,不要背代码,多用手操作,如果忘了怎么写就去
百度查一查;
牛逼