C - 使用出队进行回绕时队列的段错误

Question

好吧，所以我想用队列创建 3 个函数。它们是create_queue()、enqueue() 和dequeue()。我创建了所有三个，并在 main 中测试它们，如果它已满，它应该抛出错误，并且无论头部还是尾部碰到末端，它都应该环绕。就我而言，我得到了 enqueue() 来环绕，但没有 dequeue()。我被困在这里试图找出我在哪里犯了错误。如果有人能发现它并让我知道如何修复它，我将不胜感激! ^.^

队列测试.c

#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
#include <errno.h>

typedef struct {
  int x;
  double y;
} Foo; // Just some arbitrary struct


int main() {

  const int max_entries = 4; // size of stack
  Foo* new_foo1;
  Foo* new_foo2;
  Foo* new_foo3;
  Foo* new_foo4;
  Foo* new_foo5;
  Foo* returned_foo;

  // First, create a stack
  Queue *new_queue = create_queue(max_entries);

  // Allocate a Foo and push it onto the queue.
  new_foo1 = (Foo *) malloc(sizeof(Foo));
  new_foo1->x = 100;
  new_foo1->y = 1.11;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo1->x, new_foo1->y);
  enqueue(new_queue, (void *) new_foo1);

  // Allocate another Foo and push it onto the queue.
  new_foo2 = (Foo *) malloc(sizeof(Foo));
  new_foo2->x = 200;
  new_foo2->y = 2.22;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo2->x, new_foo2->y);
  enqueue(new_queue, (void *) new_foo2);

  // Allocate another Foo and push it onto the queue.
  new_foo3 = (Foo *) malloc(sizeof(Foo));
  new_foo3->x = 300;
  new_foo3->y = 3.33;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo3->x, new_foo3->y);
  enqueue(new_queue, (void *) new_foo3);

  // Allocate another Foo and push it onto the queue.
  new_foo4 = (Foo *) malloc(sizeof(Foo));
  new_foo4->x = 400;
  new_foo4->y = 4.44;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo4->x, new_foo4->y);
  enqueue(new_queue, (void *) new_foo4);

 // Allocate another Foo and push it onto the queue.
  new_foo5 = (Foo *) malloc(sizeof(Foo));
  new_foo5->x = 500;
  new_foo5->y = 5.55;
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo5->x, new_foo5->y);
  enqueue(new_queue, (void *) new_foo5);

  /////////////////////////////////////////////////////////////////

  // Dequeue two  Foos and print them.
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);

  /////////////////////////////////////////////////////////////////

  // Add 3 Foos
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo5->x, new_foo5->y);
  enqueue(new_queue, (void *) new_foo5);
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo1->x, new_foo1->y);
  enqueue(new_queue, (void *) new_foo1);
  printf("Pushing: x = %5d, y = %10.3f\n", new_foo2->x, new_foo2->y);
  enqueue(new_queue, (void *) new_foo2);

  /////////////////////////////////////////////////////////////////

  // Dequeue 5 Foos and print them.
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);
  returned_foo = (Foo *) dequeue(new_queue);
  printf("Removed:  x = %5d, y = %10.3f\n", returned_foo->x, returned_foo->y);

}

队列.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "queue.h"

/** Create a queue by allocating a Queue structure, initializing it,
 *  and allocating memory to hold the queue entries.
 * @param max_cells Maximum entries in the queue
 * @return Pointer to newly-allocated Queue structure, NULL if error.
 */
Queue *create_queue(int max_cells) {
  Queue *new_queue; // Holds pointer to the newly-allocated queue structure.
  new_queue = (Queue *) malloc(sizeof(Queue));

  if (new_queue == NULL) return NULL; // Error--unable to allocate.

  // Fill in the struct
  new_queue->max_cells = max_cells;
  new_queue->cells_used = 0; // Empty to start
  new_queue->ePos = 1; //Starts at first position
  new_queue->dPos = 1; //Starts at first position

  // Now allocate space for the queue entries.
  new_queue->head = (void **) calloc(sizeof(void *), max_cells);
  if (new_queue->head == NULL) {
    free(new_queue); // Unable to allocate queue entries, so free struct.
    return NULL;
  }
  new_queue->tail = new_queue->head; // Start at head

  return new_queue;
}

