AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

linux下C语言实现的哈希链表【转】

2018-01-11 1239
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 转自：http://blog.chinaunix.net/uid-28458801-id-4276934.html 操作系统：ubuntu10.04前言：     在稍微大点的项目中，基本都会遇到算法问题，特别是大数据的查找。

转自：http://blog.chinaunix.net/uid-28458801-id-4276934.html

操作系统：ubuntu10.04

前言：
    在稍微大点的项目中，基本都会遇到算法问题，特别是大数据的查找。
    在当前项目中，使用到了哈希链表。

一，概述
    实现思路：用数组保存哈希桶的关键信息，再用链表链接数据到对应的哈希桶中。
        如：管理很多字符串。以a~z，？为哈希桶。
    

二，实现
    1，结构

点击(此处)折叠或打开

  1. struct    hlist_node     
  2. {
  3.     struct hlist_node     *next;    // 指向下一个结点的指针
  4.     struct hlist_node    **pprev;// 指向上一个结点的next指针的地址
  5. };


  8. struct     hlist_head    
  9. {
  10.     struct hlist_node *first;    // 指向每一个hash桶的第一个结点的指针
  11. };


    2，初始化哈希桶

点击(此处)折叠或打开

  1. // 初始化hash桶的头结点
  2. #define    INIT_HLIST_HEAD(ptr)    ((ptr)->first = NULL)

    

    3，初始化哈希桶中的每一个节点

点击(此处)折叠或打开

  1. // 初始化hash桶的普通结点
  2. static    inline    void    INIT_HLIST_NODE(struct hlist_node *node)
  3. {
  4.     node->next    = NULL;
  5.     node->pprev    = NULL;
  6. }

    

    4，添加节点到哈希桶中

点击(此处)折叠或打开

  1. /**
  2.  * hlist_add_head
  3.  * @n: the element to add to the hash list.
  4.  * @h: the list to add to.
  5.  */
  6. static    inline    void    hlist_add_head(struct hlist_node *n,struct hlist_head *h)    
  7. {
  8.     struct hlist_node    *first = h->first;
  9.     n->next        = first;

  11.     if (first)
  12.         first->pprev    = &n->next;

  14.     h->first     = n;
  15.     n->pprev    = &h->first;
  16. }

    
        

    5，把节点插入到指定节点前面

点击(此处)折叠或打开

  1. /* next must be != NULL */
  2. /* n：要添加的新的节点。
  3.  * next：在next节点之前添加n。
  4.  * 在next节点的前面添加一个新的节点n，在使用这个函数中要特别注意，next不能为NULL。
  5.  */
  6. static    inline    void    hlist_add_before(struct hlist_node *n,
  7.                         struct hlist_node *next)
  8. {
  9.     n->pprev    = next->pprev;
  10.     n->next        = next;
  11.     next->pprev    = &n->next;
  12.     *(n->pprev)    = n;
  13. }

    


    6，把节点插入到指定节点之后

点击(此处)折叠或打开

  1. /* next must be != NULL */
  2. /* n：要添加的新的节点。
  3.  * next：表示在next节点之后添加n。
  4.  * 在next 节点的后面添加一个新的节点n，这里也要求next不能为NULL
  5.  */
  6. static inline void hlist_add_after(struct hlist_node *n,
  7.                     struct hlist_node *next)
  8. {
  9.     n->next = next->next;
  10.     next->next = n;
  11.     n->pprev = &next->next;

  13.     if(n->next)
  14.         n->next->pprev = &n->next;
  15. }

    

    7，删除节点 

