1034: 散列表（2）

题目描述

已知Hash表的表长MaxSize为11，Hash函数为HashFunc（k）=k%11，冲突处理方法为链地址法，部分代码如下，勿改动。请补充完成成员函数HashSearch，该函数的功能是动态查找k，若查找失败，则插入k，并返回查找失败所需的比较次数，若查找成功，返回查找k所需的比较次数。
#include
using namespace std;
const int MaxSize=11; //maxsize
struct Node
{
int data;
Node next;
};
class LinkHash
{
public:
LinkHash(); //initialize an empty list
int HashFunc(int k); //hash function
int HashSearch(int k); //dynamic search k
void Display();
private:
Node ht[MaxSize]; //ht数组用来保留各个链表的头指针
};
//hash function
int LinkHash::HashFunc(int k)
{
return k%11; //hash函数，假设为除余法，余数为11
}
//constructor:initialize an empty hashlist
LinkHash::LinkHash()
{
int i;
for(i=0;i ht[i]=nullptr; //empty pointer
}
void LinkHash::Display()
{
int i;
for(i=0;i {
cout<<”Hash address:”< Node p;
for(p=ht[i];p!=nullptr;p=p->next)
cout<data<<” “;
cout< }
}
//在下面补充实现动态查找算法
int main()
{
LinkHash LS;
int k;
while(1)
{
cin>>k;
if(!k) break;
try{
LS.HashSearch(k);
// LS.Display();
}
catch(const char ms)
{
cout< }
}
LS.Display();
return 0;
}

输入

输出

样例输入

47 7 29 11 16 92 22 8 3 29 0

样例输出

Hash address:0,value:22 11
Hash address:1,value:
Hash address:2,value:
Hash address:3,value:3 47
Hash address:4,value:92
Hash address:5,value:16
Hash address:6,value:
Hash address:7,value:29 7
Hash address:8,value:8
Hash address:9,value:
Hash address:10,value:

提示

来源

提交

import java.util.Scanner;
class Node{
    int data;
    Node next;
}
class LinkHash{
    int MaxSize = 11;
    Node[] ht = new Node[MaxSize];
    public LinkHash() {
        for (int i = 0; i < MaxSize; i++)
            ht[i] = null;  //NULL is empty
    }
    void Display() {
        for (int i = 0; i < MaxSize; i++) {
            System.out.print("Hash address:" + i + ",value:");
            for (Node p = ht[i]; p != null; p = p.next)
                System.out.print(p.data + " ");
            System.out.println();
        }
    }
    int HashFunc(int k){
        return k % 11;   //hash函数，假设为除余法，余数为11
    }
    int HashSearch(int k){
        int j = HashFunc(k);
        Node p = ht[j];
        while(p!=null && p.data != k) {
            p = p.next;
        }
        if(p!=null && p.data == k) return 1;
        else {
            Node s = new Node();
            s.data = k;
            s.next = ht[j];
            ht[j] = s;
        }
        return 0;
    }
}
public class Main {
    public static void main(String[] args) {
        LinkHash linkHash = new LinkHash();
        Scanner scanner = new Scanner(System.in);
        while(true){
            int k = scanner.nextInt();
            if(k == 0)break;
            linkHash.HashSearch(k);
        }
        linkHash.Display();
    }
}