如何在c中创建结构的链表

I have 3 types of structures: book, CD (in the CD I have the struct "song"- and the CD contain a list of songs), and a DVD.

我有3种类型的结构:书籍,CD(在CD中我有结构“歌曲” - 和CD包含歌曲列表)和DVD。

I need to create a linked list of products of a store My question is how to create a list of products without knowing which type is the pointer in it. It can be book, CD or DVD.

我需要创建一个商店产品的链接列表我的问题是如何创建一个产品列表,而不知道哪个类型是其中的指针。它可以是书,CD或DVD。

(I cannot use unions.)

(我不能使用工会。)

4 个解决方案

#1

Leaving the implementation of the CD / DVD data structures up to you, as well as the implementation of the linked list, you would probably want to do something like this:

保留CD / DVD数据结构的实现,以及链表的实现,你可能想要做这样的事情:

enum ptype {
    PTYPE_BOOK,
    PTYPE_CD,
    PTYPE_DVD,
};

struct book {
    char *author;
    char *title;
    char *publisher;
    char *isbn;
};

struct product {
    enum ptype type;
    void *data;
};

struct product_list {
    struct product *product;
    struct product_list *next;
};

The enumeration is responsible for distinguishing the type of product being pointed to. To create a book, for instance:

枚举负责区分所指向的产品类型。要创建一本书,例如:

struct product *
create_book(char *author, char *title, char *publisher, char *isbn)
{
    struct product *p;
    struct book *b;

    p = calloc(1, sizeof (*p));
    if (p == NULL) {
        return NULL;
    }
    p->type = PTYPE_BOOK;
    p->data = calloc(1, sizeof(*b));
    if (p->data == NULL) {
        free(p);
        return NULL;
    }
    b = p->data;

    b->author = author;
    b->title = title;
    b->publisher = publisher;
    b->isbn = isbn;

    return p;
}

This is a typical interface when unions can't be used for whatever reason. It's unfortunate in that it requires much more memory allocation (and in reality, you'll probably have to strdup(3) author / title / publisher / isbn).

当工会因任何原因无法使用时,这是一个典型的界面。不幸的是,它需要更多的内存分配(实际上,你可能不得不强调(3)author / title / publisher / isbn)。

To retrieve a book from a product, you might like to have something like this:

要从产品中检索图书,您可能希望得到以下内容:

static inline struct book *
get_book(struct product *p)
{

    assert(p->type == PTYPE_BOOK);
    return p->data;
}

You don't need to (and shouldn't) cast a void pointer in C. If you're using or supporting a C++ compiler, you may need to use return (struct book *)p->data;. You'd implement something similar for your CD and DVD types. Then, when you need to extract the product:

您不需要(也不应该)在C中转换void指针。如果您正在使用或支持C ++编译器,则可能需要使用return(struct book *)p-> data;。您将为CD和DVD类型实现类似的功能。然后,当您需要提取产品时:

switch (p->type) {
case PTYPE_BOOK:
    b = get_book(p);
    break;
case PTYPE_CD:
    c = get_cd(p);
    break;
case PTYPE_DVD:
    d = get_dvd(p);
    break;
}

You may also want to look at using something other than a linked list for storing these things, especially if they will be read / traversed many times after they are created. (A vector would not be a bad idea). If you know how many items you'll have, this can help reduce the number of allocations you must perform, and the contiguous memory access will improve speed.

您可能还希望使用链接列表以外的其他内容来存储这些内容,尤其是在创建它们之后将多次读取/遍历它们。 (矢量不是一个坏主意)。如果你知道你将拥有多少项,这可以帮助减少你必须执行的分配数量,连续的内存访问将提高速度。

If you need to search entries, I suspect you'll need an external searchable data structure anyway.

如果您需要搜索条目,我怀疑您无论如何都需要一个外部可搜索的数据结构。

#2

You need to use void pointers for the data set. Here is a snippet of code from my linked list structures I use modified for your need:

您需要为数据集使用void指针。以下是我根据您的需要修改的链表结构中的代码片段:

#define CD 1
#define DVD 2
#define BOOK 3

/* Structure for linked list elements */
typedef struct ListElmt_ {
        void *data;
        unsigned datatype;    /* variable to know which data type to cast as */
        struct ListElmt_ *next;
} ListElmt;

#define list_data(element) ((element)->data)

Using the void pointer to pack your data into the list, you can now just test the datatype variable and uncast as necessary. I use a macro to return list data (defined above). So you could use something like:

使用void指针将数据打包到列表中,您现在可以只测试数据类型变量并根据需要取消播放。我使用宏来返回列表数据(如上所述)。所以你可以使用类似的东西:

CD_struct *cd_data
if (element->datatype == CD)
      cd_data = (CD_struct *) list_data(ListElmt)

#3

if every struct has ITEMTYPE is first member, you can use LinkedList.itemtype on all

如果每个结构都有ITEMTYPE是第一个成员,则可以在所有结构上使用LinkedList.itemtype

this is because the offset to itemtype does not depend on inner struct order, since by rule i said itemtype is same type in all and first in all

这是因为对itemtype的偏移不依赖于内部结构顺序,因为通过规则i,所述itemtype在所有中都是相同的类型,并且首先在所有

#4

One way could be :

一种方法可能是:

• Create a generic Structure 'Product'

创建通用结构'产品'

• Keep a variable to keep track of the current type of product.

保留变量以跟踪当前的产品类型。

• Keep three pointers of Book, CD & DVD each.

保留Book,CD和DVD三个指针。

Or As in Archie's Comment :

或者在Archie的评论中:

• Create a generic Structure 'Product'

创建通用结构'产品'

• Keep a variable to keep track of the current type of product.

保留变量以跟踪当前的产品类型。

• Keep a void * pointer & cast when needed.

在需要时保持void *指针和强制转换。

I think the first one is useful, if at a later stage, the product can be of multiple type. Eg - Book + CD

我认为第一个是有用的,如果在稍后阶段,产品可以是多种类型。例如 - 书+ CD