大家好今天来介绍详解散列表的设计与实现，以下是小编对散列表的设计与实现 课设的归纳整理，来看看吧。
散列表的设计与实现
散列表的设计与实现
问题描述：
设计散列表实现电话号码查找系统。
基本要求：
（1） 设每个记录有下列数据项：电话号码、用户名、地址；
（2） 从键盘输入记录，分别以电话号码和用户名为关键字建立散列表；
（3） 采用双散列法解决冲突；
（4） 查找并显示给定电话号码的记录；
（5） 查找并显示给定用户名的记录。
选做带改内容：
（1） 系统功能袜滚的完善；
（告行余2） 设计不同的散列函数，比较冲突率；
（3） 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
散列表的设计c语言实现
#include
#include
#include
const int HASH_TABLE_SIZE = 13;
typedef struct hash_table_pair_s {
char *key;
int value;
struct hash_table_pair_s *next;
} hash_table_pair_t;
int ELFhash(const char *key)
{
unsigned long h = 0;
unsigned long g;
while( *key )
{
h =( h<< 4) + *key++;
g = h & 0xf0000000L;
if( g ) h ^= g >> 24;
h &= ~g;
}
return h;
}
void hash_table_insert(hash_table_pair_t *hash_table, const char *key, int value)
{
int pos;
hash_table_pair_t *new_pair;
char *new_str;
pos = ELFhash(key) % HASH_TABLE_SIZE;
if (hash_table[pos].key != NULL) {
printf(\"conflict: %s and %s\\n\", key, hash_table[pos].key);
new_pair = (hash_table_pair_t *)malloc(sizeof(hash_table_pair_t));
new_str = (char *)malloc(sizeof(char) * (strlen(key) + 1));
strcpy(new_str, key);
new_pair->key = new_str;
new_pair->value = value;
new_pair->next = hash_table[pos].next;
hash_table[pos].next = new_pair;
}
else {
new_str = (char *)malloc(sizeof(char) * (strlen(key) + 1));
strcpy(new_str, key);
hash_table[pos].key = new_str;
hash_table[pos].value = value;
hash_table[pos].next = NULL;
}
}
int hash_table_get(hash_table_pair_t *hash_table, const char *key, int *value)
{
int pos;
hash_table_pair_t *p;
pos = ELFhash(key) % HASH_TABLE_SIZE;
for (p = &hash_table[pos]; p != NULL; p = p->next) {
if (!strcmp(p->key, key)) {
*value = p->源型或value;
return 0;
}
}
return -1;
}
int main()
{
int i, status, value;
const char *MyBirds[13] = { \"租手robin\", \"sparrow\", \"hawk\", \"eagle\", \"seagull\", \"bluejay\", \"owl\", \"cardinal\", \"Jakana\", \"Moa\", \"Egret\", \"Penguin\", \"hawk\" };
hash_table_pair_t *hash_table = (hash_table_pair_t *)malloc(HASH_TABLE_SIZE * sizeof(hash_table_pair_t));
for (i = 0; i < HASH_TABLE_SIZE; i++) {
hash_table[i].key = NULL;
hash_table[i].next = NULL;
hash_table[i].value = 0;
}
for (i = 0; i < sizeof(MyBirds) / sizeof(MyBirds[0]); i++) {
hash_table_insert(hash_table, MyBirds[i], i);
}
for (i = 0; i < sizeof(MyBirds) / sizeof(MyBirds[0]); i++) {
status = hash_table_get(hash_table, MyBirds[i], &value);
if (status == -1) {
printf(\"not found %s\\n\", MyBirds[i]);
}
else {
printf(\"found %s: %d\\n\", MyBirds[i], value);
}
}
return 0;
}
高手请进散列表设计与实现程序
唉，这么多分得不到，好可惜啊，我以前编过这个的，还有文本保存呢，可是衫烂找不到了。55555.
哈哈，我打到了，不过是文字稿的，10页呢，脊塌罩估计我没有耐性把它们打下来，分不要了樱闹。
数据结构 散列表
散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。设计合理的散列函数可以集成链表塌锋和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：
散列表的主要特点：1.将输入映射到数字2.不同的输入产生不同的输出3.相同的输入产生相同的输出4. 当填装因子超过阈值时，能自动扩展。填装因子 = 散列表包含的元素数 / 位置总数，当填装因子 =1，即散列表满的时候，就需要调整散列表的长度，自动扩展的方式是：申请一块旧存储容量 X 扩容系数的新内存地址，然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置，拷贝到新申请的地址。5. 值呈均匀分布。这里的均匀指水平方向的，即数组维度的。如果多个值被映射到同一个位置，就产生了冲突，需要用团皮晌链表来存储多个冲突的键值。极端情况是极限冲突，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将握空变为最差的 O(n)，如果水平方向填充因子很小，但某些节点下的链表又很长，那值的均匀性就比较差。
以上就是小编对于详解散列表的设计与实现 散列表的设计与实现 课设问题和相关问题的解答了，希望对你有用
