如何遍历链表中的子节点

Question

我正在开发以下程序:

...
typedef struct node_tag{
    int id;
    char pLabel[10];
    struct node_tag *pNext;
    struct node_tag *pInner;
    }NODE;
...
int main(int argc, char** argv)
    {
    NODE *list = create_node("start");
    add_node(&list, "MUSIC");
    add_node(&list, "VIDEOS");
    add_node(&list, "PICTURES");
    create_sub_node( &list, "2015" ); // sub node of PICTURES
    create_sub_node( &list, "Trip" ); // sub node of 2015
    print_nodes(list);
    return (EXIT_SUCCESS);
    }

输出:

|
|-> [ID:4] PICTURES
|   |-> [ID:40] 2015
|   |   |-> [ID:400] Trip
|
|-> [ID:3] VIDEOS
|
|-> [ID:2] MUSIC
|
|-> [ID:1] start
|

到目前为止，一切都如我所愿，从输出中可以看出。然而，我想实现创建子节点的不同方法。我现在得到的是非常有限的，因为它只能创建2个子节点的深度但我想要无限的深度:

void create_sub_node( NODE **handle, char* label )
    {
    NODE *new = malloc( sizeof(NODE) );
    new->pNext = NULL;
    new->pInner = NULL;
    strncpy( new->pLabel , label , strlen(label) +1 );   
    if( (*handle)->pInner == NULL )
        {
        new->id = (*handle)->id * 10;
        (*handle)->pInner = new;        
        }
    else if( (*handle)->pInner->pInner == NULL ) 
        {
        new->id = (*handle)->pInner->id * 10;
        (*handle)->pInner->pInner = new;
        }
    }

我试着实现while循环，可以通过内部节点迭代，直到他们发现空一个，然后创建新的节点。我遇到的问题是，当我遍历节点时，指针地址改变了，我留下了一个不再工作的大烂摊子。

我试图复制所有内部节点的地址，但是我无法重新分配它们。

事情是，我必须将子节点添加到列表中，所以我将改变各种指针地址，但要做到这一点，看起来我需要一个列表的副本，在那里我可以玩它，以便原始地址不会改变。

我如何遍历子节点并创建新节点，以便我不必硬编码一堆IF语句?

Answer 1

我的C有点生疏，但是:

NODE* tail(NODE* list) {
     if (list == NULL) return NULL;
     NODE* current = list;
     while (current->pInner != NULL) { current = current->pInner; }
     return current;              
}

则函数变为:

void create_sub_node( NODE **handle, char* label )
{
    NODE *new = malloc( sizeof(NODE) );
    new->pNext = NULL;
    new->pInner = NULL;
    strncpy( new->pLabel , label , strlen(label) +1 );   
    NODE* last = tail((*handle));
    new->id = last->id * 10;
    last->pInner = new;        
}

Answer 2

你的链表更像一棵树:

|-> MUSIC
|   |-> Punk
|   |-> Funk
|-> VIDEOS
|   |-> Cats
|   |-> Cars
|   |-> Parties
|-> PICTURES
|   |-> 2014
|   |   |-> Skiing
|   |   |-> Trip
|   |   |-> Thksgvg
|   |-> 2015
|   |   |-> Birthday
|   |   |-> Wedding

你通过pNext到垂直线上的下一个节点(下一个最年长的兄弟)，你通过pInner再深入一层(最年长的孩子)。节点的所有弟妹和所有子节点都可以通过节点指针访问。你也可以保留一个指向父节点的指针，这样你就可以向上走，而不仅仅是向下走。

如果您具有创建节点和返回新节点的子节点的函数，则可以轻松构建这样的树:

int main(int argc, char **argv)
{
    NODE *list = NULL;         // list head
    NODE *p;                   // first-generation child 
    NODE *q;                   // second-generation child
    p = add_node(&list, "MUSIC");
        create_sub_node(p, "Punk");
        create_sub_node(p, "Funk");
    p = add_node(&list, "VIDEOS");
        create_sub_node(p, "Cats");
        create_sub_node(p, "Cars");
        create_sub_node(p, "Parties");
    p = add_node(&list, "PICTURES");
    q = create_sub_node(p, "2014");
        create_sub_node(q, "Skiing");
        create_sub_node(q, "Trip");
        create_sub_node(q, "Thksgvg");
    q = create_sub_node(p, "2015");
        create_sub_node(q, "Birthday");
        create_sub_node(q, "Wedding");
    print_nodes(list);
    return (EXIT_SUCCESS);
}

当您构建树时，必须将最小的兄弟节点的pNext更改为新节点，其pNext为NULL。确保仅在追加第一个节点时才更改列表的头部。同样，只有在添加第一个子节点时才更改节点的pInner。

通常必须区分两种情况:第一个节点和随后的节点。结合这些情况的一种技术是使用指向节点指针的指针遍历列表。该指针首先指向列表或子列表的头部，然后指向节点的pNext，如果有节点，即

下面是与上述main一起工作的两个函数:

NODE *add_node(NODE **head, const char *label)
{
    NODE **p = head;
    // walk to the end
    while (*p) p = &(*p)->pNext;    
    // append new node
    *p = malloc(sizeof(**p));
    (*p)->pInner = NULL;
    (*p)->pNext = NULL;
    snprintf((*p)->pLabel, sizeof((*p)->pLabel), "%s", label);        
    return (*p);
}
NODE *create_sub_node(NODE *node, const char *label)
{
    NODE **p = &node->pInner;
    // walk to the end
    while (*p) p = &(*p)->pNext;
    // append new node
    *p = malloc(sizeof(**p));    
    (*p)->pInner = NULL;
    (*p)->pNext = NULL;
    snprintf((*p)->pLabel, sizeof((*p)->pLabel), "%s", label);
    return *p;
}