链表的链表 C

Question

我正在尝试创建一个将由 LinkedLists 填充的 LinkedList。主 LinkedList 将包含角色名称和描述，以及其内部 LinkedList 中包含的节点数。内部 LinkedList 将保存它们出现的章节编号和该章节的简短描述。例如，角色乔（姓名）是国王（描述符），出现在第 4、7 和 10 章中。因此他将有 3 个内部节点，描述他在这些章节中所做的事情。我不认为我添加到列表中是正确的，因为当我调用遍历列表并打印所有内容时，我只得到我添加的第一个人。

我做的两个结构体。

struct Person{
    char * name;
    char * descriptor;
    int count;
    struct Person * next;
    struct Information * info_head;
};
struct Information{
    char * text;
    int chapter;
    struct Information * next;
};

正在创建指针。

struct Person * new_person, *temp_pers, *head_pers;
struct Information * new_info, *temp_info, *head_info;

用于添加新字符的函数。

void add(char * name, char * descriptor, char * info, int chapter){
new_person = (struct Person *)malloc(sizeof(struct Person));
new_info = (struct Information *)malloc(sizeof(struct Information));

new_info->chapter = chapter;
new_info->text = info;
new_person->name = name;
new_person->descriptor = descriptor;

if(head_pers == NULL){  //List is empty
    head_pers = new_person; //add new person
    new_person->info_head = new_info;//link to information
    head_pers->next = NULL;
    head_info = new_info; //name that information start of information list
    head_pers->count = 1;
    head_info->next = NULL;
}
else{
    temp_pers = head_pers;
    temp_info = head_info;
    while(temp_pers != NULL){ //iterate through list of people
        if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
            while(temp_info != NULL){ //iterate through that persons info list
                temp_info = temp_info->next;
            } //reached the end of the list
            temp_info = new_info;
            temp_pers->count = temp_pers->count + 1;
            temp_pers->next = NULL;
        }
        temp_pers = temp_pers->next;
    }
    //reached end of persons list with no find
    //add new person to the end of the list
    temp_pers = new_person;
    temp_pers->count = temp_pers->count + 1;
    temp_pers->next = NULL;
}

}

我测试的打印方法

void printAll(){
    temp_pers = head_pers;
    temp_info = head_info;
    while(temp_pers != NULL){
        printf("%s, %s %d\n", temp_pers->name, temp_pers->descriptor, temp_pers->count);
        while(temp_info != NULL){
            printf("%d\t%s", temp_info->chapter, temp_info->text);
            temp_info = temp_info->next;
        }
        temp_pers = temp_pers->next;
    }
}

主要方法

int main(){
    add("Joe", "the King", "had a child.", 4);
    add("Joe", "the King", "started a war", 7);
    add("Sue", "the Queen", "poisoned Joe", 10);

    printAll();

    return 0;
}

处理 LinkedLists 的 LinkedList 使我感到困惑，也许我只是遗漏了一些非常小的东西，或者可能是一些非常大的东西，但任何帮助都会很棒。差点忘了，代码确实编译并输出了这个...

    Joe, the King 2
4   had a child.

因为它打印出 Joe 的计数为 2，我认为它在起作用。

Answer 1

如您所见，您的代码打印出第一个节点和子节点：("Joe", "the King", "had a child.", 4)，这意味着您的插入工作正常，至少在开始时是这样。在此行之后它终止，意思是 temp_pers = temp_pers->next == NULL;

现在，让我们看看您的第二次插入：

else{
temp_pers = head_pers;
temp_info = head_info;
while(temp_pers != NULL){ //iterate through list of people
    if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
        while(temp_info != NULL){ //iterate through that persons info list
            temp_info = temp_info->next;
        } //reached the end of the list
        temp_info = new_info;
        temp_pers->count = temp_pers->count + 1;
        temp_pers->next = NULL;
    }
    temp_pers = temp_pers->next;
}
//reached end of persons list with no find
//add new person to the end of the list
temp_pers = new_person;
temp_pers->count = temp_pers->count + 1;
temp_pers->next = NULL;
}

您创建了一个 temp_pers 并为其分配了一些内容，但在作用域结束后，此节点未连接到您的 head_pers。因此，每次构造一个新结构并将其分配给 temp_pers 时，您都不会将其输入主链表 (a.k.a head_pers) ，所以每次你检查循环内的条件（这个：while(temp_pers != NULL)）你检查你创建的最后一个节点，并且由于它没有链接到某些东西，它会在下一个节点上给你 NULL。

如何修复：head_pers->next = temp_pers; 在 else 部分。现在，这将确保第二个节点连接到第一个节点。从现在开始，您创建的每个节点都应该连接到列表的末尾。您可以通过保存最后一个节点（O(1) 时间）或通过在每次添加时遍历列表（O(n) 时间）

