找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 3674|回复: 2

【C】语言编写的字典支持各种类型扩展

[复制链接]

9

主题

10

回帖

451

积分

用户组: 中·技术宅

UID
5181
精华
3
威望
39 点
宅币
260 个
贡献
79 次
宅之契约
0 份
在线时间
42 小时
注册时间
2019-7-25
发表于 2020-10-22 22:24:14 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
本帖最后由 天马座 于 2020-11-1 09:33 编辑
  1. #include "stdlib.h"
  2. #include "string.h"
  3. struct dictionary_node
  4. {
  5.         void *key;
  6.         void *value;
  7.         struct dictionary_node *next;
  8.        
  9. };
  10. struct dictionary_object
  11. {
  12.         struct dictionary_node *head;
  13.         struct dictionary_node *tail;
  14.         unsigned long count;
  15.         unsigned long key_vt;
  16.         unsigned long value_vt;
  17. };
  18. enum VARENUM //添加类型的时候在这里定义类型的标识
  19. {
  20.         VT_INT = 4,
  21.         VT_PCHAR = 8,
  22. } ;
  23. struct dictionary_object* dictionary_create(const unsigned long key_vt, const unsigned long value_vt); //创建一个字典
  24. void dictionary_release(struct dictionary_object* dict); //释放一个字典
  25. unsigned long dictionary_count(const struct dictionary_object *dict);        //字典元素数量
  26. int dictionary_contains(const struct dictionary_object* dict,const void *key);//判断一个KEY是否存在 这里返回的是节点地址
  27. void* dictionary_value(const struct dictionary_object* dict,const void *key);//获取KEY对应的VALUE的指针
  28. void dictionary_add(struct dictionary_object* dict,const void *key,const void *value);//添加元素
  29. void dictionary_remove(struct dictionary_object* dict,const void *key);//删除KEY对应的节点
  30. struct dictionary_node* __dictionary_get(const struct dictionary_object* dict,const void *key);//获取KEY所在的节点
  31. //扩展类型修改添加以下内容
  32. int __dictionary_typedef_size(const unsigned long vt,const void *var);//获取字典对象定义的类型
  33. void* __dictionary_select_callback(const unsigned long vt);//选择比较KEY的回调函数
  34. int __intcmp(const void *a ,const void *b);
  35. unsigned long  dictionary_count(const struct dictionary_object *dict){
  36.         return dict->count;
  37. }
  38. struct dictionary_object* dictionary_create(const unsigned long key_vt, const unsigned long value_vt)
  39. {
  40.         struct dictionary_object *p = (struct dictionary_object *)malloc(sizeof(struct dictionary_object));
  41.         if (p != NULL) {//此处应该加上对key_vt和value_vt的正确性判断
  42.                 p->head = NULL;
  43.                 p->tail = NULL;
  44.                 p->count = 0;
  45.                 p->key_vt = key_vt;
  46.                 p->value_vt = value_vt;
  47.         }
  48.         return p;
  49. }
  50. void dictionary_release(struct dictionary_object* dict)
  51. {
  52.         if (dict == NULL)
  53.                 return;
  54.         struct dictionary_node *p = dict->head;
  55.         while(p != NULL){
  56.                 struct dictionary_node *tmp = p;
  57.                 p = p->next;
  58.                 free(tmp->key);
  59.                 free(tmp->value);
  60.                 free(tmp);
  61.         }
  62.         free(dict);
  63.        
  64. }
  65. int dictionary_contains(const struct dictionary_object* dict,const void *key)
  66. {
  67.         return (int)__dictionary_get(dict,key);
  68. }
  69. struct dictionary_node* __dictionary_get(const struct dictionary_object* dict,const void *key)
  70. {
  71.         if (dict == NULL)
  72.                 return NULL;
  73.         int(*cmp)(const void * ,const void *) = (int(*)(const void * ,const void *) )__dictionary_select_callback(dict->key_vt);
  74.         struct dictionary_node *p = dict->head;
  75.         while(p != NULL && cmp(p->key,key)){
  76.                 p = p->next;
  77.         }
  78.         return p;
  79. }
  80. void* dictionary_value(const struct dictionary_object* dict,const void *key){
  81.         struct dictionary_node *p = __dictionary_get(dict,key);
  82.         return p == NULL ? p : p->value;
  83.        
  84. }
  85. void dictionary_add(struct dictionary_object* dict,const void *key,const void *value)
  86. {
  87.         if (dict == NULL)
  88.                 return;
  89.         int key_len = __dictionary_typedef_size(dict->key_vt,key);
  90.         int value_len = __dictionary_typedef_size(dict->value_vt,value);
  91.         struct dictionary_node *p = __dictionary_get(dict,key);
  92.         if (p == NULL){
  93.                 struct dictionary_node *node =(struct dictionary_node*)malloc(sizeof(struct dictionary_node));
  94.                 if (node ==NULL)
  95.                     return;
  96.                 if (dict->head == NULL)
  97.                         dict->head = node;
  98.                 else
  99.                         dict->tail->next = node;
  100.                 dict->tail = node;
  101.                 dict->tail->key = malloc(key_len);
  102.                 dict->tail->value = malloc(value_len);
  103.                 memcpy(dict->tail->key,key,key_len);
  104.                 memcpy(dict->tail->value,value,value_len);
  105.                 dict->tail->next=NULL;
  106.                 dict->count+=1;
  107.         }
  108.         else
  109.         {
  110.                 //定长类型这里不用重新分配 设计之后可以修改
  111.                 free(p->value);
  112.                 p->value = malloc(value_len);
  113.                 memcpy(p->value,value,value_len);
  114.         }
  115. }
  116. void dictionary_remove(struct dictionary_object* dict,const void *key){
  117.         if (dict == NULL || dict->head == NULL ) return;
  118.         int(*cmp)(const void * ,const void *) = (int(*)(const void * ,const void *) )__dictionary_select_callback(dict->key_vt);
  119.         if (!cmp(dict->head->key,key)){
  120.                 if (dict->head==dict->tail)
  121.                         dict->tail=NULL;
  122.                 struct dictionary_node *del = dict->head;
  123.                 dict->head = dict->head->next;
  124.                 free(del->key);
  125.                 free(del->value);
  126.                 free(del);
  127.                 dict->count-=1;
  128.         }
  129.         else
  130.         {
  131.                 struct dictionary_node *p = dict->head;
  132.                
  133.                 while(p->next != NULL && cmp(p->next->key,key))
  134.                         p = p->next;
  135.                 if (p->next != NULL){
  136.                         if (p->next == dict->tail)
  137.                                 dict->tail=p;
  138.                         struct dictionary_node *del=p->next;
  139.                         p->next = p->next->next;
  140.                         free(del->key);
  141.                         free(del->value);
  142.                         free(del);
  143.                         dict->count-=1;
  144.                 }
  145.         }
  146.        
  147.        
  148. }
  149. //添加数据类型兼容需要编写以下函数
  150. void* __dictionary_select_callback(const unsigned long vt){
  151.        
  152.         switch(vt)
  153.         {
  154.         case VT_INT:
  155.                 return __intcmp;
  156.         case VT_PCHAR:
  157.                 return strcmp;
  158.         default:
  159.                 return NULL;
  160.         }
  161.        
  162. }
  163. int __dictionary_typedef_size(const unsigned long vt,const void *var){
  164.        
  165.         switch(vt)
  166.         {
  167.         case VT_INT:
  168.                 return sizeof(int);
  169.         case VT_PCHAR:
  170.                 return strlen((char*)var) + 1;
  171.         default:
  172.                 return 0;
  173.         }
  174.        
  175. }
  176. int __intcmp(const void *a ,const void *b){
  177.         if (*(int*)a < *(int*)b)
  178.                 return -1;
  179.         else if (*(int*)b < *(int*)a)
  180.                 return 1;
  181.         else
  182.                 return 0;
  183. }
