13518219792
#include stdio.h#include stdlib.h//这里我自己设计一个hash算法来快速查找一堆数字中相等的数字，这也许是最接近原理的算法了//一个整数整除27后的来作为hash函数//定义一个保存实际数据的结构体节点struct data_node{ int num; int count; struct data_node *next;};//定义一个结构体时hash表的一部分typedef struct{ int key; //余数 struct data_node *p; //链表的头指针} hash_node;#define HASH_SIZE 27int do_hash(int num) //hash表来求余数，这样就可以了{ return num%HASH_SIZE;}//初始化//添加数字//更新数字//删除数字//查找数字hash_node HashTable[HASH_SIZE]; //这里申明一个hashtable的数组//初始化函数，需要做的事将key复制为null，将p指针指向null,返回一个头指针来指向这个hashtablevoid InitHashTable(hash_node *HashTable)
创新互联专业为企业提供石狮网站建设、石狮做网站、石狮网站设计、石狮网站制作等企业网站建设、网页设计与制作、石狮企业网站模板建站服务，十年石狮做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
{ //进行参数的校验 for(int i=0;iHASH_SIZE;i++)
{
HashTable[i].key = 0; HashTable[i].p =NULL; }
}//保存到这个链表中//如果这个链表是空的话，就作为头指针，如果这个链表不为空，则添加到吧数字添加到末尾int savedata(struct data_node **head,int num)
{ struct data_node *tmp_p = *head; struct data_node *p = (struct data_node *)malloc(sizeof(struct data_node)); if(p == NULL) return 0; if(*head == NULL)
{
*head = p; p-count = 1; p-num = num; p-next = NULL; } else //如果不为空，则这个时候应该添加到链表末尾 { while(tmp_p != NULL)//如果存在，则将这个节点的count加1就可以了 { if(tmp_p-num == num)
{
free(p); ++tmp_p-count ; return 0; } if(tmp_p-next == NULL) break; tmp_p = tmp_p-next; }
tmp_p-next = p; p-count =1; p-num = num; p-next = NULL; } return 0;}//添加数字//将这个数字经过hash求出结果，然后再保存到相应的链表中//返回真或者假就可以了int add_hash(hash_node *HashTable,int num)
{ int mod = do_hash(num); return savedata(HashTable[mod].p,num);}int main()
{ int num = 100; hash_node *H = HashTable; InitHashTable(H); add_hash(H,num); add_hash(H,num); add_hash(H,3); add_hash(H,1); add_hash(H,4); //在这里我们可以发现一个好的hash函数是多么的重要，如果hash函数不好造成很多冲突的话，效率并不会提高很多的，理想的情况是冲突几乎没有 //这也就是设计hash函数的精髓所在 return 0;}
应该是这个意思：
第一次冲突就是散列的位置+1，这次发生冲突了就继续第二次
第二次用的是平方取中，55^2= 3025，当然第二次冲突的RH2就是02了，答案(2)
/#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;
cintemp-name;
cout"输入地址："endl;
cintemp-address;
cout"输入电话："endl;
cintemp-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;i20;i++)
{
phone[i]=new node;
phone[i]-next=NULL;
}
}
void create2() //新建节点
{
int i;
nam=new mingzi[20];
for(i=0;i20;i++)
{
nam[i]=new node;
nam[i]-next=NULL;
}
}
void list() //显示列表
{
int i;
node *p;
for(i=0;i20;i++)
{
p=phone[i]-next;
while(p)
{
coutp-name'_'p-address'_'p-numendl;
p=p-next;
}
}
}
void list2() //显示列表
{
int i;
node *p;
for(i=0;i20;i++)
{
p=nam[i]-next;
while(p)
{
coutp-name'_'p-address'_'p-numendl;
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)
coutq-name"_" q-address"_"q-numendl;
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)
coutq-name"_" q-address"_"q-numendl;
else cout"无此记录"endl;
}
void save() //保存用户信息
{
int i;
node *p;
for(i=0;i20;i++)
{
p=phone[i]-next;
while(p)
{
fstream iiout("out.txt", ios::out);
iioutp-name"_"p-address"_"p-numendl;
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();
cinsel;
if(sel==3)
{ cout"9号码查询，8姓名查询"endl;
int b;
cinb;
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;
}
#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,
1.选择合适的哈希函数H(key)=key%p(p为小于或等于哈希表长的最大质数)；
2.计算各个关键字的直接哈希函数值；
3.根据处理冲突的方法建立哈希表，并输出；
4.在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。
#includestdlib.h
#includestdio.h
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
} ElemType;
int haxi(KeyType key,int m) /*根据哈希表长m，构造除留余数法的哈希函数haxi*/
{
int i,p,flag;
for(p=m;p=2;p--) /*p为不超过m的最大素数*/
{
for(i=2,flag=1;i=p/2flag;i++)
if(p%i==0)
flag=0;
if(flag==1)
break;
}
return key%p; /*哈希函数*/
}
void inputdata(ElemType **ST,int n) /*从键盘输入n个数据，存入数据表ST(采用动态分配的数组空间)*/
{
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\nPlease input %d data:",n);
for(i=1;i=n;i++)
scanf("%d",((*ST)[i].key));
}
void createhaxi(ElemType **HASH,ElemType *ST,int n,int m) /*由数据表ST构造哈希表HASH，n、m分别为数据集合ST和哈希表的长度*/
{
int i,j;
(*HASH)=(ElemType *)malloc(m*sizeof(ElemType));
for(i=0;im;i++)
(*HASH)[i].key=NULL; /*初始化哈希为空表(以0表示空)*/
for(i=0;in;i++)
{
j=haxi(ST[i].key,m); /*获得直接哈希地址*/
while((*HASH)[j].key!=NULL)
j=(j+1)%m; /*用线性探测再散列技术确定存放位置*/
(*HASH)[j].key=ST[i].key; /*将元素存入哈希表的相应位置*/
}
}
int search(ElemType *HASH,KeyType key,int m,int *time) /*在表长为m的哈希表中查找关键字等于key的元素，并用time记录比较次数，若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/
{
int i;
*time=1;
i=haxi(key,m);
while(HASH[i].key!=0HASH[i].key!=key)
{
i++;
++*time;
}
if(HASH[i].key==0)
return -1;
else
return i;
}
main()
{
ElemType *ST,*HASH;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\nPlease input nm(n=m)"); /*输入关键字集合元素个数和哈希表长*/
scanf("%d%d",n,m);
inputdata(ST,n); /*输入n个数据*/
createhaxi(HASH,ST,n,m); /*创建哈希表*/
printf("\nThe haxi Table is\n"); /*输出已建立的哈希表*/
for(i=0;im;i++)
printf("%5d",i);
printf("\n");
for(i=0;im;i++)
printf("%5d",HASH[i].key);
do /*哈希表的查找，可进行多次查找*/
{
printf("\nInput the key you want to search:");
scanf("%d",key);
i=search(HASH,key,m,time);
if(i!=-1) /*查找成功*/
{
printf("\nSuccess,the position is %d",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失败*/
{
printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContiue(y/n):\n"); /*是否继续查找yes or no*/
ch=getch();
}
while(ch=='y'||ch=='Y'); /*计算表在等概率情况下的平均查找长度，并输出*/
for(stime=0,i=0;in;i++)
{
search(HASH,ST[i].key,m,time);
stime+=time;
}
printf("\nThe Average Search Length is %5.2f",(float)stime/n);
ch=getch();
}
有现成的SHA1算法函数
复制过来。
然后打开文件， 读数据， 调用SHA1函数即可。
#include stdio.h
#include stdlib.h
#include string.h
#include assert.h
#include errno.h
#undef BIG_ENDIAN_HOST
typedef unsigned int u32;
/****************
* Rotate a 32 bit integer by n bytes
*/
#if defined(__GNUC__) defined(__i386__)
static inline u32
rol( u32 x, int n)
{
__asm__("roll %%cl,%0"
:"=r" (x)
:"0" (x),"c" (n));
return x;
}
#else
#define rol(x,n) ( ((x) (n)) | ((x) (32-(n))) )
#endif
typedef struct {
u32 h0,h1,h2,h3,h4;
u32 nblocks;
unsigned char buf[64];
int count;
} SHA1_CONTEXT;
void
sha1_init( SHA1_CONTEXT *hd )
{
hd-h0 = 0x67452301;
hd-h1 = 0xefcdab89;
hd-h2 = 0x98badcfe;
hd-h3 = 0x10325476;
hd-h4 = 0xc3d2e1f0;
hd-nblocks = 0;
hd-count = 0;
}
/****************
* Transform the message X which consists of 16 32-bit-words
*/
static void
transform( SHA1_CONTEXT *hd, unsigned char *data )
{
u32 a,b,c,d,e,tm;
u32 x[16];
/* get values from the chaining vars */
a = hd-h0;
b = hd-h1;
c = hd-h2;
d = hd-h3;
e = hd-h4;
#ifdef BIG_ENDIAN_HOST
memcpy( x, data, 64 );
#else
{
int i;
unsigned char *p2;
for(i=0, p2=(unsigned char*)x; i 16; i++, p2 += 4 )
{
p2[3] = *data++;
p2[2] = *data++;
p2[1] = *data++;
p2[0] = *data++;
}
}
#endif
#define K1 0x5A827999L
#define K2 0x6ED9EBA1L
#define K3 0x8F1BBCDCL
#define K4 0xCA62C1D6L
#define F1(x,y,z) ( z ^ ( x ( y ^ z ) ) )
#define F2(x,y,z) ( x ^ y ^ z )
#define F3(x,y,z) ( ( x y ) | ( z ( x | y ) ) )
#define F4(x,y,z) ( x ^ y ^ z )
#define M(i) ( tm = x[i0x0f] ^ x[(i-14)0x0f] \
^ x[(i-8)0x0f] ^ x[(i-3)0x0f] \
, (x[i0x0f] = rol(tm,1)) )
#define R(a,b,c,d,e,f,k,m) do { e += rol( a, 5 ) \
+ f( b, c, d ) \
+ k \
+ m; \
b = rol( b, 30 ); \
} while(0)
R( a, b, c, d, e, F1, K1, x[ 0] );
R( e, a, b, c, d, F1, K1, x[ 1] );
R( d, e, a, b, c, F1, K1, x[ 2] );
R( c, d, e, a, b, F1, K1, x[ 3] );
R( b, c, d, e, a, F1, K1, x[ 4] );
R( a, b, c, d, e, F1, K1, x[ 5] );
R( e, a, b, c, d, F1, K1, x[ 6] );
R( d, e, a, b, c, F1, K1, x[ 7] );
R( c, d, e, a, b, F1, K1, x[ 8] );
R( b, c, d, e, a, F1, K1, x[ 9] );
R( a, b, c, d, e, F1, K1, x[10] );
R( e, a, b, c, d, F1, K1, x[11] );
R( d, e, a, b, c, F1, K1, x[12] );
R( c, d, e, a, b, F1, K1, x[13] );
R( b, c, d, e, a, F1, K1, x[14] );
R( a, b, c, d, e, F1, K1, x[15] );
R( e, a, b, c, d, F1, K1, M(16) );
R( d, e, a, b, c, F1, K1, M(17) );
R( c, d, e, a, b, F1, K1, M(18) );
R( b, c, d, e, a, F1, K1, M(19) );
R( a, b, c, d, e, F2, K2, M(20) );
R( e, a, b, c, d, F2, K2, M(21) );
R( d, e, a, b, c, F2, K2, M(22) );
R( c, d, e, a, b, F2, K2, M(23) );
R( b, c, d, e, a, F2, K2, M(24) );
R( a, b, c, d, e, F2, K2, M(25) );
R( e, a, b, c, d, F2, K2, M(26) );
R( d, e, a, b, c, F2, K2, M(27) );
R( c, d, e, a, b, F2, K2, M(28) );
R( b, c, d, e, a, F2, K2, M(29) );
R( a, b, c, d, e, F2, K2, M(30) );
R( e, a, b, c, d, F2, K2, M(31) );
R( d, e, a, b, c, F2, K2, M(32) );
R( c, d, e, a, b, F2, K2, M(33) );
R( b, c, d, e, a, F2, K2, M(34) );
R( a, b, c, d, e, F2, K2, M(35) );
R( e, a, b, c, d, F2, K2, M(36) );
R( d, e, a, b, c, F2, K2, M(37) );
R( c, d, e, a, b, F2, K2, M(38) );
R( b, c, d, e, a, F2, K2, M(39) );
R( a, b, c, d, e, F3, K3, M(40) );
R( e, a, b, c, d, F3, K3, M(41) );
R( d, e, a, b, c, F3, K3, M(42) );
R( c, d, e, a, b, F3, K3, M(43) );
R( b, c, d, e, a, F3, K3, M(44) );
R( a, b, c, d, e, F3, K3, M(45) );
R( e, a, b, c, d, F3, K3, M(46) );
R( d, e, a, b, c, F3, K3, M(47) );
R( c, d, e, a, b, F3, K3, M(48) );
R( b, c, d, e, a, F3, K3, M(49) );
R( a, b, c, d, e, F3, K3, M(50) );
R( e, a, b, c, d, F3, K3, M(51) );
R( d, e, a, b, c, F3, K3, M(52) );
R( c, d, e, a, b, F3, K3, M(53) );
R( b, c, d, e, a, F3, K3, M(54) );
R( a, b, c, d, e, F3, K3, M(55) );
R( e, a, b, c, d, F3, K3, M(56) );
R( d, e, a, b, c, F3, K3, M(57) );
R( c, d, e, a, b, F3, K3, M(58) );
R( b, c, d, e, a, F3, K3, M(59) );
R( a, b, c, d, e, F4, K4, M(60) );
R( e, a, b, c, d, F4, K4, M(61) );
R( d, e, a, b, c, F4, K4, M(62) );
R( c, d, e, a, b, F4, K4, M(63) );
R( b, c, d, e, a, F4, K4, M(64) );
R( a, b, c, d, e, F4, K4, M(65) );
R( e, a, b, c, d, F4, K4, M(66) );
R( d, e, a, b, c, F4, K4, M(67) );
R( c, d, e, a, b, F4, K4, M(68) );
R( b, c, d, e, a, F4, K4, M(69) );
R( a, b, c, d, e, F4, K4, M(70) );
R( e, a, b, c, d, F4, K4, M(71) );
R( d, e, a, b, c, F4, K4, M(72) );
R( c, d, e, a, b, F4, K4, M(73) );
R( b, c, d, e, a, F4, K4, M(74) );
R( a, b, c, d, e, F4, K4, M(75) );
R( e, a, b, c, d, F4, K4, M(76) );
R( d, e, a, b, c, F4, K4, M(77) );
R( c, d, e, a, b, F4, K4, M(78) );
R( b, c, d, e, a, F4, K4, M(79) );
/* Update chaining vars */
hd-h0 += a;
hd-h1 += b;
hd-h2 += c;
hd-h3 += d;
hd-h4 += e;
}
/* Update the message digest with the contents
* of INBUF with length INLEN.
*/
static void
sha1_write( SHA1_CONTEXT *hd, unsigned char *inbuf, size_t inlen)
{
if( hd-count == 64 ) { /* flush the buffer */
transform( hd, hd-buf );
hd-count = 0;
hd-nblocks++;
}
if( !inbuf )
return;
if( hd-count ) {
for( ; inlen hd-count 64; inlen-- )
hd-buf[hd-count++] = *inbuf++;
sha1_write( hd, NULL, 0 );
if( !inlen )
return;
}
while( inlen = 64 ) {
transform( hd, inbuf );
hd-count = 0;
hd-nblocks++;
inlen -= 64;
inbuf += 64;
}
for( ; inlen hd-count 64; inlen-- )
hd-buf[hd-count++] = *inbuf++;
}
/* The routine final terminates the computation and
* returns the digest.
* The handle is prepared for a new cycle, but adding bytes to the
* handle will the destroy the returned buffer.
* Returns: 20 bytes representing the digest.
*/
static void
sha1_final(SHA1_CONTEXT *hd)
{
u32 t, msb, lsb;
unsigned char *p;
sha1_write(hd, NULL, 0); /* flush */;
t = hd-nblocks;
/* multiply by 64 to make a byte count */
lsb = t 6;
msb = t 26;
/* add the count */
t = lsb;
if( (lsb += hd-count) t )
msb++;
/* multiply by 8 to make a bit count */
t = lsb;
lsb = 3;
msb = 3;
msb |= t 29;
if( hd-count 56 ) { /* enough room */
hd-buf[hd-count++] = 0x80; /* pad */
while( hd-count 56 )
hd-buf[hd-count++] = 0; /* pad */
}
else { /* need one extra block */
hd-buf[hd-count++] = 0x80; /* pad character */
while( hd-count 64 )
hd-buf[hd-count++] = 0;
sha1_write(hd, NULL, 0); /* flush */;
memset(hd-buf, 0, 56 ); /* fill next block with zeroes */
}
/* append the 64 bit count */
hd-buf[56] = msb 24;
hd-buf[57] = msb 16;
hd-buf[58] = msb 8;
hd-buf[59] = msb ;
hd-buf[60] = lsb 24;
hd-buf[61] = lsb 16;
hd-buf[62] = lsb 8;
hd-buf[63] = lsb ;
transform( hd, hd-buf );
p = hd-buf;
#ifdef BIG_ENDIAN_HOST
#define X(a) do { *(u32*)p = hd-h##a ; p += 4; } while(0)
#else /* little endian */
#define X(a) do { *p++ = hd-h##a 24; *p++ = hd-h##a 16; \
*p++ = hd-h##a 8; *p++ = hd-h##a; } while(0)
#endif
X(0);
X(1);
X(2);
X(3);
X(4);
#undef X
}
