学步园

/* hash.h -- 哈希表头文件 */<br /> enum KindOfEntry {LEGITIMATE, EMPTY, DELETED} ;</p> <p>#define PRIME (7)<br /> #define FAILED (-2)<br /> #define NUL ('/0')<br /> #define FALSE (0)<br /> #define TRUE (1)</p> <p>/* 数据类型定义 */</p> <p>typedef char Name ;<br /> typedef struct cell<br /> {<br /> Name name ;<br /> int be_deleted ; // 在优先队列中是否是已删除过的<br /> enum KindOfEntry entry ;<br /> int index_in_adjacenty_list ;<br /> } Cell ;<br /> typedef struct hash_table<br /> {<br /> Cell * lists ;<br /> int current ;<br /> int capacity ;<br /> } * Hash_Table ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 根据一个数据产生一个数值并返回 */<br /> /* 操作前: pht 指向一个已初始化的散列表, pname 指向一个数据 */<br /> /* 操作后: 根据该数据产生一个数值并返回 */<br /> /* 时间复杂度: O(1) */<br /> int Hash (const Hash_Table * const pht, const Name * const pname) ;</p> <p>/* 操作: 创建并初始化一个散列表 */<br /> /* 操作前: pht 指向一个散列表, capacity 是指示表大小的数据 */<br /> /* 操作后: 如果 capacity > 0 && 内存分配成功, 该散列表被创建为 >= capacity 最小素数大小并初始化为空, 返回1; 否则返回0 */<br /> /* 时间复杂度: O(1) */<br /> int Initialize_H (Hash_Table * const pht, const int capacity) ;</p> <p>/* 操作: 查找并返回一个指向数据在散列表中的位置的指针 */<br /> /* 操作前: pht 指向一个已初始化的散列表, pname 指向被查找的数据 */<br /> /* 操作后: 如果找到数据域为 *pname 的元素, 返回指向该元素的指针; 否则返回指向查找结束时停止在散列表元素的指针 */<br /> /* 时间复杂度: O(N) */<br /> Cell * Find_H (const Hash_Table * const pht, const Name * const pname) ;</p> <p>/* 操作: 向散列表中添加一个元素并返回在散列表中的索引 */<br /> /* 操作前: pht 指向一个已初始化的散列表, pname 是指向名字的指针, index 是元素在邻接表中的索引 */<br /> /* 操作后: 如果表当前大小 <= 表大小的一半, 添加该元素, 返回当前索引; 否则返回 FAILED */<br /> /* 时间复杂度: O(N) */<br /> int Insert_H (const Hash_Table * const pht, const Name * const pname, const int index) ;</p> <p>/* 操作: 从散列表中懒惰删除数据域为指定数据的元素 */<br /> /* 操作前: pht 指向一个已初始化的散列表, pname 是指向名字的指针 */<br /> /* 操作后: 如果找到该元素, 对其进行懒惰删除, 返回 1 ; 否则返回 0 */<br /> /* 时间复杂度: O(N) */<br /> int Delete_H (const Hash_Table * const pht, const Name * const pname) ;</p> <p>/* 操作: 释放一个散列表所占用的内存空间 */<br /> /* 操作前: pht 指向一个已初始化的散列表 */<br /> /* 操作后: 该散列表所占内存空间被释放 */<br /> /* 时间复杂度: O(1) */<br /> void Release_H (const Hash_Table * const pht) ;