用C链表实现约瑟夫环问题

问题：设有n个人围成一个圆圈，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人再次出列，如此反复，直到所有的人全部出列为止。对于任意给定的n、s、m，求按出列次序得到的n个人员的序列。

例：

图片就是问题简单示例，里面是每次要循环的数据，后面的S是出列的人

思路：

先创建一个链表，链表的长度就是n
从第s个节点开始循环
判断是否是第m个数
如果是第m个数，就输出并删除当前节点
循环到最后一个节点，再从第一个节点接着循环

主要代码：

 void yuesefu (LinkList * head, int n, int s, int m)

 {

     LinkList * p, * r, * q;

     int i = , j = n, k, l;

     p = GetData_LinkList(head, s);    //从第S位开始

     //判断是否循环完成

     while (j > ) {

         //判断是否为第m个数

         if (i == m) {

             i = ;

             //输出这轮出局的人

             printf("%d\n", p->data);

             //存储当前节点的值

             k = p->data;

             //删除当前节点

             q = head->next;

             l=;

             while (q != NULL) {

                 //判断当前节点得值是否等于要删除的值

                 if (q->data == k) {

                     //删除节点

                     DeleteNode_LinkList(head, l);

                     break;

                 }

                 l++;

                 q = q->next;

             }

             //从下一个节点开始循环

             p = GetData_LinkList(head, l);

             j--;

         }else {

             p = p->next;

         }

         //如果超出链表长度，再从第一个节点开始循环

         if (p == NULL)

             p = head->next;

         i++;

     }

 }

整体代码：

 #include <stdio.h>

 #include <stdlib.h>

 typedef int elemtype;

 typedef struct node

 {

     elemtype data;

     struct node * next;

 }LinkList;

 //创建链表

 LinkList * Create_LinkListF(int n)

 {

     int i;

     LinkList * head, * p;

     head = (LinkList *) malloc (sizeof(LinkList));

     if (head == NULL)

         return head;

     head->next = NULL;

     for (i=; i<=n; i++) {

         p = (LinkList *) malloc (sizeof(LinkList));

         if (p == NULL)

             return head;

         p->data = i;

         p->next = head->next;

         head->next = p;

     }

     return head;

 }

 //按序号查找

 LinkList * GetData_LinkList (LinkList * head, int i)

 {

     LinkList * p;

     int j = ;

     if (i <= )

         return NULL;

     p = head;

     while (p->next != NULL && j<i) {

         p = p->next;

         j++;

     }

     if (i == j)

         return p;

     else

         return NULL;

 }

 //删除节点

 int DeleteNode_LinkList (LinkList * head, int i)

 {

     LinkList * p, * r;

     if (i <= )

         p = NULL;

     else

         if (i == )

             p = head;

         else

             p = GetData_LinkList(head, i-);

     if (p == NULL) {

         return ;

     }else {

         r = p->next;

         if (r == NULL)

             return ;

         p->next = r->next;

         free(r);

         return ;

     }

 }

 void yuesefu (LinkList * head, int n, int s, int m)

 {

     LinkList * p, * r, * q;

     int i = , j = n, k, l;

     p = GetData_LinkList(head, s);    //从第S位开始

     //判断是否循环完成

     while (j > ) {

         //判断是否为第m个数

         if (i == m) {

             i = ;

             //输出这轮出局的人

             printf("%d\n", p->data);

             //存储当前节点的值

             k = p->data;

             //删除当前节点

             q = head->next;

             l=;

             while (q != NULL) {

                 //判断当前节点得值是否等于要删除的值

                 if (q->data == k) {

                     //删除节点

                     DeleteNode_LinkList(head, l);

                     break;

                 }

                 l++;

                 q = q->next;

             }

             //从下一个节点开始循环

             p = GetData_LinkList(head, l);

             j--;

         }else {

             p = p->next;

         }

         //如果超出链表长度，再从第一个节点开始循环

         if (p == NULL)

             p = head->next;

         i++;

     }

 }

 int main (void)

 {

     int n, s, m;

     LinkList * head;

     printf("n=");

     scanf("%d", &n);

     printf("s=");

     scanf("%d", &s);

     printf("m=");

     scanf("%d", &m);

     head = Create_LinkListF(n);

     yuesefu(head, n, s, m);

 }

巴特西

用C链表实现约瑟夫环问题

最新文章

热门文章