＋设为首页 ＋添加到收藏夹
编程手记之ansi c篇-（二）哈希序列哈希表的基本思路是:由关键码的哈希函数值来决定节点的存储地址,进而来存取节点.在我的应用中,要解决的是基于命名（字符串型关键码）来查找与存储节点,节点的内容是字符串或某个结构的指针.哈希表的结构有主散列与子序列构成,主散列是一线性数组,数组的大小为size,是一个素数,也是哈希函数的模基,数组序号[0...size]即哈希函数的值域,数组存储的是根连接件,由他维护着同义词关键码（哈希函数值相同）的节点链表.子序列是存储节点的有序序列,是按各节点关键码升序排列的,子序列主要是用于处理哈希冲撞的问题.查找的路径为,根据关键码的哈希函数值在主散列中取得根连接件,然后在此子序列中查找含该关键码的节点.1.数据结构定义:/*定义哈希表*/typedef struct _hashtable{ link lk;/*哈希表自身连接件*/ linkptr pp;/*主散列线性数组指针*/ int size;/*数组大小*/}hashtable;/*定义节点*/typedef struct _hashentry{ link lk;/*节点自身连接件*/ tchar* szkey;/*关键码*/ tchar* szval;/*节点字符串值*/ unsigned long data;/*节点长整型值*/}hashentry;
/*定义从连接件指针中恢复数据节点*/#define hashtablefromlink(p) ((hashtable*)((unsigned int)p - (unsigned int)&(((hashtable*)0)->lk))) #define hashentryfromlink(p) ((hashentry*)((unsigned int)p - (unsigned int)&(((hashentry*)0)->lk))) 【程序编程相关:【头文件】c实现数组】
/*定义数据节点标识*/#define lkhashentry 1#define lkhashtable 2 【推荐阅读:ASP.NET Tips1---合并多个】
typedef int (*enumhashentryptr)(tchar* szkey,int keylen,tchar* szval,int vallen,void* pv); 【扩展信息:【头文件】c实现字符串】
/*定义枚举哈希表节的回调函数*/
2.哈希函数:/*szkey: 关键码keylen: 关键码长度nprim: 模基,一般为素数*/static int hashcode(tchar* szkey,int keylen,int nprim){unsigned int sum;int i;
assert(szkey);assert(nprim > 0);
/*keylen为-1指明szkey为´\0´结尾的字符串*/if(keylen == -1) keylen = _tcslen(szkey);
/*各字节取整求与*/sum = 0;for(i=0;i{ sum += (int)(szkey[i]);}/*求余数*/return sum % nprim;}
3.哈希表实现:/*创建哈希表nsize: 哈希函数的模基,即主散列数组的大小,一般取素数值*/linkptr createhashtable(int nsize){hashtable* pht;int i;
... 下一页