关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
(c语言)浙大数据结构Mooc作者答案集
原题谷歌翻译
闲谈
Where were you, when I was trying to make a move
Told them I would make it, they didn’t believe it
Even if dont make it,thats all my effort without regreting
思路
很直白很直白很直白的基本哈希表创建
然后我觉得 在我做的时候发现有些很容易出错的点吧
也许你也在上面出现了问题
第一个 MAXN 因为最大的数有10000的 所以你在定质数的时候
尽量把MAXN 定成100000
第二个 就是关于检查点二 如果tablecheck为1的时候
请问一下你的NewPrime函数是否考虑到了呢
如果也没有考虑到 就下次一定要记住 考虑边界情况
第三个 就是 仔细审题了吗 题目上说的 是对正数平方探测
等于 每次只会 加上 1的平方 而且 2的平方
而不是还会一加一减左右横跳
第四个 你是怎么处理你的超过tablesize的pos呢
如果你是pos减去tablesize 那可能是需要冷水洗一下脸（我就去洗脸了）
这里是用 pos%tablesize 因为到最后有可能 你的平方很大
到最后你的平方比你的几倍tablesize还要大
到最后就会导致pos比你的tablesize大 造成段错误
代码实现
上面说了可能全部容易出错的点了
下面直接给出代码吧
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MSIZE 100000
typedef struct Map
{
int* List;int size;
} *HashMap;int NewPrime(int tablesize)
{
//注意临界情况 tablesize = 1if(tablesize == 1)tablesize++;int i = tablesize,j,temp;for(i=tablesize;i<=MSIZE;i++){
temp = sqrt(i);for(j=2;j<=temp;j++){
if(i%j == 0)break;}if(j == temp+1)return i;}
}int Hash(int key,int p)
{
return(key % p);
}HashMap CreateHashMap(int tablesize)
{
HashMap H;int i;H = (HashMap)malloc(sizeof(struct Map));H->List = (int*)malloc(sizeof(int) * tablesize);H->size = tablesize;for(i=0;i<tablesize;i++)H->List[i] = -1;return H;
}void Insert(int number,HashMap H)
{
int trytimes = 0,pos,temp;pos = temp = Hash(number,H->size);while(1){
if(H->List[pos] == -1){
H->List[pos] = number;printf("%d",pos);break;}else{
trytimes++;pos = pow(trytimes,2) + temp;if(pos > H->size)pos = pos % H->size;if(trytimes == H->size)break;}}if(trytimes == H->size)printf("-");return;
}int main()
{
int tablesize,numbers,number,i,pos;HashMap H;scanf("%d %d",&tablesize,&numbers);tablesize = NewPrime(tablesize);H = CreateHashMap(tablesize);for(i=0;i<numbers;i++){
scanf("%d",&number);Insert(number,H);if(i!=numbers-1)printf(" ");}free(H->List);free(H);return 0;
}
结束语
这篇博客写了 去上体育课了
又要开心乒乓了 ??( ?? ω ?? )y
