技术宅的结界

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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 2231|回复: 2
收起左侧

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

[复制链接]

9

主题

19

帖子

439

积分

用户组: 中·技术宅

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

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

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

x
本帖最后由 天马座 于 2020-11-1 09:33 编辑

[C] 纯文本查看 复制代码
#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 long  dictionary_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;
}

评分

参与人数 1威望 +10 宅币 +30 贡献 +10 收起 理由
watermelon + 10 + 30 + 10 加油!

查看全部评分

本帖被以下淘专辑推荐:

回复

使用道具 举报

29

主题

331

帖子

2004

积分

用户组: 上·技术宅

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

9

主题

19

帖子

439

积分

用户组: 中·技术宅

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

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

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2021-10-29 05:31 , Processed in 0.044509 second(s), 34 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

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