用循环队列实现约瑟夫序列，出现的约瑟夫序列超出我输入的队列

Question

我的约瑟夫代码有问题，可能free()空间，没有释放掉，导致队列序号重复出现

/*********************************************************************
    程序名:
    版权:
    作者:
    日期: 2024-04-14 10:05
    说明:
*********************************************************************/
#include <iostream>
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
using namespace std;

typedef struct node {
    ElemType no;            //存放编号
    struct node *next;
} QNode;

//typedef struct {
//    QNode *front;
//    QNode *rear;
//} LQueue;

void InitQueue(QNode *&lq) {
    lq = NULL;
}

void DestroyQueue(QNode *&lq) {
    QNode *pre, *p;
    if (lq != NULL) {
        if (lq->next == lq)
            free(lq);
        else {
            pre = lq;
            p = pre->next;
            while (p != lq) {
                free(pre);
                pre = p;
                p = p->next;
            }
            free(pre);
        }
    }
}

void EnQueue(QNode *&lq, ElemType x) {
    QNode *s;
    s = (QNode *)malloc(sizeof(QNode));
    s->no = x;
    if (lq == NULL) {
        lq = s;
        lq->next = lq;
    } else {
        s->next = lq->next;
        lq->next = s;
        lq = s;
    }
}

int DeQueue(QNode *&lq, ElemType &x) {
    QNode *s;
    if (lq == NULL)
        return 0;
    if (lq->next == lq) {
        x = lq->no;
        free(lq);
        lq = NULL;
    } else {
        s = lq->next;
        x = s->no;
        lq->next = s->next;
        free(s);
    }
    return 1;
}

int GetHead(QNode *lq, ElemType &x) {
    if (lq == NULL)
        return 0;
    x = lq->next->no;
    return 1;
}

int QueueEmpty(QNode *lq) {
    if (lq == NULL)
        return 1;
    else
        return 0;
}

void Joseph(int &n, int &m, QNode *&lq) {
    int i, j;
    QNode *p, *q;
    for (i = 1; i <= n; i++) {
        p = lq;
        j = 1;
        while (j < m ) {
            j++;
            p = p->next;
        }
        q = p->next;
        printf("%d", q->no);
        p->next = q->next;
        DeQueue(lq, q->no);
        lq = p->next;

    }
}


int main() {
    QNode *q, *p, *lq;
    ElemType tem[20];
    InitQueue(lq);
    int n, i, j, m;
    printf("队列长度：");
    scanf("%d", &n);
    printf("队列序号：");
    for (i = 0; i < n; i++)
        scanf("%d", &tem[i]);
    printf("\n");
    printf("出队序号：");
    scanf("%d", &m);
    printf("\n");
    for (i = 0; i <= n; i++) {
        EnQueue(lq, tem[i]);
    }
    printf("n=%d,m=%d的约瑟夫序列：", n, m);
    Joseph(n, m, lq);
}

运行结果

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

问题分析：

1. 你提到可能是由于没有正确释放内存空间导致的问题。在分析代码中，发现确实存在一些内存泄漏的情况，即在队列中的节点释放时可能存在问题。
2. 另外，程序中存在一些逻辑错误，例如在循环队列中处理出队操作时的错误，以及在循环约瑟夫序列中的循环条件错误。
3. 在 main() 函数中，存在对于队列长度的输入上的问题，循环应该是小于n而不是小于等于n。
   解决方案：
4. 修正内存泄漏问题：在 DestroyQueue() 函数中，需要确保每个节点都正确释放，包括队列的头节点。修改释放节点的代码，确保释放节点的操作正确执行。
5. 修改出队操作：循环队列的出队操作需要进行头节点的移动，并且需要考虑循环条件，以确保出队后正确的队列顺序。
6. 修正循环约瑟夫序列中的逻辑错误：在循环约瑟夫序列中，需要考虑循环结束的条件以及循环体内的逻辑是否正确，确保每一步操作都符合约瑟夫问题的要求。
7. 在 main() 函数中，修改循环条件，确保队列长度的输入正确。
8. 检查代码中的输入输出操作，确保用户输入的队列数据正确读取和处理。
   代码修改建议：
   cppCopy code

   #include <iostream>
   #include <stdio.h>
   #include <malloc.h>
   typedef int ElemType;
   typedef struct node {
   ElemType no;            // 存放编号
   struct node *next;
   } QNode;
   void InitQueue(QNode *&lq) {
   lq = NULL;
   }
   void DestroyQueue(QNode *&lq) {
   QNode *pre, *p;
   if (lq != NULL) {
   pre = lq;
   p = pre->next;
   while (p != lq) {
   free(pre);
   pre = p;
   p = p->next;
   }
   free(pre); // 释放队列头节点
   }
   lq = NULL;
   }
   void EnQueue(QNode *&lq, ElemType x) {
   QNode *s;
   s = (QNode *)malloc(sizeof(QNode));
   s->no = x;
   if (lq == NULL) {
   lq = s;
   lq->next = lq;
   } else {
   s->next = lq->next;
   lq->next = s;
   lq = s;
   }
   }
   int DeQueue(QNode *&lq, ElemType &x) {
   QNode *s;
   if (lq == NULL) return 0;
   if (lq->next == lq) {
   x = lq->no;
   free(lq);
   lq = NULL;
   } else {
   s = lq->next;
   x = s->no;
   lq->next = s->next;
   free(s);
   }
   return 1;
   }
   int GetHead(QNode *lq, ElemType &x) {
   if (lq == NULL) return 0;
   x = lq->next->no;
   return 1;
   }
   int QueueEmpty(QNode *lq) {
   if (lq == NULL) return 1;
   else return 0;
   }
   void Joseph(int n, int m, QNode *&lq) {
   int i, j;
   QNode *p, *q;
   while (n > 0) { // 循环直到所有元素出队
   p = lq;
   for (j = 1; j < m; j++) {
   p = p->next;
   }
   q = p->next;
   printf("%d ", q->no); // 输出出队元素
   p->next = q->next;
   if (q == lq) lq = p->next; // 如果出队元素是队尾，则更新队尾指针
   free(q);
   n--; // 队列长度减一
   }
   }
   int main() {
   QNode *lq;
   InitQueue(lq);
   int n, i, m;
   printf("队列长度：");
   scanf("%d", &n);
   printf("队列序号：");
   for (i = 0; i < n; i++) {
   ElemType temp;
   scanf("%d", &temp);
   EnQueue(lq, temp);
   }
   printf("出队序号：");
   scanf("%d", &m);
   printf("\n");
   printf("n=%d, m=%d的约瑟夫序列：", n, m);
   Joseph(n, m, lq);
   DestroyQueue(lq); // 释放队列
   return 0;
   }
   

   这样修改后，应该能正确处理循环队列的操作，解决内存泄漏问题，并且输出正确的约瑟夫序列。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