循环链表的算法实现

有 10 个小朋友按编号顺序 1，2，。。。，10 顺时针方向围成一圈。从 1 号开 始顺时针方向 1，2，。。。，9 报数，凡报数 9 者出列（显然，第一个出圈为 编号 9 者）。 最后一个出圈者的编号是多少？第 5 个出圈者的编号是多少？

main.cpp

#include <iostream>
#include <Windows.h>

using namespace std;

//定义一个循环链表
typedef struct LinkNode {
	int data;			//链表节点的数据域
	LinkNode *next;		//链表节点的指针域
} LinkNode,		//链表节点的指针域
LinkList;		//链表头节点, 指向LinkNode节点

//初始化循环链表
bool List_Init(LinkList *&list) {		//构造一个空的循环链表list
	list = new LinkList;	//生成新的节点作为头节点,用头指针指向节点
	if (!list) return false;	//生成节点失败
	list->next = list;	//list下一个节点指向自己
	list->data = -1;		
	return true;
}

//尾部插入元素
bool List_Add_Back(LinkList *&list, LinkNode *node) {
	LinkNode *last = NULL;		//最后一个节点
	if (!list || !node) return false;

	if (list == list->next) {	//头节点的指针域指向自己, 就是空的循环链表
		node->next = list;		//新插入的元素指向头节点
		list->next = node;		//头节点指向新的节点
	} else {
		last = list->next;		//指向第一个元素
		while (last->next != list) {	//没有指向头节点
			last = last->next;			//指向下一个节点
		}
		node->next = list;		//新插入的元素指向头节点
		last->next = node;		//原来尾部节点指向新的节点
	}
	return true;
}

//输出循环链表
void Link_Print(LinkList *&list) {
	LinkList *p;
	if (!list) {
		cout << "链表为空!" << endl;
		return;
	}
	p = list->next;
	while (p != list) {
		cout << p->data << "\t";
		p = p->next;
	}
	cout << endl;
}

//interval: 表示每次间隔的元素
bool Joseph(LinkList *&list, int interval) {
	LinkList *p = NULL;	//赋值为头节点, 指向节点
	LinkList *q = NULL;	
	int i = 0;	//报数的元素
	int j = 0;	//报数的次数
	int num = 0;	//每一次出圈编号
	int times = 0;	//当前执行了多少次出圈
	p = list;		//p = 头结点

	if (!list || p->next == list) return false;	//最后一个元素的指向头节点
	if (interval < 1) return false;

	do {
		i += interval;	//第一次i=9, 第二次i=18.....

		//查找第i个节点, p指向第i个节点的上一个节点
		while (p->next) {
			if (p->next != list) j++;	//报了一个数
			if (j >= i) break;
			p = p->next;
		}
		times++;	
		q = p->next;	//临时保存被删节点的地址以备释放空间
		num = q->data;
		if (times == 5) { cout << "第5个出圈的编号是: " << num << endl; }
		p->next = q->next; //改变删除结点前驱结点的指针域 
		delete q; //释放被删除结点的空间 
		Link_Print(list);
	} while (list->next == list);	//头节点的下一个指向头节点本身,只剩下头节点

	cout << "最后一个出圈的编号是：" << num << endl; 
	return true;
}

int main(void) {
	LinkList *list = NULL;
	LinkNode *node = NULL;

	// 1.初始化循环链表
	if (List_Init(list)) {
		cout << "初始化一个空的循环链表成功" << endl;
	} else {
		exit(-1);
	}

	// 2.在循环链表尾部插入元素
	int n = 0, i = 0;
	cout << "尾插法插入元素" << endl;
	cout << "请输入插入数量:";
	cin >> n;

	while ((++i) <= n) {
		node = new LinkNode;
		node->data = i;
		node->next = NULL;
	}

	for (int i = 0; i < n; i++) {
		node = new LinkNode;
		if (!node) {
			cout << "新节点生成失败!" << endl;
			return false;
		}
		node->data = i + 1;
		List_Add_Back(list, node);	//尾插法
	}

	// 3.输出链表元素值
	Link_Print(list);
	
	Joseph(list, 9);
	system("pause");
	return 0;
}