BJFU_数据结构习题_292基于链地址法的散列表的插入

痛定思痛。 2023-06-16 12:58 7阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 292基于链地址法的散列表的插入 ###

**描述**  
请写出在散列表中插入关键字为k的一个记录的算法，设散列函数为H,H(key)=key%13，解决冲突的方法为链地址法。  
**输入**  
多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要插入的关键字k。当n=0时输入结束。  
**输出**  
每组数据输出用链地址法处理冲突的散列表。  
**输入样例 1**  
5  
1 4 2 3 5  
6  
4  
2 5 8 15  
18  
0  
**输出样例 1**  
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

#include<iostream>
    using namespace std;
    typedef struct LNode
    {
        
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    LinkList H[13];
    void Hash(int e)
    {
        
    	int index=e%13;		
    	LinkList p=H[index];
    	while(p->next)
    		p=p->next;
    	LinkList q=new LNode;
    	q->data=e;
    	q->next=NULL;
    	p->next=q;
    } 
    void Input(int n)
    {
        
    	for(int i=0;i<13;i++)
    	{
        
    		H[i]=new LNode;
    		H[i]->next=NULL;
    	}
    	while(n--)
    	{
        
    		int e;
    		cin>>e;
    		Hash(e);
    	}
    }
    void Insert(int e)
    {
        
    	Hash(e);
    }
    void Output()
    {
        
    	for(int i=0;i<13;i++)
    	{
        
    		cout<<i;
    		LinkList p=H[i]->next;
    		while(p)
    		{
        
    			cout<<" "<<p->data;
    			p=p->next;
    		}
    		cout<<endl;
    	}
    }
    int main()
    {
        
    	int n;	
    	while(cin>>n&&n!=0)
    	{
        
    		int e;
    		Input(n);
    		cin>>e;
    		Insert(e);
    		Output();
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com