将节点插入到链表的尾部

Question

本人初学C，对指针等有些理解不是很清楚，所以想用C实现一个VertexNode带链表的，但是不会在我的代码中将节点插入 List(VertexNode) 时获得正确的行为。有些问题可能很简单，但我现在真的很困惑。

这是我的 C 结构：

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

typedef struct Vertex {
    int x;
    int y;
} Vertex;

typedef struct VertexNode {
    Vertex *v;
    struct VertexNode *next;
} VertexNode;

typedef struct VertexNode *List;

List insertLL(List, Vertex *n);
void showLL(List);

VertexNode *makeNode(Vertex *n) {
    VertexNode *new = malloc(sizeof(VertexNode));
    assert(new != NULL);
    new->v = n;
    new->next = NULL;
    return new;
}

List insertLL(List L, Vertex *n) {
    // add new node at the end
    VertexNode *new = makeNode(n);
    if (L){
        if (!L->next) L->next = new;
        if (L->next){
            VertexNode *cur = NULL;
            cur = L->next;
            while(cur){
                //L->next = cur;
                cur = cur->next;
            }
            cur = new;
        }
    }
    if(!L){
        L = new;
        L->next = NULL;
    }
    return L;
}

void showLL(List L) {
    if (L == NULL)
        putchar('\n');
    else {
        printf("%d,%d ", L->v->x,L->v->y);
        showLL(L->next);

    }
    }

int main(){

    Vertex *v1,*v2,*v3;

    v1=(Vertex*) malloc(sizeof(Vertex));
    assert(v1 != NULL);
    v2=(Vertex *) malloc(sizeof(Vertex));
    assert(v2 != NULL);
    v3=(Vertex*) malloc(sizeof(Vertex));
    assert(v3 != NULL);
    v1->x=0;
    v1->y=0;
    v2->x=1;
    v2->y=2;
    v3->x=7;
    v3->y=8;

    VertexNode *L = makeNode(v1);

    insertLL(L, v2);
    insertLL(L, v3);
    showLL(L);
}

现在的输出是

0,0 1,2

我想得到正确的结果

0,0 1,2 7,8

Answer 1

您的代码问题太多。例如，您不在 main.c 中使用插入函数的返回列表。另一个问题是你的插入函数中的逻辑似乎有问题，拿纸和笔，画出（逐行阅读你的代码）发生了什么。这总是有助于列表和指针。此外，我不明白为什么要使节点的值成为指针，而它可能只是一个普通结构（而不是指向它的指针）。

这是我的方法，可能会给您一个起点：

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

typedef struct Vertex {
    int x;
    int y;
} Vertex;

typedef struct VertexNode {
    Vertex v;
    struct VertexNode *next;
} VertexNode;

typedef struct VertexNode *List;

VertexNode *makeNode(Vertex n) {
    VertexNode *new = malloc(sizeof(VertexNode));
    assert(new != NULL);
    new->v.x = n.x;
    new->v.y = n.y;
    new->next = NULL;
    return new;
}

void insertLL(List *ptraddr, Vertex n) {
                                                /* Insert v as last element of list *ptraddr */
    while (*ptraddr != NULL)                    /* Go to end of list */
        ptraddr = &((*ptraddr)->next);          /* Prepare what we need to change */
    *ptraddr = malloc(sizeof(VertexNode));      /* Space for new node */
    (*ptraddr)->v.x = n.x;                      /* Put value */
    (*ptraddr)->v.y = n.y;
    (*ptraddr)->next = NULL;                    /* There is no next element */
}

void showLL(List L) {                           /* Print elements of list */
    while (L != NULL) {                         /* Visit list elements up to the end */
        printf("(%d, %d)--> ", L->v.x,L->v.y);  /* Print current element */
        L = L->next;                            /* Go to next element */
    }
    printf("NULL\n");                           /* Print end of list */
}

/* TODO: Free the list! */

int main(void) {

    Vertex v1, v2, v3;
    v1.x=0; v1.y=0;
    v2.x=1; v2.y=2;
    v3.x=7; v3.y=8;

    VertexNode *L = makeNode(v1);

    insertLL(&L, v2);
    insertLL(&L, v3);
    showLL(L);

    return 0;
}

输出：

(0, 0)--> (1, 2)--> (7, 8)--> NULL

将节点插入到链表的尾部

insert node to the tail of linked list

c

pointers

linked-list

nodes

vertex