㈠ 如何用c语言建立哈希表 存有序对
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0 // 0为无记录标志
#define N 10 // 数据元素个数
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int KeyType; // 设关键字域为整型
struct ElemType // 数据元素类型
{
KeyType key;
int ord;
};
int hashsize[]={11,19,29,37}; // 哈希表容量递增表，一个合适的素数序列
int m=0; // 哈希表表长，全局变量
struct HashTable
{
ElemType *elem; // 数据元素存储基址，动态分配数组
int count; // 当前数据元素个数
int sizeindex; // hashsize[sizeindex]为当前容量
};
Status InitHashTable(HashTable &H)// 操作结果: 构造一个空的哈希表
{ int i;
H.count=0; // 当前元素个数为0
H.sizeindex=0; // 初始存储容量为hashsize[0]
m=hashsize[0];
H.elem=(ElemType*)malloc(m*sizeof(ElemType));
if(!H.elem)
exit(OVERFLOW); // 存储分配失败
for(i=0;i<m;i++)
H.elem[i].key=NULLKEY; // 未填记录的标志
return OK;
}
void DestroyHashTable(HashTable &H)// 初始条件: 哈希表H存在。操作结果: 销毁哈希表H
{ free(H.elem);
H.elem=NULL;
H.count=0;
H.sizeindex=0;
}
unsigned Hash(KeyType K)// 一个简单的哈希函数(m为表长，全局变量)
{ return K%m;
}
void collision(int &p,int d) // 线性探测再散列
{
p=(p+d)%m;// 开放寻址法处理冲突
}
Status SearchHash(HashTable H,KeyType K,int &p,int &c)// 在开放寻址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
{ p=Hash(K); // 求得哈希地址
while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))
{ // 该位置中填有记录．并且关键字不相等
c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
break;
}
if EQ(K,H.elem[p].key)
return SUCCESS; // 查找成功，p返回待查数据元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置
}
Status InsertHash(HashTable &,ElemType); // 对函数的声明
void RecreateHashTable(HashTable &H) // 重建哈希表
{ int i,count=H.count;
ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i<m;i++) // 保存原有的数据到elem中
if((H.elem+i)->key!=NULLKEY) // 该单元有数据
*p++=*(H.elem+i);
H.count=0;
H.sizeindex++; // 增大存储容量
m=hashsize[H.sizeindex];
p=(ElemType*)realloc(H.elem,m*sizeof(ElemType));
if(!p)
exit(OVERFLOW); // 存储分配失败
H.elem=p;
for(i=0;i<m;i++)
H.elem[i].key=NULLKEY; // 未填记录的标志(初始化)
for(p=elem;p<elem+count;p++) // 将原有的数据按照新的表长插入到重建的哈希表中
InsertHash(H,*p);
}
Status InsertHash(HashTable &H,ElemType e)// 查找不成功时插入数据元素e到开放寻址哈希表H中，并返回OK；
{ int c,p;
c=0;
if(SearchHash(H,e.key,p,c)) // 表中已有与e有相同关键字的元素
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2) // 冲突次数c未达到上限,(c的阀值可调)
{ // 插入e
H.elem[p]=e;
++H.count;
return OK;
}
else
RecreateHashTable(H); // 重建哈希表
return ERROR;
}
void TraverseHash(HashTable H,void(*Vi)(int,ElemType))// 按哈希地址的顺序遍历哈希表
{
printf("哈希地址0～%d\n",m-1);
for(int i=0;i<m;i++)
if(H.elem[i].key!=NULLKEY) // 有数据
Vi(i,H.elem[i]);
}
Status Find(HashTable H,KeyType K,int &p)// 在开放寻址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
{ int c=0;
p=Hash(K); // 求得哈希地址
while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))// 该位置中填有记录．并且关键字不相等
{ c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
if EQ(K,H.elem[p].key)
return SUCCESS; // 查找成功，p返回待查数据元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
void print(int p,ElemType r)//输出
{
printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}
void main()
{
ElemType r[N]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
HashTable h;
int i,p;
Status j;
KeyType k;
InitHashTable(h);
for(i=0;i<N-1;i++)// 插入前N-1个记录
{
j=InsertHash(h,r[i]);
if(j==DUPLICATE)
printf("表中已有关键字为%d的记录，无法再插入记录(%d,%d)\n",r[i].key,r[i].key,r[i].ord);
}
printf("按哈希地址的顺序遍历哈希表:\n");
TraverseHash(h,print);
printf("请输入待查找记录的关键字: ");
scanf("%d",&k);
j=Find(h,k,p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("没找到\n");
j=InsertHash(h,r[i]); // 插入第N个记录
if(j==ERROR) // 重建哈希表
j=InsertHash(h,r[i]); // 重建哈希表后重新插入
printf("按哈希地址的顺序遍历重建后的哈希表:\n");
TraverseHash(h,print);
printf("请输入待查找记录的关键字: ");
scanf("%d",&k);
j=Find(h,k,p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("没找到\n");
DestroyHashTable(h);
}
㈡ C语言实现哈希表的相关运算算法 编写程序实现哈希表的构造过程。
#define MaxSize 100 //定义最大哈希表长度
#define NULLKEY -1 //定义空关键字值
#define DELKEY -2 //定义被删关键字值
typedef int KeyType; //关键字类型
typedef char * InfoType; //其他数据类型
typedef struct
{
KeyType key; //关键字域
InfoType data; //其他数据域
int count; //探查次数域
} HashData;
typedef HashData HashTable[MaxSize]; //哈希表类型
void InsertHT(HashTable ha,int &n,KeyType k,int p) //将关键字k插入到哈希表中
{
int i,adr;
adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
{
ha[adr].key=k;
ha[adr].count=1;
}
else //发生冲突时采用线性探查法解决冲突
{
i=1; //i记录x[j]发生冲突的次数
do
{
adr=(adr+1) % p;
i++;
}
while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void CreateHT(HashTable ha,KeyType x[],int n,
㈢ 哈希造表: 为某个集体"人名"设计一个哈希表,平均查找长度不超过2,假设30个待填入的人名为拼音形式.
这个是我们的作业 ^^根据自己的需要改一下就行了
#include <stdio.h>
#include<malloc.h>
#include<string.h>
//#include
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()
{
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengquan";
NameList[9].py="luqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";
char *f;
int r,s0;
for (int i=0;i<NAME_NO;i++)// 求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;
for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()
{
for (int i=0; i<HASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; i<NAME_NO;)
{
int sum=0;
int adr=(NameList[i].k) % M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪散列
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}
/*-------------------------------------查找------------------------------------*/
void FindList()
{
printf("\n\n请输入姓名的拼音: "); //输入姓名
char name[20]={0};
scanf("%s",name);
int s0=0;
for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
int sum=1;
int adr=s0 % M; //使用哈希函数
int d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("无该记录!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("无记录! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
/*--------------------------------显示哈希表----------------------------*/
void Display()
{
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式
for(int i=0; i<15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
// getch();
for( i=15; i<30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n");
// getch();
for( i=30; i<40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意键继续显示...\n");
//getch();
for( i=40; i<50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
float average=0;
for (i=0;i<HASH_LEN;i++)
average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
}
/*--------------------------------主函数----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();
while(1)
{
printf("\n\n");
printf(" 1. 显示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");
err:
char ch1;
scanf("%c",&ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}
㈣ 哈希查找，就是在一个表格里按学生的成绩查找，帮忙写下代码，用c语言，还有注释，详细点，我是菜鸟。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX 20
typedef struct
{
int num;
char name[20];
}
ElemType;//定义查找的结点元素
typedef struct
{
ElemType *elem;
int count;
int sizeindex;
}
HashTable;//定义哈希表
int Hash(int num)
{
int p;
p=num%5;
return p;
}//定义哈希函数
void InitHash(HashTable *H)//创建哈希表
{
int i;
H->elem=(ElemType *)malloc(MAX*sizeof(ElemType));
H->count=0;
H->sizeindex=MAX;
for(i=0;i<MAX;i++)
H->elem[i].num=0;//初始化，使SearHash函数能判断到底有没有元素在里面
}
int SearHash(HashTable H,int key,int *p)//查找函数
{
int c=0;
*p=Hash(key);
while(H.elem[*p].num!=key&&H.elem[*p].num!=0)
{//通过二次探测再散列解决冲突
c=c+1;
if(c%2==1)
*p=*p+(c+1)*(c+1)/4;
else
*p=*p-(c*c)/4;
}
if(H.elem[*p].num==key)
return 1;
else
return 0;
}
void InsertHash(HashTable *H,ElemType e)
{//如果查找不到就插入元素
int p;
SearHash(*H,e.num,&p);
H->elem[p]=e;
++H->count;
}
void main()//主函数
{
HashTable H;
int p,key,i;
ElemType e;
InitHash(&H);
for(i=0;i<3;i++)
{//输入3个元素
printf("输入学生学号\n");
scanf("%d",&e.num);//输入学号
if(!SearHash(H,e.num,&p))
{
printf("输入学生名字\n");
scanf("%s",e.name);//输入名字
InsertHash(&H,e);//插入元素
}
else
printf("已经存在\n");//否则就表示元素的学好已经存在
}
printf("输入查找的学生学号:\n");
scanf("%d",&key);//输入要查找的学号
if(SearHash(H,key,&p))//能查找成功
{
printf("%s\n",H.elem[p].name);//输出名字
printf("%d\n",p);//输出位置
}
else
printf(" 不存在");
getch();
}
以前编的，挺简单的。用二次散列探测解决冲突。除留余数哈希函数法，除数可以任意选，我选的是5。还有哈希表的长度你可以大点。getch();可以不要啊。
㈤ 构造哈希表存储电话号码，用再哈希法处理冲突要c语言程序代码
给你个hash表的接口和实现
你根据需求该下吧
#ifndef _Hash_H_
#define _Hash_H_
/*
* 查找算法时间是 O(1)
* 优点:查找迅速
* 缺点:比较占用内存
*/
/*
*
* hash原子结构体
*
*
*/
typedef struct hash_table_pair_s{
/*hash表长*/
int length;
/*hash key*/
char *key;
/*储存的值,可以是地址*/
int value;
struct hash_table_pair_s *next;
}hash_table;
/*
* function: hash_insert
* --------------------------------------
* 往hash表中增加一个元素
* Usage:
*
* #include "corelib/hash.h"
* void run(hash_table*hash){
* int i, status, value;
* status = hash_get(hash,"hawk", &value);
* if(status!=-1){
* printf("find,%d",value);
* }else{
* printf("not find");
* }
* }
* void main(){
* hash_table* hash= hash_create(10);//创建一个表长是10的hash表
* hash_insert(hash,"robin", 0);
* hash_insert(hash,"sparrow", 1);
* hash_insert(hash,"hawk", 2);
* hash_insert(hash,"jack", 3);
* hash_insert(hash,"seagull", 4);
* run(hash);
* }
*
*/
void hash_insert(hash_table *hash,const char *key, int value);
/*
* function: hash_get
* --------------------------------------
* 根据key值在hash表中获取一个元素对象
*
*
*/
int hash_get(hash_table *hash,const char* key, int *value);
/*
* function: hash_create
* 创建一个hash表
*
*/
hash_table* hash_create(int size);
#include "corelib/hash.c"
#endif
//-----------------------------------------------------------------------------------------------
#include <default.c>
#include <stdio.h>
/*
*一个key字符串占用的字节数
*/
#define KEY_SIZE 64
/*
*
*hash函数
*
*/
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_insert(hash_table *hash,const char *key, int value){
char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));
int pos;
hash_table *new_pair;
char *new_str;
pos = ELFhash(key) % hash[0].length;
if (hash[pos].key != NULL) {
/*发生冲突*/
char log[512];
memset(log,0,512);
int j=0;
j+=sprintf(log+j,"冲突: %s and %s\n", keystr, hash[pos].key);
new_pair = (hash_table *)malloc(sizeof(hash_table));
new_str = (char *)malloc(sizeof(char) * (strlen(keystr) + 1));
strcpy(new_str, keystr);
new_pair->key = new_str;
new_pair->value = value;
new_pair->next = hash[pos].next;
hash[pos].next = new_pair;
// printf("%s",log);
}else{
int len = sizeof(char) * (strlen(keystr) + 1);
new_str = (char *)malloc(len);
memset(new_str,0,len);
strcpy(new_str, keystr);
hash[pos].key = new_str;
hash[pos].value = value;
hash[pos].next = NULL;
}
}
int hash_get(hash_table *hash,const char* key, int *value){
int pos;
hash_table *p;
char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));
pos = ELFhash(key) % hash[0].length;
for (p = &(hash[pos]); p != NULL; p = p->next) {
if (!strcmp(p->key, keystr)) {
*value = p->value;
return 0;
}
}
return -1;
}
hash_table* hash_create(int size){
int i;
hash_table *hash = (hash_table *)malloc(size * sizeof(hash_table));
hash[0].length = size;
for (i = 0; i < size; i++) {
hash[i].key = NULL;
hash[i].next = NULL;
hash[i].value = 0;
}
return hash;
}
#undef KEY_SIZE
㈥ 用哈希表实现C语言关键字的算法
#include <iostream.h>
#include<fstream.h>
#include <string>
#include <iomanip.h>
using namespace std;
const int TOTAL=32;
const int MAXLEN=10;
const int HASHLEN=41;
int cont=0;
class HashTable
{
public:
char keyword[MAXLEN];
int count;
int num;
};
HashTable HS[HASHLEN];
char KeyWords[TOTAL][MAXLEN]= {
"char", "double", "enum", "float", "int", "long", "short", "signed",
"struct", "union", "unsigned", "void", "break", "case", "continue",
"default", "do", "else", "for", "goto", "if", "return", "switch", "while",
"auto", "extern", "register", "static", "const", "sizeof", "typedef", "volatile"
};
template<class T>
class HASH
{
public:
void Show(int key);
int CreatHX(char *keyword);
int GetFreePos(int key);
void ResetHX();
int GetKey(char *keyword);
int isKeyWords(char *word);
int Read(char *filename);
int isLetter(char ch);
int FindHX(char *keyword);
private:
int key;
char *keyword;
char *word;
char ch;
};
template<class T>
void HASH<T>::Show(int key)
{
if(key<0||key>=HASHLEN)
{
cout<<"关键字不存在!"<<endl;
return;
}
if(strlen(HS[key].keyword)==0)
{
cout<<"哈希表位置："<<key<<" 记录是空的"<<endl;
return ;
}
cout<<"哈希表位置: "<<key<<" 关键字: "
<<HS[key].keyword<<" 出现次数 "<<HS[key].count<<endl;
cont++;
}
template<class T>
int HASH<T>::CreatHX(char *keyword)
{
int key;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strlen(HS[key].keyword)>0)
{
if(strcmp(HS[key].keyword,keyword)==0)
{
HS[key].count++;
return 1;
}
key=FindHX(keyword);
if(key<0)
{
key=GetFreePos(GetKey(keyword));
if(key<0) return -1;
strcpy(HS[key].keyword,keyword);
}
if(key<0) return -1;
HS[key].count++;
}
else
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
template<class T>
int HASH<T>::GetFreePos(int key)
{
int find,tem=0;
if(key<0||key>=HASHLEN) return -1;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
void HASH<T>::ResetHX()
{
int i;
for(i=0;i<HASHLEN;i++)
{
strcpy(HS[i].keyword,"");
HS[i].count=0;
HS[i].num=0;
}
}
template<class T>
int HASH<T>::GetKey(char *keyword)
{
return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41;
}
template<class T>
int HASH<T>::isKeyWords(char *word)
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0) return 1;
return 0;
}
template<class T>
int HASH<T>::isLetter(char ch)
{
if( (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z') ) return 1;
else return 0;
}
template<class T>
int HASH<T>::FindHX(char *keyword)
{
int key,find,tem=0;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0) return key;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
int HASH<T>::Read(char *filename)
{
char word[MAXLEN],ch;
int i;
FILE *read;
fstream myfile;
myfile.open("filename");
if(!myfile)
{
cout<<"文件不存在,请确认好再输入!"<<endl;
return -1;
}
ResetHX();
while(!feof(read))
{
i=0;
ch=fgetc(read);
while(isLetter(ch)==0 && feof(read)==0 )
ch=fgetc(read);
while(isLetter(ch)==1 && feof(read)==0 )
{
if(i==MAXLEN)
{
while(isLetter(ch)==1&& feof(read)==0)
{
ch=fgetc(read);
}
i=0;
break;
}
else
{
word[i++]=ch;
ch=fgetc(read);
}
}
word[i]='\0';
if(isKeyWords(word))
{
CreatHX(word);
}
}
fclose(read);
cout<<"读取成功，文件中关键字已经存入hash表，请继续操作"<<endl;
return 1;
}
void main()
{
HASH<char> hash;
char filename[128],word[MAXLEN];
int i=0,count=0;
int key;
char j,y;
cout<<"请输入要读取的文件名:";
cin>>filename;
cout<<endl;
hash.Read(filename);
for(i=0;i<HASHLEN;i++)
{
hash.Show(i);
getchar();
}
cout<<"关键字总数为："<<cont<<endl;
cout<<"请输入你想要查找的关键字： ";
cin>>word;
cout<<endl;
hash.Show(hash.FindHX(word));
cout<<" C语言中的关键字和其在哈希表的位置:"<<endl;
for(i=0;i<TOTAL;i++)
{
cout<<setiosflags(ios::left)<<"["<<setw(2)<<hash.GetKey(KeyWords[i])<<"]"
<<setiosflags(ios::left)<<setw(11)<<KeyWords[i];
if((i+1)%4==0) cout<<endl;
}
cout<<"是否显示冲突关键字列表？y(是) 其它（否）:";
cin>>j;
if(j=='y')
{
cout<<"冲突关键字列表"<<endl;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=hash.GetKey(HS[i].keyword);
if(key!=i)
{
count++;
cout<<setiosflags(ios::left)<<setw(14)<<
"\t[关键 字]:"<<HS[i].keyword<<setiosflags(ios::left)<<
setw(20)<<"\t[哈希表当前位置]: "<<i<<setiosflags(ios::left)<<
setw(20)<<"\t[冲突次数]: "<<HS[i].num<<endl;
}
}
}
if(count==0)
cout<<"没有冲突"<<endl;
else
cout<<"\t冲突关键字共:"<<count<<"个"<<endl;
}
else
cout<<"不显示冲突关键字列表，但已存在！"<<endl;
return;
}
㈦ 如何用C语言中实现哈希表
C++有 map,set
还有其他的，看STL相关的吧
数组还慢....
㈧ 希望大家帮帮我啊！！！C语言 哈希表生成及哈希查找算法 输入：待哈希数据序列 功能要求：输出哈希方法和
你看看这个哈希算法吧、、貌似。，，也差不多咯
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
typedef int KeyType;
typedef struct /*元素类型定义*/
{
KeyType key; /*关键字*/
int hi; /*冲突次数*/
}DataType;
typedef struct /*哈希表类型定义*/
{
DataType *data;
int tableSize; /*哈希表的长度*/
int curSize; /*表中关键字个数*/
}HashTable;
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n);
int SearchHash(HashTable H,KeyType k);
void DisplayHash(HashTable H,int m);
void HashASL(HashTable H,int m);
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n)
/*构造一个空的哈希表，并处理冲突*/
{
int i,sum,addr,di,k=1;
(*H).data=(DataType*)malloc(m*sizeof(DataType));/*为哈希表分配存储空间*/
if(!(*H).data)
exit(-1);
for(i=0;i<m;i++) /*初始化哈希表*/
{
(*H).data[i].key=-1;
(*H).data[i].hi=0;
}
for(i=0;i<n;i++) /*求哈希函数地址并处理冲突*/
{
sum=0; /*冲突的次数*/
addr=hash[i]%p; /*利用除留余数法求哈希函数地址*/
di=addr;
if((*H).data[addr].key==-1) /*如果不冲突则将元素存储在表中*/
{
(*H).data[addr].key=hash[i];
(*H).data[addr].hi=1;
}
else /*用线性探测再散列法处理冲突*/
{
do
{
di=(di+k)%m;
sum+=1;
} while((*H).data[di].key!=-1);
(*H).data[di].key=hash[i];
(*H).data[di].hi=sum+1;
}
}
(*H).curSize=n; /*哈希表中关键字个数为n*/
(*H).tableSize=m; /*哈希表的长度*/
}
int SearchHash(HashTable H,KeyType k)
/*在哈希表H中查找关键字k的元素*/
{
int d,d1,m;
m=H.tableSize;
d=d1=k%m; /*求k的哈希地址*/
while(H.data[d].key!=-1)
{
if(H.data[d].key==k)/*如果是要查找的关键字k，则返回k的位置*/
return d;
else /*继续往后查找*/
d=(d+1)%m;
if(d==d1) /*如果查找了哈希表中的所有位置，没有找到返回0*/
return 0;
}
return 0; /*该位置不存在关键字k*/
}
void DisplayHash(HashTable H,int m)
/*输出哈希表*/
{
int i;
printf("哈希表地址：");
for(i=0;i<m;i++)
printf("%-5d",i);
printf("\n");
printf("关键字key: ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].key);
printf("\n");
printf("冲突次数： ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].hi);
printf("\n");
}
void HashASL(HashTable H,int m)
/*求哈希表的平均查找长度*/
{
float average=0;
int i;
for(i=0;i<m;i++)
average=average+H.data[i].hi;
average=average/H.curSize;
printf("平均查找长度ASL=%.2f",average);
printf("\n");
}
void main()
{
int hash[]={23,35,12,56,123,39,342,90};
int m=11,p=11,n=8,pos;
KeyType k;
HashTable H;
CreateHashTable(&H,m,p,hash,n);
DisplayHash(H,m);
k=123;
pos=SearchHash(H,k);
printf("关键字%d在哈希表中的位置为：%d\n",k,pos);
HashASL(H,m);
}
㈨ C语言哈希表
/#include "iostream.h"
#include <iostream>
#include "string.h"
#include "fstream"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node //建节点
{
char name[8],address[20];
char num[11];
node * next;
};
typedef node* pnode;
typedef node* mingzi;
node **phone;
node **nam;
node *a;
using namespace std; //使用名称空间
void hash(char num[11]) //哈希函数
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
void hash2(char name[8]) //哈希函数
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
}
node* input() //输入节点
{
node *temp;
temp = new node;
temp->next=NULL;
cout<<"输入姓名："<<endl;
cin>>temp->name;
cout<<"输入地址："<<endl;
cin>>temp->address;
cout<<"输入电话："<<endl;
cin>>temp->num;
return temp;
}
int apend() //添加节点
{
node *newphone;
node *newname;
newphone=input();
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
void create() //新建节点
{
int i;
phone=new pnode[20];
for(i=0;i<20;i++)
{
phone[i]=new node;
phone[i]->next=NULL;
}
}
void create2() //新建节点
{
int i;
nam=new mingzi[20];
for(i=0;i<20;i++)
{
nam[i]=new node;
nam[i]->next=NULL;
}
}
void list() //显示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void list2() //显示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=nam[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void find(char num[11]) //查找用户信息
{
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"无此记录"<<endl;
}
void find2(char name[8]) //查找用户信息
{
hash2(name);
node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"无此记录"<<endl;
}
void save() //保存用户信息
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
fstream iiout("out.txt", ios::out);
iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;
p=p->next;
}
}
}
void menu() //菜单
{
cout<<"0.添加记录"<<endl;
cout<<"3.查找记录"<<endl;
cout<<"2.姓名散列"<<endl;
cout<<"4.号码散列"<<endl;
cout<<"5.清空记录"<<endl;
cout<<"6.保存记录"<<endl;
cout<<"7.退出系统"<<endl;
}
int main()
{
char num[11];
char name[8];
create();
create2() ;
int sel;
while(1)
{
menu();
cin>>sel;
if(sel==3)
{ cout<<"9号码查询，8姓名查询"<<endl;
int b;
cin>>b;
if(b==9)
{ cout<<"请输入电话号码:"<<endl;
cin >>num;
cout<<"输出查找的信息:"<<endl;
find(num);
}
else
{ cout<<"请输入姓名:"<<endl;
cin >>name;
cout<<"输出查找的信息:"<<endl;
find2(name);}
}
if(sel==2)
{ cout<<"姓名散列结果:"<<endl;
list2();
}
if(sel==0)
{ cout<<"请输入要添加的内容:"<<endl;
apend();
}
if(sel==4)
{ cout<<"号码散列结果:"<<endl;
list();
}
if(sel==5)
{ cout<<"列表已清空:"<<endl;
create();
create2();
}
if(sel==6)
{ cout<<"通信录已保存:"<<endl;
save();
}
if(sel==7) return 0;
}
return 0;
}