C语言约瑟夫环问题

比眉伴天荒 2023-06-08 06:21 13阅读 0赞

**约瑟夫环问题描述：**

**每一个结点有两个数据域和一个指针域，数据域分别存储为id和password，指针域指向下一个结点（图1-1）；**

![20191016221440309.png][]

**解决问题：**

1.  **由键盘输入人数和初始密码。**
2.  **根据输入的人数创建不带头结点（带头结点的链表也可以）的单向循环链表。**
3.  **提示输入每一个人的密码（每一个id对应唯一一个password）。**
4.  **输出id和password。**
5.  **根据输入的初始密码first\_password计数寻找第first\_password个id和password并进行删除操作释放内存，继续寻找下一个第first\_password个结点依次推理寻找输出直到链表为空为止。**

**方案：**

**定义一个结构体存储每一个结点；**

## **struct number\{**  ##

## **int id;** ##

## **int password;** ##

## **struct number \*next;** ##

## **\}\*phead,\*ptemp,\*pnew;** ##

**定义一个结构体存储输入的人数和初始密码：**

## **struct first\{**  ##

## **int num;** ##

## **int password;** ##

## **\}First;** ##

**定义三个函数，分别进行创建表存储结点，输出数据（打印）和实现约瑟夫环问题：**

### **void create();** ###

### **void print();** ###

### **void delet();** ###

**运行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70][]

源代码：

#include<stdio.h>
    #include<malloc.h>
    struct number{
    	int id;
    	int password;
    	struct number *next;
    }*phead,*ptemp,*pnew;
    
    struct first{
    	int num;
    	int password;
    }First;
    
    void create();
    void print();
    void delet();
    
    main()
    {
    	printf("输入人数\t");
    	scanf("%d",&First.num);
    	printf("初始密码\t");
    	scanf("%d",&First.password);
    	
    	create();
    	printf("---打印---\n");
    	printf("--ID---PASSWORD---\n");
    	print();
    	printf("-----删除-----\n");
    	printf("--ID---PASSWORD---\n");
    	delet();
    }
    
    void create()
    {
    	int i;
    	for(i=1;i<=First.num;i++)
    	{
    		if(i==1)
    		{
    			phead=(number*)malloc(sizeof(number));
    			printf("输入%d个密码\t",i);
    			scanf("%d",&phead->password);
    			phead->id=i;
    			phead->next=NULL;
    			ptemp=phead;
    		}
    		else
    		{
    			pnew=(number*)malloc(sizeof(number));
    			printf("输入%d个密码\t",i);
    			scanf("%d",&pnew->password);
    			pnew->id=i;
    			pnew->next=NULL;
    			ptemp->next=pnew;
    			ptemp=pnew;
    		}
    	}
    	ptemp->next=phead;
    }
    
    void print()
    {
    	ptemp=phead;
    	int i;
    	for(i=0;i<First.num;i++)
    	{
    		printf("%3d\t%3d\n",ptemp->id,ptemp->password);
    		ptemp=ptemp->next;
    	}
    }
    
    void delet()
    {
    	int i,j=First.num;
    	ptemp=phead;
    	while(First.num)
    	{
    		for(i=1;i<First.password;i++)
    		{
    			pnew=ptemp;
    			
    //			printf("i=%d\n",i);
    			ptemp=ptemp->next;
    		}
    		printf("%3d\t%3d\n",ptemp->id,ptemp->password);
    		pnew->next=ptemp->next;
    		free(ptemp);
    		First.num--;
    		ptemp=pnew->next;
    	}
    }

### 其他方法： ###

采用单链表或者双线链表，用单链表通过最后一个结点的指针域为空的性质能达到终止循环目标，可以避免打印时调用人数控制循环，但是要记得每次循环结束后ptemp结点初始为删除后的结点的下一个结点。

例如：

ptemp=phead;
    int i;
    while(First.num)	
    {
    		for(i=1;i<First.password;i++)
    		{
    			pnew=ptemp;
    			ptemp=ptemp->next;
    		}
    		printf("%3d\t%3d\n",ptemp->id,ptemp->password);
    		pnew->next=ptemp->next;
    		free(ptemp);
    		ptemp=pnew->next;
    
    if(ptemp->next==NULL)
    {
    ptemp=phead;
    }
    }

本实验的执行约瑟夫环部分代码还可以采用递归方法实现。

例如：

void delet(number *phead)
    {
    
    if（First.num==0）return 0;//结束递归循环
    ptemp=phead;
    int i;
    	for(i=1;i<First.password;i++)
    		{
    			pnew=ptemp;
    			ptemp=ptemp->next;
    		}
    		printf("%3d\t%3d\n",ptemp->id,ptemp->password);
    		pnew->next=ptemp->next;
    		free(ptemp);
    		ptemp=pnew->next;
    
    if(ptemp->next==NULL)
    {
    ptemp=phead;
    }
    First.num--;
    delet(ptemp);
    
    }

[20191016221440309.png]: /images/20230531/193dc2219592460384e9d9b370efaf3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExOTUxNw_size_16_color_FFFFFF_t_70]: /images/20230531/9ccd5ceb079d47d1b64f16ecbb85de4f.png