/**//*--------------------------------------------------------
 *    hashtable.cpp
 *    Describe : example for hashing
 *    author   : JackRain
 *    date     : 08-13-2005
 *    E_mail   :  jack.fandlr@gmail.com
 *    Test with C-Free3.5
---------------------------------------------------------*/

#include <iostream>

#define addr_scope 11
int hash(int key)
{
    return(key*3)%11;
}
typedef int KeyType,DataType,Status;
//typedef int DataType;
//typedef int Status;
typedef struct {
     KeyType key;
 //    DataType data;
     Status   stat;   //1 = over; 0
}Element;

class HashTable
{
    public:
            HashTable(int n);
            ~HashTable();
            bool insert(int e);
            bool search(int e, int *pos);
            void display();
    private:
            Element *elem;
            int     hash_size;
            int     dataNum;
};
HashTable::HashTable(int n):hash_size(n),dataNum(0)
{
  //  hash_size = n;
   // dataNum = 0;
    elem = new Element[n];
    for(int i=0;i < n;i++)
     {
        elem[i].key = 0;
        elem[i].stat = 0;
    }
}

HashTable::~HashTable()
{
    delete[] elem;
}

bool HashTable::insert(int e)
{
    if(dataNum == hash_size)
     {
        cout<<"OverFlow!"<<endl;
        return false;
    }
    int pos = hash(e),pos1;
      pos1 = pos;
    for(int i = 1; i < hash_size; i ++)
     {
        if(elem[pos].stat==0)
         {
            //success
            elem[pos].key = e;
            elem[pos].stat = 1;
            dataNum++;
            cout<<"Insert Value Success!The value is:"<<e<<";the addr is:"<<pos<<endl;
            return true;
        }
        pos = (pos1+i)%hash_size;
    }
    cout<<"Insert Value Faliure"<<endl;
    return false;
}

bool HashTable::search(int key, int* pos)
{
    int hashvalue = hash(key);
    for(int i = 1; i< hash_size; i ++)
     {
        if(elem[hashvalue].stat==1&&elem[hashvalue].key == key)
         {
            cout<<"Search Success!Search Nums="<<i<<endl;
            *pos = hashvalue;
            return true;
        }
        hashvalue = (hashvalue+1)%hash_size;
    }
    
    cout<<"Not found"<<endl;
    return false;
}

void HashTable::display()
{
    if(dataNum == 0)
     {
        cout<<"The Table is NULL"<<endl;
        return;
    }
    cout<<"************HashTable*************"<<endl;
    cout<<"addr                         value"<<endl;
    for(int i = 0; i<hash_size;i++)
     {
        if(elem[i].stat == 0)
            continue;
        else
            cout.width(4);
            cout<<elem[i].key;
            cout<<"                         ";
            cout.width(5);
            cout<<i<<endl;
    }
    cout<<"************************************"<<endl;
}

int main()
{
    int array[]= {22, 41, 53, 46, 30,13, 01,67};
    HashTable hTable(addr_scope);
    for(int i =0;i < 8;i++)
    hTable.insert(array[i]);
    hTable.display();
    return 0;
}
查找不成功的平均查找長(zhǎng)度ASL＝（2+1+8+7+6+5+4+3+2+1+1）/11≈3.63