LinkedList of LinkedLists C

Question

我试图创建一个将与LinkedLists填充的LinkedList。主LinkedList将保存一个字符的名字和描述，以及在其内部LinkedList中保存了多少个节点。内部LinkedList将保存他们出现的章节编号和该章节的简要描述。例如，角色Joe(名字)是一个国王(描述者)，出现在第4、7和10章。所以他会有三个内部节点来描述他在这些章节中所做的事情。我不认为我添加到列表中是正确的，因为当我调用遍历列表并打印所有内容时，我只得到我添加的第一个人。

我创建的两个结构体。

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 %dn", temp_pers->name, temp_pers->descriptor, temp_pers->count);
        while(temp_info != NULL){
            printf("%dt%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

除了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: %sn", 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: %sn", 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;
}

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)时间)，或者通过在每个add (O(n)时间)

Answer 3

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