肯尼斯·里科《C和指针》第12章 使用结构和指针(2)双链表

12.3 双链表

单链表的替代方案就是双链表。在一个双链表中,每个节点都包含两个指针——指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表,甚至可以随意在双链表中访问。下面的图展示了一个双链表。

下面是节点类型的声明:

typedf struct  NODE   {
        struct  NODE   *fwd;
        struct  NODE   *bwd;
        int              value;
} Node;

现在,存在两个根指针:一个指向链表的第一个节点,另一个指向最后一个节点。这两个指针允许从链表的任何一端开始遍历链表。

我们可能想把两个根指针分开声明为两个变量。但这样一来,我们必须把两个指针都传递给插入函数。为根指针声明一个完整的节点更为方便,只是它的值字段绝不会被使用。在我们的例子中,这个技巧只是浪费了一个整型值的内存空间。对于值字段非常大的链表,分开声明两个指针可能更好一些。另外,也可以在根节点的值字段中保存其他一些关于链表的信息,例如链表当前包含的节点数量。

根节点的fwd字段指向链表的第1个节点,根节点的bwd字段指向链表的最后1个节点。如果链表为空,这两个字段都为NULL。链表第1个节点的bwd字段和最后1个节点的rwd字段都为NULL。在一个有序的链表中,各个节点将根据value字段的值以升序排列。

12.3.1 在双链表中插入

这一次,我们要编写一个函数,把一个值插入到一个有序的双链表中。dll_insert函数接受2个参数:一个指向根节点的指针和一个整型值。

我们先前所编写的单链表插入函数把重复的值也添加到链表中。在有些应用程序中,不插入重复的值可能更为合适。dll_insert函数只有当待插入的值原先不存在于链表中时才将其插入。

让我们用一种更为规范的方法来编写这个函数。当把一个节点插入到一个链表时,可能出现4种情况:

1.新值可能必须插入到链表的中间位置;

2.新值可能必须插入到链表的起始位置;

3.新值可能必须插入到链表的结束位置;

4.新值可能必须既插入到链表的起始位置,又插入到链表的结束位置(即原链表为空)。

在每种情况下,有4个指针必须进行修改。

在情况1和情况2中,新节点的fwd字段必须设置为指向链表的下一个节点,链表下一个节点的bwd字段必须设置为指向这个新节点。在情况3和情况4中,新节点的fwd字段必须设置为NULL,根节点的bwd字段必须设置为指向新节点。

在情况1和情况3中,新节点的bwd字段必须设置为指向链表的前一个节点,而链表前一个节点的fwd字段必须设置为指向新节点。在情况2和情况4中,新节点的bwd字段必须设置为NULL,根节点的fwd字段必须设置为指向新节点。

/*
** 把一个值插入到一个双链表,rootp是一个指向根节点的指针,
** value是待插入的新值。
** 返回值:如果欲插值原先已存在于链表中,函数返回0;
** 如果内存不足导致无法插入,函数返回-1;如果插入成功,函数返回1。
*/
#include <stdlib.h>
#include <stdio.h>
#include "doubly_linked_list_node.h"
int
dll_insert( Node *rootp, int value )
{
     Node  *this;
     Node  *next;
     Node  *newnode;
     /*
     ** 查看value是否已经存在于链表中,如果是就返回。
     ** 否则,为新值创建一个新节点("newnode"将指向它)。
     ** "this"将指向应该在新节点之前的那个节点,
     ** "next"将指向应该在新节点之后的那个节点。
     */
     for( this = rootp; (next = this->fwd) != NULL; this = next ){
           if( next->value == value )
            return 0;
       if( next->value > value )
             break;
}
newnode = (Node *)malloc( sizeof( Node ) );
if( newnode == NULL )
    return -1;
newnode->value = value;
/*
** 把新值添加到链表中。
*/
if( next != NULL ){
/*
** 情况1或2: 并非位于链表尾部。
*/
           if( this != rootp ){      /* 情况1: 并非位于链表起始位置。 */
                 newnode->fwd = next;
                 this->fwd = newnode;
                 newnode->bwd = this;
                 next->bwd = newnode;
           }
           else {                          /* 情况2: 位于链表起始位置。 */
                 newnode->fwd = next;
                 rootp->fwd = newnode;
                 newnode->bwd = NULL;
                 next->bwd = newnode;
           }
    }
    else {
    /*
    ** 情况3或4: 位于链表的尾部。
    */
           if( this != rootp ){    /* 情况3: 并非位于链表的起始位置。 */
                 newnode->fwd = NULL;
                 this->fwd = newnode;
                 newnode->bwd = this;
                 rootp->bwd = newnode;
           }
           else {                         /* 情况4: 位于链表的起始位置。 */
                 newnode->fwd = NULL;
                 rootp->fwd = newnode;
                 newnode->bwd = NULL;
                 rootp->bwd = newnode;
           }
    }
    return 1;
}

