單鏈表
雙鏈表
這兩道題有一種好寫(xiě)的寫(xiě)法帮哈，就是左右建立哨兵，然后就不需要考慮邊界渗饮，數(shù)組模擬鏈表我還是習(xí)慣性寫(xiě)結(jié)構(gòu)體帶next的寫(xiě)法但汞，更容易理解吧宿刮。
#include<iostream>
using namespace std;
int m,idx;
const int N=100005;
struct node
{
int val,next;
}a[N];
void init()
{
a[0].next=1;
idx=2;
}
//在第k個(gè)數(shù)右邊插入x
void insert(int k,int x)
{
a[idx].val=x;
a[idx].next=a[k].next;
a[k].next=idx++;
}
void del(int k)
{
a[k].next=a[a[k].next].next;
}
int main()
{
init();
string s;
int x,k;
cin>>m;
while(m--)
{
cin>>s;
if(s=="H")
{
cin>>x;
insert(0,x);
}
else if(s=="D")
{
cin>>k;
if(k==0)
del(0);
else
del(k+1);
}
else
{
cin>>k>>x;
insert(k+1,x);
}
}
for(int i=a[0].next;i!=1;i=a[i].next)
{
cout<<a[i].val<<" ";
}
cout<<endl;
}
先初始化0,1節(jié)點(diǎn)，真正的節(jié)點(diǎn)從2開(kāi)始賦值私蕾，insert的時(shí)候僵缺，都需要先考慮新插入的點(diǎn)，先寫(xiě)長(zhǎng)的式子踩叭，最后遍歷輸出從0節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開(kāi)始磕潮，到1節(jié)點(diǎn)的前面那個(gè)節(jié)點(diǎn)。
#include<iostream>
using namespace std;
const int N=1e5;
struct node
{
int val,pre,next;
}a[N];
int idx;
void init()
{
a[0].next=1;
a[1].pre=0;
idx=2;
}
//表示在第k個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)
void insert(int x,int k)
{
a[idx].val=x;
a[idx].pre=k;
a[idx].next=a[k].next;
a[a[k].next].pre=idx;
a[k].next=idx;
idx++;
}
//將第k個(gè)插入的數(shù)刪除
void del(int k)
{
a[a[k].next].pre=a[k].pre;
a[a[k].pre].next=a[k].next;
}
int main()
{
init();
int m,x,k;
cin>>m;
string s;
while(m--)
{
cin>>s;
if(s=="L")
{
cin>>x;
insert(x,0);
}
else if(s=="R")
{
cin>>x;
insert(x,a[1].pre);
}
else if(s=="D")
{
cin>>k;
del(k+1);//k+1
}
else if(s=="IL")
{
cin>>k>>x;
insert(x,a[k+1].pre);
}
else
{
cin>>k>>x;
insert(x,k+1);
}
}
for(int i=a[0].next;i!=1;i=a[i].next)
{
cout<<a[i].val<<" ";
}
cout<<endl;
}
這樣單鏈表和雙鏈表都可以通過(guò)insert和del操作完成所有的基本操作容贝，不需要分析邊界自脯。
