在以下代码中执行删除操作时，我无法获得以下代码中返回的正确值。

Question

无法打印队列中已删除元素的正确值。 DeQueue() 用于删除元素。我对 QUEUE 使用了动态循环数组实现技术，即当 QUEUE 已满时内存加倍。删除过程中返回的第一个元素是正确的，但之后如果再次执行删除，则返回随机值。

#include <iostream>
#include <cstdlib>
#include <math.h>

using namespace std;

struct DynArrayQueue{
    int front, rear;
    int capacity;
    int* array;
};

void ResizeQueue(struct DynArrayQueue* Q);

struct DynArrayQueue* CreateDynQueue(){

    struct DynArrayQueue* Q = (struct DynArrayQueue* )malloc(sizeof(struct DynArrayQueue));

    if(!Q)
    {
        cout << "Memory Error in allocation!\n";
        return NULL;
    }

    Q->capacity = 1;
    Q->front = Q->rear = -1;
    Q->array = (int* )malloc(Q->capacity * sizeof(int));

    if(!Q->array)
     {
         cout << "Memory error in creating queue!\n";
         return NULL;
     }

    return Q;
}

int IsEmptyQueue(struct DynArrayQueue* Q){
    if(Q->front == -1){
        cout << "Queue is empty!\n";
        return 1;
    }
    else{
        cout << "Queue not empty\n";
        return 0;
    }
}

int IsFullQueue(struct DynArrayQueue* Q){
    if((((Q->rear)+1)%Q->capacity) == Q->front)
    {
        cout << "Queue is full!\n";
        return 1;
    }else{
        cout << "Queue not full!\n";
        return 0;
    }
}

void QueueSize(struct DynArrayQueue* Q){
    int s;
    s = (Q->capacity - Q->front + Q->rear + 1) % Q->capacity;
    cout << "Size of the queue is " << s;
    cout << "\n\n";
}

void EnQueue(struct DynArrayQueue* Q){
    int data;
    cout << "Enter the data to be inserted:\n";
    cin >> data;
    if(IsFullQueue(Q))
      {
          ResizeQueue(Q);
      }
    Q->rear = (Q->rear + 1)%Q->capacity;
    Q->array[Q->rear] = data;
    if(Q->front == -1)
    {
        Q->front = Q->rear;
    }
}

void ResizeQueue(struct DynArrayQueue* Q){
    int size = Q->capacity;
    Q->capacity = Q->capacity * 2;
    Q->array = (int* )realloc(Q->array, Q->capacity);
    if(!Q->array)
          cout << "Memory error!\n";
    if(Q->front > Q->rear)
    {
        for(int i = 0; i < Q->front; i++)
        {
            Q->array[i+size] = Q->array[i];
        }
        Q->rear = Q->rear + size;
    }
}

void DeQueue(struct DynArrayQueue* Q){    **this function does not work properly**
    int data = 0;
    if(IsEmptyQueue(Q))
    {
        cout << "Queue Underflow!\n";
        cout << "No element to delete!\n";
    }
    else{
        data = Q->array[Q->front];
        if(Q->front == Q->rear)
        {
            Q->front = Q->rear = -1;
        }
        else
        {
            Q->front = ((Q->front) + 1) % Q->capacity;
        }
    }
    cout << "Element deleted is " << data;
    cout << "\n";
}

void DeleteQueue(struct DynArrayQueue* Q){
    if(Q){
        if(Q->array)
        {
            free(Q->array);
        }
        free(Q);
    }
}

int main()
{
    int choice;
    struct DynArrayQueue* Q1;
    while(1)
    {
        cout << "1. Press to create a Queue:\n";
        cout << "2. Enter an element in the queue:\n";
        cout << "3. Delete an element from the queue:\n";
        cout << "4. Press to know the Queue size:\n";
        cout << "5. Press to know if Queue is full:\n";
        cout << "6. Press to know if Queue is empty:\n";
        cout << "7. Press enter to exit:\n";
        cout << "Enter your choice:\n";
        cin >> choice;
        switch(choice)
        {
        case 1:
            Q1 = CreateDynQueue();
            break;
        case 2:
            EnQueue(Q1);
            break;
        case 3:
            DeQueue(Q1);
            break;
        case 4:
            QueueSize(Q1);
            break;
        case 5:
            IsFullQueue(Q1);
            break;
        case 6:
            IsEmptyQueue(Q1);
            break;
        case 7:
            exit(0);
            break;
        default:
            cout << "Wrong choice entered!\n";
            break;
        }
    }
    DeleteQueue(Q1);
}

Answer 1

问题不在 DeleteQueue，而是在 ResizeQueue。当您调用 realloc 时，您传递的是新的元素数量，但没有考虑元素的大小（就像您最初分配 space 时一样）。应该是

Q->array = (int* )realloc(Q->array, Q->capacity * sizeof(int));

Answer 2

问题出在ResizeQueue()。

声明

Q->array = (int* )realloc(Q->array, Q->capacity);

没有分配正确的尺寸。随后的操作（直到下一个DeleteQueue()）然后愉快地假设数组比它更长，并写到最后。

此外，如果 realloc() 失败 returns NULL 并且不会释放旧内存。此分配的结果是内存泄漏（因为 Q->array 的旧值丢失到您的程序中）。

您实际需要做的（至少）是

int *temp = (int* )realloc(Q->array, Q->capacity * sizeof(int));
if (!temp)
    cout << "Memory error!\n";
else
    Q->array = temp;

即使这样还不够，因为后续代码使用 Q->array 并假定调整大小成功。如果发生故障，结果是未定义的行为。我会把解决这个问题作为一个学习练习。

此外，在 C++ 中，考虑使用标准容器（如 std::vector<int>），它们可以以受控方式调整自身大小 - 这样您就可以避免分配错误数量的内存等愚蠢行为。

在以下代码中执行删除操作时，我无法获得以下代码中返回的正确值。

While performing the delete operation in the following code, I am not able to get the correct values returned in the following code.

c++

algorithm

queue

dynamic-memory-allocation

data-structures