Problem1870--【查找】7-6 基于链地址法的散列表的插入

1870: 【查找】7-6 基于链地址法的散列表的插入

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

请写出在散列表中插入关键字为k的一个记录的算法,设散列函数为H,H(key)=key%13,解决冲突的方法为链地址法。

Input

多组数据,每组三行,第一行为待输入的关键字的个数n,第二行为对应的n个关键字,第三行为需要插入的关键字k。当n=0时输入结束。

Output

每组数据输出用链地址法处理冲突的散列表。

Sample Input Copy

5
1 4 2 3 5
6
4
2 5 8 15
18
0

Sample Output Copy

0
1 1
2 2
3 3
4 4
5 5
6 6
7
8
9
10
11
12
0
1
2 2 15
3
4
5 5 18
6
7
8 8
9
10
11
12

HINT

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*linkList;
linkList H[13];    //链地址法,13个单链表
void Hash(int e)
{//基于链地址法的散列表的插入
    /**************begin************/
   
    /**************end************/
}
void Input(int n)
{//输入数据
    for(int i=0;i<13;i++)     //建立13个带有头结点的单链表
    {
        H[i]=new LNode;
        H[i]->next=NULL;
    }
    while(n--)          //输入n个关键字,构造散列表
    {
        int e;
        cin>>e;
        Hash(e);
    }
}
void Output()
{//输出数据
    for(int i=0;i<13;i++)
    {
        cout<<i;                 //输出散列地址
        linkList p=H[i]->next;   //p初始化为链表的首元结点
        while(p)
        {
            cout<<" "<<p->data;
            p=p->next;
        }
        cout<<endl;
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        Input(n);     //输入数据
        int k;      //需要插入的关键字k
        cin>>k;
        Hash(k);
        Output();  //输出数据
    }
    return 0;
}

Source/Category