[编程笔记]-Single-Linked_Lists单链表

前言

开新章啦。

概念

链表中，每一个元素都有一个指向下一个元素的指针，这样一个链接一个，就形成了一个链式结构。

动态链表

动态链表通常就是真正意义上的链表，可以动态增加、修改、减少，但事实上用处并不大，这里就只给出模板，用以借鉴。

struct node{//组成链表的结点
	int data;
	node* next;
}

静态链表

在竞赛中，静态链表才是大头。同时，在之后，我们会学到链式前向星，与链表的关系不能说微乎其微，也只能说是一模一样。

概念

拿数组去模拟链表。

实现

同时开两个数组，储存对应编号的节点的数据和下一个节点的编号（编号不是元素在链表中的位置序号！）

这样就能通过修改对应数组的方式实现链表操作。

具体功能在代码中给出

代码

class Static_linked_list{
    public:
        int head,tail,cnt;
/*
注意，头指针并不是第一个元素，而是指向第一个元素的指针，可以视作第零号元素。
尾指针同理，并不是最后一个元素，而是最后一个元素指向的元素，作为结束的标志。
*/
        int ne[N],e[N];
        void init(int n,int h=0,int t=-1){
            head=h;tail=t;
            ne[head]=tail;
        }
        void add(int k,int x){//在**编号为k**的元素**后**增加一个新元素。
            ++cnt;//这就是编号，所以和位置没有任何关系。
            e[cnt]=x;
            ne[cnt]=ne[k];
            ne[k]=cnt;
        }
        void del(int k){//删除**编号为k**的元素**后**一位元素。
            ne[k]=ne[ne[k]];
        }
        vector<int> get(){//获取当前链表
            vector<int> lis;
            for(int i=ne[head];i!=tail;i=ne[i]){
                lis.push_back(e[i]);
            }
            return lis;
        }
}sll;

例题

AcWing826-单链表

一道模板题。

完结撒花o(￣︶￣)o