约瑟夫环

今天药忘吃喽~ 2022-04-22 06:06 253阅读 0赞

【问题描述】

编号为 1,2,...,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随 机数 m>0，从编号为 1 的人开始，按顺时针方向 1 开始顺序报数，报到 m 时停止。报 m 的人出圈， 同时留下他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始，重新从 1 开始报数，如此下 去，直至所有的人全部出列为止。

【基本要求】

利用单向循环链表存储结构模拟此过程，按照出列的顺序打印输出每个人的编号。

【数据结构】

typedef struct node   
           \{  
                 int  no;                       /\*游戏者的编号\*/  
                 unsigned int  pwd;             /\*游戏者持有的密码\*/  
                 struct node \*next;  
            \}Node, \*LinkList;

【解题思路与代码分析】

/*用尾插法创建一个结点数为n的单循环链表，返回值为尾结点的指针*/
    LinkList  create_list(int n)
    {
    	LinkList p, rear;   int i;
    	/*先创建循环链表的第一个结点*/
    	p = (Node *)malloc(sizeof(Node));
    	if (!p) {
    		printf("memory allocation error!\n");   return NULL;
    	}
    	printf("input password:");
    	scanf("%d", &(p->pwd));
    	p->no = 1;
    	p->next = p;      rear = p;

创建指针p,rear,分别指向当前结点和尾结点。因为该循环链表没有头结点，所以第一个结点的创建与其他结点有所不同，此处应应分类。创建第一个结点时，先给p申请空间，若申请成功，则输入其编号no，密码pwd，以及指针域（第一结点指向自己），使尾指针指向当前结点。

/*创建循环链表的其余n - 1个结点;
    	  返回表尾结点指针;*/
    	for (i = 2; i <= n; i++)  /*创建循环链表的其余n-1个结点*/
    	{
    		p = (Node *)malloc(sizeof(Node));
    		if (!p){
    			printf("memory allocation error!\n");  return NULL;
    		}
    		printf("input password:");   scanf("%d", &(p->pwd));
    		p->no = i;   p->next = rear->next;
    		rear->next = p;    rear = p;
    	}
    	return rear;
    }

p->next = rear->next;     rear->next = p;    rear = p;

此三句是核心，跟学过的插入一模一样，只不过实在尾结点(tail)与第一个结点(tail->next)之间插入p.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70][]

void Joseph(LinkList tail, int n, int m)
    {
    	LinkList pre, p;
    	int k; m = m % n ? m % n : n;
    	pre = tail;  p = tail->next;  k = 1;
    	while (n > 1) 
    	{/*圈中多于1个人时循环*/
    		if (k == m) 
    		{ /*数到需要出去的人（结点）时进行出圈处理*/
    			/*p指向的结点为需要删除的结点*/
    			printf("%4d", p->no); 
    			pre->next = p->next;      n--;
    			m = p->pwd % n ? p->pwd % n : n;
    			free(p);
    			p = pre->next;
    			k = 1;
    		}
    		else {
    			k++; pre = p; p = p->next;
    		}
    	}/*while*/
    	printf( "%4d\n", p->no); free(p);
    }/*Joseph*/

p指向当前结点，pre为其前驱，m每次更新为新密码，当m>n时，可以用m%n表示，m%n?m%n:n;

p从第一个结点（p->tail,pre=tail）开始找 ，k计数，初值为1，若没找到，则将pre,p统一后移一位，直到找到出圈对象时，输出该队员的序号，记下其所持密码，建立pre与p->next的关系，并且删除p结点，之后总人数n自减1，k重新计数（k=1）。循环结束的条件是当总人数只剩一人时，跳出整个循环，打印最后一人的序号并释放结点。

void output_list(LinkList head)
    {
    	LinkList p;
    	p = head;
    	do {
    		printf("(%d,%d)\t", p->no, p->pwd);
    		p = p->next;
    	} while (p != head);
    	printf("\n");
    }/*output_list*/

head=tail->next，其实就是通过p后移实现遍历链表。

