数据结构C语言实现散列：创建、解决冲突、查找元素.doc

实验课题：做这个实验时采用Open Addressing框架，也可加做Separate Chaining以形成比较。
1 构造散列表，把字符串数组中的各项加入到散列表中
string MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay",
"owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };
用C表示，可以是
char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay",
"owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };
为便于观察冲突现象，初始构造散列表时，表的容量不要过大，对Open Addressing，装载因子为0.5左右，对于Separate Chaining，装载因子为1左右即可。也不要做rehash（应该改源代码的哪里，如何改）。
建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决；
对于Open Addressing，参考代码的冲突解决方案是用的平方探测（quadratic probing），如果用线性探测（linear probing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里）？

2 观察不同的散列函数产生冲突散列地址的情况
教科书上给了3个以字符串作输入的散列函数（两教科书第3个不一样），观察记录它们产生冲突散列地址的情况，写入你的实验报告。还可对下列散列函数（所谓ELF hash，Unix System V用的）作观察
5

int hash (char * key)
{ // C version
unsigned long h = 0;
while ( *key ) {
h = (h << 4) + *key ++;
unsigned long g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h; // % M
}
int hash (const string & key)
{ // C++ version
unsigned long h = 0;
for ( int i = 0; i < key.length( ); i++ ) {
h = (h << 4) + key [ i ];
unsigned long g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h; // % M
}
3 对散列表做查找。

程序代码：
#include<stdio.h>
#include<stdlib.h>
#include "hashquad.h"
#include<string.h>
#define MinTableSize 26
typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef struct HashTbl *HashTable;

enum KindOfEntry { Legitimate, Empty, Deleted };

struct HashEntry
{
char *Element;
enum KindOfEntry Info;
};

typedef struct HashEntry Cell;
struct HashTbl
{
int TableSize;
Cell *TheCells;
};
static int NextPrime( int N )
{
int i;
if( N % 2 == 0 )
N++;
for( ; ; N += 2 )
{
for( i = 3; i * i <= N; i += 2 )
if( N % i == 0 )
goto ContOuter;
return N;
ContOuter: ;
}
}

Index Hash( const char *Key, int TableSize )
{
return *Key % TableSize;
}

HashTable InitializeTable( int TableSize )
{
HashTable H;
int i;

/* 1*/ if( TableSize < MinTableSize )
{
/* 2*/ printf( "Table size too small" );
/* 3*/ return NULL;
}

/* Allocate table */
/* 4*/ H = (struct HashTbl *)malloc( sizeof( struct HashTbl ) );
/* 5*/ if( H == NULL )
/* 6*/ printf( "Out of space!!!" );

/* 7*/ H->TableSize = NextPrime( TableSize );

/* Allocate array of Cells */
/* 8*/ H->TheCells = (struct HashEntry *)malloc( sizeof( Cell ) * H->TableSize );
/* 9*/ if( H->TheCells == NULL )
/*10*/ printf( "Out of space!!!" );

/*11*/ for( i = 0; i < H->TableSize; i++ )
{
H->TheCells[i].Element=(char *)malloc(10*sizeof(char));
H->TheCells[i].Info=Empty;
}
/*12*/

/*13*/ return H;
}
Position Find( char *Key, HashTable H )

{
Position CurrentPos;
int CollisionNum;

/* 1*/ CollisionNum = 0;
/* 2*/ CurrentPos = Hash( Key, H->TableSize );
//printf("%d\n",CurrentPos);

/* 3*/ while( H->TheCells[ CurrentPos ].Info != Empty &&
strcmp(H->TheCells[ CurrentPos ].Element,Key)!=0 )
/* Probably need strcmp!! */
{
if (H->TheCells[ CurrentPos ].Element!= NULL)
printf("冲突: %s and %s\n", H->TheCells[ CurrentPos ].Element,Key);
/* 4*/ CurrentPos += 2 * ++CollisionNum - 1;
/* 5*/ if( CurrentPos >= H->TableSize )
/* 6*/ CurrentPos -= H->TableSize;
}
/* 7*/ return CurrentPos;
}
void Insert( char *Key, HashTable H )
{
Position Pos;

Pos = Find( Key, H );
if( H->TheCells[ Pos ].Info != Legitimate )
{
/* OK to insert here */
H->TheCells[ Pos ].Info = Legitimate;
strcpy(H->TheCells[ Pos ].Element,Key);
/* Probably need strcpy! */

}
}
/*char
*Retrieve( Position P, HashTable H )
{
return H->TheCells[ P ].Element;
}
*/
void DestroyTable( HashTable H )
{
free( H->TheCells );
free( H );
}
void main()
{
int i,x,n;
char s[10];
HashTable H;
char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay",
"owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };
printf(" \n");
printf("原来的MyBirds：\n\n");
printf(" 字符串 位置\n");
for(i=0;i<13;i++)
printf("%8s: %2d\n",MyBirds[i],i+1);
/*printf(" \n");
printf("生成散列表：\n");
n=Hash( Key, H->TableSize );
for(i=0;i<13;i++)
printf("%8s: %2d\n",MyBirds[i],i+1);*/
H=InitializeTable( 29 );
printf(" \n");
printf("生成散列表：\n\n");
printf(" 字符串 散列值 位置\n");
for(i=0;i<13;i++)
Insert(MyBirds[i] , H );

for(i=0;i<29;i++)
{

if(H->TheCells[i].Info!=Empty)
printf("%8s: %2d %d\n",
H->TheCells[i].Element,
x=Hash(H->TheCells[i].Element,29),
n=Find( H->TheCells[i].Element,H));
}
printf("请输入要查找的值：");
scanf("%s",s);
for(i=0;i<29;i++)
{
if(strcmp(H->TheCells[i].Element,s)==0)
break;

}
if(i<29)
printf("查找成功，位置在：%d\n ",Find( s,H));
else printf("查找失败 \n");
DestroyTable( H );
}