复制代码

本帖被以下淘专辑推荐:

回复

使用道具 举报

29

主题

315

回帖

1561

积分

用户组: 上·技术宅

UID
3808
精华
11
威望
105 点
宅币
702 个
贡献
165 次
宅之契约
0 份
在线时间
404 小时
注册时间
2018-5-6
发表于 2020-10-23 16:21:58 | 显示全部楼层
你的这个帖子写的非常不错!C语言的知识很扎实,但是,你的这个“字典”,没看错的话,是用单向链表写的吧,可是实际上,字典的查找速度快得很,他是一个哈希结构,你可否进行改进?
Passion Coding!
回复 赞! 靠!

使用道具 举报

9

主题

10

回帖

451

积分

用户组: 中·技术宅

UID
5181
精华
3
威望
39 点
宅币
260 个
贡献
79 次
宅之契约
0 份
在线时间
42 小时
注册时间
2019-7-25
 楼主| 发表于 2020-10-23 16:39:26 | 显示全部楼层
watermelon 发表于 2020-10-23 16:21
你的这个帖子写的非常不错!C语言的知识很扎实,但是,你的这个“字典”,没看错的话,是用单向链表写的吧 ...

改进的话就无法保证添加顺序遍历了,我这个是按照vbs的字典逻辑写的,可以再实现一份哈希的
其实也是链表来写,只不过是用链表数组,一个哈希函数映射key(包括冲突)到链表数组的下标
然后再顺序查找,如果极限的话就映射到树,这个东西就是分享一下思路,写个太复杂的实现意义不大,毕竟很多专业的库都有实现
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-29 18:41 , Processed in 0.037397 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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