int main(void)
    {
    	LinkList tail;
    	int n, it;
    	printf("input the number of players and initial password:");
    	scanf("%d%d", &n, &it);
    	tail = create_list(n);   /*创建单循环链表*/
    	if (tail) {
    		output_list(tail->next);  /*输出循环链表中结点的信息*/
    		Joseph(tail, n, it);
    	}
    	system("pause");
    	return 0;
    }

开始先输入总人数和初始密码，接着调用自定义函数实现循环链表的创建，之后输出该链表的信息，（序号，密码）格式输出，最后调用Joseph函数。

【运行截图】

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1][]

上述代码整合起来就是总的，为了便于观看，故将整体代码粘贴如下：

#include<stdio.h>
    #include<stdlib.h>
    /*************************
     k:计数                  *
     p:指向计数时的当前结点  *
     pre:指向p的前驱结点     *
    **************************/
    
    typedef struct node 
    {
    	int  no;                       /*游戏者的编号*/
    	unsigned int  pwd;			 /*游戏者持有的密码*/
    	struct node *next;
    }Node, *LinkList;
    
    
    /*用尾插法创建一个结点数为n的单循环链表，返回值为尾结点的指针*/
    LinkList  create_list(int n)
    {
    	LinkList p, rear;   int i;
    	/*先创建循环链表的第一个结点*/
    	p = (Node *)malloc(sizeof(Node));
    	if (!p) {
    		printf("memory allocation error!\n");   return NULL;
    	}
    	printf("input password:");
    	scanf("%d", &(p->pwd));
    	p->no = 1;
    	p->next = p;      rear = p;
    	/*创建循环链表的其余n - 1个结点;
    	  返回表尾结点指针;*/
    	for (i = 2; i <= n; i++)  /*创建循环链表的其余n-1个结点*/
    	{
    		p = (Node *)malloc(sizeof(Node));
    		if (!p){
    			printf("memory allocation error!\n");  return NULL;
    		}
    		printf("input password:");   scanf("%d", &(p->pwd));
    		p->no = i;   p->next = rear->next;
    		rear->next = p;    rear = p;
    	}
    	return rear;
    
    }
    
    
    void Joseph(LinkList tail, int n, int m)
    {
    	LinkList pre, p;
    	int k; m = m % n ? m % n : n;
    	pre = tail;  p = tail->next;  k = 1;
    	while (n > 1) 
    	{/*圈中多于1个人时循环*/
    		if (k == m) 
    		{ /*数到需要出去的人（结点）时进行出圈处理*/
    			/*p指向的结点为需要删除的结点*/
    			printf("%4d", p->no); 
    			pre->next = p->next;      n--;
    			m = p->pwd % n ? p->pwd % n : n;
    			free(p);
    			p = pre->next;
    			k = 1;
    		}
    		else {
    			k++; pre = p; p = p->next;
    		}
    	}/*while*/
    	printf( "%4d\n", p->no); free(p);
    }/*Joseph*/
    
     
    void output_list(LinkList head)
    {
    	LinkList p;
    	p = head;
    	do {
    		printf("(%d,%d)\t", p->no, p->pwd);
    		p = p->next;
    	} while (p != head);
    	printf("\n");
    }/*output_list*/
    
    
    int main(void)
    {
    	LinkList tail;
    	int n, it;
    	printf("input the number of players and initial password:");
    	scanf("%d%d", &n, &it);
    	tail = create_list(n);   /*创建单循环链表*/
    	if (tail) {
    		output_list(tail->next);  /*输出循环链表中结点的信息*/
    		Joseph(tail, n, it);
    	}
    	system("pause");
    	return 0;
    }
    
    /*test data
       input
       7 5
       3 8 1 22 4 9 15
       output
       (1,3)   (2,8)   (3,1)   (4,22)  (5,4)   (6,9)   (7,5)
       5 2 6 7 4 3 1*/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70]: /images/20220422/8d1f21d95b4546b98e96f5177cc92641.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1]: /images/20220422/6b0bfae922b244e1915042782e2b79b0.png