cleanCode(5)
程序员文章站
2022-03-15 19:33:13
...
N 个人围成一圈顺序编号,从 1 号开始按 1、2、 3 顺序报数,报 3 者退出圈外;
其余的人再从 1、2、 3 开始报数,报 3 的人再退出圈外,依次类推。
请按退出顺序输出每个退出人的原序号。
要求使用环形链表编程。
1.之前的第一版
#include <vector>
#include <cmath>
#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef struct LoopListNodes {
int data;
LoopListNodes* next;
}LNode;
class Solution {
private:
LNode *root;
int ListSize;
LNode* delPrePtr;
LNode* deletePtr;
public:
Solution(){}
Solution(int N):ListSize(N){}
~Solution(){}
void CreateList() {
initListRoot();
//这里上下两部分并不属于同一个逻辑层欸!
LNode* rear = root;
for (int i = 2; i <= ListSize; i++) {
rearInsert(rear, i);
}
rear = NULL;
}
void initListRoot() {
root = (LNode*)malloc(sizeof(LNode));
root->data = 1;
root->next = root;
}
void rearInsert(LNode* &rear,int x) {
LNode* newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = x;
//这里的划分函数有点太多余(创建+连接)在七行之内可以接受
connectToTail(newNode, rear);
}
void connectToTail(LNode* &newNode, LNode* &rear) {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
newNode = NULL;
}
void deleteOrder() {
delPrePtr = root;
while (!isEmpty())
{
findDeletPre();
cout << deletePtr->data << " ";
deleteNode();
delPrePtr = deletePtr->next;
}
}
void findDeletPre() {
for (int i = 0; i < 1; i++) {
delPrePtr = delPrePtr->next;
}
deletePtr = delPrePtr->next;
}
void deleteNode() {
delPrePtr->next = deletePtr->next;
ListSize--;
}
bool isEmpty() {
return ListSize == 0;
}
};
int main()
{
int N;
cin >> N;
Solution test(N);
test.CreateList();
test.deleteOrder();
system("pause");
return 0;
}
2.第二版,主要是改进了循环链表的指针只需要一个尾指针,相应的所有的子函数的传入参数将不超过1(一个输入或者没有输入的小函数)
#include <vector>
#include <cmath>
#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef struct LoopListNodes {
int data;
LoopListNodes* next;
}LNode;
class Solution {
private:
LNode *rear;
int ListSize;
LNode* delPrePtr;
LNode* deletePtr;
public:
Solution() {}
Solution(int N) :ListSize(N) {}
~Solution() {}
void CreateList() {//七行之内的小函数,可以通过分块表现逻辑层
rear = (LNode*)malloc(sizeof(LNode));
rear->data = 1;
rear->next = rear;
for (int i = 2; i <= ListSize; i++) {
rearInsert(i);
}
}
void rearInsert(int x) {//七行之内的小函数,可以通过分块表现逻辑层
LNode* newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = x;
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
newNode = NULL;
}
void deleteOrder() {
delPrePtr = rear->next;
while (!isEmpty())
{
findDeletPre();
cout << deletePtr->data << " ";
deleteNode();
delPrePtr = deletePtr->next;
}
}
void findDeletPre() {
for (int i = 0; i < 1; i++) {
delPrePtr = delPrePtr->next;
}
deletePtr = delPrePtr->next;
}
void deleteNode() {
delPrePtr->next = deletePtr->next;
ListSize--;
}
bool isEmpty() {
return ListSize == 0;
}
};
int main()
{
int N;
cin >> N;
Solution test(N);
test.CreateList();
test.deleteOrder();
system("pause");
return 0;
}
上一篇: 多态的详解