静态链表

静态单链表

算法思想：

• 数组模拟单链表称为静态链表
• 存储图 存储树
• 优点：快（静态链表）因为如果指针实现时要用new()动态开辟，非常慢（注重时间最短）
• 写工程的时候用动态链表就好了（更注重内存管理）
• 单链表往往需要存下头节点的值即e[head]

代码实现：

const int N=100010;
//head表示头节点的下标 即head->o->o->o  head表示第一个o的下标，head不是一个节点
//e[i]节点i的值
//ne[i]节点i的next指针
//idx存储当前待安排的点的下标
int head,e[N],ne[N],idx;
//初始化
void init()
{
    head = -1;
    idx = 0;
}
//将x插到头节点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx, idx ++;
}
//将x插到下标是k的点的后面
void add_to_k(int k,int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++;
}
//将下标是k的后面的点删除
void remove(int k)
{
    ne[k] = ne[ne[k]];
}
init();
for(int i=head;i!=-1;i=ne[i])
{
	cout<<e[i]<<' ';
}

静态双链表

算法思想：

• 双链表往往不需要寸两端节点的值是多少，所以初始化就有两个节点（首尾）只要用0和1标记就好了，始终不用存值

const int N=100010;
int e[N],l[N],r[N],idx;
void init()
{
    //0表示左端点 1表示右端点
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
//在k号节点右边插入x    如果想实现在k号的左边插入就调用add_k(l[k],x)
void add(int k,int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}
//删除k号节点
void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}
int main()
{
    init();
    int m;
    cin>>m;
    while(m--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op == "L")   
        {
            cin>>x;
            add(0,x);
        }
        else if(op == "R")
        {
            cin>>x;
            add(l[1],x);
        }
        else if(op == "D")
        {
            cin>>k;
            remove(k+1);
        }
        else if(op == "IL")
        {
            cin>>k>>x;
            add(l[k+1],x);
        }
        else 
        {
            cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0]; i!=1;i = r[i])   cout<<e[i]<<' ';
    cout<<endl;
    return 0;
}