0

这段代码将简单的队列数据结构作为数组实现

#include <stdio.h>
#define Q_MAX_SIZE 255
#include <stdbool.h>
struct queue
{
    int* pointer;
    int* currentValue;
    int max, count, theQueue[Q_MAX_SIZE];
};

void initQueue(struct queue*);
bool pushQueue(struct queue*, int);
int* popQueue(struct queue*);

int main(void)
{
    int i, j, num = 0;
    struct queue obj[5];

    for(i=0; i<5; i++)
    {
        initQueue(&obj[i]);

        for(j = 0; j<3; j++)
        {
            num++;
            pushQueue(&obj[i], num);
        }
        num = 0;
    }

    for(i=0; i<5; i++)
    {
        printf("Queue[%d]:\n", i);
        int* inputobj;
        inputobj = popQueue(&obj[i]);

        while(inputobj != NULL)
        {
            printf("Queue[No.%d] = %d\n", i, *inputobj);
            inputobj = popQueue(&obj[i]);
        }
        putchar('\n');
    }

    puts("done..!");

    return 0;
}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

void initQueue(struct queue *Q)
{
    Q->pointer = Q->theQueue;
    Q->max = Q_MAX_SIZE;
    Q->count = 0;
}

bool pushQueue(struct queue *Q, int input)
{
    if(Q->count < Q->max)
    {
        *Q->pointer = input;
        Q->pointer++;
        Q->count++;
        return 1;
    }
    else
        return 0;
}

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

int* popQueue(struct queue *Q)
{
    int i;
    if(Q->count > 0)
    {
        Q->currentValue = Q->theQueue;
        Q->pointer--;
        Q->count--;

        for(i=0; i < Q->count; i++)
        {
            int* currentPtr = Q->theQueue + i;
            int* nextPtr = currentPtr + 1;
            *currentPtr = *nextPtr;
        }
        return Q->currentValue;
    }

    else
        NULL;
}

这行函数中的代码有问题popQueue()：

Q->currentValue = Q->theQueue;

这是工作，输出不正确

output:
Queue[0]:
Queue[No.0] = 2
Queue[No.0] = 3
Queue[No.0] = 3

Queue[1]:
Queue[No.1] = 2
Queue[No.1] = 3
Queue[No.1] = 3

Queue[2]:
Queue[No.2] = 2
Queue[No.2] = 3
Queue[No.2] = 3

Queue[3]:
Queue[No.3] = 2
Queue[No.3] = 3
Queue[No.3] = 3

Queue[4]:
Queue[No.4] = 2
Queue[No.4] = 3
Queue[No.4] = 3

done..!

但是在我更改结构currentValue中的指针 ()queue使其成为整数类型并编辑函数中的一些行之后，popQueue()一切正常。

--编辑后的函数如下：

int* popQueue(struct queue *Q)
{
  int i;
  if(Q->count > 0)
  {
    Q->currentValue = Q->theQueue[0];
    Q->pointer--;
    Q->count--;

    for(i=0; i < Q->count; i++)
    {
      int* currentPtr = Q->theQueue + i;
      int* nextPtr = currentPtr + 1;
      *currentPtr = *nextPtr;
    }
    return &Q->currentValue;
  }

-- 这是正确的输出：

Queue[0]:
Queue[No.0] = 1
Queue[No.0] = 2
Queue[No.0] = 3

Queue[1]:
Queue[No.1] = 1
Queue[No.1] = 2
Queue[No.1] = 3

Queue[2]:
Queue[No.2] = 1
Queue[No.2] = 2
Queue[No.2] = 3

Queue[3]:
Queue[No.3] = 1
Queue[No.3] = 2
Queue[No.3] = 3

Queue[4]:
Queue[No.4] = 1
Queue[No.4] = 2
Queue[No.4] = 3

问题是：是什么让第一个代码提供了错误的输出？

4

1 回答 1

1

在第一种情况下给你错误输出的是指针Q->currentValue从未改变它的值（它所持有的地址）这一事实。它总是指向队列中的第一个元素。

说包含的队列{1, 2, 3 |,<garbage>}。

这意味着，在第一次弹出之后，队列变为：

{2, 3 |, 3, <garbage>}

并且currentValue仍然保存数组中第一个元素的地址，即2.

第二次弹出后：

{3 |, 3, 3, <garbage>}

并currentValue指向第一个元素，其值为3,

最后一次，数组没有改变（因为Q->count--将Q->count的值更改为 0），所以内容是

{| 3, 3, 3, <garbage>} 并且currentValue仍然指向一个3.

我假设您更改了第二个示例以Queue->currentValue制作int.

这样，它保留了原始的第一个元素（被弹出）。

这使您的打印在您的测试用例中正常工作。

然而，

  • 0如果您的队列中有 a，您的实施将失败。
  • 您的实现为pop操作增加了不必要的复杂性 (O(n))。head使用和实现循环队列会好得多tail。
  • 保留弹出元素的副本以返回它不是我的首选。我建议实现一个isEmpty()方法，在循环中检查它的结果，while当队列不为空时，只需pop()将队列提前head返回并返回前一个头元素。
于 2013-08-17T12:41:05.380 回答