PTA浙江大学数据结构习题——第十周

#include 
#include 

#include 
#include 

using namespace std;

typedef struct HashCell
{
    int data;
    bool state; // false表示空，true表示非空
} Cell;

typedef struct HashTbl *HashTable;
struct HashTbl
{
    int size;
    Cell *cells;
};

// 计算下一个素数
int next_prime(int n)
{
	int i, flag;
	while (n ++)
	{
		i = 2;          //如果不是上一个值不是素数刷新i的值继续试除下一个数；
		flag = 1;       //刷新标志符；
		while (i < n)
		{
			if (n % i == 0)
			{
				flag = 0;
				break;
			}
			i ++;
		}
		if (flag == 1)
		{
			break;
		}
	}
	return n;
}

// 初始化散列表
HashTable create(int size)
{
    HashTable h;
    h = (HashTable)malloc(sizeof(struct HashTbl));
    h->size = next_prime(size);
    h->cells = (Cell*)malloc(sizeof(struct HashCell) * h->size);
    for (int i = 0; i < h->size; i ++)
    {
        h->cells[i].state = false;
        h->cells[i].data = 0;
    }
    return h;
}

// 散列函数
int h_key(int key, int p)
{
    return key % p;
}

int find(int key, HashTable h)
{
    int cur_pos = h_key(key, h->size), new_pos = cur_pos;
    int cnt = 0;    // 冲突次数
    
    while (h->cells[new_pos].state && h->cells[new_pos].data != key) // 发生冲突
    {
        cnt ++;
        new_pos = (cur_pos + cnt * cnt) % h->size;
        if (cnt == h->size / 2) return -1;
    }
    return new_pos;
}

int insert(int key, HashTable h)
{
    int pos = find(key, h);
    
    if (pos == -1)  return -1;
    
    if (h->cells[pos].state == false)
    {
        h->cells[pos].data = key;
        h->cells[pos].state = true;
    }
    return pos;
}

int main()
{
    int size, n;
    cin >> size >> n;
    HashTable h = create(size);
    
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        int pos = insert(x, h);
        if (i)  printf(" ");
        if (pos == -1)  printf("-");
        else    printf("%d", pos);
    }
    
    return 0;
}