约瑟夫环(循环列表实现)

约瑟夫(Joseph)问题的一种描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,令其出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新报数,如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。

    实验要求

利用无头结点的单向循环链表存储结构模拟此过程,按照出列的顺序打印出各人的编号。

测试数据:

    m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为8(正确的出列顺序应为6,1,4,7,2,3,5)

 实验提示:

    程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密码,可设n<=30,此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限。

#include<iostream>//用链表实现约瑟夫环问题 (循环链表)
using namespace std;
typedef struct node  
{
	int num;
	int pwd;
	struct node* next;
}Node ,*list;
list Createlist(int n)//创建循环列表
{
	list head = NULL,rear=NULL, temp = NULL;
	head = rear;
	for (int i = 1; i <= n; i++)
	{
		temp = new node;
		temp->num = i;
		cin >> temp->pwd;
		if (head == NULL)//若为空则赋给头指针
		{
			head = temp;
		}
		else
		{
			rear->next = temp;//接在尾指针后
		}
		rear = temp;
	}
	rear->next = head;//尾指针指向头指针
	return head;
}
//void Printlist(list l)//打印输出
//{
	//list p = l;
	//for (int i = 0; i < 14; i++)
	//{
		//cout << p->num << p->pwd << " ";
		//p = p->next ;
	//}
	//cout << endl;
//}
void Getlist(list l,int n,int m)//约瑟夫环
{
	list p = l, q = NULL;
	while (p->next != p)//循环直到只剩一个 头尾相指
	{
		for (int i = 1; i < m; i++)
		{
			q = p;//保留离开点的上一个节点
			p = p->next;
		}
		cout << p->num<<" ";
		m = p->pwd;
		q->next = p->next;//剔除该点
		p = p->next;//从下一节点重新计数
	}
	cout << p->num;
}
int main()
{
	list l;
	int n, m;
	cin >> n >> m;
	l = Createlist(n);
	//Printlist(l);
	Getlist(l, n, m);
}

文章来源地址:https://www.uudwc.com/A/8d6zv/

原文地址:https://blog.csdn.net/qq_74156152/article/details/132819401

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇2023年09月12日 07:18
【使用Cpolar和Qchan搭建自己的个人图床】
下一篇 2023年09月12日 07:18