数组仿真链表的优化

数组仿真链表的优化
在最初数组仿真链表的优化中，每次加入一个新值都要在数组当中寻找一个空位来储存数据，这样会有一个问题，就是当链表中加入n个元素时，每一次都会用线性的时间复杂度去寻找空位，造成了很大时间上的浪费，因此需要进行优化。
用一个堆栈记录所有没有被加入到链表中的数组元素下标，栈的元素可以初始化为1...MAXN-1,以方便使用。每次对链表进行删除操作时，再将删除的数组元素所对应的数组下标入栈，下次再添加新元素进链表时，只需去处栈顶的数组下标即可，因为这个下标对应的数组显然是空的。

这个优化方法将O(n)寻找空位的过程直接变成了O(1)。

#include<iostream>
#define MAXN 100001
using namespace std;

int linklst_data[MAXN];
int linklst_point[MAXN];
int stack[MAXN];                                //用于记录没有加入链表的数组下标的栈
int head=-1;                                    //链表的头指针
int stack_head=0;                               //栈顶指针

void del_by_data(int del_data)                  //删除一个含有del_data的元素
{
    int p=head,pre=-1;                          //从头开始遍历链表
    while(p!=-1)
    {
        if(linklst_data[p]==del_data)           //找到要删除的值，进行删除操作
        {
            if(p==head)                         //如果删除的是头指针，则更新头指针
                head=linklst_point[head];
            else                                //这个else等同于if(pre!=1),因为当P!=head时p前面已经有元素了
                linklst_point[pre]=linklst_point[p];
            linklst_data[p]=-1;                 //删除p指向元素的值
            linklst_point[p]=-1;
            stack[--stack_head]=p;              //将删除元素的下标入栈
            return ;
        }
        pre=p;
        p=linklst_point[p];
    }
    return ;
}

void add_front(int add_data)                   //在链表前段加入元素
{
    int p=1;
    p=stack[stack_head++];                     //直接取出栈中的空位
    linklst_data[p]=add_data;                  //将要加入的结点选好的空位赋值
    linklst_point[p]=head;                     //将当前加入的指针指向head
    head=p;                                    //使当前的元素成为链表头指针
}


void add_rear(int add_data)
{
    int p=1,pre;
    p=stack[stack_head++];                     //直接取出栈中的空位
    linklst_data[p]=add_data;                  //对要加入的节点的空位进行赋值
    if(head!=-1)                               //链表不为-1
    {
        pre=head;                              //找到链表中最后一个元素
        while(linklst_point[pre]!=1)
            pre=linklst_point[pre];
        linklst_point[pre]=p;                  //当当前链表的最后一个指针指向要加入的元素
    }
    else                                       //否则直接对head所指的元素赋值
        head=p;
}

void output()
{
    int p=head;
    while(p!=-1)
    {
        cout<<linklst_data[p]<<" ";
        p=linklst_point[p];
    }
    cout<<"\n";
    return ;
}

void init()                                    //初始化数组指针
{
    for(int i=0; i<MAXN; i++)
    {
        linklst_point[i]=-1;
        linklst_data[i]=-1;
        stack[i]=i+1;                         //从1到MAXN给栈加入数组下标
    }
    return ;
}

int main()                                    //演示链表的操作
{
    int ins,data;
    init();
    while(1)
    {
        cout<<"1.Insert a value in front  \n";
        cout<<"2.Insert a value in rear \n";
        cout<<"3.Delete a value \n";
        cout<<"4.Quit \n";
        cin>>ins;
        switch(ins)
        {
        case 1:
            cout<<"Please insert a value:";
            cin>>data;
            add_front(data);
            break;
        case 2:
            cout<<"Please insert a value:";
            cin>>data;
            add_rear(data);
            break;
        case 3:
            cout<<"Please insert a value:";
            cin>>data;
            del_by_data(data);
            return 0;
        }
        output();
    }
    return 0;
}