我需要用 C 语言为赋值编程队列结构。节点有一个指向下一个节点和值的指针(到目前为止，很正常)。但是，由于我需要将它与线程一起使用，因此我将错误地将所有容量放在堆上。 但是，节点和队列的定义如下：
//Element of a queue
struct queue_node {
// Pointer to next element in the queue
struct queue_node* next;
// Value/Data of the queue element
int value;
};
// Queue data structure
struct queue {
// Head of the linked list
struct queue_node* head;
// Max capacity of the queue
int capacity;
// Current size of the queue. size <= capacity, always
int size;
};
我遇到的问题是推送元素，因为我没有任何关于哪个是分配内存的开始或结束的信息。所以我决定让头节点始终是空间中的第一个节点，这样我就可以使用 我像这样编写了基本功能：
struct queue* queue_new(int capacity){
struct queue_node* head1 = malloc(sizeof(struct queue_node)*capacity);
struct queue* ret = malloc(sizeof(struct queue));
/*
struct queue_node head2;
head2.next = NULL;
(*head1) = head2;
*/
(*head1).next = NULL;
(*ret).head = head1;
(*ret).size = 0;
(*ret).capacity = capacity;
return ret;
}
void queue_delete(struct queue* queue){
free((*queue).head);
free(queue);
}
所以。但是，当我想将某些东西推入队列时，我遇到了麻烦。显然，首先要做的，就是填满脑袋。这似乎有效。但是，将元素追加到头节点不会：
int queue_push_back(struct queue* queue, int value){
if((*queue).size >= (*queue).capacity){
return -1;
}else if((*queue).size == 0){
(*(*queue).head).value = value;
(*queue).size++;
return (*queue).size;
} else{
if((*(*queue).head).next == NULL){ ////((*queue).head + sizeof(struct queue_node))
printf("Intern queue size 1: %dn", (*queue).size);
(*(*queue).head).next = ((*queue).head + sizeof(struct queue_node));
printf("Error here?n");
(*(*(*queue).head).next).value = value;
printf("Error here 2?n");
(*(*(*queue).head).next).next = NULL;
printf("Error here 3?n");
printf("Intern queue size 2: %dn", (*queue).size);
printf("Intern queue capacity: %dn", (*queue).capacity);
(*queue).size++;
return (*queue).size;
}
}
我跳过了常见情况的代码，因为这甚至不起作用。出于某种原因，如果我想推送第二个元素，它会覆盖我的队列结构。我不知道为什么。 有人可以帮助我并告诉我，我哪里做错了什么？
您似乎正在尝试混合两种不同的方法来解决问题：
-
将队列维护为数组，以及
-
将队列维护为链表。
在一个块中为全部节点分配空间，将队列头保持在块的开头，并且首先具有固定的队列容量，这些都是类似阵列使用的特征。 另一方面，具有"next"指针的元素节点结构是链表的形式。
如果将队列作为数组进行管理，则next指针是多余的，并且如果您实际使用它们，它们实际上会受到限制。 相反，您始终可以通过指向节点块开头的指针和节点索引来识别和导航到节点：my_queue_ptr->head[node_num]。 您还可以根据队列的当前大小确定下一个可用节点：my_queue_ptr->head[my_queue_ptr->size]。
但是，每当将节点取消排队时，都必须将所有其他节点(或至少是它们的数据)向前移动一个位置。 如果你移动整个节点，那么你就会搞砸它们的next指针，因为每个指向位置的东西与以前不同，并且具有不同的意义。
另一方面，如果您将队列作为链表进行管理，那么将所有节点分配在一个块中是没有意义的。 相反，通常为排队的每个值分配一个新节点，并取消分配取消排队的每个值的节点。 在这种情况下，您将在对第一个元素进行排队和对任何元素进行出队列时修改队列的head指针。 如果您没有维护指向当前尾部的指针(就像目前没有的那样)，那么每次将元素排队时，您都需要遍历列表以找到尾节点，并将新节点附加到该节点。
更新：
如果您仍然继续执行您所描述的内容，那么对我来说唯一有意义的方法是采用基于数组的方法，并完全忽略数据结构的链接列表方面。 您提供的queue_new()和queue_delete()函数是合理的。 另一方面，您的queue_push_back()甚至不是内部一致的，更不用说适合类似数组的方法了。
但是，在详细介绍之前，我想指出您的代码不必要地难以阅读。 此时您肯定已经介绍给->操作员;它专门设计用于简化指向结构的指针的使用，尤其是易于使用指向结构的指针链。 这是您的queue_push_back()函数的第一部分，重写以使用->;呈现的部分与原件的相应部分完全相同：
int queue_push_back(struct queue* queue, int value){
if (queue->size >= queue->capacity) {
return -1;
} else if (queue->size == 0) {
queue->head->value = value;
queue->size++;
return queue->size;
} else {
// ...
}
这更容易阅读，至少对我来说是这样。 现在，干扰更少，可以更轻松地看到您设置的头节点的唯一属性是其value。 您不设置其next指针。 如果你已经理解了我的建议，那么你就会意识到这实际上很好- 你将使用数组中的索引来访问元素，而不是链接，这充其量是多余的。
但是现在考虑一下当你推送下一个元素时你尝试做什么。 第一件事是测试头节点的next指针的值，您从未设置过该指针。 未定义的行为结果。 现在你可以管理链接并使用它们(尽管如果你想支持容量大于2的队列，你需要比现在更复杂的东西)，但正如我所说，我的建议是完全忽略链接。
已经验证队列有空间容纳另一个元素后，您可以按queue->head[queue->size]直接访问该元素：
queue->head[queue->size].value = value;
queue->size++;
瞧，仅此而已。 但是等等，它会变得更好！ 如果您仔细观察，您会发现第一个节点的情况与其他节点的情况几乎没有区别。 事实上，差异纯粹是句法上的;第一个节点(当queue->size == 0时)同样可以通过我刚刚介绍的代码得到很好的服务;它根本不需要是特例：
int queue_push_back(struct queue* queue, int value){
if (queue->size >= queue->capacity) {
return -1;
} else {
queue->head[queue->size].value = value;
return ++queue->size;
}
// That's all, folks!
}