目前我正在为 C 中的常见数据结构创建一个小型库。这主要是为了学习目的,但我确实计划在其他项目中使用这个库,看看它的工作情况和问题所在.到目前为止,我对我的散列和二叉树实现很满意,但我无法决定链表的设计。
到目前为止实现的所有数据结构都使用 void
指针,并且不负责创建或销毁数据,即它们仅引用数据。一个设计目标是使它们尽可能通用,以提高可重用性。
关于链表,目前我发现了三种做法:
专用列表头:列表具有专用列表头,用作抽象数据类型。
Nodes only:和上面的例子一样,除了所有函数都在
list_node
上运行。用于 GLib .在payload中:在payload数据中添加一个
list_node
结构,并用宏计算到payload的偏移量。参见 lists in the linux kernel编辑 使用宏生成类型列表:使用宏创建列表结构和函数的特定类型版本。
1 和 2 的示例:
/* list.h */
typedef struct list_t list;
typedef int (*comparator)(const void* a, const void* b);
list* list_new (comparator c);
void list_delete (list* l);
void list_insert_after (list* l, uint32_t index, void* data);
void list_remove (list* l, void* data);
uint32_t list_size (list* l);
/* other functions operating on lists */
/* list.c */
#include "list.h"
typedef struct list_node_t {
struct list_node_t* next;
struct list_node_t* prev;
void* data;
} list_node;
struct list_t {
list_node* begin;
list_node* end;
uint32_t size;
comparator cmp;
}
现在问题:这些方法中哪种方法最通用?还有其他方法吗?
最佳答案
我更喜欢第二种方法,即仅节点。
它的优点是非常简单,因为大多数列表操作(拆分、推送、弹出、子列表...)的结果本身就是列表。
另请注意,您缺少重要的列表操作,主要是 push()
和 pop()
。您应该利用列表允许在 O(1) 中插入这一事实。
关于c - C中链表实现的设计,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6436996/