哈希表链地址法.cpp

vc开发的二次探测在散列算法,学习数据结构的学习者看看吧!!

// 哈希表链地址法.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream.h>
#define MAX 100

int ha[MAX],hlen[MAX],n,m,p;

void creathash()
{
         int i,j,d,d1,odd,s,key[MAX];
         cout<<("           =======建立散列表=========        ")<<endl;
         cout<<("输入元素个数 n:");
         cin>>n;
         cout<<("输入哈希表长 m:");
         cin>>m;
         cout<<("散列函数：h(k)=k MOD p:");
         cin>>p;
         for(i=0;i<m;i++) ha[i]=hlen[i]=0;
             i=0;
         while(i<n)
		 {
            cout<<"第"<<i+1<<"个元素："<<" ";
            cin>>key[i];
                odd=1;
            if(key[i]<=0) cout<<("输入错误，重新输入！\n");
            else 
				i++;
		 }
                i=0;
            cout<<("哈希表建立如下：\n");
          while(i<n)
		  {
                odd=1;
            d=d1=key[i]%p;
            j=s=1;
            cout<<d<<endl;
          while(ha[d]!=0)
		  {
               cout<<(" 冲突\n");
             if(odd)
			 {
               d=(d1+j*j)%m;
               cout<<d<<endl;
               odd=0;
			 }
             else
			 {
               d=(d1-j*j)%m;
               cout<<d<<endl;
               odd=1;
               j++;
			 }
               s++;
		  }
           cout<<s<<endl;
           ha[d]=key[i];
           hlen[d]=s;
               i++;
		  }
}
/*void disphash()
{
        int i,s=0;
        cout<<("\n 散列表H为：\n");
        for(i=0;i<m;i++)
        cout<<(i);
        cout<<("\n");
        for(i=0;i<m;i++)
        cout<<(ha[i]);
        cout<<("\n");
        for(i=0;i<m;i++)
        cout<<(hlen[i]);
        cout<<("\n");
        for(i=0;i<m;i++)
        s=s+hlen[i];
        cout<<(n,(1.0*s)/n);  
}*/
/*void findhash()
{
        int x,j,d,d1,odd=1;
        cout<<("\n 输入查找的值：");
        cin>>x;
        d=d1=x%p;
        j=1;
        while(ha[d]!=0 && ha[d]!=x)
		{
             if(odd)
			 {
             d=(d1+j*j)%m;
             odd=0;
			 }
             else
			 {
             d=(d1-j*j)%m;
             odd=1;
             j++;
			 }
		}
        if(ha[d]==0) cout<<("\t 输入的查找值不正确！\n");
        else cout<<(d,x);//"\t 查找值：ha[%d]=%d!\n",
}*/
void main()
{
       creathash();
      // disphash();
      // findhash();
}