约瑟夫环 - 找神奇数字
本帖最后由 UNKNOWN404 于 2024-11-2 15:04 编辑大家好，
我最近在练习一个算法，通过双向环链表狀问题来找出一个神奇数字，移除全部'X'、只保留'O'。我已经完成了部分代码，但遇到了一些困难，希望得到大家的帮助。
由'O'和'X'组成的字符串，需要通过一个双向链表来模拟这个过程。算法需要从顺时针开始数，遇到第一个'X'时删除它并转换方向，然后重复这个过程。
我已经有了基本的节点定义和链表创建函数，但是不确定如何实现寻找神奇数字的函数。以下是我目前的代码框架：
范例：
输入：OXOXOXX
输出：神奇数字为 7
/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 1000
/* 定义节点 */
typedef struct Node {
char data; // 纪录 'O'和'X'
struct Node *next; // 指向下一个节点的指针
struct Node *prev; // 指向前一个节点的指针
} Node;
/* 建立一个新节点的函式 */
Node *createNode(char data) {
// 使用 malloc 分配内存给新节点
Node *newNode = (Node*)malloc(sizeof(Node));
// 检查内存是否成功分配
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);// 如果失败，退出执行
}
// 初始化新节点的资料和指针
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;// 返回新创建的节点
}
/* 建立双向环状链节串行的函式 */
Node *createCircularList(char *str) {
int i = 0;
int len = strlen(str);// 获取字符串长度
if (len == 0) return NULL;// 如果字符串为空，返回 NULL
Node* head = createNode(str);// 建立头节点
Node* current = head;
// 为字符串中的每个字符创建一个节点并连接
for (i = 1; i < len; i++) {
Node* newNode = createNode(str);
current->next = newNode;
newNode->prev = current;
current = newNode;
}
// 将最后一个节点和第一个节点连接，形成双向环状结构
current->next = head;
head->prev = current;
return head;// 返回头节点
}
/* 计算环状链节串行中节点数量的函式 */
int countNodes(Node *head) {
if (head == NULL) return 0;// 如果链节串行为空，返回 0
int count = 1;// 从 1 开始计数（头节点）
Node *current = head->next;// 从第二个节点开始
// 遍历链表直到回到头节点
while (current != head) {
count++;
current = current->next;
}
return count;// 返回节点总数
}
/* 打印双向环状链节串行的函式 */
void printList(Node* head) {
if (head == NULL) {
printf("链节串行为空\n");
return;
}
Node *current = head;
do {
printf("%c ", current->data);// 打印当前节点的数据
current = current->next; // 移动到下一个节点
} while (current != head);// 当回到头节点时停止
printf("\n");
}
/* 从双向环状链节串行中移除指定节点的函式 */
Node *removeNode(Node* head, Node* nodeToRemove) {
if (head == NULL || nodeToRemove == NULL) {
printf("错误：removeNode 函数收到空指针\n");
return head;
}
// 如果要移除的是头节点
if (head == nodeToRemove) {
if (head->next == head) {
// 如果链节串行中只有一个节点
free(head);
return NULL;
}
// 更新头节点
Node *newHead = head->next;
newHead->prev = head->prev;
head->prev->next = newHead;
free(head);
return newHead;
}
// 移除中间的节点
nodeToRemove->prev->next = nodeToRemove->next;
nodeToRemove->next->prev = nodeToRemove->prev;
free(nodeToRemove);
return head;
}
/* 释放双向环状链节串行内存的函式 */
void freeList(Node *head) {
if (head == NULL) return;
Node* current = head->next;
Node* temp;
// 释放除了头节点外的所有节点
while (current != head) {
temp = current;
current = current->next;
free(temp);
}
// 释放头节点
free(head);
}
/* 修改后的查找神奇数字的函式 */
int findMagicNumber(Node **head, char *originalStr) {
int i = 0;
int magicNumber = 1;// 从 1 开始尝试
int isClockwise = 1;// 1 表示顺时针，0 表示逆时针
Node *current = *head;
int remainingX = 0;// 记录剩余的 'X' 数量
// 计算初始 'X' 的数量
Node *temp = *head;
do {
if (temp->data == 'X') remainingX++;
temp = temp->next;
} while (temp != *head);
// 主循环：持续直到所有 'X' 被移除
while (remainingX > 0) {
printf("当前链表: ");
printList(*head);
printf("尝试神奇数字: %d (方向: %s)\n",
magicNumber,
isClockwise ? "顺时针" : "逆时针");
// 移动到第 magicNumber 个节点
for (i = 1; i < magicNumber; i++) {
if (isClockwise) {
current = current->next;
} else {
current = current->prev;
}
}
// 如果当前节点是 'X'，移除它并切换方向
if (current->data == 'X') {
printf("移除节点: %c\n", current->data);
Node *nodeToRemove = current;
current = isClockwise ? current->next : current->prev;
*head = removeNode(*head, nodeToRemove);
remainingX--;
if (*head == NULL) {
printf("错误：链节串行为空\n");
return -1;
}
// 切换方向
isClockwise = !isClockwise;
printf("切换方向为: %s\n", isClockwise ? "顺时针\n" : "逆时针\n");
} else {
// 如果是 'O'，重建链表并重置方向为顺时针
printf("遇到 'O'，重建链表\n\n");
freeList(*head);
*head = createCircularList(originalStr);
current = *head;
isClockwise = 1;// 重置为顺时针
magicNumber++; // 增加神奇数字
}
}
return magicNumber;// 返回找到的神奇数字
}
/* 修改主函数以传递原始字符串 */
int main() {
// 步骤 1: 打开输入文件
FILE *file = fopen("input.txt", "r");
if (file == NULL) {
printf("无法打开 input.txt 文件\n");
return 1;
}
// 步骤 2: 读取输入字符串
char str;
if (fgets(str, MAX_LENGTH, file) == NULL) {
printf("无法从 input.txt 读取数据\n");
fclose(file);
return 1;
}
fclose(file);
// 步骤 3: 移除字符串末尾的换行符（如果存在）
str = 0;
printf("输入: %s\n", str);
// 步骤 4: 创建双向环状链节串行
Node* head = createCircularList(str);
if (head == NULL) {
printf("创建环状链表失败\n");
return 1;
}
// 步骤 5: 查找神奇数字，传入原始字符串用于重建
int magicNumber = findMagicNumber(&head, str);
// 步骤 6: 输出结果
if (magicNumber != -1) {
printf("神奇数字为 %d\n", magicNumber);
} else {
printf("未能找到神奇数字\n");
}
// 步骤 7: 释放剩余节点的内存
freeList(head);
return 0;
}
你在实现约瑟夫环问题时遇到了一些困难。根据你的描述和代码框架，我注意到了一些需要修正的地方。以下是一些建议和修改：
1. **字符串读取和处理**：
- 你在读取字符串时使用了`char str;`，这应该是一个字符数组而不是单个字符。
- 使用`fgets`读取字符串时，确保字符串数组的大小足够大。
2. **创建链表**：
- 在`createCircularList`函数中，`createNode(str)`应该是`createNode(str)`，因为你需要为每个字符创建节点。
3. **查找神奇数字的逻辑**：
- 在`findMagicNumber`函数中，确保在每次重建链表时正确地重置`current`指针。
- 确保在移除节点后，`current`指针指向下一个有效节点。
4. **文件读取和字符串处理**：
- 确保在读取字符串后移除换行符。
- 使用`str[strcspn(str, "
")] = 0;`来移除换行符。
以下是一些修改后的代码片段：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 1000
typedef struct Node {
char data;
struct Node *next;
struct Node *prev;
} Node;
Node *createNode(char data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败
");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
Node *createCircularList(char *str) {
int len = strlen(str);
if (len == 0) return NULL;
Node* head = createNode(str);
Node* current = head;
for (int i = 1; i < len; i++) {
Node* newNode = createNode(str);
current->next = newNode;
newNode->prev = current;
current = newNode;
}
current->next = head;
head->prev = current;
return head;
}
int findMagicNumber(Node **head, char *originalStr) {
int magicNumber = 1;
int isClockwise = 1;
Node *current = *head;
int remainingX = 0;
Node *temp = *head;
do {
if (temp->data == 'X') remainingX++;
temp = temp->next;
} while (temp != *head);
while (remainingX > 0) {
for (int i = 1; i < magicNumber; i++) {
current = isClockwise ? current->next : current->prev;
}
if (current->data == 'X') {
Node *nodeToRemove = current;
current = isClockwise ? current->next : current->prev;
*head = removeNode(*head, nodeToRemove);
remainingX--;
isClockwise = !isClockwise;
} else {
freeList(*head);
*head = createCircularList(originalStr);
current = *head;
isClockwise = 1;
magicNumber++;
}
}
return magicNumber;
}
int main() {
FILE *file = fopen("input.txt", "r");
if (file == NULL) {
printf("无法打开 input.txt 文件
");
return 1;
}
char str;
if (fgets(str, MAX_LENGTH, file) == NULL) {
printf("无法从 input.txt 读取数据
");
fclose(file);
return 1;
}
fclose(file);
str[strcspn(str, "
")] = 0;
printf("输入: %s
", str);
Node* head = createCircularList(str);
if (head == NULL) {
printf("创建环状链表失败
");
return 1;
}
int magicNumber = findMagicNumber(&head, str);
if (magicNumber != -1) {
printf("神奇数字为 %d
", magicNumber);
} else {
printf("未能找到神奇数字
");
}
freeList(head);
return 0;
}
希望这些建议和修改能帮助你解决问题！如果有其他问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 双向遍历节点，遇到 X 就删除节点，这和约瑟夫环有什么关系，神奇的数字和残存节点又是什关系，你这不止1个“O”，是都留下还是只留1个？
页:
[1]