点击(此处)折叠或打开

  1. /* n：要删除的节点。
  2.  * 对于删除操作的话，要注意n是不是末尾节点，如果是末尾节点的话，next就是NULL?
  3.  * 所以就没有指向的pprev，就更不能进行相应的修改了，否则进行修改。
  4.  */
  5. static inline void __hlist_del(struct hlist_node *n)
  6. {
  7.     struct hlist_node *next = n->next;
  8.     struct hlist_node **pprev = n->pprev;
  9.     *pprev = next;
  10.     if (next)    
  11.         next->pprev = pprev;
  12. }


  15. /* n：要删除的节点。
  16.  * 在这个函数中首先删除了n节点，之后将n节点的两个指针指向了LIST_POSION，表示不可使用的地方
  17.  */
  18. static inline void hlist_del(struct hlist_node *n)
  19. {
  20.     __hlist_del(n);
  21.     n->next     = LIST_POISON1;
  22.     n->pprev    = LIST_POISON2;
  23. }


    8，判断节点是否在哈希桶中

点击(此处)折叠或打开

  1. /*
  2.  * 判断一个结点是否已经存在于hash桶中
  3.  * 判断h->prev是不是为空，如果pprev的指向是空的话，表示这个节点没有添加到这个链表当中来，
  4.  * 如果是空，返回true，否则返回false
  5.  */
  6. static inline int hlist_unhashed(const struct hlist_node *h)
  7. {
  8.     return !h->pprev;
  9. }


    9，判断哈希桶是否为空

点击(此处)折叠或打开

  1. // 判断一个hash桶是否为空
  2. /* h：struct hlist_head节点指针（hlist链表的头节点）。
  3.  * 判断hlist链表是不是空链表，如果是，返回true，否则返回false。
  4.  */
  5. static inline int hlist_empty(const struct hlist_head *h)
  6. {
  7.     return !h->first;
  8. }


    10，遍历

点击(此处)折叠或打开

  1. /* ptr：表示struct hlist_node类型的一个地址。
  2.  * type：结构体名
  3.  * member：type结构体中的hlist_node成员变量的名称
  4.  * 表示得到ptr所指地址的这个结构体的首地址
  5.  */

  7. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)


  10. /* pos：struct hlist_node类型的一个指针；
  11.  * head：struct hlist_head类型的一个指针，表示hlist链表的头结点。
  12.  * 这个实际上就是一个for循环，从头到尾遍历链表。
  13.  */
  14. #define hlist_for_each(pos, head) \
  15.     for (pos = (head)->first; pos != NULL ; 1; }); \
  16.      pos = pos->next)


  19. /* 这个实际上就是一个for循环，从头到尾遍历链表。这个和前面的不同的是多了一个n，
  20.  * 这么做是为了遍历过程中防止断链的发生。删除时用这个。
  21.  * pos：struct hlist_node类型的一个指针；
  22.  * n：struct hlist_node类型的一个指针；
  23.  * head：struct hlist_head类型的一个指针，表示hlist链表的头结点。
  24.  */
  25. #define hlist_for_each_safe(pos, n, head) \
  26.     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
  27.      pos = n)



  31. /* tops：用来存放遍历到的数据结构的地址，类型是type *；
  32.  * pos：struct hlist_node类型的一个指针；
  33.  * head：hlist链表的头结点；
  34.  * member：struct hlist_node在type结构体中的变量的名称。
  35.  * 在循环中，我们就可以使用tops来指向type类型结构体的任何一个变量了。
  36.  */
  37. /**
  38.  * hlist_for_each_entry    - iterate over list of given type
  39.  * @tpos:    the type * to use as a loop cursor.
  40.  * @pos:    the &struct hlist_node to use as a loop cursor.
  41.  * @head:    the head for your list.
  42.  * @member:    the name of the hlist_node within the struct.
  43.  */
  44. #define hlist_for_each_entry(tpos, pos, head, member)             \
  45.     for (pos = (head)->first;                     \
  46.      (pos != NULL) &&             \
  47.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  48.      pos = pos->next)



  52. /* tops：用来存放遍历到的数据结构的地址，类型是type *；
  53.  * pos：struct hlist_node类型的一个指针；
  54.  * n：struct hlist_node类型的一个指针；
  55.  * head：hlist链表的头结点；
  56.  * member：struct hlist_node在type结构体中的变量的名称。
  57.  * 在循环中，我们就可以使用tops来指向type
  58.  * 类型结构体的任何一个变量了。这个宏函数也是为了防止在遍历的时候删除节点而引入的。
  59.  */
  60. /**
  61.  * hlist_for_each_entry_safe - iterate over list of given type safe against
  62. removal of list entry
  63.  * @tpos:    the type * to use as a loop cursor.
  64.  * @pos:    the &struct hlist_node to use as a loop cursor.
  65.  * @n:        another &struct hlist_node to use as temporary storage
  66.  * @head:    the head for your list.
  67.  * @member:    the name of the hlist_node within the struct.
  68.  */
  69. #define hlist_for_each_entry_safe(tpos, pos, n, head, memsber)          \
  70.     for (pos = (head)->first;                     \
  71.      pos && ({ n = pos->next; 1; }) &&                  \
  72.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  73.      pos = n)



