深入探究：在双链表指定元素的后面进行插入操作的顺序

🕗 发布于 2024-10-05 23:27 数据结构

归纳编程学习的感悟，
记录奋斗路上的点滴，
希望能帮到一样刻苦的你！
如有不足欢迎指正！
共同学习交流！
🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言📝
惟有主动付出，才有丰富的果实获得收获！

前言：

昨天，我们探究了在双链表指定元素的前面进行插入操作的顺序，并总结了方便记忆的规律今天我们继续探究在后面插入的顺序规律，并且将今天的规律与昨天的作对比，综合起来，找到相同之处与不同所在，这会让我们对双链表底层原理理解的更加深入，在考试当中可以快速给出正确优美的答案。

注意：本章节讲的是在p指向待插入元素的前面，所以后面讲的结论只适用于往p指向的结点后面插入一个元素，关于p指向待插入元素的后面的规律，请参考上一篇博文！！！

一、代码部分与昨天一样，只改变了宏的定义

#include<stdio.h>
#include<stdlib.h>

// 定义数据类型为整型
#define DataType int
// 定义一个简单的调试宏，用于输出整数
#define debug(a) printf("%d ",a)

// 下面四个宏定义了插入节点时需要执行的操作
#define one s->prior=p       // 设置新节点s的前驱指针指向p
#define two p->next=s        // 将p的后继指针指向新节点s
#define three s->next=p->next // 设置新节点s的后继指针指向p的下一个节点
#define four p->next->prior=s // 如果p后面有节点，则更新该节点的前驱指针为s

// 双向链表结点结构体定义
typedef struct DLNode
{
    DLNode *prior;  // 指向前驱结点
    DLNode *next;   // 指向后继结点
    DataType data;  // 结点存储的数据
}DLNode, *DLinkList;

// 初始化双向链表
void InitDLinkList(DLinkList *head);
// 创建双向链表
void CreatDLinkList(DLinkList head, int a[]);
// 在指定位置i处插入元素e
int InsertElem(DLinkList head, int i, DataType e);
// 顺序打印双向链表中的所有元素
void printElem(DLinkList head);
//逆序打印双向链表中的所有元素
void rprintElem(DLinkList head);

int main()
{
    // 初始化数组
    int a[10] = {10,20,30,50,60,70,80,90};
    DLinkList L;
    // 初始化链表
    InitDLinkList(&L);
    // 使用数组创建链表
    CreatDLinkList(L, a);
    // 打印链表
    printElem(L);
    // 在第3个位置后面插入40
    InsertElem(L, 3, 40);
printf("插入元素后，从前往后遍历：\n");
    // 再次打印链表以验证插入操作
    printElem(L);
printf("插入元素后，从后往前遍历：\n");
    rprintElem(L);
    return 0;
} 

// 初始化链表头结点，并设置其next指针为空
void InitDLinkList(DLinkList *head)
{
    if ((*head = (DLNode*)malloc(sizeof(DLNode))) == NULL)
    {
        exit(-1);  // 如果分配内存失败则退出程序
    };
    (*head)->next = NULL;  // 头结点的next设为NULL
}

// 根据给定数组创建双向链表
void CreatDLinkList(DLinkList head, int a[])
{
    DLNode *p, *s;
    p = head;  // p开始指向头结点
    for (int i = 0; i < 8; i++)
    {
        s = (DLNode*)malloc(sizeof(DLNode));  // 分配新结点
        s->data = a[i];  // 设置新结点的数据
        p->next = s;  // 链接新结点到当前p之后
        s->prior = p;  // 设置新结点的前驱指针
        s->next = NULL;  // 新结点的next设为NULL
        p = s;  // 移动p到新结点
    }
}

// 在指定位置i处插入元素e
int InsertElem(DLinkList head, int i, DataType e)
{
    DLNode *p;
    p = head;
    int j = 0;
    // 查找插入位置
    while (p->next && j < i)
    {
        p = p->next;
        j++;
    }
    if (j < i)
    {
        return 0;  // 如果未找到正确的位置，则返回失败
    }
    DLNode *s;
    s = (DLNode*)malloc(sizeof(DLNode));
    s->data = e;  // 设置新结点的数据
    one;  two;  three;  four;  // 使用宏指令完成新结点的链接
    return 1;  // 返回成功
}

// 顺序打印链表中的所有元素
void printElem(DLinkList head)
{
    DLNode *p;
    p = head->next;  // 跳过头结点，从第一个实际数据结点开始
    while (p)
    {
        printf("%d ", p->data);  // 打印结点数据
        p = p->next;  // 移动到下一个结点
    }
    printf("\n");  // 打印换行符
}
// 逆序打印链表中的所有元素
void rprintElem(DLinkList head)
{
DLNode *p;
p=head;
while(p->next)
{
p=p->next;
}
while(p!=head)
{
printf("%d ",p->data);
p=p->prior;
}
printf("\n");
}

代码部分相比昨天只改变了宏的部分，因为只需要把p指向前一个元素，宏定义改成后端插入元素的操作即可，为了第一次看这篇博文的人方便，我还是把代码全部展示上吧。^_^

重点关注宏定义以及插入的顺序：

宏定义：

#define one s->prior=p // 设置新节点s的前驱指针指向p
#define two p->next=s // 将p的后继指针指向新节点s
#define three s->next=p->next // 设置新节点s的后继指针指向p的下一个节点
#define four p->next->prior=s // 如果p后面有节点，则更新该节点的前驱指针为s

