/**
1、初始化
2、前插
3、后插
7、遍历


***///

//单项链表

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

using namespace std;

typedef int Elemdata;

typedef struct _LinkList {
	Elemdata data;
	_LinkList* next;

}List, Node;

//循环表初始化
bool initlist(List*& L) {

	L = new List;
	if (!L) return false;
	L->next = L;
	L->data = -1;//这里给头节点的data初始化为1但是我们
	//并不会用它来存数据，只是给它一个标志数据-1也，可以不初始化
	return true;
}

//循环链表前插法			
bool insert_front(List*& L, Node* node) {//为什么这里只用传一个一级指针，一级指针不是只是只能值得传入不能将值带出的吗

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

	node->next = L->next;
	L->next = node;

	return true;

}
//循环链表尾插法

bool insert_end(List*& L, Node* node) {

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

	//找到最后一个结点
	Node* last = L;

	while (last->next!=L) {
		last = last->next;

	}

	node->next = last->next;

	last->next = node;
	
	return true;

}

//解决约瑟问题
//循环从链表中踢出元素、
//这个程序的终止条件很关键，按照这个报数的规则所有的元素必须要被删除掉
//但是循环链表结束不能机械的设置为NULL,因为报数的时候肯定要循环往复进行
//但是删除元素的个数肯定是固定的元素的个数
void getJfo(List*& L, int interval) {
	//防御性编程，interval 是指间隔数，间隔肯定要大于1才能删除
	//L结点必须存在，并且它里面肯定要存元素否则没有元素可以删除
	if (interval < 1 || !L->next||!L) return;
	
	int order = 0;
	int times = 0;

	Node* q, * d;
	q = L;


	//计算链表中的元素个数
	Node* CountList = L;
	int num = 0;

	while (CountList ->next != L) {
		CountList = CountList->next;
		num++;

	}
//计算个数，就是我们需要删除元素的个数，当删除的个数为0自动结束程序
	while (num!=0) {
		num--;
	

		
		for (int i = 0; i < interval - 1; i++) {
			//找到要删除元素的前一个结点
			q = q->next;
			
			//q结点不断的指向下一个结点，因为我们设置的头节点并不储存数据
			//所以当到头节点，自动指向下一个结点不能让头结点参与报数
			if (q == L) {
				q = q->next;
			}

			times++;



			if (times == interval - 1) {

				//找到要删除的前一个结点
				d = q->next;

				
			
				if (d == L) {
				//头节点不参与报书，也不能删除头节点。当删除的结点是头节点	
				//自动指向下一个结点	
					d = q->next->next;
				}
				q->next = d->next;


				order++;
		cout << "第" << order << "个出圈的元素是:" << d->data << endl;
				
				//删除结点后自动清0，继续每interval踢出一个结点
				times = 0;
				delete d;


			}


		}

	}
	//结束之后我们让L结点恢复原位，仍然指向它自己，因为L结点自身不会被删除
	//它要像火车头一样继续驱动，而如果不设置为L->next=L;
	//明明没有元素，L->next已经delete掉了，但是L->next仍然会指向那个被	     
	//delete掉了的地址但是那个结点已经不存在了
	//再访问那个地址就会报错
	//所以要这么一行代码，否则这个L结点后面就不能用了
	L->next = L;

}

//遍历链表
void initPrint(List*& L) {

	if (!L)return;

	List* p = L->next;

	while (p) {


		printf("%d\t", p->data);
		p = p->next;
	}

	printf("\n");

}
int main() {

	List* L = NULL;

	if (initlist(L)) {

		printf("链表初始化成功!\n");
	}
	else {
		printf("链表初始化失败!\n");
	}

	//前面插入法
	printf("请输入5个插入的值:");
	for (int i = 0; i < 5; i++) {

		Node* node = new Node;

		//scanf("%d", &node->data);
		cin>>node->data;

		insert_front(L, node);

	}

	getJfo(L, 9);

	printf("请输入5个插入的值:");
	for (int i = 0; i < 5; i++) {

		Node* node = new Node;

		//scanf("%d", &node->data);
		cin >> node->data;

		insert_end(L, node);

	}

	getJfo(L, 9);


	system("pause");
	return 0;

}