`

（第五章 1）组合——从DList到HashTable

 
阅读更多

       在HashTable中，用到了DList来解决冲突，我们不用重新实现其内部的DList，只需将已经实现的双向链表DList组合到HashTable中使用即可。下面给出工程的全部代码：



就不再解释其中每个文件干嘛的了，我懂的。 依次来看看：

 

1. Makefile

-D name: Predefine name as a macro. (man gcc可以看到)

 

2. typedef.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#ifndef TYPEDEF_H
#define TYPEDEF_H

typedef enum _Ret
{
	RET_OK,
	RET_OOM,
	RET_STOP,
	RET_INVALID_PARAMS,
	RET_FAIL
}Ret;

typedef void     (*DataDestroyFunc)(void* ctx, void* data);
typedef int      (*DataCompareFunc)(void* ctx, void* data);
typedef Ret      (*DataVisitFunc)(void* ctx, void* data);
typedef int       (*DataHashFunc)(void* data);

#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END   }
#else
#define DECLS_BEGIN
#define DECLS_END
#endif/*__cplusplus*/

#define return_if_fail(p) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n", \
		__func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n",\
	__func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}

typedef Ret (*SortFunc)(void** array, size_t nr, DataCompareFunc cmp);

#endif/*TYPEDEF_H*/

 

 

3. hash_table.h

#include <stdio.h>
#include "typedef.h"

#ifndef HASH_TABLE_H
#define HASH_TABLE_H

DECLS_BEGIN

struct _HashTable;
typedef struct _HashTable HashTable;

HashTable* hash_table_create(DataDestroyFunc data_destroy, void* ctx, DataHashFunc hash, int slot_nr);

size_t   hash_table_length(HashTable* thiz);
Ret      hash_table_insert(HashTable* thiz, void* data);
Ret      hash_table_delete(HashTable* thiz, DataCompareFunc cmp, void* data);
Ret      hash_table_find(HashTable* thiz, DataCompareFunc cmp, void* data, void** ret_data);
Ret      hash_table_foreach(HashTable* thiz, DataVisitFunc visit, void* ctx);

void hash_table_destroy(HashTable* thiz);

DECLS_END

#endif/*HASH_TABLE*/

 

 

4.hash_table.c

#include "dlist.h"
#include "hash_table.h"

struct _HashTable
{
	DataHashFunc    hash;
	DList**         slots;
	size_t          slot_nr;
	DataDestroyFunc data_destroy;
	void*           data_destroy_ctx;
};

HashTable* hash_table_create(DataDestroyFunc data_destroy, void* ctx, DataHashFunc hash, int slot_nr)
{
	HashTable* thiz = NULL;

	return_val_if_fail(hash != NULL && slot_nr > 1, NULL);
	
	thiz = (HashTable*)malloc(sizeof(HashTable));

	if(thiz != NULL)
	{
		thiz->hash = hash;
		thiz->slot_nr  = slot_nr;
		thiz->data_destroy_ctx = ctx;
		thiz->data_destroy = data_destroy;
		if((thiz->slots = (DList**)calloc(sizeof(DList*)*slot_nr, 1)) == NULL)
		{
			free(thiz);
			thiz = NULL;
		}
	}

	return thiz;
}

Ret      hash_table_insert(HashTable* thiz, void* data)
{
	size_t index = 0;

	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

	index = thiz->hash(data)%thiz->slot_nr;
	if(thiz->slots[index] == NULL)
	{
		thiz->slots[index] = dlist_create(thiz->data_destroy, thiz->data_destroy_ctx);
	}

	return dlist_prepend(thiz->slots[index], data);
}

Ret      hash_table_delete(HashTable* thiz, DataCompareFunc cmp, void* data)
{
	int index = 0;
	DList* dlist = NULL;

	return_val_if_fail(thiz != NULL && cmp != NULL, RET_INVALID_PARAMS);

	index = thiz->hash(data)%thiz->slot_nr;
	dlist = thiz->slots[index];
	if(dlist != NULL)
	{
		index = dlist_find(dlist, cmp, data);
	
		return dlist_delete(dlist, index);
	}

	return RET_FAIL;
}

size_t   hash_table_length(HashTable* thiz)
{
	size_t i = 0;
	size_t nr = 0;

	return_val_if_fail(thiz != NULL, 0);

	for(i = 0; i < thiz->slot_nr; i++)
	{
		if(thiz->slots[i] != NULL)
		{
			nr += dlist_length(thiz->slots[i]);
		}
	}

	return nr;
}

Ret    hash_table_find(HashTable* thiz, DataCompareFunc cmp, void* data, void** ret_data)
{
	int index = 0;
	DList* dlist = NULL;
	return_val_if_fail(thiz != NULL && cmp != NULL && ret_data != NULL, RET_INVALID_PARAMS);
	
	index = thiz->hash(data)%thiz->slot_nr;
	dlist = thiz->slots[index];
	if(dlist != NULL)
	{
		index = dlist_find(dlist, cmp, data);

		return dlist_get_by_index(dlist, index, ret_data);
	}

	return RET_FAIL;
}

Ret      hash_table_foreach(HashTable* thiz, DataVisitFunc visit, void* ctx)
{
	size_t i = 0;
	
	return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

	for(i = 0; i < thiz->slot_nr; i++)
	{
		if(thiz->slots[i] != NULL)
		{
			dlist_foreach(thiz->slots[i], visit, ctx);
		}
	}

	return RET_OK;
}

void hash_table_destroy(HashTable* thiz)
{
	size_t i = 0;

	if(thiz != NULL)
	{
		for(i = 0; i < thiz->slot_nr; i++)
		{
			if(thiz->slots[i] != NULL)
			{
				dlist_destroy(thiz->slots[i]);
				thiz->slots[i] = NULL;
			}
		}

		free(thiz->slots);
		free(thiz);
	}

	return;
}

#ifdef HASH_TABLE_TEST
#include "test_helper.c"

int main(int argc, char* argv[])
{
	int i = 0;
	int n = 10000;
	int ret_data = 0;
	HashTable* hash_table = hash_table_create(NULL, NULL, hash_int, 31);

	for(i = 0; i < n; i++)
	{
		assert(hash_table_length(hash_table) == i);
		assert(hash_table_insert(hash_table, (void*)i) == RET_OK);
		assert(hash_table_length(hash_table) == (i + 1));
		assert(hash_table_find(hash_table, cmp_int, (void*)i, (void**)&ret_data) == RET_OK);
		assert(ret_data == i);
	}

	for(i = 0; i < n; i++)
	{
		assert(hash_table_delete(hash_table, cmp_int, (void*)i) == RET_OK);
		assert(hash_table_length(hash_table) == (n - i -1));
		assert(hash_table_find(hash_table, cmp_int, (void*)i, (void**)&ret_data) != RET_OK);
	}
	
	hash_table_destroy(hash_table);

	return 0;
}
#endif/*HASH_TABLE_TEST*/

 

5. 最后来复习一下以前写的几个文件

typedef.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#ifndef TYPEDEF_H
#define TYPEDEF_H

typedef enum _Ret
{
	RET_OK,
	RET_OOM,
	RET_STOP,
	RET_INVALID_PARAMS,
	RET_FAIL
}Ret;

typedef void     (*DataDestroyFunc)(void* ctx, void* data);
typedef int      (*DataCompareFunc)(void* ctx, void* data);
typedef Ret      (*DataVisitFunc)(void* ctx, void* data);
typedef int       (*DataHashFunc)(void* data);

#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END   }
#else
#define DECLS_BEGIN
#define DECLS_END
#endif/*__cplusplus*/

#define return_if_fail(p) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n", \
		__func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n",\
	__func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}

typedef Ret (*SortFunc)(void** array, size_t nr, DataCompareFunc cmp);

#endif/*TYPEDEF_H*/

 

dlist.h

#include <stdio.h>
#include "typedef.h"

#ifndef DLIST_H
#define DLIST_H

DECLS_BEGIN

struct _DList;
typedef struct _DList DList;

DList* dlist_create(DataDestroyFunc data_destroy, void* ctx);

Ret dlist_insert(DList* thiz, size_t index, void* data);
Ret dlist_prepend(DList* thiz, void* data);
Ret dlist_append(DList* thiz, void* data);
Ret dlist_delete(DList* thiz, size_t index);
Ret dlist_get_by_index(DList* thiz, size_t index, void** data);
Ret dlist_set_by_index(DList* thiz, size_t index, void* data);
size_t   dlist_length(DList* thiz);
int      dlist_find(DList* thiz, DataCompareFunc cmp, void* ctx);
Ret      dlist_foreach(DList* thiz, DataVisitFunc visit, void* ctx);

void dlist_destroy(DList* thiz);

DECLS_END

#endif/*DLIST*/

 
 

 

 

  • 大小: 5.6 KB
  • 大小: 7.5 KB
分享到：
| （第四章 3）锁与嵌套锁的实现
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Dlist_链表_

    1. 构造函数`Dlist()`通常初始化为空链表，头尾指针为`nullptr`，大小为0。 2. 析构函数`~Dlist()`需要负责释放链表中的所有节点，防止内存泄漏。 3. `insert(int value, int index)`函数在指定位置插入新值，需要...

    dlist:以及它在 elixir 中的实现

    第first和last操作是最坏情况 O(n)。 to_list也是 O(n) 最坏的情况。 alias Dlist . Dequedeque = Deque . newdeque = Deque . append (deque, 2 )deque = Deque . append (deque, 3 )deque = Deque . prepend ...

    Dlist.cpp

    Dlist.cpp

    dlist：Haskell中的差异列表

    import Data.DList -- 创建一个差异列表，表示在任何列表后面添加1,2,3 dl = singleton 1 &lt;&gt; singleton 2 &lt;&gt; singleton 3 -- 将差异列表应用于空列表，得到[1,2,3] normalList = execDList dl [] -- 使用差异列表...

    Dlist2.rar_C/C++_

    在C/C++中，这个过程可能涉及到遍历链表，查找满足特定条件的节点，然后从链表中移除这些节点。这涉及到对链表结构的深入理解和操作，包括节点的指针操作和内存管理。 在提供的压缩包中，"Dlist2.c"可能是源代码...

    dlist:实验性 Javascript 双向链表

    dlist（未经测试） 用 Javascript 编写的双向链表数据结构。 这是一个 Javascript 和伪经典模式的实验。列表（[元素...]） 列表取决于ddict字典对象。 继承的字典方法用于管理 List 状态： seed, cursor并允许使用...

    python利用os模块编写文件复制功能——copy()函数用法

    dlist = os.listdir(dir1) os.mkdir(dir2) for f in dlist: file1 = os.path.join(dir1, f) file2 = os.path.join(dir2, f) if os.path.isfile(file1): mycopy(file1, file2) elif os.path.isdir(file1): ...

    matlab资源 “使用 MATLAB 掌握编程”的课程文件、编程作业和最终项目的集合 仅供学习参考用代码.zip

    6. **Week5-Object_Oriented_Programming**：第五周专注于面向对象编程，包含多个与"DList"相关的文件，如"DList_5.m", "DList_v5.m", "DList.m", "DList_6.m", "DList_v6.m"。这些可能是实现双链表的不同版本，展示...

    【实验报告】 线性数据结构的实现与应用_双端队列_逆波兰式_呼叫中心_XAUAT_(原问题自杜克大学C++ Stacks and Queues and List

    本次实验的主要目的是理解和掌握线性数据结构——双端队列（Double-Ended Queue，简称deque）的实现与应用。通过实际编程，加深对双端队列特性的理解，如其在头部和尾部进行插入和删除操作的灵活性。同时，将双端...

    双向链表内结点的插入(C++)

    1. **插入到链表的第一个结点之前**：此时新结点将成为链表的新头部。 2. **插入到链表的末尾**：此时新结点将成为链表的新尾部。 3. **插入到链表的中间某个位置**：在这种情况下，需要更新前后的结点指针以正确...

    jPage分页（只针对Sql Server数据库）

    1、在.net2005 studio中，添加新控件，将下载到本地的jwork.dll加至工具箱中。 2、Jpage分页会默认读取web.config配置文件中，名为data的连接字符串。 ;uid=sa;pwd=1234;database=...

    matlab批量读入图片

    通过上述内容的学习，我们可以了解到MATLAB在图像批量读取方面的基本操作流程及其相关的高级技巧。这对于从事图像处理领域的研究人员来说是非常实用的知识点。未来还可以根据实际需求进一步扩展，例如添加图像的...

    androidjava源码下载-dlist_api:这是我在GU（Gentofte青年学校）的编程班上正在做的一个项目，它是一个Java库，用

    【标题】中的“androidjava源码下载-dlist_api”表明这是一个与Android开发相关的Java源代码库，名为“dlist_api”。这个项目可能是为Android应用程序提供特定功能或服务的一个库，可能涉及数据列表的处理和展示。 ...

    spring中的list、map.zip

    在配置Bean对象时，有时候它的成员变量是一个list集合或者是一个map，对于list和map有另外的语法。有兴趣可关注本博客：https://blog.csdn.net/qq_40634846，有循序渐进的spring，零基础入门。

    DataList中如何响应DropDownList的SelectedIndexChanged事件

    `DataList`可以绑定到任何实现了`IEnumerable`接口的数据源，例如数据库查询结果、数组或列表。在`DataList`的模板中，嵌入一个`DropDownList`控件，这样每个`DataList`项都会有一个独立的下拉列表。 ```aspx ...

    基于模板技术的多层次可视化数据结构实验环境研究.doc

    DObject提供了诸如流输出、流输入、保存到文件和从文件加载数据的基本功能。 3. **线性表**： - **DList**： DList是线性表逻辑类，作为具体存储类型线性表的基类，封装了底层操作接口。DList类具有以下成员方法...

    Python高级特性 切片 迭代解析

    切片：方便截取list、tuple、字符串部分索引的内容 正序切片 语法：dlist = doList[0:3]表示，从索引0开始取，直到索引3为止，但不包括索引3。...语法：slist = dolist[-2:] 表示，从倒数第2个索引开始，取到索引为

    Flash笔记（1）

    在这里，当用户点击按钮时，`big.gotoAndPlay(1)` 会使得影片剪辑 `big` 从第一帧开始播放。 4. **AS与XML交互**： - `System.useCodepage = true;` 设置为true可以确保XML数据中的中文字符正确显示，避免编码问题...

    线性表的应用线性表的连接

    如果存在某个共同的关键字段（即表A的第i列与表B的第j列相等），那么可以通过简单的自然连接来生成一个新的表C，其中包含了满足连接条件的所有记录组合。 #### 实验内容 ##### 3.1 创建与管理线性表 - **创建...

    jquery 3d展开收缩图文列表代码

    &lt;img src="images/item1.jpg" alt="Item 1"&gt; 这是项目1的描述 &lt;!-- 更多列表项 --&gt; ``` 接下来，`css`目录下的CSS文件用于定义列表的样式，包括3D变换前后的样式。例如，我们可以为`#my3DList`设置基础...

Magicbox
Global site tag (gtag.js) - Google Analytics