/** Deletes a queue, including the structure and the memory
 * for holding the queue entries, but not the entries themselves.
 * @param which_queue Pointer to Queue structure.
 */
void delete_queue(Queue *which_queue) {
  free(which_queue->head); // Free memory block with queue entries.
  free(which_queue); // Then free the struct.
}

/** Pushes a pointer onto a Queue.
 * @param which_queue Pointer to queue you want to push onto.
 * @param ptr Pointer to be pushed.
 * @return 0 if successful, -1 if not.
 */
int enqueue(Queue *which_queue, void *ptr) {

 // Check if queue is already full
  if ((which_queue->cells_used) >= (which_queue->max_cells)) {
    which_queue->cells_used = which_queue->max_cells;
    printf("Error: Queue overflow\n");
    return -1;  // Queue overflow.
  }

  // Check if tail is at the end of the Queue
  if ((which_queue->ePos) == (which_queue->max_cells)) {

    //Sets tail to the beginning of queue
    (which_queue->tail) = (which_queue->tail) - (which_queue->max_cells);
    //Sets position back to beginning
    (which_queue->ePos) = 1;
  }

  // Push onto queue.
  *(which_queue->tail) = ptr;  // Store the pointer on the stack
  (which_queue->tail)++;       // Point to next free cell
  (which_queue->cells_used)++;
  (which_queue->ePos)++;
  return 0;  // Success
}

/** Removes head of queue, and returns it.
 * @param which_queue Pointer to Queue you want to dequeue from.
 * @return Head entry of the queue, NULL if queue is empty.
 */
void* dequeue(Queue *which_queue) {

  // Check if queue is empty
  if ((which_queue->cells_used) <= 0) {
    which_queue->cells_used = 0;
    printf("Error: Queue underflow\n");
    return NULL;  // Queue empty
  }

  // Check if head is at the end of the Queue
  if ((which_queue->dPos) == (which_queue->max_cells)) {

    //Sets head to the beginning of queue
    (which_queue->head) = (which_queue->head) - 3;
    //Sets position back to beginning
    (which_queue->dPos) = 1;
    (which_queue->cells_used)--;
    return (*((which_queue->head) + 3));
  }

  // Remove head from queue.
  (which_queue->cells_used)--;
  (which_queue->head)++;
  (which_queue->dPos)++;
  return (*((which_queue->head) - 1));
}

注意:我知道我使用了 - 3 和 + 3 而不是 max_cells - 1 等。我只是想看看这是否是一个问题，但事实并非如此。另一个注意事项是，如果我用 1 2 3 替换 -3 或 +3，它仍然会给我一个段错误。

队列.h

/** Struct to define a queue; each entry can hold a pointer to anything.
 */
struct queue {
  void **head; // Pointer to head of queue
  void **tail;  // Pointer to next free cell (tail);
  int max_cells; // Maximum number of entries in the queue
  int cells_used; // Currently used number of cells
  int ePos; //Position of the enqueue
  int dPos; //Position of the dequeue
};

typedef struct queue Queue;

// Function prototypes

Queue *create_queue(int max_cells);

void delete_queue(Queue *which_queue);

int enqueue(Queue *which_queue, void *ptr);

void* dequeue(Queue *which_queue);

因此，在调用第二个 dequeue() 后，seg 错误发生在打印行上。这意味着 returned_foo 有一个错误的值，这是由于出队函数没有在 if 语句部分正确运行环绕而引起的(至少我认为这是错误>.>)。任何帮助都会有帮助!提前致谢。

Answer 1

您的 enqueue() 实现永远不会填充队列中的最后一个元素。

create_queue();  // ePos = 1, queue: x x x x
enqueue(A);      // ePos = 2, queue: A x x x
enqueue(B);      // ePos = 3, queue: A B x x
enqueue(C);      // ePos = 4, queue: A B C x
enqueue(D);      // This already wraps because ePos == max_cells!
                 // ePos = 2, queue: D B C x

当dequeue()到达队列的最后一个元素时，它读取NULL(这是最后一个元素包含的内容，因为calloc 用零填充内存块)，然后程序崩溃。