dram.me

C语言中的链表

相信但凡学习过编程的人,对于链表都不会陌生。而在C中,语言本身和标准库中都并没有针对链表的接口,这样,作为如些重要的一类数据结构,在编程实践中必然经常需要实现它。所以有必要稍作整理。

在BSD中的queue.h对各类链表提供了比较统一的宏接口,如单链表、双向链表等,可以作为参考。

以下主要总结单向链表的一些实现方式。

最为直接的方法是在需要组织为链表的结构体中添加指向本身的指针,比如在struct user中添加struct user *next成员。这一方法会导致数据抽象并不完美,因为对于struct user来说,*next与它实现的数据抽象无关,同样链表的整体结构要依赖与它的数据。

另一方式就是通过定义struct user_list_node,其中包含两个成员,一个是指向struct user的指针,另一个是指向struct user_list_node的指针。再定义一个struct uer_list指向链表头。这一方式的不足是对于使用struct user_list的代码,需要同时处理struct user_liststruct user_list_node两个结构,使得接口不大明朗。

最后,可以借鉴Lisp中list的思想,将第二种方法中的struct user_liststruct user_list_node合并,这样,任何这个链表结点的指针都是一个完整的链表结构,是原链表的一个子链表。这个方式的不足是在不另外包裹一层结构体的情况下,无法方便地实现向链表尾部追加数据,而这其实也是Lisp中list的一个特点。