浙大数据结构：11-散列4 Hashing

浙大数据结构：11-散列4 Hashing - Hard Version

这道题主要在于思路，感觉像个模拟题，用到了线性探测的算法
机翻
在这里插入图片描述

1、条件准备

visit数组看这个位置有没有放进来数，num存非负整数，s存未到放入时机的数。
answer存答案。n为总共数量。

#include <iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
#define endl '\n'

int visit[1005];
vector<int> num;
set<int> s;
vector<int> answer;
int n;

2、主函数

先输入存入Hash，也就是放原始哈希表，然后调用init函数，再建立answer数组，最后输出。

int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
   cin>>n;
  vector<int> Hash(n);
  init(Hash,num);
  insertanswer(Hash);
   for(int i=0;i<answer.size()-1;i++)
      cout<<answer[i]<<' ';
   cout<<answer[answer.size()-1];
  return 0;
}

3、init函数

初始化Hash数组，把非负整数放进num数组中，然后排序，因为我们要数尽可能小的优先输出，所以要从小到大进行判断

void init(vector<int>&Hash,vector<int>&num)
{
  for(int i=0;i<n;i++)
  {
    cin>>Hash[i];
    if(Hash[i]>=0)
     num.push_back(Hash[i]);
  }
  sort(num.begin(),num.end());
}

4、initanswer函数

遍历num数组，看能不能直接放入哈希表，即调用inserthash函数，如果不能就把数放进set中备用。
当我们遍历到后面某个数时，看看set中的数能不能插入哈希表，因为输出是多种可能数小的先输出，所以遍历set数组直到里面的数都不能放入哈希表，因为set里面的数比当前数大，再来判断当前数能否放入

void insertanswer(vector<int>& Hash)
{

  for(int i=0;i<num.size();i++)
  {
    while(setinsert(Hash,num[i]));
    if(inserthash(Hash,num[i]))
      answer.push_back(num[i]);
    else
       s.insert(num[i]);
  }
  while(s.size())
    setinsert(Hash,INT_MAX);
  
}

5、inserthash函数

先算出应该放入的下标，若这个下标对应的数不为当前数，则下标加1再取模。如果该位置的数还没放进来，说明当前数此时放早了，还不能放进来，返回0.
如果当前数与哈希表当前位置一样，则return 1，否则0.

bool inserthash(vector<int> &Hash,int elem)
{
     int idx=elem%n;
     while(Hash[idx]!=elem)
     {
        if(visit[idx]==0)return 0;
        idx=(idx+1)%n;
     }
     if(elem==Hash[idx])
    {visit[idx]=1; return 1;}
     return 0;
}

6、setinsert函数

先把数都放进数组里，然后循环判断，如果不能放就继续，能放就放，并删除该元素，返回1.
都不能放返回0

bool setinsert(vector<int>& Hash,int up)
{
    vector<int> t(s.begin(),s.end());
    for(int i=0;i<t.size();i++)
    {
       int elem=t[i];
      if(inserthash(Hash,elem)==0||elem>up)continue;
      s.erase(elem);
      answer.push_back(elem);
      return 1;
    }
    return 0;
}

7、总结

感觉像个模拟题，算法方面性不强，偏思维题＋推导
完整代码如下

#include <iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
#define endl '\n'

int visit[1005];
vector<int> num;
set<int> s;
vector<int> answer;
int n;

bool inserthash(vector<int> &Hash,int elem)
{
     int idx=elem%n;
     while(Hash[idx]!=elem)
     {
        if(visit[idx]==0)return 0;
        idx=(idx+1)%n;
     }
     if(elem==Hash[idx])
    {visit[idx]=1; return 1;}
     return 0;
}
bool setinsert(vector<int>& Hash,int up)
{
    vector<int> t(s.begin(),s.end());
    for(int i=0;i<t.size();i++)
    {
       int elem=t[i];
      if(inserthash(Hash,elem)==0||elem>up)continue;
      s.erase(elem);
      answer.push_back(elem);
      return 1;
    }
    return 0;
}

void init(vector<int>&Hash,vector<int>&num)
{
  for(int i=0;i<n;i++)
  {
    cin>>Hash[i];
    if(Hash[i]>=0)
     num.push_back(Hash[i]);
  }
  sort(num.begin(),num.end());
}
void insertanswer(vector<int>& Hash)
{

  for(int i=0;i<num.size();i++)
  {
    while(setinsert(Hash,num[i]));
    if(inserthash(Hash,num[i]))
      answer.push_back(num[i]);
    else
       s.insert(num[i]);
  }
  while(s.size())
    setinsert(Hash,INT_MAX);
  
}
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
   cin>>n;
  vector<int> Hash(n);
  init(Hash,num);
  insertanswer(Hash);
   for(int i=0;i<answer.size()-1;i++)
      cout<<answer[i]<<' ';
   cout<<answer[answer.size()-1];
  return 0;
}