三，实例

点击(此处)折叠或打开

  1. /*
  2.  * hlist begin
  3.  */

  5. #define        CMD_HASH_HEAD_SIZE        27

  7. typedef    struct _cmd_hash_head
  8. {
  9.     struct     hlist_head        head;        // 哈希桶的首地址
  10.     int8_t                    ch;            // 哈希桶的关键字(a~z,?，总共27个)
  11.     int8_t                    offset;        // 这个哈希桶在整个哈希表中的偏移
  12.     int16_t                    count;        // 当前哈希桶中节点的个数
  13. }cmd_hash_head_t;

  15. typedef    struct    _cmd_hash_node
  16. {
  17.     struct    hlist_node        node;
  18.     int8_t                    name[20];
  19. }cmd_hash_node_t;

  21. static    cmd_hash_head_t        cmd_hash[CMD_HASH_HEAD_SIZE];

  23. static    void    cmd_hash_init(void)
  24. {
  25.     int32_t        index = 0;

  27.     memset(cmd_hash,0,sizeof(cmd_hash));

  29.     for(index = 0; index < (CMD_HASH_HEAD_SIZE - 1); index++)
  30.     {
  31.         INIT_HLIST_HEAD(&cmd_hash[index].head);
  32.         cmd_hash[index].count    = 0;
  33.         cmd_hash[index].offset    = index;
  34.         cmd_hash[index].ch        = 'a' + index;
  35.     }    

  37.     index = CMD_HASH_HEAD_SIZE - 1;
  38.     INIT_HLIST_HEAD(&cmd_hash[index].head);
  39.     cmd_hash[index].count    = 0;
  40.     cmd_hash[index].offset    = index;
  41.     cmd_hash[index].ch        = '?';
  42. }

  44. static    void    cmd_hash_show(void)
  45. {
  46.     int32_t        index = 0;

  48.     for (index = 0; index < (CMD_HASH_HEAD_SIZE - 1); index++)
  49.         printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  50.                 cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);

  52.     index = CMD_HASH_HEAD_SIZE - 1;
  53.     printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  54.             cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);
  55. }


  58. static    void    to_lower(int8_t    *str)
  59. {
  60.     int32_t        len     = 0;
  61.     int32_t        index     = 0;

  63.     if (str == NULL)    return;
  64.     len     = strlen((char*)str);

  66.     for (index = 0; index < len; index++)
  67.     {
  68.         str[index] = tolower(str[index]);
  69.     }
  70. }

  72. static    int8_t    node_type(int8_t    *name)
  73. {
  74.     int8_t    ch         = 0x00;
  75.     int8_t    offset     = 0;
  76.     if (name == NULL)    return -1;

  78.     ch    = name[0];
  79.     switch(ch)
  80.     {
  81.         case 'a':
  82.         case 'b':
  83.         case 'c':
  84.         case 'd':
  85.         case 'e':
  86.         case 'f':
  87.         case 'g':
  88.         case 'h':
  89.         case 'i':
  90.         case 'j':
  91.         case 'k':
  92.         case 'l':
  93.         case 'm':
  94.         case 'n':
  95.         case 'o':
  96.         case 'p':
  97.         case 'q':
  98.         case 'r':
  99.         case 's':
  100.         case 't':
  101.         case 'u':
  102.         case 'v':
  103.         case 'w':
  104.         case 'x':
  105.         case 'y':
  106.         case 'z':
  107.             offset = ch - 'a' + 0;
  108.             break;

  110.         default :
  111.             offset = 26;
  112.             break;
  113.     }

  115.     return offset;    
  116. }


  119. //static    cmd_hash_node_t ptr_buffer[100];
  120. static    void    hash_node_init(int8_t    *name)
  121. {
  122.     int8_t        offset = 0;

  124.     cmd_hash_node_t *node_ptr = (cmd_hash_node_t*)calloc(1,sizeof(cmd_hash_node_t));
  125.     

  127.     offset = node_type(name);

  129.     if(offset < 0)    return;

  131.     strlcpy(node_ptr->name, name, strlen((char*)name));
  132.     INIT_HLIST_NODE(&node_ptr->node);
  133.     hlist_add_head(&node_ptr->node,&cmd_hash[offset].head);
  134.     cmd_hash[offset].count++;
  135. }


  138. static    void    cmd_hash_node_init(void)
  139. {
  140.     hash_node_init((int8_t*)"hello");
  141.     hash_node_init((int8_t*)"help");
  142.     hash_node_init((int8_t*)"scan");
  143.     hash_node_init((int8_t*)"???");
  144. }

  146. static    void    cmd_hash_node_show(void)
  147. {
  148.     int32_t        index = 0;
  149.     int16_t        count = 0;
  150.     
  151.     cmd_hash_node_t    *entry = NULL;
  152.     struct hlist_node *ptr = NULL;

  154.     printf("display\n");

  156.     for (index = 0; index < CMD_HASH_HEAD_SIZE; index++)
  157.     {
  158.         count = cmd_hash[index].count;
  159.         if (count > 0)
  160.         {
  161.             printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  162.                 cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);

  164.             hlist_for_each_entry(entry,ptr, &cmd_hash[index].head, node)
  165.             {
  166.                 printf("    name : %s\n",entry->name);
  167.             }    
  168.         }        
  169.     }
  170. }


  173. static    void    test_hlist_oper(void)
  174. {
  175.     cmd_hash_init();
  176.     cmd_hash_show();
  177.     cmd_hash_node_init();
  178.     cmd_hash_show();
  179.     cmd_hash_node_show();    
  180. }


  183. static    void    test_hlist(void)
  184. {
  185.     test_hlist_oper();
  186. }

  188. /*
  189.  * hlist end
  190.  */


    结果：
    