上述案例的插入顺序：

这里给出图像便于理解：

我们还用昨天的顺序，方便记忆，像在空中画一个躺下来的数字8

下面我们看该顺序1234的运行结果：

什么！！！竟然没有将40正确的插入30的后面，输出是一个死循环，为什么昨天1234的顺序可以正确的插入50的前面呢？？？我这里只让p指向了待插入元素的前面

我们改变一下顺序，变成1324顺序，再运行一下，观察结果如何，只调换2和3的位置。

我们看运行结果：

上面的两个例子表明1234和1324都不可行。

我们再把2放在最后面成1342，观察结果：

结果表明1342可以正确插入。

二、分析为什么1234和1324不可以，而1342可行呢？

这个问题与昨天极其相似，我们直接顺着昨天的思路，观察先2后3还有先2后4为什么不行？

我们给出先2后3的代码部分：

p->next=s;

s->next=p->next;

这两步合起来不就是s->next=s吗，和昨天的错误一样，都是s自己指向了自己，但是昨天并不影响输出原链表，因为只是找不到正确的前驱了，但是这个会影响输出原来的链表，因为这个找不到正确的后继了，从前往后遍历会因为s形成了环而找不到双链表的尾结点，造成一直输出s里面保存的数据。

我们在给出先2后4的代码：

p->next=s;

p->next->prior=s

合并一下就是s->prior=s，错误很明显了

只要充分理解昨天《标题二》的内容，这里我相信会很容易的。

三、下面我们给出正确的8种情况的顺序，以及16种错误顺序

四、总结规律

有了昨天的经验，我们直接看2关于3和4的位置

发现

2只要在3和4的后面就是正确的，

2只要在3前面或者4前面就是错误的

五、我们来一道考研真题练练手

4-4.设双向循环链表中结点的结构有数据域 data，指针域 pre和next，链表不带头结点。若在指针 p所指结点之后插入结点 s，则应执行下列（）操作。【南京理工大学 2005 一、3（1分）】【北京交通大学 2006 一、1（2 分）】
A.p->next=s; s->pre=p;p->next->pre=s; s->next=p->next;
B.p->next=s; p->next->pre=s; s->pre=p; s->next=p->next;
C.s->pre=p; s->next=p->next; p->next=s; p->next->pre=s;
D.s->pre=p; s->next =p->next; p->next->pre=s; p->next=s;

有了结论可以快速标序号找到答案，就是D

原文地址：https://blog.csdn.net/2301_80585598/article/details/142714887

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：字符和ACSII编码
下一篇：洛谷P5723、P5728、P1428、P1319 Python解析

力扣59.螺旋矩阵||
所有元素，且元素按顺时针顺序螺旋排列的。
阅读更多2024-10-08
健康信息管理：SpringBoot的创新应用
Java语言具有很好的面向对象性，可以符合人的思维模式进行设计，封装是将对象的属性和方法尽可能地隐藏起来，使得外界并不知道是如何实现的，外界能通过接口进行访问，继承是指每个类都会有一个父类，所有的子类
阅读更多2024-10-08
【CF2021E】Digital Village（All Version）
给你一张n个点m条边的无向图，有p个关键点。你需要选择k个点染黑，使得这p个关键点到这k个黑点的代价和最小。定义代价为两点之间边权最大的边的最小值。你需要求出 k = 1,2,…,n 的所有答案。
阅读更多2024-10-08
毕业设计深度学习昆虫识别系统（源码+论文）
🔥这两年开始毕业设计和毕业答辩的要求和难度不断提升，传统的毕设题目缺少创新和亮点，往往达不到毕业答辩的要求，这两年不断有学弟学妹告诉学长自己做的项目系统达不到老师的要求。为了大家能够顺利以及最少的精力
阅读更多2024-10-08
69.x的平方根 367.完全有效的平方数
经典平方根问题，用二分法慢慢逼近找开方值，注意mid*mid要用。
阅读更多2024-10-08
window 安装永洪BI Desktop版本教程
vividime Desktop是一款轻量级桌面智能数据分析工具,基于本机安装,省去繁琐的部署环节,即装即用.提供一站式、敏捷、高效的数据治理及可视化分析能力,可以帮助企业用户摆脱服务端产品的各种门限
阅读更多2024-10-08
tts（text to speech）使用 pyttsx3 实现文本转语音 - python 实现
tts（text to speech）使用 pyttsx3 实现文本转语音 - python 实现
阅读更多2024-10-08
程序员/IT行业从业者/科研人员【冬季养生指南】
中医理论认为，冬季寒气与肾相应，最易耗伤肾的阳气。而肾为先天之本，肾精气的强弱，决定着人的生长壮老已。冬天养肾不仅能增强人体抵御寒冷的能力，而且还可提高人体免疫力和抗病力，延缓衰老。
阅读更多2024-10-08
leetcode|刷算法线段树原理以及模板
线段树
阅读更多2024-10-08
Linux的root用户
但是发现提示“用户名不在 sudoers文件中，此事将被报告” .这是因为该普通用户不在sudoers文件中,所以要找到该文件，把普通用户添加入sudoers文件中，才能有sudo这个权限。操作如下:
阅读更多2024-10-08