深入探究：在双链表指定元素的前面进行插入操作的顺序
深入探究：在双链表指定元素的前面进行插入操作的顺序
归纳编程学习的感悟，
记录奋斗路上的点滴，
希望能帮到一样刻苦的你！
如有不足欢迎指正！
共同学习交流！
🌎欢迎各位→点赞 👍+ 收藏⭐ + 留言 📝
惟有主动付出，才有丰富的果实获得收获！
前言：
在学习数据结构与算法的课程中，单链表的插入操作只用操作两个指针就可以完成操作，因为单链表就一个next的指针域可控操作，但是在双链表中新加了prior指针域，这会使我们在进行插入操作时需要进行4步的改变指针指向操作才能完成，也就是说如果将这4个步骤的顺序全排列，就会出现4！= 24种进行双链表插入操作的顺序。但是这24种情况只有8种是可以成功插入的，为什么是8种，以及为什么另外16种会插入失败，还有在考试中如何快速判断题目给出的顺序是否正确？这些问题我们在正文中进行详细的讲解。
注意：本章节讲的只是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);
//逆序打印双链表
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); // 打印双链表
InsertElem(L,4,40); // 在第4个位置前面插入40
printf("插入元素后，从前往后遍历：\n");
printElem(L); // 再次打印双链表
printf("插入元素后，从后往前遍历：\n");
rprintElem(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"); // 打印换行符
}
//逆序打印双链表的所有元素
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");
}
上述案例的运行结果：
结果表明可以将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这个顺序不可行。
如果把1放在234的后面，成2341呢？
结果是这样：
可以发现逆序输出的时候40是一个死循环输出，也就是2341这个顺序也不可行。
二、分析为什么1234可以，而1423和2341不可以呢？
如果你可以充分理解这里的原因，那么剩下的21中情况，以及明天的24种后端插入的情况将迎刃而解！
我们先观察顺序，原来的顺序是1234，
我只是把4放在了2前面，
变成了1423，
为什么就插入失败了呢？
另外一个把1挪到了最后面为什么也不行？
既然只动了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
我们再来看为什么2341会造成40的死循环输出呢？
我们把1挪到了4后面，所以，我们直接看41这个顺序的代码
p->prior=s;
s->prior=p->prior;
合并起来不就是s->piror=s;吗，这会使s形成一个环，在逆序输出时导致找不到头指针而无限输出s里面保存的元素
三、下面我们给出正确的8种情况的顺序，以及16种错误顺序
正确顺序：1234,1243,1324,2134,2143,2314,3124,3214
错误顺序：1342,1423,1432,2341,2413,2431,3142,3412,3241,3421,4123,4132,4213,4231,4312,4321
这24种情况是我一个一个输出检验过的，只有24种还是可以动手一一列举的，要是5！= 120我就还是让计算机完成吧o(╥﹏╥)o
我们找到答案以后还应该寻找规律，不总结我们很难记住这24种哪个对哪个错，我们总结的目的之一就是方便考试的时候可以快速的判断正确错误。
四、在考试中如何快速判断题目给出的顺序是否正确？
正确顺序：1234,1243,1324,2134,2143,2314,3124,3214
错误顺序：1342,1423,1432,2341,2413,2431,3142,3412,3241,3421,4123,4132,4213,4231,4312,4321
我们仔细观察并寻找规律，首先正确的有8个，错误的有16个；其次1开头的有3个正确的，有3个错误的；2开头的3个正确的3个错误；3开头的又是2个正确4个错误；最后4开头的全是错误的。
这只是我们初步观察发现的规律，只看这个结果发现的，那这感觉还是不好记呀，虽然只是找到了一点统计上的规律，可是我在考试还得将代码转换成1234才能用这个规律，有没有更简单的方法呀！o(╥﹏╥)o
当然有！找到最方便好记的规律我们就要结合《标题二：分析为什么1234可以，而1423和2341不可以呢？ 》的原理，结合是什么原因造成的插入成功与失败。
观察发现，
4在1和2之后就是正确的，
4只要在1前或者2前就是错误的，
正确顺序：1234,1243,1324,2134,2143,2314,3124,3214（4在12后）
错误顺序：1342,1423,1432,2341,2413,2431,3142,3412,3241,3421,4123,4132,4213,4231,4312,4321（4只要在1前或者2前）
也就是在考试中，我们只需要观察4关于1和2的位置关系即可，
4在1和2之后就是正确的，
4只要在1前或者2前就是错误的，
原因在就在《标题二》的分析中。
五、结论
4在1和2之后就是正确的，
4只要在1前或者2前就是错误的，
一定注意：该结论只适用于p指向待插入元素的后面，关于p指向待插入元素的前面的规律，我会在明天发文总结！！！