来做到这一点

Answer 2

在add中，循环后，temp_pers指向NULL。您需要保留指向列表中最后一个人的指针：

struct Person *last_pers;

last_pers = temp_pers;

while(temp_pers != NULL){ //iterate through list of people
    if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
        while(temp_info != NULL){ //iterate through that persons info list
            temp_info = temp_info->next;
        } //reached the end of the list
        temp_info = new_info;
        temp_pers->count = temp_pers->count + 1;
        temp_pers->next = NULL;
    }
    last_pers = temp_pers;
    temp_pers = temp_pers->next;
}
//reached end of persons list with no find
//add new person to the end of the list
last_pers->next = new_person;  
new_person->count = 1;
new_person->next = NULL;

Answer 3

除了 pers_head 之外的所有全局变量都应该是局部变量。只有一个头部，即人员列表的头部。所有其他信息都包含在此列表中：其他人查看 next 指针；通过此人的 info 获取信息。最重要的是，没有全局信息头；信息头属于每个人。

打印人物和事件列表时，应该使用两个循环：

void printAll()
{
    struct Person *pers = head;

    while (pers) {
        printf("%s, %s [%d]\n",
            pers->name, pers->desc, pers->count);

        struct Information *info = pers->info;

        while (info) {
            printf("    %d: %s\n", info->chapter, info->text);
            info = info->next;
        }

        pers = pers->next;
    }
}

请注意 pers 和 info 是局部变量，而不是全局变量。它们仅在定义它们的范围内使用并具有意义。这很好：很容易看出 pers 只是遍历所有人，没有别的。

当您添加一个人时，您会立即创建一个新的人节点。但如果此人已在列表中，则您可能不需要新节点。仅在确实需要时才创建节点。

您的 add 函数做了太多事情：它分配和填充节点和信息，并组织列表。如果您编写单独的函数来创建节点和向人员插入信息，核心列表代码看起来会更清晰。

一个可能的实现（稍微改变，或者更确切地说，缩短变量名）可能是：

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

struct Person{
    char *name;
    char *desc;
    int count;
    struct Person *next;
    struct Information *info;
};
struct Information{
    char *text;
    int chapter;
    struct Information *next;
};

struct Person *head;

struct Information *info_new(char *text, int chapter)
{
    struct Information *info = malloc(sizeof(*info));

    info->text = text;
    info->chapter = chapter;
    info->next = NULL;

    return info;
}

struct Person *pers_new(char *name, char *desc)
{
    struct Person *pers = malloc(sizeof(*pers));

    pers->name = name;
    pers->desc = desc;
    pers->next = NULL;
    pers->info = NULL;
    pers->count = 0;

    return pers;
}

void pers_add_info(struct Person *pers, struct Information *info)
{
    if (pers->info == NULL) {
        pers->info = info;
    } else {
        struct Information *j = pers->info;

        while (j->next) j = j->next;
        j->next = info;
    }

    info->next = NULL;
    pers->count++;
}

void add(char *name, char *desc, char *infotext, int chapter)
{
    struct Information *info = info_new(infotext, chapter);
    struct Person *pers = head;
    struct Person *prev = NULL;

    while (pers) {
        if (strcmp(pers->name, name) == 0
         && strcmp(pers->desc, desc) == 0) {
            pers_add_info(pers, info);
            return;
        }
        prev = pers;
        pers = pers->next;
    }

    pers = pers_new(name, desc);
    pers_add_info(pers, info);

    if (prev) {
        prev->next = pers;
    } else {
        head = pers;
    }
}

void printAll()
{
    struct Person *pers = head;

    while (pers) {
        printf("%s, %s [%d]\n",
            pers->name, pers->desc, pers->count);

        struct Information *info = pers->info;

        while (info) {
            printf("    %d: %s\n", info->chapter, info->text);
            info = info->next;
        }

        pers = pers->next;
    }
}

int main()
{
    add("Joe", "the king", "had a child", 4);
    add("Sue", "the queen", "gave birth to a child", 4);
    add("Ben", "the prince", "is born", 4);
    add("Joe", "the king", "started a war", 7);
    add("Joe", "the king", "returns home victorious", 8);
    add("Ben", "the prince", "is squire to Lord Sam", 8);
    add("Sam", "High Lord", "takes Sam as apprentice", 8);
    add("Ben", "the prince", "goes on a quest", 9);
    add("Sue", "the queen", "poisoned Joe", 10);
    add("Ben", "the prince", "takes revenge", 10);
    add("Sam", "High Lord", "goes on a crusade", 11);
    add("Sue", "the queen", "repents", 14);
    add("Sue", "the hermit", "dies of old age and lonely", 14);

    printAll();

    return 0;
}

链表的链表 C

LinkedList of LinkedLists C

c

linked-list