回 帖 发 新 帖 刷新版面

主题:链表中使用二重指针的优点有什么

看有些链表中定义的item,并非使用 *next, *prev,

而是向前指针使用二重指针

类似如下这种:
struct QUEUE_ITEM *tqe_next;      
struct QUEUE_ITEM **tqe_prev;  

请问这样做有什么好处吗,感觉跟直接使用*prev没什么区别,想不太明白

回复列表 (共11个回复)

11 楼

我觉得主要的区别在于头节点。
如果用一级指针(prev指向前一个节点),则头节点和其它节点都应该用相同类型的struct(因为头节点之后的第一个节点的prev指针需要指向头节点)。
如果用二级指针(prev指向前一个节点的next指针),则头节点和其它节点不必是相同类型的struct,只要大家都有next指针即可。

看看原帖:http://www.iteye.com/topic/292836
其中有一段代码如下,
5.struct QUEUE_ITEM{  
6.    int value;  
7.    TAILQ_ENTRY(QUEUE_ITEM) entries;  
8.};  
9.TAILQ_HEAD(,QUEUE_ITEM) queue_head;  
宏替换之后的结果为:
3.struct QUEUE_ITEM{  
4.    int value;  
5.    struct {  
6.        struct QUEUE_ITEM *tqe_next;  
7.        struct QUEUE_ITEM **tqe_prev;  
8.    }entries;  
9.};  
10.struct {  
11.    struct QUEUE_ITEM *tqh_first;  
12.    struct QUEUE_ITEM **tqh_last;  
13.}queue_head;  

可以看到,头节点的类型是一个匿名struct,只有first(相当于普通节点的next)和last(指向最后一个节点的next)两个指针。而其它节点的类型是struct QUEUE_ITEM,除了prev和next两个指针之外,还有着第三个元素value,用于保存数据。
由于在链表中,头节点不必保存数据,而其它节点则应该保存数据,因此头节点和其它节点使用不同的类型,可以节约一点内存。可见经典的C编程还是很“抠门”的,能省则省。

我来回复

您尚未登录,请登录后再回复。点此登录或注册