循环链表与双向链表

一、前言

线性表的顺序存储结构（例如：数组），存储空间是连续的因此我们不用担心元素之间的逻辑关系，线性表最大优点在于可以快速的存取表中任一位置的元素。
线性表顺序存储的缺点在于插入和删除操作时需要移动大量元素时间复杂度为O(n)，线性表的长度也难以适应变化较大的情况，且线性表的扩容需要重新开辟出一块满足大小需求且连续的空间，这容易造成空间碎片。
我们学习链式存储结构的单链表，单链表可以很好的解决数组的这些问题，但是访问单链表的某一位置的元素，需要遍历整个单链表，且每次都要头开始进行单方向的遍历。为了解决这些问题我们引用循环链表和双向链表。

二、循环链表

循环链表：将单链表中最后一个结点的指针域指向头结点（带头结点的链表）或首元结点（不带头结点的链表），使整个单链表形成一个首尾相连的环。

循环链表带头结点的空表：

非空表：

在判断单链表是否是最后一个结点时只需要判断p->next是否为NUll，但是循环链表需要判断p->是否等于头结点，若等于则说明是最后一个结点，否则不是。

当我们经常在链表尾部进行增查操作时，我们可以使用带尾指针的循环链表，将头指针换成尾指针指向链表最后一个结点即可。

循环链表解决约瑟夫环问题

约瑟夫环问题： 即有n个人围成一圈每个人编号为1-n，从第k个人开始报号，报号为m的人出圈，剩余的人继续重复此过程，直至所有人都出圈，输出出圈的先后顺序。

约瑟夫环有两大难题：

1. 如何循环重复出圈
2. 如歌判断循环结束而不会造成死循环

第一个问题我们用环形的循环链表完美解决，出圈的人只需要删除此结点即可。
解决第二个问题有三种思路

• 带头结点的循环链表这样可以通过判断是否只剩一个头结点实现，但是每次循环要判断结点是否为头结点然后跳过头结点。这样显然是没有体现链式存储结构不连续不需要就删除的优点
• 如果不用头结点，只是循环判断条件为p->next != null 这样最后剩余的一个结点会造成死循环。我们换一个思路，最后剩余的一个结点一定是最后出圈的，既然这样我们在循环结束之后再出圈也是可以的，那么只要最后一个结点的next是自己就说明只剩一个结点了这个时候结束循环，最后再单独让最后一个结点出圈。
• 我们可以另外用一个变量记录圈中剩余的人数，这样在剩余人数为0时跳出循环即可。

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int data;
    struct node*next;
}Node,*link;
yuesefuhuan(int n,int m,int k)
{
    int i,count=0;
    Node *p = NULL,*pr = NULL,*q = NULL;  //q暂存第一个节点以便后续建立循环链表 
    for(i = 1;i <= n;i++){
            p=(Node*)malloc(sizeof(Node));
    if(p == NULL)
    {
        printf("memory out use");
        exit(0);
    }
        p->data = i;
    if(q == NULL)  //第一个节点的情况 
    {
        q = p;
        pr = p;        //pr挂起整个链表 
    }else {          //非第一个节点 
       pr->next = p;
       pr = p; 
            }
   }
        p->next = q;  //链表最后一个节点指向第一个节点构成循环链表 
    p = q;
    for(i = 0;i < k-1;i++){         
        p = p->next;   //p指向开始报数的节点 
    }
      while(p != p->next){    //循环退出的条件仅剩一个节点最后另外输出否则就是死循环 
           count++;    //计数 
      if(count != m)
    {
        q = p;  //q指向要删除节点的前一个节点 
        p = p->next;
    }else {
        count = 0;
         pr = p;   //pr 暂存要删除的节点，以便删除后不影响p继续循环下一个节点 
        printf("%5d",pr->data);
        q->next = pr->next;
        free(pr);
        p = p->next;    
    }
    
 } 
 printf("%5d",p->data);
    
}
int main()
{
    int n,m,k;
    printf("请输入总人数：");
    scanf("%d",&n);
        printf("请输入到第几个人出列：");
    scanf("%d",&m);
    printf("请输入从第几个人开始报数："); 
    scanf("%d",&k);
     yuesefuhuan(n,m,k);
    return 0;
}

循环数组解法：

