投稿
  1. 首页
  2. 软件运维

数据结构 哈希表，C语言解答

zeno • 2023-5-25 • 软件运维 • 阅读 34

数据结构 哈希表，C语言解答,第1张

#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="chengdaoquan"

NameList[9].py="ludaoqing"

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=0i<NAME_NOi++)// *求出各个姓名的拼音所对应的整数

{

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=0i<HASH_LENi++)//哈希表的初始化

{

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=0r<20r++)//求出姓名的拼音所对应的整数(关键字)

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=0i<15i++)

{

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=15i<30i++)

{

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=30i<40i++)

{

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=40i<50i++)

{

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=0i<HASH_LENi++)

{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

}

}

}

算法设计

已知一个含有100个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求在等概率情况下查找成功的平均查找长度不超过3。

（1） 根据平均查找长度不超过3，确定装填因子α；

snl≈1/2(1+(1/(1-α))){使用线性探测再散列解决冲突}

因snl<裂大慎=3,所以α至少为0.8,取α=0.8.

（2） 根据α确定表长

由α=（表中添入的记录数）/（哈希表的长度）

所以 哈希表的长度=100/α=125

取肆敬表长=150；

（3） 选取哈希函数

H(key)=key MOD 149

(4) key 的选取方法。

设大写字母在表中用1..26 表示，小写字母用27--52 表示。每个人的姓名取四个字

　母（两字姓名取首尾两个字母，三字姓名取各字拼音第一仿念个字母，中间字取首尾两

　个拼音字母）。

将前两个拼音字母的序号并起来，后两个也并起来, 然后相加形成关键字。要求姓名

　的第一个拼音字母要大写，如姓名'王丽明'拼音为'Wang liming'，取出四个拼音字母

　为'W,l,i,m',个字母序号依次为 23 38 35 39，组成关键字为 2338+3539=5877，该姓

　名的哈希地址为 5877 MOD 149=66。

(5) 用线性探测再散列处理冲突。

这是设计原理，别的要求没拉：（

有现成的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[i&0x0f] ^ x[(i-14)&0x0f] \

^ x[(i-8)&0x0f] ^ x[(i-3)&0x0f] \

, (x[i&0x0f] = 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

}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/yw/12487675.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
zeno zeno 一级用户组
0 0
上一篇 2023-05-25
下一篇 2023-05-25

发表评论

登录后才能评论

评论列表（0条）

保存