Species Tree 利用HashTable实现实例代码分享

—-想了解Species Tree 利用HashTable实现实例代码分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

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 <stdio.h>  #include <string.h>    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 <stdio.h>  #include <stdlib.h>  #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 <iostream>  #include <map>  using namespace std;    int main() {    int n, q;    cin >> n >> q;      map<int,int> mp;     map<int,int>::iterator it;    int x, y, z;    for (int i=1; i<n; ++i) {        cin >> x >> y;      mp.insert(pair<int,int>(y,x));      }      int sum = 0;    for (int i=0; i<q; ++i) {      cin >> z;      it = mp.find(z);        if (it != mp.end()) {        it = mp.find(it->second);          if (it != mp.end())          sum += it->second;        }    }      cout << sum;    return 0;  }    

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！