数据结构之链表——加里森的任务（循环链表）

题目：加里森的任务

有n个加里森敢死队的队员要炸掉敌人的一个军火库，谁都不想去，队长加里森决定用轮回数数的办法来决定哪个战士去执行任务。规则如下：如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个编号为x的战士开始计数，当数到y时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第y时，此战士接着去执行任务。以此类推，直到任务完成为止。 加里森本人是不愿意去的，假设加里森为1号，请你设计一程序为加里森支招，求出n,x,y满足何种条件时,加里森能留到最后而不用去执行任务;。 要求： 主要数据结构采用链式结构存储。 自拟1个实验实例验证程序正确性（即：n,x,y自拟）。

循环链表的运用，最常见的一种，时间复杂度是O(n^3).

//#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct node{			//加里森队员链表结构
	int data;
	struct node* next;
}Linknode, *Link;

Link ListCreate(int n){
	Link head = NULL, curr = NULL, last = NULL;
	while (n){					//对n个成员进行创建链表并编号
		head = (Link)calloc(1, sizeof(Linknode));
		if (NULL == head)
			cout << "Error in calloc." << endl;
		head->data = n;
		head->next = curr;
		curr = head;
		if (NULL == last){//保存最后一个节点的地址
			last = head;
		}
		n--;
	}
	last->next = head;//进行首尾链接
	return head;
}

Link ListDel(Link prev){
	if (NULL == prev->next){//一种情况执行完毕，进行最后的节点空间释放。
		free(prev);
		return NULL;
	}
	Link curr = prev->next;
	prev->next = curr->next;
	free(curr);
	return prev;
}

Link Josephus(Link head, int x, int y){
	Link prev = NULL;
	while (head->next->data != x)//进行遍历，直到指针的下一个节点的编号为x
		head = head->next;
	while (head != head->next){//循环直到只剩下一个节点
		for (int i = 0; i < y; i++){
			prev = head;
			head = head->next;
		}
		head = ListDel(prev);
	}
	head->next = NULL;//将无限循环单节点链表断开
	return head;
}

void ListPrintSol(Link head,int n, int i, int j){
	if (1 == head->data){
		cout << "The solution of " << n << " is: from " << i << " by " << j << endl;
		//cout << "The last of the list is: " << head->data << endl;
	}
}

int main(){
	int n;
	//FILE *stream;
	//freopen_s(&stream,"op.txt", "w", stdout);
	Link head = NULL;
	cout << "Please input the number of members n:";
	cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			head = ListCreate(n);//创建链表
			head = Josephus(head,i,j );//调用约瑟夫函数进行编号计数抽选，派遣队员，直到最后一人
			ListPrintSol(head,n,i,j);//输出使加里森成为最后一人的x,y
			head = ListDel(head);//释放空间
		}
	}
	return 0;
}