程序链表中的链表

Question

假设我想创建一个图书列表，这些书有一个或多个作者，以及书中的主要人物。为此创建结构的最佳方法是什么？下面的内容是准确的，还是不同的设置？

struct name
{
char prefix[5];
char first[50];
char middle[50];
char last[50];
char suffix[5];
struct name *next; /* linked list   */
struct name *previous; /* linked list   */
};


struct book
{
 struct name authors;  
 struct name main_characters;
char title[100];   
char publisher[100]; 

结构书*下一步；结构书*前一本；

};

Answer 1

我认为您的计划很好，使用authors和main_characters的指针。当您对书籍、作者和主要人物使用侵入式链接列表时，您可能会发现将链接列表结构和操作分解出来很有帮助。

如果您声明这样的结构：

struct node
{
    struct node *next;
    struct node *previous;
};
typedef struct node node;

您可以将其作为第一个元素嵌入到每个类型中：

struct name
{
    node linked_list;
    char name_prefix[10];
    char name_first[50];
    char name_middle[50];
    char name_last[50];
    char name_suffix[5];
};

struct book
{
    node linked_list;
    name *authors;  
    name *main_characters;

    /* variables for book */
    char title[100];   /* the title of the book */
    char publisher[100]; /* publisher */
    //etc.
};

这使您的类型成为 type。然后，可以根据node类型定义链接列表操作：

void 
node_add_node(node **head, node *object)
{
    if (*head == NULL) {
        *head = object;
    }
    else {
        node *current, *previous;
        for (current = *head; current != NULL; current = current->next) {
            previous = current;
        }
        previous->next = object;
    }
}

然后定义类型安全操作，将图书添加到图书和图书名称列表中：

void 
books_add_book(struct book **books, struct book *book)
{
    node_add_node((node**)books, (node*)book);
}

void
book_add_author(struct book *book, struct name *author)
{
    node_add_node((node**)&book->authors, (node*)author);
}

void
book_add_main_character(struct book *book, struct name *character)
{
    node_add_node((node**)&book->main_characters, (node*)character);
}

然后，实现构造函数：

void node_init(node *node)
{
    node->previous = NULL;
    node->next = NULL;
}

struct book *
book_create(const char *title, const char *publisher)
{
    struct book *b = malloc(sizeof(book));
    if (b) {
        node_init(&b->linked_list);
        b->authors = NULL;
        b->main_characters = NULL;
        strcpy(b->title, title);
        strcpy(b->publisher, publisher);
    }
    return b;
}

struct name *
name_create(const char *prefix, const char *first, const char *middle, 
    const char *last, const char *suffix)
{
    name *n = malloc(sizeof(name));
    if (n) {
        node_init(&n->linked_list);
        strcpy(n->name_prefix, prefix);
        strcpy(n->name_first, first);
        strcpy(n->name_middle, middle);
        strcpy(n->name_last, last);
        strcpy(n->name_suffix, suffix);
    }
    return n;
}

然后，您可以创建这样的书籍(注意事项：我将name_prefix的大小增加到10)：

 struct book *books = NULL;
 struct book *b = book_create("War and Peace", "Wordsworth");
 struct name *n = name_create("Count", "Lev", "Nikolayevich", "Tolstoy", "");
 book_add_author(b, n);
 n = name_create("Count", "Pyotr", "Kirillovich", "Bezukhov", "");
 book_add_main_character(b, n);
 n = name_create("Countess", "Natalya", "Ilyinichna", "Rostova", "");
 book_add_main_character(b, n);
 books_add_book(&books, b);

Answer 2

为此创建结构的最佳方法是什么？

什么是最好的取决于问题的细节，并在某种程度上取决于意见。

下面的内容是准确的，还是不同的设置？

你提出的两种选择看起来都是合理的。

第一种选择，即两个名称struct本身是图书struct的成员，在某些情况下可能会更方便一些，因为需要较少的动态分配。另一方面，它使每个内部链接列表的第一个元素成为一个特例，这可能会使您的代码总体上更加复杂。

第二种选择是，书中的struct包含指向两个名称struct的指针，它提供了更多的一致性，并且更好地适应了一个或两个内部列表都为空的可能性。考虑到所有的事情，这就是我可能会选择的。

Answer 3

您需要的数据结构大部分时间都是根据您拥有的数据类型和您想要在其上执行的操作来决定的。

链接清单适用于下列需要：

1. 频繁插入和删除数据
2. 数据的数量可能不适合在一个地方/或可用的第一次。

它附带以下问题：

1. 搜索和检索数据的速度慢
2. 在代码中增加更多的复杂性和方向。

据我所见，字符串的动态数组(char数组)对于authors来说已经足够了，或者，如果粒度是您所关心的问题，您也可以使用指向struct name的指针数组，因为一本书可能有多个作者。

如果您想要静态数组，请执行以下操作：

#define MAX_AUTHOR_LIMIT 10
struct boook {
    ...
    struct name *authors[MAX_AUTHOR_LIMIT];
    int author_count;
    ...
}

或者，如果您想做得更好，也可以使用动态数组。

链接列表也是另一种选择，但对于不需要频繁插入删除的少量数据项，使用链接并不是一个好主意，但正如我所指出的，您知道应用程序需要在权衡的基础上做哪些决定。