NOJ-构造哈希表-西工大数据结构

    今天上课讲了哈希表，回来写了一下。题目如下：

    看一下题，他说用最简单的方法建一个最简单的哈希表，然后输出平均查找长度，毫无难度。。。

    我哈希表用了一个struct指针，如果要存东西，就申请一个节点并把节点地址塞里面，否则就是NULL，可以节省一点空间（虽然毫无必要。。。）。

    我步数在建表的时候就算完了，最后算个和就行，当然也可以单纯建表，然后查找并记录步数，再求和，其实都差不多。。。 

    我的实现如下：

#include <stdio.h>
#include <stdlib.h>
struct hashTableNode
{
int data;
int flag;
};
struct hashTableNode *T[11];
int dataList[8] = {22, 41, 53, 46, 30, 13, 01, 67};
void run();
void getHashTable();
int H(int data);
struct hashTableNode *createHashTableNode(int data, int flag);
void putOutAverageSearchLength();
int main()
{
run();
return 0;
}
void run()
{
getHashTable();
putOutAverageSearchLength();
}
void getHashTable()
{
int i, pos, flag;
for(i = 0; i <= 7; i++)
{
flag = 1;
pos = H(dataList[i]);
while(T[pos] != NULL) ++pos, ++flag;
T[pos] = createHashTableNode(dataList[i], flag);
}
}
int H(int data)
{
return (3 * data) % 11;
}
struct hashTableNode *createHashTableNode(int data, int flag)
{
struct hashTableNode *p;
p = (struct hashTableNode *)malloc(sizeof(struct hashTableNode));
p->data = data;
p->flag = flag;
return p;
}
void putOutAverageSearchLength()
{
int i, sum;
for(i = 0, sum = 0; i <= 10; i++)
{
if(T[i] != NULL)
{
sum += T[i]->flag;
}
}
printf("%dn", sum / 8);
}

    以下是各函数的注释：

void run()
{
getHashTable();//创建哈希表
putOutAverageSearchLength();//输出查找平均长度
}

void getHashTable()
{
int i, pos, flag;
for(i = 0; i <= 7; i++)//遍历关键字序列
{
flag = 1;//初始查找步数为1；
pos = H(dataList[i]);//通过哈希映射函数后的位置
while(T[pos] != NULL) ++pos, ++flag;//找到映射位置起的第一个空位，同时增加查找步数
T[pos] = createHashTableNode(dataList[i], flag);//创建节点塞进去
}
}

int H(int data)
{
return (3 * data) % 11;//哈希映射函数
}

struct hashTableNode *createHashTableNode(int data, int flag)
{
struct hashTableNode *p;
p = (struct hashTableNode *)malloc(sizeof(struct hashTableNode));//创建节点并赋值
p->data = data;
p->flag = flag;
return p;
}

void putOutAverageSearchLength()
{
int i, sum;
for(i = 0, sum = 0; i <= 10; i++)//遍历哈希表
{
if(T[i] != NULL)//非空
{
sum += T[i]->flag;//步数和增加
}
}
printf("%dn", sum / 8);//输出平均
}

最后

以上就是喜悦冰淇淋为你收集整理的NOJ-构造哈希表-西工大数据结构的全部内容，希望文章能够帮你解决NOJ-构造哈希表-西工大数据结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。