一开始,函数使this指向根节点。next指针始终指向this之后的那个节点。它的思路是这两个指针同步前进,直到新节点应该插入到这两者之间。for循环检查next所指节点的值,判断是否到达需要插入的位置。

如果在链表中找到新值,函数就简单地返回;否则,当到达链表尾部或找到适当的插入位置时循环终止。在任何一种情况下,新节点都应该插入到this所指的节点后面。注意,在决定新值是否应该实际插入到链表之前,并不为它分配内存。如果事先分配内存,但发现新值原先已经存在于链表中,就有可能发生内存泄漏。

4种情况是分开实现的。让我们通过把12插入到链表中来观察情况1。下面这张图显示了for循环终止之后几个变量的状态。

然后,函数为新节点分配内存,下面几条语句执行之后,

newnode->fwd = next;
this->fwd = newnode;

链表的样子如下所示。

然后,执行下列语句:

newnode->bwd = this;
next->bwd = newnode;

这就完成了把新值插入到链表的过程。

批注:书中给的图错了吧,,,如果执行newnode->bwd = this和next->bwd=newnode,应该不是上面的这张图吧。。。

简化插入函数

细心的程序员会注意到,在函数中各个嵌套的if语句群存在大量的相似之处,而优秀的程序员会对程序中出现这么多的重复代码感到厌烦。所以,我们现在将使用两个技巧消除这些重复的代码。第一个技巧是语句提炼(statement factoring),如下面的例子所示:

if( x == 3) {
          i = 1;
          something;
          j = 2;
}
else {
          i = 1;
          something different;
          j = 2;
}

注意,不管表达式x==3的值是真还是假,语句i=1和j=2都将执行。在if之前执行i=1不会影响x==3的测试结果,所以这两条语句都可以被提炼出来,这样就产生了更为简单但同样完整的语句:

i = 1;
if( x == 3 )
          something;
else
          something different;
j = 2;

把上面程序最内层嵌套的if语句进行提炼,就产生了下面程序的代码段。请将这段代码和前面的函数进行比较,确认它们是等价的。

/*
** 把新节点添加到链表中。
*/
if( next != NULL ){
    /*
    ** 情况1或情况2: 并非位于链表的尾部。
    */
          newnode->fwd = next;
          if( this != rootp ){     /* 情况1: 并非位于链表起始位置。 */
               this->fwd = newnode;
               newnode->bwd = this;
          }
          else {                         /* 情况2: 位于链表起始位置。 */
               rootp->fwd = newnode;
               newnode->bwd = NULL;
          }
          next->bwd = newnode;
}
else {
      /*
      ** 情况3或情况4: 位于链表尾部。
      */
          newnode->fwd = NULL;
          if( this != rootp ){  /* 情况3: 并不位于链表起始位置。 */
               this->fwd = newnode;
               newnode->bwd = this;
          }
          else {                       /* 情况4: 位于链表起始位置。 */
               rootp->fwd = newnode;
               newnode->bwd = NULL;
          }
          rootp->bwd = newnode;
          }

第二个简化技巧很容易用下面这个例子进行说明:

if( pointer !=NULL )
         field = pointer;
else
         fileld = NULL;

这段代码的意图是设置一个和pointer相等的变量,如果pointer未指向任何内容,这个变量就设置为NULL。但是,请看下面这条语句:

field = pointer;

如果pointer的值不是NULL,field就像前面一样获得它的值的一份副本。但是,如果pointer的值是NULL,那么field将从pointer获得一份NULL的副本,这和把它赋值为常量NULL的效果是一样的。这条语句所执行的任务和前面那条if语句相同,但它明显简单多了。

在上面程序中运用这个技巧的关键是找出那些虽然看上去不一样但实际上执行相同任务的语句,然后对它们进行改写,写成同一种形式。我们可以把情况3和情况4的第一条语句改写为:

newnode->fwd = next;

由于if语句刚刚判断出next==NULL,这个改动使if语句两边的第一条语句相等,因此可以把它提炼出来。请做好这个修改,然后对剩余的代码进行研究。

我们还可以对代码作进一步的完善。第一条if语句的else子句的第一条语句可以改写为:

this->fwd = newnode;

这是因为if语句已经判断出this==rootp。现在,这条改写后的语句以及它的同类也可以被提炼出来。

下面的程序是实现了所有修改的完整版本。它所执行的任务和最初的函数相同,但体积要小得多。局部指针被声明为寄存器变量,进一步改善了代码的体积和执行速度。

