4

我正在用 C 重写我几年前学到的所有数据结构，以增加我对数据结构和 C 语言的理解。我正在做的第一个是单链表，所以我正在为它们设计一个 API。我还没有编写任何实现，但我想获得一些关于我的函数原型的反馈，以确保我所做的事情是明智和合乎逻辑的。

先说几点：

  1. 我希望很多人会建议 node 结构的 typedef，但这是个人决定，我不喜欢 typedef 结构。

  2. 我最不确定我对返回类型和值的选择。我有两个函数返回指向已删除节点的数据变量的指针。这些函数从列表中删除节点，保存指向数据的指针，并释放节点。这意味着用户需要释放返回的数据。这是不好的形式吗？我不确定如何以允许静态返回数据的方式执行此操作，因为这需要提前知道数据的大小，这会削弱库的实用性。

  3. 我想让 API 支持所有可以用单链表完成的有用的事情，其中​​之一是实现堆栈。关于单链表上的推送/弹出操作让我感到困扰的一件事是，似乎有些人脑子里有这样的想法，即推送/弹出应该只发生在列表的末尾。如果您需要在尾部（末尾）进行推送/弹出操作，堆栈是一种后进先出机制 (LIFO)，它不适合单链表。这显然是因为使用尾部而不是列表的头部会非常低效，因为只有遍历列表才能到达最后一个元素。下面的 push/pop 函数模仿堆栈的行为，但操作发生在列表的前面。这是一个糟糕的设计吗？

下面是一个包含元素的列表示例：

[哨兵]->[0]->[1]->[2]->[3]->NULL

每个节点都是结构节点类型。结构节点是具有数据和下一个字段的结构：

struct node {
    void *data;
    struct node *next;
}

此实现将使用哨兵节点来简化边界条件。每个列表有一个哨兵节点，位于列表的最前面。

一个空列表包含一个指向 null 的哨兵节点，如下所示：[SENTINEL]->NULL

列表的类型为 struct sllist。结构 sllist 有一个哨兵字段，其中包含指向哨兵节点的指针：

struct sllist {
    struct node *sentinel;
}

最后，这是一个操作列表及其相关的函数原型（带有描述）：

    //create new list:
    struct *sllist new_sllist();
            //Returns a pointer to a new, empty sllist.

    //destroy list:
    void destroy_sllist(struct sllist *sllist); 
            //Frees the memory of the list struct and all associated nodes.

    //insert after node:    
    int sllist_insert_after(struct sllist *sllist, struct *node, void *data); 
            //Adds a node after the passed node.
            //If allocation fails, returns -1, otherwise returns 0.

    //prepend node to the list:
    int sllist_push(struct sllist *sllist, void *data);
            //Adds a node to the front of the list. If allocation fails, returns -1, otherwise returns 0.
            //Note that the front of the list is defined to be the first node after the sentinel node.

    //extract after node:   
    void* sllist_extract_after(struct sllist *sllist, struct node *node);
            //Removes a node from the linked list, save a pointer to the data, free the node 
            //(but do not the data itself), and return a pointer to the data so that it can be used. 
            //If the node doesn't exist in the list, returns NULL.

    //extract first node:
    void* sllist_pop(struct sllist *sllist);
            //Same as extract after node, but restricted to the first node (first node after sentinel.)
            //Analogous to sllist_push(), the name sllist_pop suggests usage as a stack.

    //destroy after node:
    void sllist_destroy_after(struct sllist *sllist, struct node *node);
            //Removes from the list the node after the passed node and frees all associated memory.

请让我知道是否有任何明显不合时宜、奇怪或设计不佳的地方。

4

1 回答 1

0

链表通常是更高级别数据结构的实现细节，即队列、列表、堆栈等……所以，我会确保实现每个所需的所有操作。push_back, push_front, pop_front, pop_back, front, back, 当然还有随机访问。

对于有效载荷，用户应该负责分配和释放。毕竟，它们可能会传递一个指向堆栈上内存的指针，而您当然不想释放该内存。另一种方法是在插入时制作有效负载的副本（即 memcpy），然后您可以确保内存在弹出时被释放，并且不会对用户造成任何意外行为：这是以数据的线性副本。

此外，您可能会发现将链接列表修改为以下内容会有所帮助：

struct sllist {
struct node *head;
struct node *tail;
struct node *current;
unsigned size;
}
于 2013-05-19T01:47:48.807 回答