更加灵活的数据结构——链表

更加灵活的数据结构——链表

/ 0评 / 1905次 / 7

链表链表,顾名思义,指的是由链子组成的数据表。

与我们常见的数组,栈,队列等顺序数据结构不同,链表的存储是不连续的。这时候可能有聪明的小朋友就要问了:“不连续存放数据怎么对数据操作啊?”别忘了,我们有链子啊。打个比方,你带你家狗出去溜弯,你也没抱着狗出门不是么?相反,你用一根狗链子牵着,就算你蒙着眼睛你也能知道你家又在哪儿。这时候假设你有超多条狗,你要带他们一起出门,但是你只愿意牵着一根狗链子,你就可以把狗与狗之间通过链子连在一起,这样你只需要牵着离你最近的一条狗也就可以得到你所有狗的位置。

(什么?你养的是猫?)

(滚。)

通常情况下,链表有多种形式,最为常见也是最为便捷的便是一种双向非循环式的链表,他大约长这样。

每一个节点长这样,并用一个结构体去存放

struct node
{
    node *prev;
    int value;
    node *nxt;
};

其中prev表示其前驱节点的地址,nxt表示后驱节点的地址,value则表示当前节点的值。

将多个这样的节点连接起来,就得到了链表

这里我们以一条题目去更好的理解链表的使用

而对于链表的增添操作就更加简单,我们只需要断开原先的连接,添加上新的连接即可。

断开连接
申请空间
重新连接

我们这里就用一个简单的题目,去方便大家理解链表操作的便捷性与增减数据时的高效性。

洛谷P1160 队列安排

题目描述

一个学校里老师要将班上\(N\)个同学排成一列,同学被编号为\(1∼N\),他采取如下的方法:

先将\(1\)号同学安排进队列,这时队列中只有他一个人;

\(2−N\)号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为\(1~(i−1)\)中某位同学(即之前已经入列的同学)的左边或右边;

从队列中去掉\(M (M<N)\)个同学,其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。

输入格式

第\(1\)行为一个正整数\(N\),表示了有\(N\)个同学。

第\(2−N\)行,第ii行包含两个整数\(k,p\),其中\(k\)为小于\(i\)的正整数,\(p\)为\(0\)或者\(1\)。若\(p\)为\(0\),则表示将\(i\)号同学插入到\(k\)号同学的左边,\(p\)为\(1\)则表示插入到右边。

第\(N+1\)行为一个正整数\(M\),表示去掉的同学数目。

接下来\(M\)行,每行一个正整数\(x\),表示将\(x\)号同学从队列中移去,如果\(x\)号同学已经不在队列中则忽略这一条指令。

输出格式

\(1\)行,包含最多\(N\)个空格隔开的正整数,表示了队列从左到右所有同学的编号,行末换行且无空格。

本题中的队列增添删去次数超过\(1×10^5\)次,使用一般的数组去进行操作根本不可能,而这正是链表所擅长的地方,对于节点的增添与删除只涉及到本身已经前驱后驱(如果存在)节点中的指针值,所需的时间几乎可以忽略不计。

再加上本题当中数据值不重复,我们就可以利用一个“桶”去建立所有节点的地址索引并实时更新,这就使得我们的操作效率得到大大提高,在1s内完成 \(1×10^5\)次 操作成为可能。

先上代码,大家可以通过注释去理解linkedlist_add()与linkedlist_erase()这两个最常用的函数

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-03-31 15:42:01
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
struct node
{
    node *prev;
    int value;
    node *nxt;
};
node *ptr[100005];                                 //存放节点地址,便于检索
node *curhead;                                     //为了便于输出所以用一个不断更新的头结点
void linkedlist_add(int value, node *pos, int opr) //需要插入的值以及(前/后驱)位置
{
    node *addon = (node *)malloc(sizeof(node)); //申请空间存放节点
    (*addon).value = value;
    ptr[value] = addon;
    (*addon).prev = NULL;
    (*addon).nxt = NULL;
    if (opr == 1) //向右
    {
        (*addon).prev = pos;
        if ((*pos).nxt != NULL) //非tail节点添加
        {
            (*addon).nxt = (*pos).nxt;
            (*(*addon).nxt).prev = addon;
        }
        (*pos).nxt = addon;
    }
    else
    {
        (*addon).nxt = pos;
        if ((*pos).prev != NULL) //非tail节点添加
        {
            (*addon).prev = (*pos).prev;
            (*(*addon).prev).nxt = addon;
        }
        else //tail节点需要更新curhead值
        {
            curhead = addon;
        }
        (*pos).prev = addon;
    }
}
void linkedlist_erase(node *pos) //删除pos处的的节点
{
    if ((*pos).nxt == NULL) //删除tail节点
    {
        (*(*pos).prev).nxt = NULL;
    }
    else if ((*pos).prev == NULL) //删除head节点
    {
        (*(*pos).nxt).prev = NULL;
        curhead = (*pos).nxt; //更新curhead值
    }
    else //非首尾节点
    {
        (*(*pos).prev).nxt = (*pos).nxt; //重建连接
        (*(*pos).nxt).prev = (*pos).prev;
    }
    ptr[(*pos).value] = NULL; //重置索引
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    node head;
    head.value = 1;
    head.nxt = NULL;
    head.prev = NULL;
    ptr[head.value] = &head;
    curhead = &head;
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int k, p;
        cin >> k >> p;
        linkedlist_add(i, ptr[k], p);
    }
    int t;
    cin >> t;
    while (t--)
    {
        int tmp;
        cin >> tmp;
        if (ptr[tmp] != NULL) //存在此节点
        {
            linkedlist_erase(ptr[tmp]); //删除
        }
    }
    //最后按照从头节点向尾结点递归输出值即可
    while (1)
    {
        cout << (*curhead).value << " ";
        if ((*curhead).nxt != NULL)
        {
            curhead = (*curhead).nxt;
        }
        else
        {
            break;//到头了
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.59616