使用双向链表解决约瑟夫环问题

问题描述：

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

源码：

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

struct Node {		//结点
	int data;		//数据
	Node* pred;		//前驱
	Node* succ;		//后继
	
};

Node* rear;			//头指针
Node* head;			//尾指针

int count = 0;		//累计器

void InitLinkedList(int);	//初始化链表

void DeleteNode(Node*);		//删除链表的某个节点

int main() {
	cout << "请输入总人数n，开始计数的人k(1为起点)，被杀掉的次序m：";
	int n, k, m;
	cin >> n >> k >> m;
	if (n <= k || n <= m) abort();
	cout << "被杀的次序为：";
	InitLinkedList(n);
	Node* ptr = head;
	while (--k)
		ptr = ptr->succ;
	while (count) {
		int i = m;
		while (--i)
			ptr = ptr->succ;
		cout << ptr->data << ' ';
		Node* tmp = ptr;
		ptr = ptr->succ;
		DeleteNode(tmp);
	}
}

void InitLinkedList(int n) {
	if (n <= 0) return;			//如果为0，直接返回
	head = new Node;			//分配第一个结点
	head->succ = head;			//前驱为本身
	head->pred = head;			//后继为本身
	head->data = 1;				//编号为1
	rear = head;				//尾指针指向这个节点
	count++;					//累加器+1
	for (int i = 2; i <= n; i++) {	//循环
		Node* ptr = new Node;		//分配第i个结点
		ptr->data = i;				//编号为i
		ptr->succ = rear->succ;		//新分配结点的后继为原来尾的后继
		ptr->pred = rear;			//前驱为原来的尾
		rear->succ = ptr;			//尾的后继为新分配结点
		ptr->succ->pred = ptr;		//新分配结点的后继的前驱为新分配结点
		rear = ptr;					//尾指针后移
		count++;					//累加器+1
	}
}

void DeleteNode(Node* p) {
	if (p == head) {				//如果删除的为头节点
		head = head->succ;			//绕过头节点
		rear->succ = head;			//尾的后继为新头
		head->pred = rear;			//新头的前驱为尾
		delete p;					//释放原来的空间
		count--;					//累加器-1
	}
	else if (p == rear) {			//同理
		rear = rear->pred;
		rear->succ = head;
		head->pred = rear;
		delete p;
		count--;
	}
	else {
		p->pred->succ = p->succ;	//同理
		p->succ->pred = p->pred;
		delete p;
		count--;
	}
}