约瑟夫环

实例说明：

        本实例使用循环链表实现约瑟夫环。给定一组编号分别是4、7、5、9、3、2、6、1、8。报数初始值由用户输入，这里输入4，如图12.18所示，按照约瑟夫环原理打印输出队列。

实现过程：

        (1)在 VC++6.0中创建一个C文件。
        (2)引用头文件，声明结构体，声明自定义函数等。代码如下:

#include <stdio.h>
#define N 9
#define OVERFLOW 0
#define OK 1
int KeyW[N]={4,7,5,9,3,2,6,1,8};

        (3)声明structLNode类型，代码如下：

typedef struct LNode
{int keyword;struct LNode *next;
} LNode, *LinkList;

        (4)自定义函数Joseph0)，使用循环链表实现约瑟夫环算法，根据给定数获得一个数列。代码如下:

void Joseph(LinkList p, int m, int x)
{LinkList q; /*声明变量*/int i;if (x == 0)return;q - p;m %= x;if (m == 0)m = x;for (i = 1; i <= m; i++) /*找到下一个节点*/{p = q;q = p->next;}p->next = q->next;i = q->keyword;printf("%d ", q->keyword);free(q);Joseph(p, i, x - 1);        /*递归调用*/
}

        (5)创建 main()函数作为程序的入口函数，调用自定义函数 Joseph()实现约瑟夫环算法，并将得到的数列输出。代码如下:

#include <stdio.h>
#include <stdlib.h>
#define N 9
#define OVERFLOW 0
#define OK 1
int KeyW[N] = {4, 7, 5, 9, 3, 2, 6, 1, 8};typedef struct LNode
{int keyword;struct LNode *next;
} LNode, *LinkList;void Joseph(LinkList p, int m, int x)
{LinkList q; /*声明变量*/int i;if (x == 0)return;q = p;m %= x;if (m == 0)m = x;for (i = 1; i <= m; i++) /*找到下一个节点*/{p = q;q = p->next;}p->next = q->next;i = q->keyword;printf("%d ", q->keyword);free(q);Joseph(p, i, x - 1); /*递归调用*/
}
int main(int argc, char const *argv[])
{int i, m;LinkList Lhead, p, q;Lhead = (LinkList)malloc(sizeof(LNode)); /*申请节点空间*/if (!Lhead)return OVERFLOW;Lhead->keyword = KeyW[0]; /*数据域赋值*/Lhead->next = NULL;p = Lhead;for (i = 1; i < 9; i++){/*创建循环链表*/if (!(q = (LinkList)malloc(sizeof(LNode))))return OVERFLOW;q->keyword = KeyW[i];p->next = q;p = q;}p->next = Lhead;printf("请输入第一次计数值m: \n");scanf("%d", &m);printf("输出的队列是: \n");Joseph(p, m, N);return OK;
}

运行结果：

技术要点：

        约瑟夫环算法是:n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k(k为起点人手中的密码值)数数。数到k的人退出圈子，然后从下一个人开始继续从1到i(刚退出圈子的人的密码)数数，数到i的人退出圈子。重复上面的过程。直到剩下最后一个人。

        希望能对您的学习和工作有所帮助！