约瑟夫环的链表实现

た入场券 2022-05-28 11:48 132阅读 0赞

**这篇算是预告吧-------以后会陆续出数据结构的类实现代码和STL详细汇总。**

**所以，关注一下我是不错的嘻嘻：）**

\------------------------------------------------分界线-------------------------------------------------------------------------

**1.**刚开始做这道题我是把头节点一起连进环里的，后来发现有些情况会比较复杂一直if if的，所以**果断不连头节点**了。

**2.**单链表做的这道题，所以要删除一个节点，肯定是**在这个节点的前一个节点进行操作**，所以干脆就从前一节点为起点报数（举个栗子，按正常如果报到3，指向应该是那个要山粗（删除）的节点，但现在是指向它的前一个节点）。

**3.**还有就是什么时候停止报数，当然是剩下一个人啦~~,也就是**这个节点的Next指向它自己**（脑补贪吃蛇失败的画面）。

### 放题目： ###

## 题目描述 ##

**约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。**

**用循环链表实现约瑟夫环。**

## 输入 ##

**输入多组测试数据，每组测试数据格式如下：**

**人数n(>0) 开始位置k(>0) 报数m(>0)**

## 输出 ##

**对每组测试数据，输出出圈顺序。**

## 样例输入 ##

3 1 2

5 3 3

## 样例输出 ##

2 1 3

5 3 2 4 1

### 详细意淫下实现 ###

/*2018/4/4 by SZU_Crayon   */ 
    void TakingTurn(Node* StartNode,int CallNum)  //如果报3就删除，那么callnum=3，startNode是一开始从谁开始报数的那个节点的前一个，
                                                 //比如如果从1开始报数 ，那startNode就是编号1的前一个节点，画个图就知道1的前一个节点是最后一个人
    {
    	int Baoshu=0;   //定义一个报数量，每轮到一个人就加一
    	while(StartNode->Next!=StartNode)    //当圈里剩下一个人的时候肯定是它节点的Next指向它自己节点的地址，如果出现这种情况就不再报数了
    	{
    		Baoshu++;   //while里面就是报数的过程
    		Node* WillBe_Delete_Node=StartNode->Next;   /*记录下那个要被输出和删除的节点 WillBe_Delete_Node，因为为了便于删除，报数都是提前一个节点的，
    												  比如报3的那个节点得删除，其实报3的时候，StartNode处于被删除节点的前一个。所以真正要输出和删除的节点在StartNode后面 */ 
    		if(Baoshu==CallNum)   //报数报到了需要删除的情况 
    		{
    			cout<< WillBe_Delete_Node->Num<<endl;    //输出被踢出去的那个节点的数据 
    			StartNode->Next=WillBe_Delete_Node->Next;    //删除被踢出去的节点（也就是 StartNode这个节点连上被删除节点的下一节点，也就是 WillBe_Delete_Node->Next
    			delete WillBe_Delete_Node;   //释放空间 
    			Baoshu=0;    //报数量置0，因为每踢出去一个节点就继续从1开始报数了   
    		} 
    		else           //还没到要删除的时候，就轮到下一个人报数，就让节点后移就可以了 
    			StartNode=StartNode->Next;
    		/*一个注意的点，为什么执行删除操作后没有把节点后移？ 答：因为单链表的特殊性质（删除节点肯定是得从被删除节点的前一节点进行操作），
    		如果节点后移相当于没有提前一个节点报数*/ 
    	} 
    	/*剩下一个人了， 跳出了while循环，把剩下那一个人的数据输出就完成整个约瑟夫环*/
    	cout<<StartNode->Num<<endl; 
    }

### AC代码： ###

/*2018/3/7  by SZU_Crayon*/
    #include<iostream>
    using namespace std;
    struct Node {
    	int Num;
    	Node* Next;
    };
    Node* CreateList(Node* Head, int ListSize)
    {
    	Node* Tail = Head;
    	for (int i = 1; i <= ListSize; i++)
    	{
    		Node* NewNode = new Node;
    		NewNode->Num = i; NewNode->Next = NULL;
    		Tail->Next = NewNode;
    		Tail = NewNode;
    	}
    	Tail->Next = Head->Next;
    	return Tail;
    }
    Node* FindNode(Node* NewHead, int Index,int ListSize)   //查找开始报数的那个节点的前一个节点
    {
    	Node* TempIndex = NewHead;
    	int cnt = 0;
    	while (cnt<ListSize)
    	{
    		if (++cnt == Index)
    			return TempIndex;
    		TempIndex = TempIndex->Next;
    	}
    	return NULL;
    }
    void TakingTurn(Node* Start, int Turns)  
    {
    	int cnts = 0, i = 0;
    	while (Start != Start->Next)
    	{
    		cnts++;
    		Node* DeleteNode = Start->Next;
    		if (Turns == cnts)
    		{
    			if (++i == 1)            //控制输出格式而已，下面一样
    				cout << DeleteNode->Num;
    			else
    				cout << " " << DeleteNode->Num;
    			Start->Next = DeleteNode->Next;
    			delete DeleteNode;
    			cnts = 0;
    		}
    		else
    			Start = Start->Next;
    	}
    	if (++i == 1)
    		cout << Start->Num << endl;
    	else
    		cout << " " << Start->Num << endl;
    	delete Start;
    }
    /*void PrintList(Node* NewHead)    //Text outPut
    {
    	//Node* TempHead=NewHead;
    	while (NewHead->Next!=NewHead)
    	{
    		Node* TempDeleteNode = NewHead->Next;
    		cout << TempDeleteNode->Num << " ";
    		NewHead->Next = TempDeleteNode->Next;
    		delete TempDeleteNode;
    	}
    	cout << NewHead->Num << endl;
    	delete NewHead;
    }*/
    int main()
    {
    	int ListSize, Start, Turn;
    	
    	while (cin >> ListSize >> Start >> Turn)
    	{
    		Node* Head = new Node;
    		Head->Next = NULL;
    		Head=CreateList(Head, ListSize);
    		//PrintList(Head);     //测试环链表是否正确
    		TakingTurn(FindNode(Head, Start,ListSize), Turn);
    	}
    	return 0;
    }

### 完结BB： ###

用单链表做这道题的话会有点绕，因为一直得借用前一节点，如果有需要，麻烦点点评论，我会更博放双链表实现约瑟夫环的嘻嘻。

说好的渣得不缩进对齐呢？ 点点关注，我保证下次做个渣男~