C:超出队列和内存限制

Question

我是 C初学者，决定参加一个小型在线比赛以练习。

在当前问题中，我被要求编写一个带有 struct 的队列响应命令 PushBack和 PopFront .

输入包括

• 一个号码 n ( n <= 1000000 ) 表示命令输入的数量。
• n线。每行由两个整数组成 a和 b :
  • a是2用于执行 PopFront , 在这种情况下 b是预期的弹出值。
  • a是3对于 PushBack , 在这种情况下 b是要排队的值。

如果我们尝试从空队列中弹出，则返回值为 -1 .

任务是打印YES或 NO执行最后一条命令后，如果任何 PushBack 返回的值程序执行过程中是否与期望值一致。

我实现了这个版本，但在提交我的答案后，在线法官给出了 Maximum-Limit-Excedeed (在 27 的最后一个测试中)。

我正在阅读它，这个问题可能与其中一些有关:

1. 使用太大的数组或数据结构。
2. 程序中存在无限(或太大)递归。
3. 指针使用不当(诊断为 MLE)。

我不确定是什么问题。在我看来，在某些测试中，添加节点的数量远远大于删除节点的数量(这意味着 1. 发生在我的代码中)，这反过来导致 while循环 EmptyQueue太大( 2. 也会发生)。我无法发现指针的使用是否有误。

我的问题是:

• 我做错了什么？
• 我应该怎么做才能解决这个问题？

代码:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//===================
//Definitions:

typedef int Item;

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct queue
{
    Node * front;
    Node * rear;
    long counter;
} Queue;

//===================
//Function Prototypes:

void InitializeQueue(Queue * pq);
bool PushBack(Queue * pq, Item item);
int PopFront(Queue * pq);
void EmptyQueue(Queue * pq);


int main(void)
{
    Queue line;
    long n, i;
    int command, expected, received;
    bool check = true;

    scanf("%ld", &n);

    InitializeQueue(&line);

    i = 0;
    while (i < n)
    {
        scanf("%d %d", &command, &expected);

        switch (command)
        {
            case 2:
                received = PopFront(&line);
                if (received != expected)
                    check = false;
                break;
            case 3:
                PushBack(&line, expected);
                break;

        }
        i++;
    }

    if (check == true)
        printf("YES\n");
    else
        printf("NO\n");

    // free memory used by all nodes
    EmptyQueue(&line);

    return 0;

}




void InitializeQueue(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
    pq->counter = 0;
}

bool PushBack(Queue * pq, Item item)
{
    Node * pnode;

    //Create node
    pnode = (Node *)malloc(sizeof(Node));

    if (pnode == NULL)
    {
        fputs("Impossible to allocate memory", stderr);
        return false;
    }
    else
    {
        pnode->item = item;
        pnode->next = NULL;
    }

    //Connect to Queue
    if (pq->front == NULL)
    {
        pq->front = pnode;
        pq->rear = pnode;
    }
    else
    {
        pq->rear->next = pnode;
        pq->rear = pnode;
    }

    pq->counter++;

    return true;
}


int PopFront(Queue * pq)
{
    int popped;
    Node * temp;

    temp = pq->front;

    if (pq->counter == 0)
        return -1;
    else
    {
        popped = pq->front->item;
        pq->front = pq->front->next;
        free(temp);
        pq->counter--;
        return popped;
    }
}




void EmptyQueue(Queue * pq)
{
    int dummy;

    while (pq->counter != 0)
        dummy = PopFront(pq);
}

谢谢。

Answer 1

我认为该代码在功能上实际上没有任何问题，尽管它可以通过一些格式改进来实现:-)

我会提一件事:

The task is to check whether the returned value after executing PopFront coincides with the expected one. If so, then print YES. Print NO, otherwise.

我会将此解读为对 each PopFront 的要求。您似乎正在存储故障情况，最后只打印 YES 或 NO 一次。

我建议先解决这个问题，然后看看在线评委会返回什么。

---

