本关讨论散列存储,散列函数使用除留余数法,冲突解决方法采用独立链表地址法。假设有 8 个关键码: 7 , 15 , 23 , 31 , 12 , 14 , 10 , 17 ,采用散列函数hash(key)=key%7,其存储结构图如图 1 所示,它由 7 个独立链表组成,散列值相同的关键码在同一个链表里,独立链表的头结点组成散列表,一共 7 行,编号 0 , 1 , … , 6 。独立链表的每个结点是一个 struct HNode 结构,其定义如下:
struct HNode
{
int key; //假设关键码为整数
HNode* next;
};
在散列表中,如果表项的key字段等于 0 (假设有效的关键码值不等于 0 ),则表示该行是一条空链表,例如图 1 中编号为 4 和编号为 6 的行。 散列表的开始地址保存在pn中,散列表的行数为n(图 1 中,n=7),将pn和n组织成结构:
struct LHTable
{
HNode* pn; //指向散列表,每个表结点是独立链表的表头结点
int n; //散列表的长度,一般取(小于等于数据个数的最大)质数
};
定义如下操作,各操作函数的功能详见下面给出的代码文件 indLnkHash.cpp 的代码框架:
LHTable* ILH_Create(int n);
void ILH_Free(LHTable* pt);
bool ILH_InsKey(LHTable* pt, int x);
bool ILH_FindKey(LHTable* pt, int x);
bool ILH_DelKey(LHTable* pt, int x);
void ILH_Print(LHTable *pt);
输入输出格式说明 输入格式: 首先输入一个正整数n,创建一个长n的散列表。 然后输入多个操作:如果输入 “insert” ,则后面跟一个数x,表示将x插入;如果输入 “delete” ,则后面跟一个数x,表示将x删除;如果输入 “end” ,表示输入结束。 输出格式: 输出n个独立链表。 以下是平台对 step2/Main.cpp 的样例测试集: 样例输入:
11
insert 54
insert 77
insert 94
insert 89
insert 14
insert 45
insert 76
insert 23
insert 43
insert 47
end
样例输出:
0:
77
1: 89 -> 45 -> 23
2: -
3: 14 -> 47
4: -
5: -
6: 94
7: -
8: -
9: -
10: 54 -> 76 -> 43
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "indLnkHash.h"
LHTable* ILH_Create(int n)
//创建散列表, n为表长度,最佳取值:n取小于等于数据个数的最大质数
{
HNode* pn=(HNode*)malloc(sizeof(HNode)*n);
for (int i=0; i<n; i++)
{
pn[i].key=0;
pn[i].next=NULL;
}
LHTable* pt=(LHTable*)malloc(sizeof(LHTable));
pt-> pn=pn;
pt->n=n;
return pt;
}
void ILH_Free(LHTable* pt)
//释放散列表
{
if (pt==NULL) return;
for (int i=0; i<pt->n; i++)
{
HNode* curr=pt->pn[i].next;
while (curr)
{
HNode* next=curr->next;
free(curr);
curr=next;
}
}
free(pt->pn);
free(pt);
}
bool ILH_InsKey(LHTable* pt, int x)
//插入关键码x
//返回true,表示插入成功
//返回false,表示插入失败(关键码已经存在)
{
int d=x%pt->n;
if (pt->pn[d].key==0)
{
pt->pn[d].key=x;
return true;
}
else if (pt->pn[d].key==x)
{
return false;
}
HNode* prev=&(pt->pn[d]);
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x)
{
prev=curr;
curr=curr->next;
}
if (curr)
{
return false;
}
HNode* pnode=(HNode*)malloc(sizeof(HNode));
pnode->key=x;
pnode->next=NULL;//pt->pn[d].next;
prev->next=pnode;
return true;
}
bool ILH_FindKey(LHTable* pt, int x)
//查找关键码x
//返回true表示找到
//返回false表示没找到
{
int d=x%pt->n;
if (pt->pn[d].key==0)
{
return false;
}
else if (pt->pn[d].key==x)
{
return true;
}
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x)
{
curr=curr->next;
}
if (curr)
{
return true;
}
else
{
return false;
}
}
bool ILH_DelKey(LHTable* pt, int x)
//删除关键码
//返回true表示该关键码存在,且成功删除
//返回false表示该关键码不存在
{
int d=x%pt->n;//关键码x的散列值d
if (pt->pn[d].key==0)
{
return false;
}
else if (pt->pn[d].key==x)
{
if (pt->pn[d].next ==NULL)
{
pt->pn[d].key=0;
}
else
{
HNode* first=pt->pn[d].next;
pt->pn[d].key=first->key;
pt->pn[d].next=first->next;
free(first);
}
return true;
}
HNode* prev=&(pt->pn[d]);
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x)
{
prev=curr;
curr=curr->next;
}
if (curr==NULL)
{
return false;
}
prev->next=curr->next;
free(curr);
return true;
}
void ILH_Print(LHTable *pt)
{
for (int i=0; i<pt->n; i++)
{
printf("%5d:", i);
if (pt->pn[i].key)
{
printf("%d", pt->pn[i].key);
HNode* curr=pt->pn[i].next;
while (curr)
{
printf("->%d", curr->key);
curr=curr->next;
}
printf("\n");
}
else
{
printf("-\n");
}
}
}
|