|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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[0]); // 建立头节点
- Node* current = head;
- // 为字符串中的每个字符创建一个节点并连接
- for (i = 1; i < len; i++) {
- Node* newNode = createNode(str[i]);
- 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[MAX_LENGTH];
- if (fgets(str, MAX_LENGTH, file) == NULL) {
- printf("无法从 input.txt 读取数据\n");
- fclose(file);
- return 1;
- }
- fclose(file);
- // 步骤 3: 移除字符串末尾的换行符（如果存在）
- str[strcspn(str, "\n")] = 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[i])`，因为你需要为每个字符创建节点。
3. **查找神奇数字的逻辑**：
- 在`findMagicNumber`函数中，确保在每次重建链表时正确地重置`current`指针。
- 确保在移除节点后，`current`指针指向下一个有效节点。
4. **文件读取和字符串处理**：
- 确保在读取字符串后移除换行符。
- 使用`str[strcspn(str, "
")] = 0;`来移除换行符。
以下是一些修改后的代码片段：
希望这些建议和修改能帮助你解决问题！如果有其他问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-11-2 11:55:10
置顶卡
千斤顶
显身卡
发表于 2024-11-2 11:55:30