这一切都忽略了一个事实，即调试代码实际上相当困难，除非您可以重现问题。如果您无法从在线竞赛中获取数据集，则可能值得生成您自己的(大型)数据集，看看是否可以让您的代码失败。

一旦遇到可重复的故障，调试就会变得非常容易。

---

虽然这不太可能，但您可能(如 mch 在评论中指出的那样)与有限的内存发生冲突。我认为这不太可能，因为您自己的评论表明最后只使用了 5 兆的空间，这并不繁重。但是，如果是这种情况，可能是因为每个整数都带有指针的开销。

如果你想调查那个途径，你可以稍微调整结构如下(去掉不必要的counter):

#define ITEMS_PER_NODE 1000

typedef struct node {
    Item item[ITEMS_PER_NODE];  // array of items.
    int startIndex;             // start index (one to pop from).
    int nextIndex;              // next index (one to push at).
    struct node *next;          // next node.
} Node;

typedef struct queue {
    Node *front;                // first multi-item node.
    Node *rear;                 // last multi-item node.
} Queue;

想法是在每个节点存储许多项，这样next指针的开销就大大减少了(每千项一个指针而不是每件一件)。

队列操作的代码会变得稍微复杂一些，但仍然可以理解。首先，一个用于创建新节点的辅助函数，准备好将数据添加到:

// Helper to allocate a new node and prep it for appending.
// Returns node or NULL (and prints error) if out of memory.

Node *GetNewNode(void) {
    Node *pnode = malloc (sizeof(Node));
    if (pnode == NULL)
        fputs ("Impossible to allocate memory", stderr);
    else
        pnode->startIndex = pnode->nextIndex = 0;
    return pnode;
}

接下来，基本不变的队列初始化:

void InitializeQueue (Queue *pq) {
    pq->front = pq->rear = NULL;
}

pushback 稍微复杂一些，如果队列为空或当前最后一个节点已到达末尾，它首先添加一个新的多项目节点。无论发生与否，都会将一个项目添加到最终节点:

bool PushBack (Queue *pq, Item item) {
    // Default to adding to rear node (assuming space for now).

    Node *pnode = pq->rear;

    // Make sure queue has space at end for new item.

    if (pq->front == NULL) {
        // Handle empty queue first, add single node.

        if ((pnode = GetNewNode()) == NULL)
            return false;
        pq->front = pq->rear = pnode;

    } else if (pq->rear->nextItem == ITEMS_PER_NODE) {
        // Handle new node needed in non-empty queue, add to rear of queue.

        if ((pnode = GetNewNode()) == NULL)
            return false;
        pq->rear->next = pnode;
        pq->rear = pnode;
    }

    // Guaranteed space in (possibly new) rear node now, just add item.

    pq->rear->item[pq->rear->nextIndex++] = item;
}

弹出也有点复杂 - 它获取要返回的值，然后删除第一个节点(如果现在已用完)。如果它删除的节点是唯一的节点，这也可能需要清除队列:

int PopFront (Queue * pq) {
    // Capture empty queue.

    if (pq->first == NULL)
        return -1;

    // Get value to pop.

    Node *currFront = pq->front;
    int valuePopped = currFront->item[currFront->startIndex++];

    // Detect current node now empty, delete it.

    if (currFront->startItem == currFront->endIndex) {
        // Detect last node in queue, just free and empty entire queue.

        if (currFront == pq->rear) {
            free (currFront);
            pq->front = pq->rear = NULL;
        } else {
            // Otherwise remove front node, leaving others.

            pq->front = currFront->next;
            free (currFront);
        }
    }

    // Regardless of queue manipulation, return popped value.

    return valuePopped;
}

除了我们清除节点而不是项目之外，清空队列在很大程度上没有改变:

void EmptyQueue (Queue * pq) {
    // Can empty node at a time rather than item at a time.

    while (pq->front != NULL) {
        Node *currentFront = pq->front;
        pq->front = pq->front->next;
        free (currentFront);
    }
}