数据结构C++版王红梅 OJ习题

2022-11-01 19:32:38

1035: 散列表（3）*

Description

已知Hash表的表长MaxSize为11，Hash函数为HashFunc（k）=k%11，冲突处理方法为线性探测法，部分代码如下，勿改动。请补充完成成员函数HashSearch，和函数HashASL，其中函数HashSearch的功能是动态查找k，若查找失败，返回查找失败所需的比较次数，若查找成功，返回查找k所需的比较次数。HashASL的功能是计算等概论查找成功时的ASL值。

#include<iostream>        

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();

    double HashASL();

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<MaxSize;i++)

ht[i]=NULL;  //NULL is empty

}

void LinkHash::Display()

{

int i;

for(i=0;i<MaxSize;i++)

{

cout<<"Hash address:"<<i<<",value:";

Node *p;

for(p=ht[i];p;p=p->next)

cout<<p->data<<" ";

cout<<endl;

}

}

int main()

{

LinkHash LS;

  int k;

while(1)

{

cin>>k;

if(!k) break;

try{

LS.HashSearch(k); 

// LS.Display(); 

}

catch(const char *ms)

{

cout<<ms<<endl;

}

}

LS.Display();  

cout<<"ASL="<<LS.HashASL();

return 0;

}

Input

Output

Sample Input

47 7 29 11 16 92 22 8 3 29 0

Sample Output

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:
ASL=1.33333

//
// Created by Legends丶Hu on 2020/2/6.
//

#include<iostream>

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();

    double HashASL();

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 < MaxSize; i++)
        ht[i] = NULL;  //NULL is empty
}

void LinkHash::Display() {
    int i;
    for (i = 0; i < MaxSize; i++) {
        cout << "Hash address:" << i << ",value:";
        Node *p;
        for (p = ht[i]; p; p = p->next)
            cout << p->data << " ";
        cout << endl;
    }
}
int LinkHash::HashSearch(int k) {
    int j = HashFunc(k);
    Node *p = ht[j];
    int cnt = 1;
    while (p && p->data != k){
        p = p->next;
        cnt++;
    }
    if(p && p->data == k)return cnt;
    Node *s = new Node;
    s->data = k;
    s->next = ht[j];
    ht[j] = s;
}
double LinkHash::HashASL() {
    double s = 0;
    int n = 0;
    for(int i = 0; i < MaxSize; i++) {
        for(Node *p = ht[i]; p; p = p->next,n++) {
            s += HashSearch(p->data);
        }
    }
    return s / n;
}

//47 7 29 11 16 92 22 8 3 29 0
int main() {
    LinkHash LS;
    int k;
    while (1) {
        cin >> k;
        if (!k) break;
        try {
            LS.HashSearch(k);
// LS.Display();
        }
        catch (const char *ms) {
            cout << ms << endl;
        }
    }
    LS.Display();
    cout << "ASL=" << LS.HashASL();
    return 0;
}

码农公寓