四日总结PART1链表

常规
1

Day1-链表

链表一共分为3种：单向链表，循环链表，双向链表。

先来讲第一个，定义什么的就不多说了，就是由一个节点链着另外一个节点构成的数据结构，主要就是数字域和指针域比较难理解，可能听起来和高大上，其实就是一个节点里面有一个变量存它本身的值，另一个指针指向下一个节点的地址。定义方法如下:

struct str{
    int data;
    str *next;
}

接着就要定义头指针和尾指针，说白了头指针就是一个指向链表的第一个节点的指针，而尾指针就是链表的最后一个结点。方法也很简单。定义方法如下：

str *head,*tail;
head=new str;//new申请动态空间
head->next=NULL;//让头指针指向空，即链表长度为1
tail=head;//让尾指针也指向空

再然后就是创建新的节点，方法如下：

str *p;//当前节点
for{int i=1;i<=n;i++}
{
    p=new node;
    cin>>p->data;//输入当前节点的数字域
    p->next=NULL;//让p的下一个指向空，即p为此时的最后一个节点
    tail->next=p;//让尾指针指向p
    tail=p;//让尾指针等于p(即p成为链表的尾节点)
}

最后的遍历啦，查找啦，删除啦，插入啦之类的，我就不贴代码了，也比较简单。

第二个，循环链表，这个更简单，就在定义头，尾指针的时候，把 tail=head 改为 tail->next=head就可以了.

第三个，双向链表，这个就是单向链表的升级版，各方面速度都比单向链表要快，但要注意的是，双向链表是在用空间换时间，在内存要求高的时候要慎用(MLE真的烦人)。

定义方法如下:

struct str{
    int data;
    str *next,*pre;
}

其他的和单向链表差不多，无非就是多了几行代码。

最后，链表的指针写法主要在初赛的选择题中，而代码实现多用数组模拟的方式(我其实觉得指针方法挺好的)，下面我就用数组的方法模拟一下双向链表。

首先，定义方面，就是两个数组，一个存结点的左节点下表，一个存结点的右结点下标。

int r[N],l[N],idx,data[N];//分别表示右结点，左结点，data数组下标,数字域
int main(){
r[0]=1;
l[1]=0;
idx=2;
return 0；
}

插入操作也简单写一下吧：

data[idx]=x;//数字域
r[idx]=r[k];//右指针指向右结点
l[idx]=k;//左指针指向左结点
l[r[k]]=idx;//左结点的右指针指向该节点
r[k]=idx;//右结点的左指针指向该节点

那么这就是链表的全部内容了,给个赞再走吧

                                                                   ——2023.7.13记
7 个赞