赞
踩
题目有:
随机给定一个数作为起始循环次数n,循环n次后当前节点的人淘汰,然后以它的号码为下一次的循环性次数,循环往复,最终留下一个人为获胜者,求是第几号的人。
- node* create() { //首先暴力创建一个单项循环链表
- node* head = new node(1, 15);
- head->next = new node(2, 21);
- head->next->next = new node(3, 14);
- head->next->next->next = new node(4, 1);
- head->next->next->next->next = new node(5, 12);
- head->next->next->next->next->next = new node(6, 8);
- head->next->next->next->next->next->next = head;
- return head;
- }
创建结构体由三部分组成
- struct node { //结构体为如下 val是编号 ,secret是那个会被当做是循环次数的值
- int val;
- int secret;
- node* next;
- node(int n, int m) :secret(m), val(n), next(nullptr) {}
- };
开始进入方法体
- int* yuesefu(node* head) {
- const int count = 2;//以常数模拟, 初次给定的移动的次数
- int cur = count; //用来记录循环次数
- int* arr = new int[6]; //在堆中创建临时数组,c语言没有垃圾回收需要释放
- int i = 0; //i是arr用来记录被淘汰的人的编号的数组的下标
- node* temp = nullptr;
-
- //终止条件是当head的下一个是自己时,说明当前链表是一个只剩一个节点的单链表
- while (head->next != head) {
- while (cur != 0) {//循环cur次
- if (cur == 1)
- temp = head;//用temp指针记录到需要被删除的节点的前一个节点
- head = head->next;
- cur--;
- }
- cur = head->secret; //取出secret作为新一次循环的值
- arr[i++] = head->val; //把淘汰的值放到数组中
- cout << "被淘汰:" << head->val << endl;
- temp->next = temp->next->next; //关键点移除head指向的链表
- temp = temp->next;
- head = temp;
- }
- arr[i] = head->val;//获胜者记录在数组结尾
- return arr;
- }
约瑟夫环已问题解决
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。