找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 6297|回复: 0

[原]随想录(再谈链表)

[复制链接]
发表于 2012-4-24 23:20:34 | 显示全部楼层 |阅读模式
【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】


    在软件开发中,我想链表是除了数组之外,用的最多的一种数据结构。但是,如何把链表结构和数据本身能够完美地融合在一起,这本身确是一件复杂的事情。但是linux kernel在这方面为我们做出了示范,让我们在充分地享受方便的同时,无需考虑链表的一些具体操作。那么,在linux kernel下面,链表是怎么做到的呢?我们可以自己编写一个代码示范一下,基本原理都是一样的,可能在实现方式上略有不同。


(1)定义链表的基本结构
  1. typedef struct _LINK_NODE
  2. {
  3.         struct _LINK_NODE* prev;
  4.         struct _LINK_NODE* next;
  5. }LINK_NODE;
复制代码


(2)定义链表的基本操作
  1. void link_init(struct _LINK_NODE* pNode)
  2. {
  3.         ASSERT(NULL != pNode);
  4.         pNode->prev = NULL;
  5.         pNode->next = NULL;
  6. }
  7. void link_add(struct _LINK_NODE* pNode, struct _LINK_NODE* head)
  8. {
  9.         ASSERT(NULL != pNode && NULL != head);
  10.         pNode->next = head->next;
  11.         pNode->prev = head;
  12.         head->next = pNode;
  13.         if(pNode->next)
  14.                 pNode->next->prev = pNode;
  15. }
  16. void link_del(struct _LINK_NODE* pNode)
  17. {
  18.         ASSERT(NULL != pNode);
  19.         pNode->prev->next = pNode->next;
  20.         if(pNode->next)
  21.                 pNode->next->prev = pNode->prev;
  22. }
复制代码
    这里定义了链表的三个基本操作,即初始化、添加和删除。我们在这里设计的时候,为了说明方便,考虑的情况比较简单。这里编写的代码其实是有三个基本前提的:链表存在一个head节点,这个节点永远不删除;链表添加的数据都是放在head后面的;链表虽然是双向链表,但本身并不是循环链表。

(3)在数据中嵌套使用LINK_NODE
  1. typedef struct _DATA_TYPE
  2. {
  3.         LINK_NODE head;
  4.         int value;
  5. }DATA_TYPE;
复制代码
    这里定义了一个简单的数据类型,即为DATA_TYPE。可是,我们记得前面定义的操作都是 关于 LINK_NODE的,那么我们如何才能利用LINK_NODE数据本身访问到DATA_TYPE数据本身呢?其实不难,转化一下数据即可。

(4)利用pNode访问pData
    现在假设存在这样的一个节点pNode,它的地址就是在DATA_TYPE中head的地址,那么怎么才能进行转化呢?我们看看下面的代码是怎么做的?大家也可以自己在编译器上试一试?

  1. #define GET_DATA_ADDRESS(pNode, DATA, head) \
  2.         (DATA*)((char*)(pNode) - (&((DATA*)(0))->head))
复制代码
    这是一个宏,如果需要实际运算的话,应该这么做。

  1. DATA_TYPE* pData =  GET_DATA_ADDRESS(pNode, DATA_TYPE, head);
复制代码
     这中间其实存在一个技巧。那就是我们既然知道pNode的地址,那么只需要知道pNode和pData之间的偏移值就可以了。两者相减一下,获得值就是pData的数值,所以,这里可以利用(&((DATA*)(0))->head)获取这个偏移值,就是这么简单。

(5)利用pNode遍历pData
    因为这里的pNode是一个链表,所以利用pNode遍历pData就十分方便了。根据上面开发的思路,我们这里依然可以利用宏的方法实现pData和pNode之间的自动转换。

  1. #define FOR_EACH_DATA(pNode, pData, DATA, head) \
  2.         for(; \
  3.             pNode && (pData = GET_DATA_ADDRESS(pNode, DATA, head));\
  4.                 pNode = pNode->next)
复制代码
    使用的话依然十分简单,简单输入数据和数据结构类型即可,
  1.         FOR_EACH_DATA(pNode, pData, DATA_TYPE, head)
  2.         {
  3.                 printf("pData->value = %d\n", pData->value);
  4.         }
复制代码
(6)其他

    通常为了使用方便,链表还会引申出更多的功能,比如自定义head节点,添加list的统计函数,或者是修改添加的方式、删除的方式等等。这些功能朋友们自己根据需要可以独立完成。当然,如果大家的思维再发散一下,也可以把这种方法推广到二叉树、平衡二叉树或者是红黑树上面。总之一句话,链表是我们在编程中使用得最多地一种技巧方法,希望朋友们可以多多掌握。



作者:feixiaoxing 发表于2012-4-16 23:39:22 原文链接

您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2024-3-29 10:04 , Processed in 0.013116 second(s), 7 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表