① C语言编程，求字符串的hash值（散列值）
#include<stdio.h>
intmain(){
chars[256];
char*p;
unsignedlonglonginth=0;
scanf("%s",s);
for(p=s;*p;p++){
h=h*31+*p;
}
printf("%llu",h);
}
② C语言中如何查找字符串
用strstr这个函数
包含文件：string.h
函数名: strstr
函数原型：extern char *strstr(char *str1, char *str2);
功能：找出str2字符串在str1字符串中第一次出现的位置（不包括str2的串结束符）。
返回值：返回该位置的指针，如找不到，返回空指针。
源代码:
#include<stdio.h>
#include<string.h>//调用string.h中的strstr函数
void main(){
char ch1[255]="abcde";
char ch2[100]="cd";
char* ch;//用于接受返回值
if((ch=strstr(ch1,ch2))==NULL){//说明没有要找的字符串
printf("-1\n");
}else{//说明找到了那个字符串
printf("%d\n",ch-ch1+1);//cde的地址减去abcde的地址+1
}
}
③ C语言 运用散列函数拼写检查
可以考虑建一个桶式的散列表,表的主体结构是个长为26*27的指针数组,每个指针分别指向一个子链表,每个链表分别存放开头为a,aa,ab,ac......g,ga,gb,......zy,zz为单词.(不区分大小写)
这样的话,假设单词存放在字符串str中,则散列函数就是
h(str)=(str[0]-'A')*27+str[1]-'A'
从题目给的散列函数就可以明显看出,散列表肯定要用长度为HASHSIZE的数组啊,你的链表设想肯定不符合题目要求
④ 希望大家帮帮我啊！！！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<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;
}