1033: 散列表（1）

题目描述

已知Hash表的表长MaxSize为11，Hash函数为HashFunc（k）=k%11，冲突处理方法为线性探测法，部分代码如下，勿改动。请补充完成成员函数HashSearch，该函数的功能是动态查找k，若查找失败，则插入k，并返回查找失败所需的比较次数，若查找成功，返回查找k所需的比较次数，若表满，则抛出异常“Overflow”
#include
using namespace std;
const int MaxSize=11; //hash表的表长，即教材中的m
class HashList
{
private:
int ht[MaxSize]; // hashtable
public:
int HashFunc(int k); //hash function
HashList(); //consturctor
void Display(); //display
int HashSearch(int k); //dynamic search k
double HashASL(); //search ASL
};
//hash function
int HashList::HashFunc(int k)
{
return k%MaxSize; //hash函数，假设为除余法，余数为MaxSize
}
//constructor:initialize an empty hashlist
HashList::HashList()
{
int i;
for(i=0;i ht[i]=-1; //-1 is empty
}
void HashList::Display()
{
int i;
for(i=0;i cout< cout<}
double HashList::HashASL()
{
double ASL=0;
int i,n=0;
for(i=0;i if(ht[i]!=-1)
{
ASL+=HashSearch(ht[i]);
cout< n++;
}
// cout< return ASL/n;
}
//在下面补充动态查找算法
int main()
{
HashList HL;
// HL.Display();
while(1)
{
int k;
cin>>k;
if(!k) break;
try{
HL.HashSearch(k);
}
catch(const char *ms)
{
cout< }
}
HL.Display();
cout<<”ASL=”< return 0;
}

输入

输入数据以0结束，依次实现动态查找。

输出

输出数据 （各行数据依次为）：
hash表中的数据的输出；
各个元素的值及其查找次数；
ASL值

样例输入

47 7 29 11 16 92 22 8 3 29 0

样例输出

11 22 -1 47 92 16 3 7 29 8 -1
11 1
22 2
47 1
92 1
16 1
3 4
7 1
29 2
8 2
ASL=1.66667

提示

来源

提交

import java.util.Scanner;
class HashList{
    int MaxSize = 11;
    int[] ht = new int[MaxSize];
    int HashFunc(int k) {
        return k%MaxSize;
    }
    public HashList() {
        for(int i=0;i<MaxSize;i++)
            ht[i]=-1;
    }
    void Display(){
        for (int i=0;i<MaxSize;i++)
            System.out.print(ht[i]+" ");
        System.out.println();
    }
    int HashSearch(int k) throws Exception {
        int j = HashFunc(k);
        if (ht[j] == k)
            return 1;
        else if (ht[j] == -1)
            ht[j] = k;
        else {
            int i = (j + 1) % MaxSize;
            int cnt = 1;
            while (ht[i] != -1 && i != j) {
                cnt++;
                if (ht[i] == k) {
                    return cnt;
                } else
                    i = (i + 1) % MaxSize;
            }
            if(i == j) throw new Exception("Overflow");
            else {
                ht[i] = k;
            }
        }
        return -1;
    }
    double HashASL() throws Exception {
        double ASL=0;
        int n=0;
        for(int i=0;i<MaxSize;i++)
            if(ht[i]!=-1) {
                ASL+=HashSearch(ht[i]);
                System.out.println(ht[i] + " " + HashSearch(ht[i]));
                n++;
            }
        return (double)Math.round(ASL/n*100000)/100000;
    }
}
public class Main {
    public static void main(String[] args) throws Exception {
        HashList hashList = new HashList();
        Scanner scanner = new Scanner(System.in);
        while(true){
            int k = scanner.nextInt();
            if(k == 0)break;
            hashList.HashSearch(k);
        }
        hashList.Display();
        System.out.println("ASL="+hashList.HashASL());
    }
}