單鏈表(靜態陣列實作方式)
原理，思想：
正常插入插入的值按順序放入val陣列當中
ne陣列用來記錄鏈表第k個數的下一位在val陣列當中的位置，
h代表鏈表的頭，初始值要定義成-1，才能不停地在ne陣列中傳遞下去，代表鏈表終止的條件，
idx表示順序插入陣列的數字
洗掉鏈表中第k位的元素并非真實洗掉val中的數字，而是將ne[k-1]=ne[k]，這樣鏈表就會繞過這個點，到下一個點，
代碼：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int M=100000+10;
ll h=-1,val[M],ne[M],idx;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m;
cin>>m;
memset(ne,-1,sizeof ne);
while(m--)
{
char ch;
ll k,x;
cin>>ch;
if (ch=='H') //添加頭
{
cin>>x;
ne[idx]=h;
h=idx;
val[idx++]=x;
}
else if (ch=='D') //洗掉
{
cin>>k;
if (k==0) //洗掉頭
{
h=ne[h];
}
else //洗掉的非頭
ne[k-1]=ne[ne[k-1]];
}
else //插入元素到鏈表尾部
{
cin>>k>>x;
val[idx]=x;
ne[idx]=ne[k-1];
ne[k-1]=idx++;
}
}
for (ll i=h;i!=-1;i=ne[i]) //用ne來遍歷輸出鏈表
cout<<val[i]<<' ';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/224565.html
標籤：其他
上一篇：鏈表