双链表的存储结构

news/2024/11/22 20:17:00/

双向链表是一种复杂类型的链表，它的节点包含指向序列中前一个节点和下一个节点的指针。 因此，在双向链表中，节点由三部分组成：节点数据，指向下一个节点的指针(next指针)，指向前一个节点的指针(prev指针)。

0514732e492f491583df44d59b2dee29.png

 双链表和单链表的区别本质上就是, 双链表的每个节点都增加了一个指向上一个节点的指针 ,这样就可以方便节点之间的互通了.

注: 我这里为了方便, 称节点 prior 指针为前驱指针, next 指针为后继指针

 然后, 相关操作, 都增加了一步, 就是节点的 前驱指针需要指向上一个节点, 我们在覆盖指针的时候,注意相关顺序.

下面,开始我们的构思:

第一步: 我们想要创建一个双链表, 首先就要定义节点的类型, 

typedef int ElemType;

第二步: 定义链表节点的结构体 ,包括自定义数据, 前驱结点和后继节点

typedef struct DNode

{

        ElemType data;                        //节点数据

        struct DNode *prior;                //指向前驱节点的指针

        struct DNode *next;                //指向后继节点的指针

}DLinkList;

第三步: 我们已经把节点结构体定义了, 接下来, 就是通过构建各个结点之间的关系, 来创建一个我们所需要的单链表了 ,

基本操作,包括如下几步:

初始化链表 

为头结点分配空间, 然后头节点后继指针置空 ,这样就初始化了双链表

 L=(DLinkList *)malloc(sizeof(DLinkList));   //创建头结点L->prior=L->next=NULL;

双链表插入思路:

这样我们就构建了一个双链表 , 那如何往里面插入元素的或修改元素的 ,如何 进行相关的操作的?

我们看图示:

61961f6e22f44e778c2c60fd3b0901b7.png

图上只标了 P 节点

插入前, 我们要让新节点插入到两个节点之间的话, 就要考虑指针了, 包括先后顺序

我们尝试性的把, S 的后继指针指向 后一个节点,

那后一个节点的位置在哪里 呢? 

插入前, 后一个结点的位置指针在P->next 

所以, 我们不能轻易的去覆盖指针 P->next 

a6a3872d0a0f44fba0e70a2627330561.png

我们要用到 p->next ,所以先进行

s->next = p->next;   

因为这时双链表 , 我们让新节点指向了后一个结点 ,当然,后一个节点的前驱指针也要指向s 

29bae769e6a743d2b073d89d59d31d3c.png

 后一个节点的位置在 P->next ,其前驱指针即为 p->next ->prior ,所以 把 s 的指针送给 后一个节点的前驱节点

p->next->prior = s;

那新节点和 后一个节点就已经链接上了 , 接下来把 s 和 p 链接起来

0d5b6a70e1474002b68c1b5834007ed2.png

s -> prior = p;                //新节点的前驱指针指向 p p->next =s ;                       //前一个结点的后继指针指向 s

这两个指针不冲突, 顺序不影响

2941364e33ed44cbb09530491517a061.png

s ->next = p->next;
p->next->prior = s;
s ->prior = p;
p ->next =s;

这几步就是,双链表插入节点的步骤, 还是那几个注意的点, 我们按照常规思维去覆盖指针前,要看那个指针对我们有没有用, 我们要先处理完, 安全后, 再覆盖,.

 头插法建立双链表

思路: 我们是把一个数组里面的数据,插入到初始单链表 , 每次插入都是插入到头结点的后边 , 

f429469ce5584337b87c7f2dd2dc616f.png

 数组 ElemType a[]

0bf87448e2ca4f50839649b664e61245.png

 头结点 L

a159439c4ab944cf91f2d32a25324d21.png

插入到 双链表 , 就是如上图所示:

至于插入的操作, 参考上面我们往双链表里插入元素的四步操作

下面开始我们的实操:

构建成员方法:

传入要建立的链表 ,传入要插入的数组数据 , 传入要操作的个数

