链表中的入队函数

Question

我正在尝试理解我的教授所做的功能 "enqueue"，但我没有得到一些步骤。

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

所以顺便说一句，在尝试阅读我教授的解决方案之前，我尝试自己做一个 "enqueue" 函数

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

typedef struct queue_node* queue;定义了一个新的类型，这样你就可以写

queue* myqueue = (queue*)malloc(sizeof(struct queue_node));

而不是

struct queue_node** myqueue = (struct queue_node**)malloc(sizeof(struct queue_node));

正如评论中指出的，这是一个指向指针的类型。

行

if (!n) return 1;

测试指针 n 是否有效（即不是 NULL），如果比较失败，returns 1 作为错误代码。

现在代码

for (iter=tail; **iter != NULL; iter = &((*iter)->next)
{
    *iter = n; /* -->this is the part i don't really get... */
    return 0;
}

遍历列表，直到遇到 NULL 指针。 *iter = n; 行取消引用当前迭代器（在本例中是指向当前 node 的指针并将 n 分配给它。所以这实际上搜索队列的末尾并分配新的元素到最后。

**((iter)->next)

与

不一样

&((*iter)->next)

语句 (*iter)->next 取消引用 iter，它是指向 struct queue_node 的指针的指针，因此您只有指向 queue 的实际指针。然后它从 queue 中获取 next 字段。 & 为您提供指向 next 引用的元素的指针（它是地址运算符），而您的代码将为您提供 ->next 引用的实际对象。

现在为您输入代码：

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

除了我一开始的评论，我看不出有什么不妥。但我还没有实际测试代码是否运行 ;)

我希望这能让事情变得更清楚。 :) 如果我的解释有任何歧义，请发表评论，不要简单地否决，我知道我不是最有经验的 C 程序员。

Answer 2

如果要使用你定义的 queue

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

typedef struct queue_node queue;

那么该函数将如下所示。

int enqueue( queue **tail, int item ) 
{
    queue *node = ( queue * )malloc( sizeof( queue ) );
    int success = node != NULL;

    if ( success )
    {
        node->item = item;
        node->next = NULL;

        while ( *tail != NULL ) tail = &( *tail )->next;

        *tail = node;
    }

    return success;
}

与您的函数定义相反，此函数returns如果成功，即成功分配将附加到队列的新节点时为 1，否则为 0。

因此，如果您通过以下方式声明队列

队列 *head = NULL;

那么函数调用可以像这样

enqueue( &head, value );

其中 value 是一些整数表达式。

如您所见，您需要使用指针间接传递 queue 的头部。否则，如果不使用指针并将头部直接传递给函数，则该函数将获得头部的副本。所以函数中copy的任何改动都不会影响到原来的head。

在此声明中

    queue *node = ( queue * )malloc( sizeof( queue ) );

创建了一个新节点。函数 malloc returns 指向动态分配节点的指针。

在此声明中

    int success = node != NULL;

表达式 node != NULL 的结果（1 或 0）取决于 malloc 的调用是否成功。

如果 malloc 的调用成功，即 node 不等于 NULL，则新节点被初始化并将其附加到队列的末尾。如果（成功） { 节点->项目=项目；节点->下一个= NULL；

        while ( *tail != NULL ) tail = &( *tail )->next;

        *tail = node;
    }

如何找到列表的尾部？

如果列表最初为空，则 *tail 等于 NULL 并且 while *tail != NULL 的条件将等于 false。所以等于NULL的tail的当前值被分配节点的地址

代替

*tail = node;

否则如果*tail不等于NULL我们得到当前节点的数据字段next

( *tail )->next

然后获取它的地址，就像我们通过引用将头部传递给函数一样

&( *tail )->next

最后，当此数据字段包含 NULL 时，我们将此 NULL 替换为新创建节点的地址。

如果你想编写一个递归函数将新节点添加到队列中，那么它看起来像

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

void enqueue( node **tail, int data )
{
    if ( *tail != NULL )
    { 
        enqueue( &( *tail )->next, data );
    }
    else
    {
        node *tmp = malloc( sizeof( node ) );
        tmp->value = data;
        tmp->next = NULL;

        *tail = tmp;
    }
}

Answer 3

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

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

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

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

链表中的入队函数

enqueue function in linked list

c

pointers

linked-list

singly-linked-list