算法竞赛阶段二-数据结构（36）数据结构双向链表模拟实现

//#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int N=1e5+10;
//定义
int e[N],pre[N],ne[N],h,id;
int mp[N];
//头插
//  兵          y
//        x 
void push_front (int x)
{
id++;
e[id]=x;
mp[x]=id;
pre[id]=h;
ne[id]=ne[h];
//先修改新节点 
//     pre[ne[id]]=id;    ne【id】就是ne【h】看上边，刚赋的值 
pre[ne[h]]=id;
//     pre[id]=h;
ne[h]=id; //最后改这个 

} 
// 遍历打印，无视pre即可
void print()
{
for(int i=ne[h];i;i=ne[i])
{
cout<<e[i]<<" ";
}cout<<endl;
} 
// 按值查找，mp数组优化·
int find(int x)
{
return (mp[x]);
} 
// 任意位置（存储位置，下标）之后插入
//   p
//   1       3
//       x  
void insert(int p,int x)
{
id++;
e[id]=x;
mp[x]=id;
pre[id]=p;
ne[id]=ne[p];
//    pre[id]=p;
pre[ne[p]]=id;
ne[p]=id;
} 
//任意位置(存储位置，下标）之前插入
//                p
//      1         2
//           x 
void insret_front(int p,int x)
{
id++;
e[id]=x;
mp[x]=id;

ne[id]=p;
pre[id]=pre[p];
ne[pre[p]]=id;
pre[p]=id;
}
//删除任意位置元素
//         p
//   1          2
//           x 
void erase(int p)
{
//    mp[p]=0; 这个不对 
mp[e[p]]=0;

ne[pre[p]]=ne[p];
pre[ne[p]]=pre[p];
} 

int main()
{
for(int i=0;i<6;i++)
{
push_front(i);

}
print();
cout<<    find(0)<<endl;
cout<<    find(2)<<endl;
insert(1,33);
print();
insert(7,88);
print();
cout<<    find(33)<<endl;
cout<<    find(88)<<endl;
insret_front(1,66);
print();
insret_front(3,33);
print();
insret_front(8,100);
print();
insret_front(9,666);
print(); 
erase(1);
print(); 
cout<<    find(100)<<endl;
erase(11);
print(); 
erase(7);
print(); 
erase(find(666));
print(); 
return 0;
}