博客

可以把链表的两头连接，使其成为了一个环状链表，通常称为循环链表。

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

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
typedef struct node{
    int number;
    struct node * next;
}person;


person* createNode(int num)
{
     person* p = (person*)malloc(sizeof(person));
     if(NULL == p) { printf("malloc failed.\n"); return NULL;}
     bzero(p, sizeof(person));
     p->number = num;
     p->next = NULL;
     return p;
}

void displayList(person* const head, const int sum)
{
    person* p = head;
        for (int i = 1 ; i < sum+1; i++)
        {
         printf("p->number = %d\n", p->number);
         p = p->next;
        }


}


person * initLink(int n)
{
     person* head = createNode(1);
     person* tail = head;
      for(int i = 2; i < n+ 1; i++)
      {
            tail->next  = createNode(i);
            tail =tail->next;
      }
      tail->next = head;   //首尾相连
 return head;

}

void findAndMoveOutPerson(person* head, int k, int m)
{
         person* tail = head;
         person* p = head;
         //找到编号为k的人
         while(p->number != k)
         {
          p= p->next;
         }
//从编号为k的人开始，当 p->next==p时，
 //        说明链表中除了p结点，所有编号都出列了，
         while(p->next != p)
         {
              for(int i = 1; i< m ; i++)
              {
               tail = p;
                   p = p->next;
              }
               tail->next = p->next; //从链表上删除节点p
           printf("the number  of moving out from queue = %d\n", p->number);
               free(p);

               p = tail->next;
         }
printf("the number  of moving out from queue = %d\n", p->number);
    free(p);

}


int main()

{
    printf("the total persons around the table\n");
    int n;
    scanf("%d",&n);
    person * head=initLink(n);
    displayList(head, n);

   printf(" the person k numbers off(k>1且k< =n)：");
   int k;
   scanf("%d",&k);
   printf("the number(m) the person  count \n");
   int m;
    scanf("%d",&m);
   findAndMoveOutPerson(head, k, m);
    return 0;
}