【C】语言编写的字典支持各种类型扩展
本帖最后由 天马座 于 2020-11-1 09:33 编辑#include "stdlib.h"
#include "string.h"
struct dictionary_node
{
void *key;
void *value;
struct dictionary_node *next;
};
struct dictionary_object
{
struct dictionary_node *head;
struct dictionary_node *tail;
unsigned long count;
unsigned long key_vt;
unsigned long value_vt;
};
enum VARENUM //添加类型的时候在这里定义类型的标识
{
VT_INT = 4,
VT_PCHAR = 8,
} ;
struct dictionary_object* dictionary_create(const unsigned long key_vt, const unsigned long value_vt); //创建一个字典
void dictionary_release(struct dictionary_object* dict); //释放一个字典
unsigned long dictionary_count(const struct dictionary_object *dict); //字典元素数量
int dictionary_contains(const struct dictionary_object* dict,const void *key);//判断一个KEY是否存在 这里返回的是节点地址
void* dictionary_value(const struct dictionary_object* dict,const void *key);//获取KEY对应的VALUE的指针
void dictionary_add(struct dictionary_object* dict,const void *key,const void *value);//添加元素
void dictionary_remove(struct dictionary_object* dict,const void *key);//删除KEY对应的节点
struct dictionary_node* __dictionary_get(const struct dictionary_object* dict,const void *key);//获取KEY所在的节点
//扩展类型修改添加以下内容
int __dictionary_typedef_size(const unsigned long vt,const void *var);//获取字典对象定义的类型
void* __dictionary_select_callback(const unsigned long vt);//选择比较KEY的回调函数
int __intcmp(const void *a ,const void *b);
unsigned longdictionary_count(const struct dictionary_object *dict){
return dict->count;
}
struct dictionary_object* dictionary_create(const unsigned long key_vt, const unsigned long value_vt)
{
struct dictionary_object *p = (struct dictionary_object *)malloc(sizeof(struct dictionary_object));
if (p != NULL) {//此处应该加上对key_vt和value_vt的正确性判断
p->head = NULL;
p->tail = NULL;
p->count = 0;
p->key_vt = key_vt;
p->value_vt = value_vt;
}
return p;
}
void dictionary_release(struct dictionary_object* dict)
{
if (dict == NULL)
return;
struct dictionary_node *p = dict->head;
while(p != NULL){
struct dictionary_node *tmp = p;
p = p->next;
free(tmp->key);
free(tmp->value);
free(tmp);
}
free(dict);
}
int dictionary_contains(const struct dictionary_object* dict,const void *key)
{
return (int)__dictionary_get(dict,key);
}
struct dictionary_node* __dictionary_get(const struct dictionary_object* dict,const void *key)
{
if (dict == NULL)
return NULL;
int(*cmp)(const void * ,const void *) = (int(*)(const void * ,const void *) )__dictionary_select_callback(dict->key_vt);
struct dictionary_node *p = dict->head;
while(p != NULL && cmp(p->key,key)){
p = p->next;
}
return p;
}
void* dictionary_value(const struct dictionary_object* dict,const void *key){
struct dictionary_node *p = __dictionary_get(dict,key);
return p == NULL ? p : p->value;
}
void dictionary_add(struct dictionary_object* dict,const void *key,const void *value)
{
if (dict == NULL)
return;
int key_len = __dictionary_typedef_size(dict->key_vt,key);
int value_len = __dictionary_typedef_size(dict->value_vt,value);
struct dictionary_node *p = __dictionary_get(dict,key);
if (p == NULL){
struct dictionary_node *node =(struct dictionary_node*)malloc(sizeof(struct dictionary_node));
if (node ==NULL)
return;
if (dict->head == NULL)
dict->head = node;
else
dict->tail->next = node;
dict->tail = node;
dict->tail->key = malloc(key_len);
dict->tail->value = malloc(value_len);
memcpy(dict->tail->key,key,key_len);
memcpy(dict->tail->value,value,value_len);
dict->tail->next=NULL;
dict->count+=1;
}
else
{
//定长类型这里不用重新分配 设计之后可以修改
free(p->value);
p->value = malloc(value_len);
memcpy(p->value,value,value_len);
}
}
void dictionary_remove(struct dictionary_object* dict,const void *key){
if (dict == NULL || dict->head == NULL ) return;
int(*cmp)(const void * ,const void *) = (int(*)(const void * ,const void *) )__dictionary_select_callback(dict->key_vt);
if (!cmp(dict->head->key,key)){
if (dict->head==dict->tail)
dict->tail=NULL;
struct dictionary_node *del = dict->head;
dict->head = dict->head->next;
free(del->key);
free(del->value);
free(del);
dict->count-=1;
}
else
{
struct dictionary_node *p = dict->head;
while(p->next != NULL && cmp(p->next->key,key))
p = p->next;
if (p->next != NULL){
if (p->next == dict->tail)
dict->tail=p;
struct dictionary_node *del=p->next;
p->next = p->next->next;
free(del->key);
free(del->value);
free(del);
dict->count-=1;
}
}
}
//添加数据类型兼容需要编写以下函数
void* __dictionary_select_callback(const unsigned long vt){
switch(vt)
{
case VT_INT:
return __intcmp;
case VT_PCHAR:
return strcmp;
default:
return NULL;
}
}
int __dictionary_typedef_size(const unsigned long vt,const void *var){
switch(vt)
{
case VT_INT:
return sizeof(int);
case VT_PCHAR:
return strlen((char*)var) + 1;
default:
return 0;
}
}
int __intcmp(const void *a ,const void *b){
if (*(int*)a < *(int*)b)
return -1;
else if (*(int*)b < *(int*)a)
return 1;
else
return 0;
} 你的这个帖子写的非常不错！C语言的知识很扎实，但是，你的这个“字典”，没看错的话，是用单向链表写的吧，可是实际上，字典的查找速度快得很，他是一个哈希结构，你可否进行改进？ watermelon 发表于 2020-10-23 16:21
你的这个帖子写的非常不错！C语言的知识很扎实，但是，你的这个“字典”，没看错的话，是用单向链表写的吧 ...
改进的话就无法保证添加顺序遍历了，我这个是按照vbs的字典逻辑写的，可以再实现一份哈希的
其实也是链表来写，只不过是用链表数组，一个哈希函数映射key(包括冲突)到链表数组的下标
然后再顺序查找，如果极限的话就映射到树，这个东西就是分享一下思路，写个太复杂的实现意义不大，毕竟很多专业的库都有实现
页:
[1]