[SOJ] 简单哈希

Description

使用链地址法（又称拉链法）可以解决Hash中的冲突问题。其基本思想是：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构（图1）。

现在给定哈希函数为Hash(key)= key mod 13，要求使用链地址法处理冲突，设有冲突的元素均插入表尾。要求建立起相应哈希表，并按一定格式打印。

Input

输入包含多组数据。对于每组数据：

第1行为整数n（1 <=n <= 100），代表key的总数。
接下来n行，每行一个整数，代表一个key。Key与key两两不相同。

当n=0的时候表示输入结束。该行不作处理。

Output

对于每一组数据输出13行，每行表示某个哈希值下的Key。如果没有任何key，则对应NULL。Key之间用空格隔开，每行行末没有空格。格式如下面例子。

输出建立好的hash表，比如下表

应输出
0#22 11
1#89
2#NULL
3#3 47
4#37 92
5#16
6#50
7#29 7
8#8
9#NULL
10#10

Sample Input

Copy sample input to clipboard

Sample Output

0#7644 8723

1#2757 5890 5006

2#7711 7529 2316 288 106 4370

3#7673

4#6868 9741

5#9040

6#5141 3035 2190

7#5350

8#9264 6729

9#5547 1842 2648 3805 1101

10#4664 2662 7446

11#8253 37 778 8942

12#2859

#include<iostream>

#include<vector>

using namespace std;

int main()

{

    int num;

    int key;

    while(cin>>num&&num)

    {

       vector<int> hashTable[13];

       while(num--)

       {

          cin>>key;

          int temp=key%13;

          hashTable[temp].push_back(key);

       }

        for(int i=0;i<13;i++)

       {

          cout<<i<<'#';

          if(hashTable[i].empty())

             cout<<"NULL";

          else

          {

             for(vector<int>::iterator it=hashTable[i].begin(); it!=hashTable[i].end(); it++)

                cout<<*it<<" ";

          }

          cout<<endl;

       }

    }

    return 0;

}

巴特西

[SOJ] 简单哈希

最新文章

热门文章