/*
** 把一个新值插入到一个双链表中。rootp是一个指向根节点的指针,
** value是需要插入的新值
    ** 返回值:如果链表原先已经存在这个值,函数返回0。
    ** 如果为新值分配内存失败,函数返回-1。
    ** 如果新值成功地插入到链表中,函数返回1。
    */
    #include <stdlib.h>
    #include <stdio.h>
    #include "doubly_liked_list_node.h"
    int
    dll_insert( register Node *rootp, int value )
    {
         register Node  *this;
         register Node  *next;
         register Node  *newnode;
         /*
         ** 查看value是否已经存在于链表中,如果是就返回。
         ** 否则,为新值创建一个新节点("newnode"将指向它)。
         ** "this"将指向应该在新节点之前的那个节点,
         ** "next"将指向应该在新节点之后的那个节点。
         */
         for( this = rootp; (next = this->fwd) != NULL; this = next ){
               if( next->value == value )
                    return 0;
                if( next->value > value )
                    break;
         }
         newnode = (Node *)malloc( sizeof( Node ) );
         if( newnode == NULL )
                return -1;
         newnode->value = value;
         /*
         ** 把新节点添加到链表中。
         */
         newnode->fwd = next;
         this->fwd = newnode;
         if( this != rootp )
              newnode->bwd = this;
         else
              newnode->bwd = NULL;
         if( next != NULL )
              next->bwd = newnode;
         else
              rootp->bwd = newnode;
         return 1;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/377222.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

为什么大模型需要向量数据库?

AIGC 时代万物都可以向量化&#xff0c;向量化是 LLM 大模型以及 Agent 应用的基础。 比如&#xff1a;爆火的 Google 大模型 Gemini 1.0 原生支持的多模态&#xff0c;在预训练的时候就是把文本、图片、音频、视频等多模态先进行 token 化&#xff0c;然后构建一维的“语言”…

Powershell Install 一键部署Openssl+certificate证书创建

前言 Openssl 是一个方便的实用程序,用于创建自签名证书。您可以在所有操作系统(如 Windows、MAC 和 Linux 版本)上使用 OpenSSL。 Windows openssl 下载 前提条件 开启wmi,配置网卡,参考 自签名证书 创建我们自己的根 CA 证书和 CA 私钥(我们自己充当 CA)创建服务器…

数据结构第九天(堆排序)

目录 前言 概述 源码&#xff1a; 主函数&#xff1a; 运行结果&#xff1a; 其他 前言 哈哈&#xff0c;这个堆排序算法很久之前就已经敲过一遍了&#xff0c;时间一久&#xff0c;思路有点淡忘。今天重新看过一遍之后&#xff0c;又亲自撸代码&#xff0c;幸运的是&am…

【RL】Bellman Equation (贝尔曼等式)

Lecture2: Bellman Equation State value 考虑grid-world的单步过程&#xff1a; S t → A t R t 1 , S t 1 S_t \xrightarrow[]{A_t} R_{t 1}, S_{t 1} St​At​ ​Rt1​,St1​ t t t, t 1 t 1 t1&#xff1a;时间戳 S t S_t St​&#xff1a;时间 t t t时所处的sta…

C++ | vector二维数组的初始化与行、列数的获取

如果直接使用vector<int,vector<int> > v;创建二维数组&#xff0c;那么就会得到一个空的容器&#xff0c;这样再通过push_back赋值是非常麻烦的。 初始化二维数组 在此介绍二维数组初始化的一般操作。 首先看一维数组的初始化示例&#xff1a; 定义一个长度为n&a…

拿捏循环链表

目录&#xff1a; 一&#xff1a;单链表&#xff08;不带头单向不循环&#xff09;与循环链表&#xff08;带头双向循环&#xff09;区别 二&#xff1a;循环链表初始化 三&#xff1a;循环链表头插 四&#xff1a;循环链表尾插 五&#xff1a;循环链表头删 六&#xff1…

MessageBox好用吗?

MessageBox作为一种能够对接多系统平台的工具&#xff0c;在数字营销领域具有很大的实用性和价值。它提供了实时的数据同步、个性化的营销策略、用户互动功能等多种功能&#xff0c;可以帮助企业实现更精准、高效的营销活动。具体来说&#xff0c;MessageBox的优点包括&#xf…

Laykefu客服系统后台登录绕过

【产品介绍】 Laykefu 是一款基于workermangatawayworkerthinkphp5搭建的全功能webim客服系统&#xff0c;旨在帮助企业有效管理和提供优质的客户服务 【漏洞介绍】 请求头中Cookie中的”user_name“不为空时即可绕过登录系统后台&#xff0c;恶意攻击者可利用此漏洞获得后台…

基于摄像头的虹膜识别技术

随着苹果公司的指纹识别TouchID的推广流行&#xff0c;三星等公司的积极跟进&#xff0c;生物识别技术正被移动设备厂商所重视。 虹膜是什么&#xff1f; 人的眼睛由巩膜、虹膜、瞳孔三部分构成。巩膜即眼球外围的白色部分&#xff0c;约占总面积的30%&#xff1b;眼睛中心为瞳…

【React】如何使antd禁用状态的表单输入组件响应点击事件?

最近遇到一个需求&#xff0c;需要在<Input.textarea>组件中&#xff0c;设置属性disabled为true&#xff0c;使textarea响应点击事件&#xff0c;但直接绑定onClick并不会在禁用状态下被响应。 解决方法1 之后尝试了很多方法&#xff0c;比如设置csspointer-events:no…

日本失去的三十年:去杠杆用了14年

去年以来&#xff0c;日股在日本央行转鹰预期、基本面改善和一系列监管新规的催化下高歌猛进&#xff0c;日经指数已经逼近90年代资产泡沫时期的高位。今年迄今累计上涨8.51%&#xff0c;领跑全球&#xff0c;“失落的三十年”似乎已经远去。 日本因何走向衰退&#xff1f;“失…

MPLS VPN功能组件(2)

MP-BGP 采用地址族(Address Family)来区分不同的网络层协议,以便正确处理VPN-IPv4路由 传统的BGP-4(RFC1771)只能管理IPv4的路由信息,无法正确处理地址空间重叠的VPN的路由。 为了正确处理VPN路由,VPN使用RFC2858(Multiprotocol Extensions for BGP-4)中规定的MP-BG…

云计算 - 弹性计算技术全解与实践

一、引言 在过去的十年里&#xff0c;云计算从一个前沿概念发展为企业和开发者的必备工具。传统的计算模型通常局限于单一的、物理的位置和有限的资源&#xff0c;而云计算则通过分布式的资源和服务&#xff0c;为计算能力带来了前所未有的"弹性"。 弹性&#xff1a;…

TryHackMe-Vulnerability Capstone练习

本文相关的TryHackMe实验房间链接&#xff1a;TryHackMe | Vulnerability Capstone 先nmap扫一下 接下来我们访问一下 接下来我们searchsploit找一下漏洞 searchsploit Fuel CMS 执行漏洞exp&#xff08;此处使用TryHackMe中的box&#xff09; 如果使用本地机需要下载exp&am…

算法练习-删除二叉搜索树中的节点(思路+流程图+代码)

难度参考 难度&#xff1a;中等 分类&#xff1a;二叉树 难度与分类由我所参与的培训课程提供&#xff0c;但需要注意的是&#xff0c;难度与分类仅供参考。且所在课程未提供测试平台&#xff0c;故实现代码主要为自行测试的那种&#xff0c;以下内容均为个人笔记&#xff0c;旨…

制作离线版element ui文档

链接&#xff1a;https://pan.baidu.com/s/1k5bsCK9WUlZobhFBLItw1g?pwdgeyk 提取码&#xff1a;geyk --来自百度网盘超级会员V4的分享 https://github.com/ElemeFE/element 克隆官方代码 使用nvm切换node版本&#xff0c;推荐使用14.0.0 http://doc.xutongbao.top/doc/#/zh…

Prompt Engineering实战-构建“哄哄模拟器”

目录 一 背景 二 “哄哄模拟器”的Prompt Prompt 的典型构成 三 操作步骤 3.1 创建对话 3.2 游戏测试 一 背景 前几天《AI 大模型全栈工程师》第二节课讲了“Prompt Engineering&#xff0c;提示工程”&#xff0c;里面提到一些prompt相关的技巧&#xff0c;原则&#xf…

浅谈分布式CAP定律、BASE理论

第一节 分布式架构设计理论与Zookeeper环境搭建 1. 分布式架构设计理论 学习Zookeeper之前,我们需要掌握一些分布式系统基础知识&#xff1a;了解分布式系统的概念、原理。 配置管理 域名服务 分布式同步 发布订阅 1. 分布式架构介绍 1.1 什么是分布式 《分布式系统原理和…

构建异步高并发服务器:Netty与Spring Boot的完美结合

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 ChatGPT体验地址 文章目录 前言IONetty1. 引入依赖2. 服务端4. 客户端结果 总结引导类-Bootstarp和ServerBootstrap连接-NioSocketChannel事件组-EventLoopGroup和NioEventLoopGroup 送书…

COMSOL接触(高度非线性)仿真常见报错及解决方法总结

前言 由于COMSOL采用隐式求解器&#xff0c;相较于使用显式求解器的Dyna、Abaqus等软件。要在COMSOL中实现结构接触这一高度非线性问题难度较大&#xff0c;报错时有发生。究其原因&#xff0c;是当物体之间相互接触时&#xff0c;物体受到的应力、运动路径会发生突变&#xff…