主题:链表中使用二重指针的优点有什么
Garand
[专家分:340] 发布于 2011-06-21 22:33:00
看有些链表中定义的item,并非使用 *next, *prev,
而是向前指针使用二重指针
类似如下这种:
struct QUEUE_ITEM *tqe_next;
struct QUEUE_ITEM **tqe_prev;
请问这样做有什么好处吗,感觉跟直接使用*prev没什么区别,想不太明白
回复列表 (共11个回复)
11 楼
eastcowboy [专家分:25370] 发布于 2011-06-23 00:27:00
我觉得主要的区别在于头节点。
如果用一级指针(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编程还是很“抠门”的,能省则省。
我来回复