四，参考
1，linux内核源码

【作者】 张昺华
【新浪微博】 张昺华--sky
【twitter】 @sky2030_
【facebook】 张昺华 zhangbinghua
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.
文章标签：
云数据库 ClickHouse
Linux
索引
C语言
关键词：
链表c语言
C语言链表
C语言Linux
Linux链表
Linux C语言
sky-heaven
目录
相关文章
ephemerals__
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
55 4
石小浪♪
|
2月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装，包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
石小浪♪
29 0
ephemerals__
|
29天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
42 0
石小浪♪
|
2月前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法，包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除，以及链表的打印等功能。文章通过具体的代码示例，展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除，以及如何清空和销毁链表。
石小浪♪
38 0
单链表之无头链表(C语言版)
石小浪♪
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表，并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现，以及一个示例程序来演示这些操作。
石小浪♪
29 0
可能只会写BUG
|
3月前
|
Shell Linux API
C语言在linux环境下执行终端命令
本文介绍了在Linux环境下使用C语言执行终端命令的方法。首先，文章描述了`system()`函数，其可以直接执行shell命令并返回结果。接着介绍了更强大的`popen()`函数，它允许程序与命令行命令交互，并详细说明了如何使用此函数及其配套的`pclose()`函数。此外，还讲解了`fork()`和`exec`系列函数，前者创建新进程，后者替换当前进程执行文件。最后，对比了`system()`与`exec`系列函数的区别，并针对不同场景推荐了合适的函数选择。
可能只会写BUG
82 1
1387503158665997
|
3月前
|
Linux
linux内核中的几种链表
linux内核中的几种链表
1387503158665997
21 0
梦笔生花伟
|
5月前
|
Linux C语言 Windows
C语言文件编程-Linux环境下运行
本文介绍了在Linux环境下使用C语言进行文件编程时的两种主要接口：C标准库函数与Linux系统调用。C标准库提供了`fopen`, `fread`, `fwrite`, 和 `fclose`等函数，适用于普通文件操作；而Linux系统调用如`open`, `read`, `write`, 和 `close`则更适合处理设备文件，同时也可用于普通文件。这两种方法的主要区别在于前者使用文件指针，后者使用文件描述符。文章还给出了两个示例程序：一个使用C标准库函数实现文件复制，另一个则使用Linux系统调用完成相同任务。
梦笔生花伟
63 2
TiAmoZhang
|
5月前
|
存储 数据管理 C语言
C语言实战 | 使用链表完成“贪吃蛇”游戏
【7月更文挑战第1天】整体思维，即系统思维，强调以整体视角理解事物。在编程中，结构体体现这种思想，将相关变量打包处理。示例展示了如何用链表而非数组实现“贪吃蛇”游戏，链表提供了更灵活的动态数据管理。一系列代码图片详细描绘了链表结构体在游戏中的应用，包括节点定义、移动、碰撞检测等，凸显了使用链表的优势和代码的清晰组织。
TiAmoZhang
50 0
C语言实战 | 使用链表完成“贪吃蛇”游戏
7fa6b5ui5pmtk
|
6月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
32 2

