深入探究：在双链表的前面进行插入操作的顺序

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

前言：

在学习数据结构与算法的课程中，单链表的插入操作只用操作两个指针就可以完成操作，因为单链表就一个next的指针域可控操作，但是在双链表中新加了prior指针域，这会使我们在进行插入操作时需要进行4步的改变指针指向操作才能完成，也就是说如果将这4个步骤的顺序全排列，就会出现4！= 24种进行双链表插入操作的顺序。但是这24种情况只有12种是可以成功插入的，为什么是12种，以及为什么另外12种会插入失败，还有在考试中如何快速判断题目给出的顺序是否正确？这些问题我们在正文中进行详细的讲解。

注意：本章节讲的只是p指向待插入元素的后面，所以后面讲的结论只适用于往p指向的结点前面插入一个元素，关于p指向待插入元素的前面的规律，我会在明天发文总结！！！

一、我们先展示代码

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

#define DataType int
#define debug(a) printf("%d ",a)

// 宏定义简化了插入操作中的四个关键步骤
#define one s->prior=p->prior  // 新节点s的前驱指向p的前驱
#define two p->prior->next=s    // p的前驱的后继指向新节点s
#define three s->next=p         // 新节点s的后继指向p
#define four p->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);

int main()
{	
	int a[10]={10,20,30,50,60,70,80,90};
	DLinkList L;
	InitDLinkList(&L);  // 初始化双链表
	CreatDLinkList(L,a);  // 根据数组创建双链表
	printElem(L);  // 打印双链表
	InsertElem(L,4,40);  // 在第4个位置插入40
	printElem(L);  // 再次打印双链表
	return 0;
} 

// 初始化双链表头结点
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++)  // 循环创建8个数据结点
	{
		s=(DLNode*)malloc(sizeof(DLNode));  // 分配新结点
		s->data=a[i];  // 设置新结点的数据
		p->next=s;  // 将新结点链接到p后面
		s->prior=p;  // 设置新结点的前驱为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;  // 移动p到下一个结点
		j++;  // 计数加一
	}
	if(j<i)  // 如果i超过了链表长度，则返回错误
	{
		return 0;
	}
	DLNode *s;  // 创建新结点
	s=(DLNode*)malloc(sizeof(DLNode));
	s->data=e;  // 设置新结点的数据
	one;  // 更新新结点的前驱
	two;  // 更新原p的前驱的后继
	three;  // 更新新结点的后继
	four;  // 更新p的前驱
	return 1;  // 返回成功标志
}

// 打印双链表的所有元素
void printElem(DLinkList head)
{
	DLNode *p;
	p=head->next;  // 从第一个实际数据结点开始
	while(p)
	{
		printf("%d ",p->data);  // 打印当前结点的数据
		p=p->next;  // 移动到下一个结点
	}
	printf("\n");  // 打印换行符
}

上述案例的运行结果：

结果表明可以将40这个数据正确的插入30的后面

这里注意我为了探究插入顺序定义的宏：

// 宏定义简化了插入操作中的四个关键步骤
#define one s->prior=p->prior // 新节点s的前驱指向p的前驱
#define two p->prior->next=s // p的前驱的后继指向新节点s
#define three s->next=p // 新节点s的后继指向p
#define four p->prior=s // p的前驱指向新节点s

这4步画出来如图所示：

这个顺序像是在空中画一个躺下来的数字8一样，方便记忆，这个顺序我们在明天的p后面插入同样这样记忆

上面的例子的顺序是1234，运行结果表明可以正确的插入。

如果顺序换成1423呢？结果会是怎么样？

下面我们看这种情况的运行结果：

可以发现没有将40正确的插入链表当中，也就是1423这个顺序不可行。

二、分析为什么1234可以，而1423不可以呢？

如果你可以充分理解这里的原因，那么剩下的22中情况，以及明天的24种后端插入的情况将迎刃而解！

我们先观察顺序，原来的顺序是1234，

我只是把4放在了2前面，

变成了1423，

为什么就插入失败了呢？

既然只动了2和4的位置，那我们就重点关注2和4分别是什么操作，

2是p->prior->next=s，也就是p指向的前一个节点的下一个节点指向s，

4是p->prior=s，也就是p指向的前一个节点。

1234这个顺序，2在前面，4在后面，也就是先执行2这个操作，将p的前驱指向s，然后再改变p的前驱成为s

1423这个顺序，4在前面，2在后面，也就是先执行4这个操作，先改变p的前驱成为s，然后再让p的前驱指向s

仔细思考这句话，既然你都将p的前驱变成s了，你还能让p的前驱指向s吗？当然不可以，这不是妥妥的s自己指向自己了吗？

如果自然语言描述不懂，我们来看先4后2的代码

我们看42这个顺序的代码

p->prior=s;

p->prior->next=s;

这不是翻译过来就是s->next=s吗

那么先执行4再执行2，这样就造成了p的真正前驱丢失，就不能让p的前驱正确的指向s啦(*^▽^*)

注意：这只会造成p的前驱丢失，并不会影响p的真正前驱指向p哦^_^，也就是我们可以正常输出原来的链表10 20 30 50 60 70 80 90

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

正确顺序：1234,1243,1324,2134,2143,2314,2341,2413,2431,3124,3214,3241

错误顺序：1342,1423,1432,3142,3412,3421,4123,4132,4213,4231,4312,4321

这24种情况是我一个一个输出检验过的，只有24种还是可以动手一一列举的，要是5！= 120我就还是让计算机完成吧o(╥﹏╥)o

我们找到答案以后还应该寻找规律，不总结我们很难记住这24种哪个对哪个错，我们总结的目的之一就是方便考试的时候可以快速的判断正确错误。

四、在考试中如何快速判断题目给出的顺序是否正确？

正确顺序：1234,1243,1324,2134,2143,2314,2341,2413,2431,3124,3214,3241

错误顺序：1342,1423,1432,3142,3412,3421,4123,4132,4213,4231,4312,4321

我们仔细观察并寻找规律，发现它有极其高的对称性，首先正确的有12个，错误的有12个；其次1开头的有3个正确的，有3个错误的；2开头的全是正确的；3开头的又是3个正确3个错误；最后4开头的全是错误的。

这只是我们初步观察发现的规律，只看这个结果发现的，那这感觉还是不好记呀，虽然比记住24种方便了一点，可是我在考试还得将代码转换成1234才能用这个规律，有没有更简单的方法呀！o(╥﹏╥)o

当然有！找到最方便好记的规律我们就要结合《标题二：分析为什么1234可以，而1423不可以呢？》的原理，结合是什么原因造成的插入成功与失败，在《标题二》的分析中，我们知道这是2和4的位置顺序造成的，跟13没有关系，那我们现在观察一下结果中2和4的顺序是怎么影响结果的。

观察发现， 只要4在2的后面就是正确的，只要4在2的前面就不对

正确顺序：1234,1243,1324,2134,2143,2314,2341,2413,2431,3124,3214,3241（4在2后）

错误顺序：1342,1423,1432,3142,3412,3421,4123,4132,4213,4231,4312,4321（4在2前）

也就是在考试中，我们只需要观察4和2的位置关系即可，

4在2后就是正确的，也就是p->prior=s在p->prior->next=s的后面就是正确的，

4在2前就是错误的，也就是p->prior=s在p->prior->next=s的前面就是错误的。

原因在就在《标题二》的分析中。

这样我们在考试中只用观察这两个操作的位置即可，只要13存在，就观察24位置就好啦O(∩_∩)O