Problem1871--【查找】7-7 基于链地址法的散列表的删除

1871: 【查找】7-7 基于链地址法的散列表的删除

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
3
4
1 10 14 27
14
0

Sample Output Copy

0
1 1
2 2
3
4 4
5 5
6
7
8
9
10
11
12
0
1 1 27
2
3
4
5
6
7
8
9
10 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)
{//基于链地址法的散列表的插入
    int index=e%13;       //计算散列地址
    linkList p=H[index];   //工作指针p指向链表的头结点
    while(p->next)         //移至表尾
        p=p->next;
    linkList q=new LNode;    //生成新结点*q
    q->data=e;               //将新结点*q的数据域置为e
    q->next=NULL;            //将新结点*q插入在尾结点*p之后
    p->next=q;
}
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 Delete(int e)
{//基于链地址法的散列表的删除
    /**************begin************/
   
    /**************end************/
}
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;
        cin>>k;
        Delete(k);  //需要删除的关键字k
        Output();  //输出数据
    }
    return 0;
}

Source/Category