链表的链表C

Question

我正在尝试创建一个包含LinkedList的LinkedList。主LinkedList将保存人物名字、描述以及其内部LinkedList中保存的节点数量。内部LinkedList将保存它们出现的章节号和该章节的简要描述。

例如，人物Joe（姓名）是国王（描述），出现在第4、7和10章。所以他将有3个内部节点，并附带了他在这些章节中所做的事情的描述。

但是我认为我没有正确地向LinkedList添加元素，因为当我调用迭代函数并打印每个节点时，只得到了我添加的第一个人物。

以下是我创建的两个结构体：

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

处理一个由链表组成的链表让我感到困惑，也许我只是错过了一些很小的东西，或者可能是一些很大的东西，但任何帮助都将是极好的。几乎忘记了，代码可以编译并输出以下内容...

    Joe, the King 2
4   had a child.

因为它将Joe的计数打印为2，所以我认为它有些起作用。

- John

---

在 add 函数中，您需要实际分配 last_pers->next = temp_pers（其中 last_pers 需要指向列表中的最后一个人）。 - Klas Lindbäck

一个错误修正是，在内部 while 循环之前，您需要将 temp_info 更新为正确的内部链表头，例如：temp_info = temp_pers->info_head; 假设内部列表是独立列表，不相互连接，那么您就不需要全局 head_info。 - Selçuk Cihan

哦，好的，@SelçukCihan，我会进行修复。 - John

@KlasLindbäck，不就是通过遍历列表来实现吗？ - John

遍历列表后，temp_person 指向 NULL。在此之后分配 temp_person 不会更改列表中最后一项的 next 指针。 - Klas Lindbäck

@Shane，在C语言中使用malloc时不需要进行强制类型转换：https://dev59.com/dHRB5IYBdhLWcg3wgHWr - CIsForCookies

Answer 1

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

- M Oehm

---

谢谢！这样做更有意义，所有其他内容都应该是本地的！你是对的，将所有内容分解成更多的方法使其更易于阅读和理解。你的代码帮了很大的忙，谢谢。 - John

Answer 2

正如您所看到的，您的代码打印出了第一个节点和子节点：("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)时间)来实现。

- CIsForCookies

---

你的修复方法不起作用。head_pers 总是指向第一个项目，因此你的修复方法将列表限制为2个项目。他需要找到最后一个项目（其中 ->next == NULL），并将其 next 指针设置为新人。 - Klas Lindbäck

@KlasLindbäck 你说得对。那只会修复第二个元素。我会添加通用的修复方法。谢谢你指出这个问题。 - CIsForCookies

Answer 3

在循环后，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;

- Klas Lindbäck

---

我将其更改为结构体Person * las_pers;，现在它可以工作了一点...现在它会打印出'Joe, the King 2 4 had a child. Joe, the King 12 Sue, the Queen 7'。 - John

谢谢，那是我的笔误。 - Klas Lindbäck