数据结构实验——约瑟夫环

问题描述

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

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

实验方案

（一）算法设计思路：

先创建一个含有n个结点（不带头结点）的单循环链表，然后由第一个结点起从1开始计数（此时假设k=1），计数到m时，对应结点从链表中删除，接下来从被删除结点的下一个结点重新开始从1开始计数，计到m时，从链表中删除对应结点，如此循环，直至最后一个结点从链表中删除，算法结束。

（二）使用模块及变量的说明

1、typedef struct lnode定义单链表结构体

2、LinkList Creat_LinkList(n)创建从1开始到n结束的单向循环链表

3、LNode* Locate_LinkList（L,k）函数确定开始位置，并返回指针

4、void Del_LinkList(p,m,n)输出并删除对应节点

5、主调函数部分：用户输入人数n，报数上限m，开始值k，按照出列顺序打印编号。其中n m k必须为大于等于一的正整数，否则报错。

实验代码

C++版

#include<iostream>
using namespace std;

typedef struct lnode  
{
	int data;
	struct lnode* next;
}LNode,*LinkList;  //链表

LinkList Creat_LinkList(int n)//创建单向循环链表
{
	LinkList L;
	L = new LNode;
	L->data = 1;
	L->next = L;
	LNode* s, * r ;
	r = L;
	for (int i = 2; i <= n; i++)
	{
		s = new LNode;
        s->data = i;
		s->next = r->next;
		r->next = s;
		r = s;	
	}
	return L;
}

//确定开始位置
LNode* Locate_LinkList(LinkList L, int k) {
	LNode* p = L;
	while ( p->data != k)
		p = p->next;
	return p;
}

void Del_LinkList(LNode*p, int m, int n)
{
	LNode* q; 
	cout << "输出编号顺序为：";
	if (m == 1) {      //m=1时，单独处理
		q = p;
		for (int i = 1 ; i <= n; i++) {
			cout << q->data << " ";
			q = q->next;
		}
	}
	else {
		for (int j = 1; j <= m; j++) {
			if (j == m - 1 && p->next != p) {
				q = p->next;
				p->next = p->next->next;
				p = p->next;
				cout << q->data << " ";
				delete q;
				j = 0;
				continue;
			}
			if (p->next == p) {
				cout << p->data;
				j = m + 1;
			}
			else p = p->next;
		}
	}
	cout << endl;
}

int main()
{
	int n, m, k;
	cout << "请输入人数n：";
	cin >> n;
	cout << "请输入报数上限值m：";
	cin >> m;
	cout << "输入开始编号k：";
	cin >> k;
	if (n < 1 || m < 1 || k < 1)
	{
		cout << "输入有误" << endl;
		system("pause");
		exit(0);
	}
	LinkList L;
	L = Creat_LinkList(n);	
	LNode* p;
	p = Locate_LinkList(L, k);
	Del_LinkList(p, m, n);
	LNode* d = L, *d2 = NULL;
	for (int i = 1; i < n; i++) {
		d2 = d;
		d = d->next;
		delete d2;
	}
	delete d；
	return 0;
}

实验总结

1、创建单向循环链表时，出现警告C6011：取消对NULL指针“r”的引用，加上对空指针的判断后，问题解决。后改进程序，建立循环空链表后，再尾插法插入元素，无需设置NULL指针。

2、删除结点部分，p指针指向待删除结点前一个结点时，方便完成删除操作，m=1时，删除操作不便完成，所以单独处理。m=1时，直接从开始结点打印输出循环链表。

3、动态申请的空间（new），最终要释放（delete），new，delete要配套使用。