0

这是两个以简单形式实现队列数据结构的c程序

  • 首先：

    定义一个队列，它工作得很好

  • 第二：

    定义多个队列并在执行时崩溃

两个程序中的功能是相同的，只是main()实现有点不同。

所以这里的问题是：为什么第二个代码不起作用？

* 这里是代码 *

代码1：

/*
 Single queue  -- this work perfectly
*/
#include <stdio.h>
#define Q_MAX_SIZE 255

struct queue {
    int* pointer;
    int* currentValue;
    int max, count, theQueue[Q_MAX_SIZE];
};

//prototyps
void initQueue(struct queue*);
unsigned short pushQueue(struct queue*, int);
int* popQueue(struct queue*);

int main(void) {
    int j;
    struct queue q;

    initQueue(&q);

    for (j = 0; j < 6; j++)
        pushQueue(&q, j);

    int* inputobj = popQueue(&q);
    while (inputobj != NULL)
    {
        printf("%d  ", *inputobj);
        inputobj = popQueue(&q);
    }

    printf("\n\ndone..Queue is empty\n");

    return 0;
}

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

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

unsigned short 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;
}

代码2：

/*
 Multiple queues  -- this not work and crash at execution
*/
#include <stdio.h>
#define Q_MAX_SIZE 255

struct queue {
    int* pointer;
    int* currentValue;
    int max, count, theQueue[Q_MAX_SIZE];
};

//prototyps
void initQueue(struct queue*);
unsigned short pushQueue(struct queue*, int);
int* popQueue(struct queue*);

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

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

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

    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');
    }

    return 0;
}

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

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

unsigned short 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;
}

更新：问题出在initQueue()，通过分配内存解决了Q->currentValue这里是编辑后的功能：

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

4 回答 4

3

正如两个答案已经说明的那样，问题在于Q->current_value从未被赋值，因此它指向一个未定义的地址，并且每个取消引用*Q->currentValue = ..都是未定义的行为。代码 1 看似有效的事实并不能证明其他任何事情，因为由于 UB 的性质，无法保证任何行为，您的程序可能会或可能不会崩溃（或者您的狗可能会爆炸，龙从您的鼻子飞出...... :- ) )

当然，有多种解决方案都意味着不同的东西：

  1. 如果currentValue应该只保存某个值的副本，它可能是int currentValue而不是int *...并且分配将是

    Q->currentValue = *Q->theQueue;

    并且返回语句将是return &Q->currentValue. 在这种情况下，您将返回一个指向原始值的指针theQueue[0]

  2. 如果您想指向 中的位置theQueue，Jim 的分析器会告诉您正确的方法：

    Q->currentValue = Q->队列；

    在这种情况下，您将返回一个指向新值的指针theQueue[0]（这可能是您不想要的）

  3. 您可以为Q->currentValuemy分配内存malloc( sizeof (int) );，然后按原样保留分配。在这种情况下，您将返回指向(1) 中的原始值的指针theQueue[0]

于 2013-08-30T16:45:58.557 回答
1

首先，我不会尝试将这样的代码投入生产。事情可以做得更简单、清晰、高效且不易出错。

我已经通过在尽可能少的地方更改内容来“修复”您的程序。必须清楚的是，这并没有让事情变得更优雅。只有重新思考和重写才能让事情变得更优雅。

您遇到的错误（在第一个和第二个程序中）是例程 popQueue。

  1. 您在 else 子句中不返回任何内容。你应该“返回NULL”。这至少是草率的编程。

  2. 例程为队列返回 1 2 3 4 5 5 和 1 2 2。这是因为 Q->CurrentValue 指向 theQueue 数组中的第一个位置，并且您将所有值上移。这意味着 CurrentValue 实际上指向下一个值。

您的问题的解决方案（同样：它并不优雅，我也不会将其投入生产，但对原始版本的改动很小）是：

  1. 结构中的更改（以保存真正的 CurrentValue）

    struct queue
{
  int* pointer;
  int currentValue;
  int max, count, theQueue[Q_MAX_SIZE];
};

  2. 改变常规popQueue

    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
        return NULL;
}

亲切的问候，PB

于 2013-09-01T09:35:05.950 回答
1

我认为这实际上是一个非常微妙的问题。问题（我认为）是 popqueue() 中的这一行：

*Q->currentValue = *Q->theQueue;

我仔细检查了你的初始代码（没有数组）也有段错误。它不像你说的那样工作。你应该写：

Q->currentValue = Q->theQueue;

C 可以对指针有点理解并适当地分配事物，但是当您添加另一个级别（数组）时，我认为分配被强制进入了一些不起作用的东西。这是我的看法。我想我会提供赏金，以便您获得更好的答案。

于 2013-08-30T13:16:17.540 回答
0

位置 Q->currentValue 无法访问，这就是问题所在。它没有被分配。

解决方案是在 init 例程中分配正确的内存部分：

Q = malloc(sizeof(struct queue));

之后也许还会初始化所有变量的值。

于 2013-08-27T20:32:12.423 回答