1. 哈希表查找的設計(用c語言編譯,答案盡可能詳細,謝謝)
STL map
2. C語言哈希表,為什麼輸入查找名字就沒了音訊(點進來有詳細內容喲~)
HASH函數里 scanf("%s",&namekey); 去掉namekey前的&號。namekey已經是一個指針了,不需要再取地址。
3. c語言 簡單哈希表
哈希,其實是一種數據結構。
比如你拿到一組數據,你需要將這些數據一一存儲到你定義的數組中,假如現在用的是哈希的方式去存儲的,而不是順序存儲,那麼,就會出現一個哈希函數,(數值/一個質數),得到的結果就是應該存儲在數組中的下標值,這樣就可以使得分布很平均。
4. 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;
}
5. 哈希表的c語言程序。。
int ELFhash(char *key)
{ unsigned long h=0;
while(*key)
{ h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
6. 用哈希表實現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;
}
7. c語言數據結構有關哈希表的,要添加一個查找函數,具體程序看補充
現在還需要解答么?
8. 哈希表存儲C語言關鍵字的演算法以及利用Hash查找技術統計該程序中的關鍵字出現的頻度
線性探測,平方探測……
9. 數據結構 哈希表,C語言解答
設計一個哈希表,哈希函數用除留余數法,用開放定址法、線性探測處理沖突,從文本文件讀入30個左右中文人名,每行一人,可用本班學生名單。要求:
1.成功的平均查找長度不超過3,能查找人名,能插入新人名,能顯示當前哈希表中每個元素,每行顯示6個。
2.編寫主函數測試這些功能,並統計實際的平均查找長度。用菜單式操作。
3.如果有餘力,可以增加刪除功能(選做)。
提示:
根據成功的平均查找長度要求和估算公式求出裝填因子α上界及哈希表長度m。
#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()
{ int i;
char *f;
int r,s0;
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";
for (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()
{int i; for ( 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()
{ int r;
char name[20]={0};
int s0=0;
int sum=1;
int adr;
int d;
printf("\n\n請輸入姓名的拼音: "); //輸入姓名
scanf("%s",name);
for ( r=0;r<20;r++) //求出姓名的拼音所對應的整數(關鍵字)
s0+=name[r];
adr=s0 % M; //使用哈希函數
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()
{int i; float average=0; printf("\n\n地址\t關鍵字\t\t搜索長度\tH(key)\t\t拼音 \n"); //顯示的格式 for( 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");
}
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)
{ char ch1;
printf("\n\n");
printf(" 1. 顯示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");
err:
scanf("%c",&ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n請輸入正確的選擇!");
goto err;
}
}
}
10. 希望大家幫幫我啊!!!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);
}