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

前言：

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

        注意：本章节讲的是在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