void CreateListF(DLinkList *&L, ElemType a[] , int n){ 

先构造头结点;

分配空间,

L = (DLinkList *)malloc(sizeof(DLinkList));              // 分配空间

L->prior=L->next=NULL;                                        //  头结点后继指针置空

ef5ea5630efc415b9121bf8b6303c959.png

然后, 我们要往里面插入新节点了, 新节点的数据就是数组里面的元素

那我们需要为新节点分配空间 ,定义新节点是 s

193709faf99b4bf391eee7963fc0a1d1.png

DLinkList *s;                //定义新节点指针

因为每次插入的都是新节点, 所以每次插入都需要分配空间, 我们定义一个 for 循环来进行新节点的构造操作:

for(int i=0; i < n ; i++){

                                                       //n是要构建的双链表新节点的个数

s = (DLinkList *)malloc(sizeof(DLinkList));        //为每个新节点分配空间

s->data = a[i];                        //为节点分配数据

        

//下面开始进行插入节点的操作 , 按照插入节点的操作, 考虑到只有头指针可以指引节点, 所以先把头结点的后继指针进行操作,

s ->next =L->next;        //将新节点后继指针指向 头结点的后一个节点

//接下来,是如果插入前 , 头结点的后一个节点不为空, 就需要操作后面节点的前驱指针了,

//第一个插入的节点, 当然不用管后面的结点的前驱指针

        if(L->next!NULL)

        {        

                L->next->prior = s;

        }

        //后一个节点 , 已经操作完了, 下面开始操作新节点

        L ->next = s;        //头结点指向 新节点

        s ->prior = L;         //新节点的前驱指针指向头结点

}


尾插法建立双链表

思路: 尾插法, 就是在链表的尾结点上再连接一个结点 , 和 头插法的区别就是插入的新节点就是链表的尾结点, 尾结点最后置空 就行了.

所以我们要和单链表的尾插法一样 , 用一个指针指向尾结点, 然后进行相关操作就行了

首先

传入要建立的链表 ,传入要插入的数组数据 , 传入要操作的个数

void CreateListF(DLinkList *&L, ElemType a[] , int n){ 

然后 建立头结点

L = (DLinkLIst *)malloc(sizeof(DLinkList));
r = L;

然后接下来就是循环的建立新节点,分配新节点空间, 然后插入到双链表的尾部了

为构造新节点指针和尾结点指针

DLinkList *s , *r;
for(int i; i<n; i++)
{s=(DLinkList *)malloc(sizeof(DLinkList));    //新节点分配空间s->data = a[i];                //为新节点送入输入里的数据r ->next = s;                  //把尾结点的后继指针指向 新节点 ss -> prior = r;                //因为这是双链表, 新节点前驱指针指向链表尾结点r = s;                         //新节点链接完成,尾结点指针后移向新节点
}r->next = NULL;                    //全部新节点插入完成后,链表尾指针置为空
这样尾插法的操作就完成了
b5e118140a5142de8e85920ec9f7682b.png

完整代码如下:

void CreateListR(DLinkList *&L, ElemType a[],int n)
{DLinkList *s, *r;int i;L = (DLinkLIst *)malloc(sizeof(DLinkList));r = L;for(i = 0; i<n; i++){s = (DLinkList *)malloc(sizeof(DLinkList));s -> data = a[i];r->next=s;s->prior = r;r = s;}r ->next = NULL;  //尾插法,新节点没有后继节点,后继指针置为空就可以
}

在链表特定位置插入数据元素

首先传入要构建的链表 , 操作数据元素插入到第 i 个数据元素的位置 , 传入插入的元素

bool ListInsert(DLinkList *&L , int i , ElemType e){

假如我们在第 i 个 位置插入元素 , 我们首先要找到第i-1这个位置,然后插入到她后面就行了.

注: 我们所说的 第 i 个元素是生活中的第 i 个元素, 是从1 开始,到第 i 个 ,那双链表的 头结点一般不存数据元素 , 所以我们把头结点的后继节点称为第一个数据节点

我们要先找到第 i-1个元素 ,

第一个元素是 头结点 L -＞next

寻找指针 p 先指向 L的后继节点

DLinkList *p = L-＞next;              //寻找第 i 个元素的指针 ,初始指向第一个数据元素 （顾名思义，头结点不存数据）

DLinkList *s;                  //新节点指针

然后开始寻找第 i-1个节点

Iint j=1;    //刚开始, p指向第一个元素 L

while(j<=i-1 && p!= NULL)

{

        j++;

        p=p->next;

}

如果 p 指向 NULL , 说明链表没有第 i 个元素, 链表已经到头了

if( p == NULL)

{

        return false;

}

如果上述情况,都不发生的话,就说明我们找到了第 i -1个元素 p

else

{

        s = (DLinkList *)malloc(sizeof(DLinkLIst ));        //创建新节点

        s->data = e;                                                        //为新节点赋值 

        s ->next = p->next;                                //在P后面插入新元素, 要考虑到其后面是否有

                                                           //      结点 ,有节点的话,还要安排它后面节点的前驱指针

     

    //如果p 后面有节点,那就先安排其下一个节点的前驱指针,指向新节点

        if(p->next !=NULL)

        {

                p->next->prior =s;

        }

     //然后再把新节点的前驱指针指向 第 i-1 个节点p , 第 i-1个节点的后继指针指向 新结点s

        s->prior = p;

        p ->next =s;

        return true;

}

完整代码如下:

bool ListInsert(DLinkList *&L, int i, ElemType e)
{int j=0;DLinkList *p=L->next,*s;while(j<i-1 && p!=NULL){j++;p=p ->next;}if(P==NULL){return false;}else{s =(DLinkList *)malloc(sizeof(DLinkList));s ->data = e;s->next = p->next;if(p->next != NULL){p->next->prior =s;}s->prior = p;p->next =s;return true;}
}

在双链表中,删除第 i 个节点 

构思: 删除第 i 个节点的意思就是, 把第 i -1 个元素 和 第 i+1 个元素 链接起来, 

说白了就是

让第 i-1个元素的后继指针指向 第 i +1 个元素 ,第 i +1 个元素和前驱指针指向 第 i -1 个元素

,然后 第 i 个元素就脱离了链表的联系 , 然后我们就可以释放第 i 个节点的空间了.

fd1841b270254ddbbc9ae9d93d2d08ce.png

下面开始实操:

传入链表 ,传入删除的节点位置, 设置保存删除元素的指针变量

bool ListDelete(DLinkList *&L , int i, ElemType &e){   //我们的函数操作代码都在大括号里面

我们接下来

我们要删除指定的节点 , 当然要找到 其 前一个节点 ,和后一个节点 ,

首先, 定义指针 *p  寻找 第 i-1 个节点 , 为了释放第 i 个结点 ,再定一个一个指针 *q ,来定位第 i 个节点

DLinkList *p;

DLinkList *q;

然后 ,开始遍历操作 , 头结点是第一个节点,我们要找第 i -1 个节点

int j=1;        // 从第一个节点开始

p = L ;        //p初始的时候指向 L

开始循环,找到 第 i 个节点,让 p依次向后遍历

while( j <= i-1  && p != NULL)    //当 超过链表长度p 就变成空了,没必要再遍历下去
{j++;p = p->next;
}

简单验证一下 , 在循环内 当 j 等于 2 时, p指向 L的后一个节点,就是第二个结点 

当 i 超过链表的节点个数的时候, 当然 p 就会指向空, 我们也删除不了,就返回错误

if ( p == NULL)

{

        return false;

}

当我们找到 第 i -1 个节点 *p 的时候 , 我们就进行上述我们的链接操作

else

{

        //先定位 要删除的节点 q

        q = p->next;

        //找到第 i-1 个元素只能证明 , 第 i-1个 元素不是空,我们要时刻警惕空指针异常

        if(q == NULL)

        {

                return false;

        }

        //如果通过上步的检验,我们就可以得知存在第 i 个元素 ,就把删除的数值传回

        e = q->data;

        //进行双链表链接操作

        //第 i-1 个节点指向第 i+1 个元素, 然后第 i+1个元素的前驱指针指向第 i-1个元素

        p->next = q-> next;        / /我们已经进行了存储 p->next ,所以放心覆盖

       // 然后第 i+1 个节点的前驱指针指向 第 i-1 个节点, 

        //再次警惕空指针异常, 存在第 i 个元素,就存在 第 i -1 个元素吗?

        //如果存在第 i+1个元素,我们就要把第i+1 个节点的前驱指针指向第 i-1 个元素

        if( p->next !=NULL)

         {

                p->next->prior = p;        //  p->next 此时已经指向第i+1个元素

        }

        free(q);        //释放删除的节点空间

        return true;

}

}

完整代码如下:

bool ListDelete(DLinkList *&L, int i, ElemType &e)
{int j = 0;DLinkList *p = L , *q;while(j<i-1 && p!NULL){j++;p = p->next;}if( p == NULL){return false;}else{q = p->next;if(q == NULL){return false;}e= q->data;p->next = q->next;if(p->next != NULL){p->next->prior = p;}free(q);return true;}
}

逆置双链表

问题:

        有一个带头结点的双链表L,设计一个算法将其所有元素逆置 ,即第一个元素变为最后一个元素,第二个元素变成倒数第二个元素, ......, 最后一个元素变为第一个元素 ,

构思:

很简单,就是利用头插法,把链表的元素,重新插入到头结点的第一个节点上,

d210abb7c28e4ec6877f25d4b6d7f386.png

 传入要修改的链表;

void reverse(DLinkList *&L){

然后定义一个指针节点 *p 指向要重新排列的元素

DLinkList *p;

再来一个元素存储重新排列元素的下一个元素,避免节点断开后失去联系

DLinkList *q;

第一个要重新排列的是头结点的后继节点

p = L->next;

往头节点插入前,链表先初始化, 

L ->next =   NULL;

下面开始遍历 ,插入头结点

whlie(p != NULL)
{q = p->next;p->next = L ->next;if(L->next != NULL){L->next->prior = p;}L->next = p;p->prior = L;p = q;
}

刚进入的时候, 当 p 所指向的节点不是 NULL的时候, 说明,L->next 不是空, 也就是我们所要逆置的

双链表不是空链表

d210abb7c28e4ec6877f25d4b6d7f386.png

我们要将第一个节点插入,自然要使用头插法,插入到链表头结点的后面

我们让 *p 指向要操作的节点,

p->next = L ->next;        (直接操作指针错误)

我们能这样直接操作吗?

答案是,不能, 我们直接覆盖 p->next , 会造成 要操作节点的下一个节点失去联系,那下次我们就找不到要操作的节点了,所以要找指针*q ,先来存放 p->next,再来操作指针p->next 

q = p->next;           //存放 操作节点的下一个节点 ,直到 q = NULL,就表明没有可操作的节点了

然后,我们根据头插法的 操作, 先让操作的新节点指向头指针后一个节点

p ->next = L ->next;

新节点已经指向后一个节点了,那后一个节点指向 新节点吗?

如果插入前,单链表是空, 那头指针的后继指针 L->next 是空,我们上面已经让新节点指向 空指针 ,

如果插入前 ,单链表后面还有节点, 那头指针的后继指针L->next 不是空,我们上面的操作,是让新节点指向后一个节点

这两种结果,我们都让新节点指向了头结点的后继指针 ,

但是因为这是双链表 , 所以如果插入前, 头结点后有节点 *q 的话 ,我们就需要 *q 指向新节点 *p

 if(L->next != NULL)        //如果头指针后继节点不为空
    {
        L->next->prior = p;        //那就让后继节点的前驱指针,指向新节点(头插法只在头结点                                                    //     和第一个节点之间操作)
    }
    L->next = p;                        //然后让头结点的后继指针指向新节点 p ,
    p->prior = L;                        //双链表让新节点指向头指针

   p = q;                                  // p要继续向后遍历 ,这是我们存储的下一个节点的线索节点

所以逆置双链表的完整算法如下:

void reverse(DLinkList *&L)
{DLinkList *p = L->next,*q;L->next =NULL;while(p!=NULL){q = p ->next;p->next = L->next;if(L->next !=NULL){L->next->prior = p;}L->next = p;p->prior = L;p = q;}
}


http://www.ppmy.cn/news/118065.html

相关文章

海尔电脑重装系统怎么装win10

海尔电脑重装系统怎么装win10

现在新购买的电脑基本都是预装win11的系统了&#xff0c;可能很多小伙伴会觉得win11没有win10那么好用&#xff0c;就想换回win10系统&#xff0c;那么海尔电脑重装系统怎么装回win10呢&#xff1f;电脑可以开机的情况下不需要u盘直接就可以在线重装了。 更多一键重装系统教程…
阅读更多...
海尔智家：“超预期”成为“新常态”

海尔智家：“超预期”成为“新常态”

8月29日晚&#xff0c;海尔智家发布了2022半年报。对于这份财报&#xff0c;从股民的评价和券商机构的研报中&#xff0c;不难发现海尔智家不仅超越了股民的预期&#xff0c;也超越了投资机构的预期。 观察海尔智家的人发现&#xff0c;自2020三季报以来&#xff0c;海尔智家的…
阅读更多...
gt和htd什么区别_海尔冰柜HTD跟HDB什么区别？

gt和htd什么区别_海尔冰柜HTD跟HDB什么区别？

海尔冰柜hd跟hd的区别是这样的。一般企业做法&#xff1a;出口创汇&#xff0c;走出去又退回来做订牌 海尔创新做法&#xff1a;出口创牌&#xff0c;海外建立“三位一体”本土化模式 海尔管理创新&#xff1a;实施“市场链”流程再造,走出国门&#xff0c;出口创牌 上个世纪九…
阅读更多...
【机器学习】分类问题和逻辑(Logistic)回归算法详解

【机器学习】分类问题和逻辑(Logistic)回归算法详解

在阅读本文前&#xff0c;请确保你已经掌握代价函数、假设函数等常用机器学习术语&#xff0c;最好已经学习线性回归算法&#xff0c;前情提要可参考https://blog.csdn.net/weixin_45434953/article/details/130593910 分类问题是十分广泛的一个问题&#xff0c;其代表问题是&…
阅读更多...
JS字符串处理：split和replace

JS字符串处理：split和replace

题目1.现在有一个字符串"Rome was not built in a day"&#xff0c;请用程序统计该字符串中有多少个单词。注&#xff1a;单词与单词之间是以空格隔开的。 测试代码 var str3 "Rome was not built in a day"var str3_arr str3.split(" ");docu…
阅读更多...
UE4蓝图学习篇（九）-- 人物重定向

UE4蓝图学习篇（九）-- 人物重定向

在平常的游戏制作或者项目练习过程中&#xff0c;我们想使用其他比较好看的模型&#xff0c;但是却想使用小白人的动画&#xff0c;这个时候要怎么去处理呢&#xff1f; 这个时候就需要使用到重定向功能&#xff0c;让两者使用同一套骨骼&#xff0c;把小白人动画重定向到我们…
阅读更多...
判断当前页面是否有元素被iframe嵌套

判断当前页面是否有元素被iframe嵌套

我当时的场景&#xff1a;在某一页面判断该页面有没有元素是被iframe嵌套的&#xff0c;根据是否被嵌套做页面其他 逻辑处理 我是用的方法二解决的问题&#xff1a;top.frames.length>0 &#xff0c;大于0 就是有被嵌套的&#xff0c;等于0就是没有被嵌套 方法一&#xff1…
阅读更多...
Oracle非分区表的重组

Oracle非分区表的重组

Oracle非分区表 一、概念 非分区表&#xff08;Non-partitioned table&#xff09;是指在创建表时没有使用分区&#xff08;Partitioning&#xff09;功能进行数据划分的表。分区表是将表中的数据按照某个特定的列或表达式进行划分&#xff0c;并存储在不同的分区中。而非分区…
阅读更多...
最新文章

Copyright @ 2022~2023