#include<stdio.h>
#include <stdlib.h>
int fun(int n, int m, int k);
int main() {
    int n = 0, m = 0, k = 0;
     scanf("%d%d%d", &n, &m, &k);
     fun(n, m, k);
     return 0;
}
int fun(int n, int m, int k) {
   //动态创建数组 开辟内存 
   int *flags = (int*)malloc(sizeof(int)*n); 
    int i;
   //数组全初始化为0 
for(  i = 0;i < n;i++ ){
    flags[i] = 0;
}
  int nowIndex = k - 1;                    // 当前下标
   int count = 0;                           // 计数器
  int nowLength = n;                         // 剩余人数
  while (nowLength > 0) {
        if (flags[nowIndex] == 0) {
             count ++;
             if (count == m) {
                   count = 0;
                   flags[nowIndex] = 1;
                   nowLength --;
                   printf("%d ", nowIndex + 1);
                  }
             }
           nowIndex ++;
              if (nowIndex == n) {
              nowIndex = 0;
              }
     }
}

三、双向链表

双向链表：链表中每个结点有两个指针域，一个指向直接前趋，一个指向后继，构成一个双向的链表。

//链表结点定义：
typedef struct node{
    int data;  //数据域
    struct node* next;  //直接前趋
    struct node* prior;  //直接后继
}Node;

双向链表带头结点的空表：

非空表：

删除结点操作

    //p为待删除结点    
    q=p->prior;
    q->next=p->next;
    p->next->prior=q;
    free(p);

插入结点操作：

p->prior = q;  //p的前驱指向q
q->next->prior = p;   // q的直接后继结点的前驱指向p
p->next = q->next;   //p的后继指向q的直接后继结点
q->next = p; // q的后继指向p

双向链表的创建、遍历、删除某一个结点

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int data;
    struct node*next;
    struct node*prior;
}Node;
Node*create(Node*head,int n)
{
    //创建头结点 
    head=(Node*)malloc(sizeof(Node));
    head->next=NULL;
    head->prior=NULL;
    head->data=0;
    int a;
    Node*p=NULL,*q=head;
    //初始化双向链表 
    for(int i=0;i<n;i++)
    {
        //初始化新的结点 p 
            p=(Node*)malloc(sizeof(Node));
        p->next=NULL;
         p->prior=NULL;
        scanf("%d",&a);
        p->data=a;
         //移动q指针，指向最后一个结点 
        q->next=p;
        p->prior=q;
        q=q->next;

     }         
      return head; 
}
  //遍历双向链表，前后两种遍历 
void display(Node*head)
{
    Node*pr = head->next,*p = NULL;
    while(pr)
    {
        printf("%5d",pr->data);
        p=pr;
        pr=pr->next;
    }
    printf("\n");
    while(p->prior)
    {
        printf("%5d",p->data);
        p=p->prior;
    } 
    printf("\n");  
}
 Node*del(Node*head,int num)
{
    Node*p=head->next,*q=NULL;
    if(head==NULL)
    {
        printf("empty list\n");
        return NULL;
    }
    while(p->data != num)
    {
        p = p->next;
    }
    if( p == NULL)
    {
        printf("not find \n");
    }
    //p为待删除结点    
    q=p->prior;
    q->next=p->next;
    p->next->prior=q;
    free(p);
return head;
}

//在链表尾部加入一个结点  
Node*add(Node*head,int num)
{
    Node*p=NULL,*pr=head;
    p=(Node*)malloc(sizeof(Node));
    if(p==NULL){
        printf("memory out use \n");
        return NULL;
    }
    p->data=num;
    //遍历得到最后一个结点 
        while(pr->next){
            pr=pr->next;
        }
        //增加一个结点 
        pr->next=p;
        p->prior=pr;
        p->next=NULL;
    return head;
}
int main()
{
    int n,m,k;
    scanf("%d",&n);
    Node*head=NULL;
    head=create(head,n);
    display(head);
    printf("please input a delete number:\n");   //删除一个数k 
    scanf("%d",&k);
    head=del(head,k);
    display(head);
    printf("please input a add number:\n");  //增加一个数m 
    scanf("%d",&m);
    head=add(head,m); 
    display(head);   
    return 0;
}

四、总结

1. 不管是循环链表还是双向链表本质都是线性链式存储的链表，不同的是改变链表的指针指向和数量使得链表能够更加方便进行某一场景的使用。

2. 在解决链表问题中为了使插入和删除任何位置都能一致操作，通常会加入一个头结点，头结点不是第一个结点，头结点也称为哑结点，其数据域没有意义。当然头结点并不是必须的，只是方便操作引用的一个结点。
3. 链表的增删操作结合图形更方便写代码和理解过程。

参考《大话数据结构》(程杰)