c - 如何在 C 中的队列中存储 (x,y) 坐标

Question

我正在使用广度优先搜索算法，但在将队列实现中的起始坐标存储为 (x,y) 作为队列中的一个元素时遇到问题。

我使用了数组和结构，但它不断将每个 int 值作为两个单独的队列元素输入。有没有办法将两个元素存储为一个队列？

struct queue {
int items[SIZE];
int front;
int rear;
};

struct queue* createQueue();

 struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

struct queue* q = createQueue();  
int c[2] = {2,3};

enqueue(q, c);
enqueue(q, 6);
printQueue(q);

void enqueue(struct queue* q, int value){
    if(q->rear == SIZE-1)
        printf("\nQueue is Full!!");
    else {
        if(q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

Expected:

Queue Contains: (2,3), 6

Answer 1

据我了解，您需要一个队列，可以在其中存储表示整数对(又名 x,y)的项目和表示单个整数的项目。

您定义的队列不可能做到这一点:

struct queue {
    int items[SIZE];  <--- each item can only hold a single integer! Not a pair of integers
    int front;
    int rear;
};

所以你需要另一个数据结构。

此外，您的 enqueue 函数是使用两种不同类型的参数调用的

int c[2] = {2,3};
enqueue(q, c);     <--- here the argument is a int-pointer (because c decays into int-pointer)
enqueue(q, 6);     <--- here the argument is a integer

这在 C 中是不允许的。所以你需要两个不同的函数。一种用于对，另一种用于整数。

有许多不同的方法可以实现您的要求。下面是一个使用 struct dataitem 来存储实际数据的示例。 size 字段用于检查存储的数据是一对还是单个整数。

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

#define SIZE 8

struct dataitem
{
  int size;     // Will be 2 for pairs and 1 for single integers
  int data[2];
};

struct queue {
  struct dataitem items[SIZE];
  int front;
  int rear;
};


struct queue* createQueue() {
  struct queue* q = malloc(sizeof *q);
  q->front = 0;
  q->rear = 0;
  return q;
}

int full(struct queue* q)
{
  return (((q->rear + 1) % SIZE) == q->front);
}

int empty(struct queue* q)
{
  return (q->rear == q->front);
}

// Add single integer
void enqueue_int(struct queue* q, int value){
  if (full(q))
  {
    printf("\nQueue is Full!!");
    return;
  }

  q->items[q->rear].size = 1;
  q->items[q->rear].data[0] = value;
  q->rear = (q->rear + 1) % SIZE;
}

// Add pair of integers
void enqueue_pair(struct queue* q, int* values){
  if (full(q))
  {
    printf("\nQueue is Full!!");
    return;
  }

  q->items[q->rear].size = 2;
  q->items[q->rear].data[0] = values[0];
  q->items[q->rear].data[1] = values[1];
  q->rear = (q->rear + 1) % SIZE;
}

void printQueue(struct queue* q)
{
  int tmp = q->front;
  printf("Queue Contains: ");
  int flag = 0;
  while(tmp != q->rear)
  {
    if (flag) printf(", ");
    flag = 1;
    if (q->items[tmp].size > 1)
    {
      printf("(%d,%d)", q->items[tmp].data[0], q->items[tmp].data[1]);
    }
    else
    {
      printf("%d", q->items[tmp].data[0]);
    }
    tmp = (tmp + 1) % SIZE;
  }
  printf("\n");
}

struct dataitem dequeue(struct queue* q)
{
    struct dataitem res;
    if (empty(q))
    {
        res.size = 0;
    }
    else
    {
        res = q->items[q->front];
        q->front = (q->front + 1) % SIZE;
    }
    return res;
}

int main()
{
  int c[2] = {2,3};
  struct queue* q = createQueue();
  enqueue_pair(q, c);
  enqueue_int(q, 6);
  printQueue(q);

  struct dataitem data;
  for (int i=0; i<3; ++i)
  {
    data = dequeue(q);
    if (data.size == 0)
    {
      printf("queue was empty\n");
    }
    else if (data.size == 1)
    {
      printf("queue had integer %d\n", data.data[0]);
    }
    else
    {
      printf("queue had pair (%d,%d)\n", data.data[0], data.data[1]);
    }
  }
  return 0;
}