c - 链表中的入队函数

Question

我试图理解我的教授所做的“排队”功能，但我没有得到一些步骤。

struct queue_node {
int item;
struct queue_node* next;
};
typedef struct queue_node* queue;


int enqueue (queue* tail, int i) {
queue n;
queue *iter;
n = (queue)malloc(sizeof(struct queue_node));
if (!n) return 1;
n->item = i;
n->next = NULL;
for (iter=tail; *iter != NULL; iter = &((*iter)->next)
;
*iter = n;
return 0;
}

首先是“typedef struct queue_node* queue；”让我感到困惑，所以我尝试以这种方式重新解释代码(如果我错了，请更正代码)

struct queue_node {
int item;
struct queue_node* next;
};
typedef struct queue_node queue;

int enqueue (queue **tail, int i) {
queue *n;
queue **iter;
n = (queue)malloc(sizeof(struct queue_node));
if (!n) return 1; --->what does that mean?
n->item = i;
n->next = NULL;
for (iter=tail; **iter != NULL; iter = &((*iter)->next)--->last part of the for is unclear to me... can i rewrite it as "iter = **((iter)->next)"?
;
*iter = n; -->this is the part i don't really get...
return 0;
}

所以顺便说一下，在尝试阅读我教授的解决方案之前，我尝试自己做一个“入队”功能

typedef struct node{
int value;
struct node *next;
}node;

void enqueue(node *head,int data){
if(head->next != NULL){
enqueue(head->next,data);
}
node *new=NULL;
new=malloc(sizeof(node));
new->value=data;
new->next=NULL;
head->next=new;
}

这样好吗？或者我不能使用它？预先感谢大家的帮助

Answer 1

您和您的教授基本上以不同方式对待变量。根据当时的命名，我认为教授的目标是一张看起来像这样的图片:

tail 指针指的是您要从中出队的最右边的节点，为了到达您入队的位置，您重复直到到达队列的前面。现在这里要注意的重要一点是 iter 并不直接指向节点，它指向每个节点内的 next 单元格，直到它找到一个 NULL 一个，正如我在此处尝试说明的那样。

我认为在实践中您不想为了添加节点而遍历队列是正确的。实际的队列实现(有时使用链表实现)需要恒定时间 O(1) 入队和出队，因此它们始终持有指向队列任一端的指针。

最后一点，每个人对 C 的命名约定都有不同的看法，但我倾向于同意你的看法，教授的例子有一些令人困惑的 typedef。某些代码库(例如 linux 内核)建议根本不要对指针甚至结构使用 typedef。