算法基础——用数组模拟实现单链表和双向链表

x33g5p2x  于2021-10-01 转载在 其他  
字(3.0k)|赞(0)|评价(0)|浏览(351)

铺垫

在学这个之前,小伙伴们最好先要了解下如何用结构体形成单链表,因为如果理解了那个,这儿就很好理解了,不懂得小伙伴可以去看看博主之前的文章。带你重温单链表
很多小伙伴可能会好奇?结构体形成单链表玩的好好的,为什么要用数组来玩了?其实这就要涉及到效率的问题了,如果用之前的方法,在C++中我们每创建一个节点,就要new一下,如果单链表很长,那么会很消耗时间,有时在面试题中甚至都过不了,因为new消耗的时间太多了。

基本思想

用数组实现单链表的基本思想就是用两个数组:一个存放值,一个存放下一个节点的下标(在结构体的写法中,就相当于存放下一个节点的地址)。在这个过程中我们要用到一个变量idx来记录当前可用节点的下标。这个算法说起来很抽象,不容器理解,下面我们来看代码以及结合之前结构体形成链表的方法来理解,就很容器理解了。

初始化

void init()
{
    head=-1;
    idx=0;
}

一开始链表中为空,-1为下标的位置就是空节点,idx为0,说明当前为0个可用节点。

向头节点插入

这种方法其实在结构体形成链表中也就是头插法。

void  add_to_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

1.首先给这个位置赋值为x,一开始我们就说了,idx为当前可用位置的下标。所以代码为e[idx]=x。
2.当前位置的next(ne[]数组代替)指向头,然后让这个位置变为头节点。所以相应代码为:
ne[idx]=head;
head=idx;
3.这样就完成了头插操作,此时当前位置已经用过了,所以idx++。

下面的几个函数接口也是采用同样的类比方法来理解,这儿就不在赘述。

在任意节点之后插入一个x

void add_to_after(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

删除任意位置之后的一个节点

void move_after(int k)
{
    ne[k]=ne[ne[k]];
}

单链表题目

这儿要注意的一个点是:
要理解第k个插入的数的含义,我们来举例看看(以结构体形成单链表中而言),第一个数插入之后,其下标为0,第二个插入之后其下标为1,那么第k个插入的数其下标则为k-1。

代码实现

#include<iostream>
using namespace std;

const int N=100010;

int e[N],ne[N],idx,head;

void init()
{
    head=-1;
    idx=0;
}
void  add_to_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

void add_to_after(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

void move_after(int k)
{
    ne[k]=ne[ne[k]];
}

int main()
{
    int m;
    cin>>m;
    init();

    while(m--)
    {
        char op;
        int x;
        int k;
        cin>>op;
        if(op=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op=='I')
        {
            cin>>k>>x;
            add_to_after(k-1,x);
        }
        else
        {
            cin>>k;
            if(!k) head=ne[head];
            else move_after(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
    {
        cout<<e[i]<<" ";
    }
    cout<<endl;
    return 0;
}

注意:
1.至于这儿为什么要传k-1,上面已经说过了。
2.在D的这种情况中,要处理一下特殊情况,如果k=0,也就是删除头节点之后的节点的情况。
3.

在这儿也是要类比结构体实现单链表中一样理解,我们要打印单链表中的值,就要遍历他,通过ne这个数组来遍历,因为其中相当于存放了他们之间的连接关系,首先从head开始,然后ne[i]从头往后遍历,之后最后遇到-1(空节点)停止。

双向链表题目

双链表的思路也是,同样需要类比之前用指针实现的双向循环链表的思路,这是博主之前的关于双向链表的文章:双向循环链表
注意:这儿的双向链表并不是双向循环链表

代码实现

#include<iostream>

using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx;

//初始化 0表示左端点,1表示右端点
void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}

//在节点k的右边插入一个节点
void add_k_right(int k,int x)
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;   //这两个顺序不能反,因为你要引用r[k]
    r[k]=idx++;
}

//删除k节点
void movek(int k)
{
     l[r[k]]=l[k];
     r[l[k]]=r[k];
}

int main()
{
    int m;
    cin>>m;
    init();
   while(m--)
   {
       string op;
       cin>>op;
       int x;
       int k;
       if(op=="L")
       {
           cin>>x;
           add_k_right(0,x);
       }
       else if(op=="R")
       {
           cin>>x;
           add_k_right(l[1],x);
       }
       else if(op=="D")
       {
           cin>>k;
           //注意这儿idx是从2开始的,即第一个插入的元素idx为2,因为0,1被左右端点占据了
           movek(k+1);
       }
       else if(op=="IL")
       {
           cin>>k;    //注意这儿的顺序,k写在前面,因为在函数传参时,先传的是有关k+1的这个,所以k的cin要写在前面
           cin>>x;
           add_k_right(l[k+1],x);
       }
       else
       {
           cin>>k>>x;  //注意这儿的顺序,k写在前面,因为在函数传参时,先传的是有关k+1的这个,所以k的cin要写在前面
           add_k_right(k+1,x);
       }

   }
   for(int i=r[0];i!=1;i=r[i])
   {
       cout<<e[i]<<' ';
   }
   cout<<endl;
   return 0;
}

注意:
1.这儿只需要两个接口就可以实现5个功能,我们实现的是在k节点右边插入一个节点,如果要在它的左边插入一个节点,可以将问题转化为在k的左节点的右边插入一个节点。
2.在双向链表中0表示左端点,1表示右端点,仅起标识作用,不存放值。
3.正因为有0,1左端点和右端点的存在,所以idx是从2开始的,即第一个插入的元素的idx为2,所以在传第k个插入元素的时候要传k+1进去。
4.cin>>k>>x这儿要注意顺序,不能先写x再写k,因为你函数传参时是先传的有关k的参,所以要先把k写在前面。
5. l[r[k]]=idx; r[k]=idx++; 这两句代码写的时候要注意顺序,不然可能会对之后的代码造成影响。

相关文章