12.23 Hash

没有整动态内存，静态hash凑乎看吧

 

#include <bits/stdc++.h>
using namespace std;
typedef char* Elemtype;
typedef  int   Status;
typedef Elemtype KeyType;
struct HashTable
{
    char elem[100][100];
    int count;
    int sizeindex;
};
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
int hashsize[500]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
const char NULLKEY = '\0';
int getHash(char *s,HashTable &H)
{
    return (s[0]-'a')*2%hashsize[H.sizeindex];
}
Status EQ(Elemtype K,Elemtype to)
{
    return !strcmp(K,to);
}
void collision(int &p , int cnt,HashTable H)
{
    p = (p+cnt)%hashsize[H.sizeindex];
}
Status SearchHash(HashTable H,KeyType K,int &p,int &c)
{
    p = getHash(K,H);
    while(H.elem[p][0]!=NULLKEY && !EQ(K,H.elem[p]))
    {
        collision(p,++c,H);
    }
    if(EQ(K,H.elem[p]))return SUCCESS;
    return UNSUCCESS;
}
Status InsertHash(HashTable &H,Elemtype e)
{
    cout<<e<<':'<<' ';
    int c = 0 , p;
    if(SearchHash(H,e,p,c)) {cout<<111<<endl;return DUPLICATE;}
    else if(c<hashsize[H.sizeindex]/2){
        cout<<p<<' ';
        for(int i = 0 ; i <= strlen(e) ; i++)
            H.elem[p][i]=e[i];
        ++H.count;
        cout<<"Success"<<endl;
        return 1;
    }
    cout<<000<<endl;
    return 0;
}
int main()
{
    char s[1000];
    HashTable H;
    H.sizeindex = 11;
    H.count = 0;
    memset(H.elem,0,sizeof(H.elem));
    srand((int)time(NULL));
    for(int i = 0 ; i <20;i++)
    {
        int length = rand()%30;
        for(int j = 0 ; j < length;j++)
        {
            s[j] = rand()%26+'a';
        }
        s[length] = '\0';
        cout<<s<<endl;
        InsertHash(H,s);
    }
    cout<<"+++++++++++++++++++"<<endl;
    for(int i = 0 ; i < hashsize[H.sizeindex] ;i ++) {
        if (H.elem[i][0])
        {
            int p;int c = 0;
            SearchHash(H,H.elem[i],p,c);
            cout << i<<' '<<H.elem[i] << ' '<<p<<endl;

        }
    }
    return 0;
}