热门文章

最新文章

  • 1
    [剑指offer] 复杂链表的复制
  • 2
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 3
    LeetCode 21：合并两个有序链表 Merge Two Sorted Lists
  • 4
    [LeetCode] Rotate List 旋转链表
  • 5
    线性表概述及单链表的Java实现
  • 6
    从尾到头打印链表
  • 7
    [LintCode] Swap Two Nodes in Linked List 交换链表中的两个结点
  • 8
    IAM页，IAM链表，分配单元
  • 9
    【转】数据结构链表操作之双链表的基本操作
  • 10
    [剑指offer] 反转链表
  • 1
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    49
  • 2
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    50
  • 3
    操作系统实战（一）（linux+C语言）
    123
  • 4
    C语言学习
    38
  • 5
    C语言：深入补码计算原理
    72
  • 6
    C语言：预处理
    59
  • 7
    C语言：编译与链接
    44
  • 8
    C语言：文件操作
    47
  • 9
    C语言：动态内存管理
    56
  • 10
    C语言：自定义类型 - 结构体 & 联合体 & 枚举
    48

    • 相关课程

    更多
  • Linux高级网络应用 - 网络管理与配置实战
  • Linux MySQL服务器搭建与应用
  • 计算机基础与Linux入门
  • Linux基本命令
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • Alibaba Cloud Linux 3 发布
  • ECS系统指南之Linux系统诊断
  • ECS运维指南 之 Linux系统诊断

    • 相关实验场景

    更多
  • 使用计算巢企业应用，一键获取专属的Linux服务器管理软件
  • 部署Linux主机管理系统WDCP
  • 快速配置Linux云服务器
  • 基于Linux命令实现WordPress手动建站
  • Linux系统的安全登录
  • Linux指令入门-文件管理

    • 推荐镜像

    更多
  • mxlinux-iso
  • archlinuxarm
  • archlinuxcn
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月