0。小结在上一篇【数据结构之链表】看完这篇文章，终于明白了链表。链接存储结构已经被引入。介绍了链式存储结构最基本（简单）的实现——单向链表。单向链表，顾名思义，就是单向的。因为单向链表的每个节点只有一个数据域和一个指针域，而指针域只存储下一个节点的地址，所以我们只能通过某个节点找到它的直接后继节点，而不能通过某个节点节点。一个节点找到它的直接前驱。另外，由于单向链表结束于尾节点（链表的最后一个节点），所以尾节点的指针字段为NULL表示链表终止，这就导致我们遍历到尾节点，如果想再次遍历，只能手动回到头节点重新开始遍历。为了弥补单链表的上述两个缺点，下面介绍两个链表，它们都是单链表的变形。如果你了解单向链表，就会很容易理解这两种变形。内容1.单向循环链表1.1．结构单链表尾节点的指针字段为NULL，所以单链表到此结束。如果我们用单向链表的尾节点的指针字段来存储头节点的地址，即尾节点的直接后继节点就是头节点，这样单向链表就形成了一个环（循环），称为单项循环链表。1.2.实现思路单向循环链表是由单链表演变而来的，被视为单链表的“儿子”。因此，单链表的结构完全适用于单向循环链表。从上图也可以看出结构并没有太大的变化，两者的区别仅在于端节点，所以我们只需要在端节点和相关的操作上下功夫即可结束节点。因此，单向链表的结构与单向链表的结构相同。/*单向循环链表的节点结构体*/typedefstruct_Node{intdata;//数据域：存放数据struct_Node*next;//指针域：存放直接后继节点的地址}Node;为了统一空链表和非空链表的操作，我们使用带首节点的链表来实现。1.3.空链表和空链表的初始化如图所示，头指针和头结点只有一个：空链表的头结点的指针域指向自身，形成一个循环，我们可以用this判断链表是否为空。if(head->next==head){printf("空链表。\n");}初始化一个空链表很简单，只需要创建一个头节点，让头节点的next指针指向自己即可：Node*create_node(intelem){Node*new=(Node*)malloc(sizeof(Node));new->data=elem;new->next=NULL;returnnew;}/***初始化链表*p_head:指向头指针的指针*/voidinit(Node**p_head){//创建头节点Node*head_node=create_node(0);//头指针指向头节点*p_head=head_node;//头节点的next指针指向自己，形成一个环head_node->next=head_node;}1.4.Insert这里的操作只演示头插入法和尾插入法【头插入法】因为取的是首节点，不需要考虑是否为空链表，下图是向空链表插入两个元素的过程：单向循环链表的头部插值过程/***头部插值，新节点是头部节点的直接后继*p_head：指向头指针的指针*elem：新节点的数据*/voidinsert_at_head(Node**p_head,intelem){Node*new=create_node(elem);Node*head_node=*p_head;//头节点//新节点插入到头节点后new->next=head_node->next;head_node->next=new;}【tail插值法】因为为了尽可能简单，我们没有设置tail指针指向尾节点，所以在插入尾部之前，我们需要用一个指针遍历到尾节点，然后插入。/***尾插入方式：新插入的节点总是在链表的尾部*p_head：指向头指针的指针*elem：新节点的数据*/voidinsert_at_tail(Node**p_head,intelem){Node*new=create_node(elem);Node*head_node=*p_head;//头节点Node*tail=head_node;//尾指针指向头节点while(tail->next!=head_node){//尾遍历到链表尾部tail=tail->next;}//尾部插入new->next=tail->next;tail->next=new;}1.5.删除操作删除的本质是“跳过”要删除的节点，所以我们需要找到要删除的节点的直接前驱节点，然后让直接前驱节点的next指针指向它的直接后继节点，从而“跳过”要删除的节点，最后保存其数据字段并释放该节点，即完全删除。这里只演示去掉header的方法。因为删除的是头节点的直接后继节点，所以我们不用费劲去找要删除的节点的直接前驱节点。单向循环链表头删除过程/***头删除方法：删除头节点之后的节点*p_head：指向头指针的指针*elem：指向保存数据变量的指针*/voiddelete_from_head(Node**p_head,int*elem){Node*head_node=*p_head;//头节点if(head_node->next==head_node){printf("空链表，不能删除任何元素。\n");return;}Node*first_node=head_node->next;//第一个节点：头节点的下一个节点*elem=first_node->data;//保存删除节点head_node的数据->next=first_node->next;//删除节点free(first_node);//释放}1.6.遍历操作我们可以循环遍历链表，下面是循环打印节点20次的代码：/***循环打印20个节点*/voidoutput_20(Node*head){if(head->next==head){printf("空链表.\n");return;}Node*p=head->next;for(inti=0;i<=20;i++){if(p!=head){//不打印头节点printf("%d",p->data);}p=p->next;}printf("\n");}2.双向链表2.1.结构双向链表顾名思义，有两个方向，一个向前，一个向后。单向链表中的一个节点只能找到其直接后继的缺陷如图：双向链表2.2.实现思路为了达到指向forw的效果ard和backward，单靠next指针肯定是不够的，所以我们需要再加一个指针——prev，指针指向一个节点的直接前驱节点。/*双向链表的节点结构*/typedefstruct_Node{intdata;//数据域struct_Node*prev;//直接前驱节点指针struct_Node*next;//直接后继节点指针}Node;2.3.空链表和初始化双向链表的空链表如图所示：为双向空链表初始化这样一个空链表，需要创建一个头节点，然后清空两个指针字段：Node*create_node(intelem){Node*new=(Node*)malloc(sizeof(Node));new->data=elem;new->prev=NULL;new->next=NULL;returnnew;}voidinit(Node**p_head){//创建头节点Node*head_node=create_node(0);//head指针指向头节点*p_head=head_node;}2.4.插入操作这里只演示头插入法，过程如下：双向链表头插入法代码如下：/***头插入法，新结点是头的直接后继node*p_head:指向头指针的指针*elem:新节点的数据*/voidinsert_at_head(Node**p_head,intelem){Node*new=create_node(elem);Node*head_node=*p_head;//头节点if(head_node->next!=NULL){//非空链表Node*first_node=head_node->next;//第一个节点：head节点指向的下一个节点//第一个节点的prev指针指向newnodefirst_node->prev=new;//新节点的next指针指向第一个节点new->next=first_node;}//新节点prev指针指向头节点new->prev=head_node;//头节点的next指针指向新节点head_node->next=new;}2.5．删除操作这里只演示头部删除方法。下图是将一个有两个元素节点的双向链表头删除成一个空链表的过程：双向链表头删除方法代码如下：/***头删除方法*p_head:指向链表的指针头指针*elem：指向保存变量的指针*/voiddelete_from_head(Node**p_head,int*elem){Node*head_node=*p_head;//头节点Node*first_node=head_node->next;//第一个要删除的节点：头节点该点的下一个节点if(head_node->next==NULL){//判断为空printf("空链表，没有要删除的元素。\n");return;}*elem=first_node->data;//保存数据(first_node);}2.6。遍历操作有了next指针域，我们就可以一路向后遍历；有了prev指针域，我们就可以一路向前遍历。这里不再展示代码。3.小结了解了单向循环链表和双向循环链表之后，就像搭积木一样，我们也可以创建一个双向循环链表。这里不再演示，读者可以自行尝试。只要理解了上面的三个链表，这绝不是什么难事。以上是链表的部分技巧，后续会持续更新。参考资料[1]GitHub：https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo[2]Gitee：https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo
