通过尾指针添加到链接列表，而没有3个间接级别 [英] Add to linked list via tail pointer without 3 levels of indirection

问题描述

我正在从事一个需要实现链表的项目.在开始该项目之前，我正在回顾创建链接列表的经典方法.

I am working on a project that requires an implementation of a linked list. Before I started the project, I was reviewing the classic method of creating a linked list.

我意识到过去，我是通过 head 指针将元素添加到链接列表中的，该指针会遍历列表直到到达空指针.

I realized that in the past, I had been adding elements to a linked list via the head pointer that traverses the list until it reaches the null pointer.

我发现没有必要以这种方式来实现，而以一种涉及 tail 指针的方式来实现它，但是我唯一想到的就是三重指针或全局指针.我想知道，是否有一种更简单的方法使用更少的间接级别?

I figured out that there is no need to do it this way, and to implement it in a way that involves a tail pointer, but the only way I could think of is a one that involves a triple pointer or a global pointer. I was wondering, is there an easier approach that uses less levels of indirection?

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


typedef struct list {
    int val;
    struct list *next;
} list;


void printlist(list *head);
void freelist(list *head);

void AddList(list ***tail, int val);


int main(void)
{
    /* create first node */
    list *head = (list *)malloc(sizeof(*head));

    /* assign members of first node */
    head->val = 1;
    head->next = NULL;

    /* create tail */
    list **tail = &head->next;

    /* add values to list */
    AddList(&tail, 2);
    AddList(&tail, 3);
    AddList(&tail, 4);
    AddList(&tail, 5);
    AddList(&tail, 6);
    AddList(&tail, 7);
    AddList(&tail, 8);
    AddList(&tail, 9);

    /* print list */
    printlist(head);

    /* free list */
    freelist(head);

    /* exit program */
    system("pause");
    return 0;
}


void AddList(list ***tail, int val)
{
    list *node = (list *)malloc(sizeof(*node));

    node->val = val;
    node->next = NULL;

    **tail = node;

    *tail = &node->next;
}

void printlist(list *head)
{
    while (head) {
        printf("%d\n", head->val);
        head = head->next;
    }
}

void freelist(list *head)
{
    list *tmp = head;
    while (head) {
        head = head->next;
        free(tmp);
        tmp = head;
    }
}

推荐答案

tail 指针应指向最后一个节点，而不是最后一个节点的 next 指针:

The tail pointer should point to the last node, not the next pointer of the last node:

在 main 中:

/* create tail */
list *tail = head;

在 AddList 中:

void AddList(list **tail, int val)
{
    list *node = malloc(sizeof(*node));

    node->val = val;
    node->next = NULL;

    (*tail)->next = node;
    *tail = node;
}

这篇关于通过尾指针添加到链接列表，而没有3个间接级别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！