问题描述

有10个人围坐在一个圆桌周围，把这n个人依次编号为1，…，10。从编号是1的人开始报数，数到第9个人出列，然后从出列的下一个人重新开始报数，数到第9个人又出列，…，如此反复直到所有的人全部出列为止。

通过循环链表的方式解决

循环单链表和单链表的区别在于，表中的最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。

#include<iostream>
using namespace std;


typedef struct LinkNode {

	int data;		//结点的数据域

	struct LinkNode* next;	//结点的指针域

}LinkNode, LinkList;	


//初始化循环链表
bool InitLoopList(LinkList*& L) {

	L = new LinkNode;		//构造一个空的循环链表

	if (!L)return false;	//生成结点失败

	L->next = L;			//头结点的指针域指向自己
	L->data = -1;

	return true;
}


//尾插法
bool LoopListInsertBack(LinkList*& L, LinkNode* node) {

	LinkNode* last = NULL;

	if (!L || !node)return false;

	if (L == L->next) {//头结点的指针域指向了自己，就是空的循环链表
		node->next = L;
		L->next = node;
	}else{//非空的循环链表
	last = L->next;
	while (last->next!=L) {
		last = last->next;//定位尾节点
	}
	//新的结点链接到最尾部
	node->next = L;
	last->next = node;
	}
	return true;

}

//打印循环链表
void LoopLinkPrint(LinkList* &L) {

	LinkList* p;
	if (!L || L->next == L) {
		cout << "链表为空！" << endl;
		return;
	}

	p = L->next;
	while (p != L) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
	return;
}


bool Joseph(LinkList* &L,int interval) {

	LinkNode *p=L,*q;
	int i = 0, j = 0, ans = 0,num;

	if (!L || p->next == L) {
		cout << "链表为空" << endl;
		return false;
	}

	if (interval < 1) {
		cout << "报数淘汰口令不能小于1" << endl;
		return false;
	}

	do {
		i += interval;

		//查找第i个结点，p指向该结点的上一个结点
		while (p->next) {
			if (p->next != L)j++;
			if (j >=i)break;
			p = p->next;

		}
		ans++;

		q = p->next;//临时保存被删结点的地址以备释放空间
		num = q->data;
		if (ans == 5)cout << "第五个出列的编号是：" << num << endl;
		printf("cur:%d   last:%d    next:%d\n", q->data, p->data, q->next->data);
		p->next = q->next;
		delete q;	//释放被删除结点的内存

		LoopLinkPrint(L);
	} while (L->next != L);//链表不为空继续报数
	cout << "最后一个出圈的编号是：" << num << endl;

	return true;
}



int main() {

	LinkList* L;
	LinkNode* s;

	//1.初始化一个空的循环链表
	if (InitLoopList(L)) {
		cout << "初始化一个循环链表成功！" << endl;
	}
	else {
		exit(-1);//结束程序
	}

	//2.创建循环链表（尾插法）
	cout << "尾插法创建循环链表，插入十个元素" << endl;
	for (int i = 1; i < 11; i++) {
		s = new LinkNode;
		s->data = i;
		s->next = NULL;

		if (LoopListInsertBack(L, s)) {
			cout << "插入成功！"<<" ";
		}
		else {
			cout << "插入失败!" << " ";
		}
	}
	cout << endl;

	LoopLinkPrint(L);


	//3.解答约瑟夫问题
	Joseph(L, 9);


	return 0;
}

总结