SpeciesTree如何使用HashTable实现-创新互联
这篇文章主要介绍了Species Tree如何使用HashTable实现,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
网站建设哪家好,找成都创新互联!专注于网页设计、网站建设、微信开发、小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了东安免费建站欢迎大家使用!Species Tree 利用HashTable实现
题目再现
题目内容:
给定一个物种演化图, 关系的表示方式如下: x y : 表示x为y的先祖。 一个物种只会有一个先祖, 一个先祖可以有很多个演化出来的物种, 请你找出每个问题询问物种的祖父物种(先祖的先祖), 每个物种会使用一个不重复的编号来表示, 如果该物种没有祖父物种的话或是不存在, 那么请将他的祖父物种当是0。(凭空而生) 保证所有物种间一定有所关连, 且不会有重复演化的现象发生, 即演化图只会是一棵树。 输入格式: 只有一组测资。 第一行会有两个数字N、Q,代表总共有N个物种及Q个问题。 接下来N-1行,每一行有两个数字x、y, 意义如题目所述。 接下来的Q行,每一行有一个数字Z, 代表要询问的物种编号。 测资范围: 1 < N < 10000 0 < Q < 1000 0 < x, y, z < 1000000 输出格式: 对于每一个询问的物种编号,将他们的祖父物种编号加总后再输出。 输入样例: 6 3 1000 2000 1000 3000 2000 4000 3000 5000 5000 6000 5000 6000 1234 输出样例: 4000 时间限制:100ms内存限制:16000kb
算法实现
1. 简单数组下标查找法
通过题目的要求,这里可以使用最简单的方法,因为输入的x , y中,y的值是确定不变的,所以这里可以定义一个y的取值范围那么大的数组,下标就是y的值,内容就是x的值,这样查找起来十分方便,时间复杂度是O(1),但是空间上就会浪费比较多了。
#include#include int main(){ int arrBucket[1000000]; int N, Q; int x, y, z; long long sum = 0; memset(arrBucket, 0, sizeof(arrBucket)); scanf("%d %d", &N, &Q); while(N -- > 1){ scanf("%d %d", &x, &y); arrBucket[y] = x; } while(Q --){ scanf("%d", &z); if(arrBucket[z] != 0){ if(arrBucket[arrBucket[z]] != 0){ sum += arrBucket[arrBucket[z]]; } } } printf("%lld", sum); return 0; }
2. Hash表实现
因为方法1中,浪费空间严重,所以这里使用Hash表实现。
#include#include #define NULLKEY -1 typedef struct { int *elem; //元素 int *elemP; //父元素 int count; }HashTable; int Hash(HashTable H, int k){ return k % H.count; } void InitHashTable(HashTable *H){ int i; H->elem = (int *)malloc(sizeof(int) * H->count); H->elemP = (int *)malloc(sizeof(int) * H->count); for(i = 0; i < H->count; i ++){ H->elem[i] = NULLKEY; H->elemP[i] = NULLKEY; } } void InsertHash(HashTable *H, int key, int value){ int addr; addr = Hash(*H, key); while(H->elem[addr] != NULLKEY){ addr = (addr + 1) % H->count; } H->elem[addr] = key; H->elemP[addr] = value; } int FindHash(HashTable *H, int key, int *addr){ *addr = Hash(*H, key); while(H->elem[*addr] != key){ *addr = (*addr + 1) % H->count; if(H->elem[*addr] == NULLKEY || *addr == Hash(*H, key)){ return 0; } } return 1; } int main(){ int N, Q; int x, y, z, addr; long long sum = 0; HashTable H; scanf("%d %d", &N, &Q); H.count = N - 1; InitHashTable(&H); while(N -- > 1){ scanf("%d %d", &x, &y); InsertHash(&H, y, x); } while(Q --){ scanf("%d", &z); if(FindHash(&H, z, &addr)){ if(FindHash(&H, H.elemP[addr], &addr)){ sum += H.elemP[addr]; } } } printf("%lld", sum); return 0; }
3. 用C++的map来实现
看着用C实现起来,相对来说实现的各个功能都要自己写,这里看一下用C++的STL里面的map来实现上面的题目,非常简单(不得不说STL真的很好用,但是不如HashTable速度快,空间上也不如HashTable占用的小)
#include#include
感谢你能够认真阅读完这篇文章,希望小编分享的“Species Tree如何使用HashTable实现”这篇文章对大家有帮助,同时也希望大家多多支持创新互联建站,关注创新互联网站建设公司行业资讯频道,更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:SpeciesTree如何使用HashTable实现-创新互联
网页链接:http://pwwzsj.com/article/diodhh.html