快捷導(dǎo)航

Species Tree 利用HashTable實(shí)現(xiàn)實(shí)例代碼

更新時(shí)間：2017年01月20日 10:00:10 投稿：lqh

這篇文章主要介紹了Species Tree 利用HashTable實(shí)現(xiàn)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下

Species Tree 利用HashTable實(shí)現(xiàn)

題目再現(xiàn)

題目?jī)?nèi)容：

給定一個(gè)物種演化圖，
關(guān)系的表示方式如下：
x y : 表示x為y的先祖。
一個(gè)物種只會(huì)有一個(gè)先祖，
一個(gè)先祖可以有很多個(gè)演化出來(lái)的物種，
請(qǐng)你找出每個(gè)問(wèn)題詢問(wèn)物種的祖父物種(先祖的先祖)，
每個(gè)物種會(huì)使用一個(gè)不重復(fù)的編號(hào)來(lái)表示，
如果該物種沒(méi)有祖父物種的話或是不存在，
那么請(qǐng)將他的祖父物種當(dāng)是0。(憑空而生)
保證所有物種間一定有所關(guān)連，
且不會(huì)有重復(fù)演化的現(xiàn)象發(fā)生，
即演化圖只會(huì)是一棵樹。

輸入格式:
只有一組測(cè)資。
第一行會(huì)有兩個(gè)數(shù)字N、Q，代表總共有N個(gè)物種及Q個(gè)問(wèn)題。
接下來(lái)N-1行，每一行有兩個(gè)數(shù)字x、y，
意義如題目所述。
接下來(lái)的Q行，每一行有一個(gè)數(shù)字Z，
代表要詢問(wèn)的物種編號(hào)。
測(cè)資范圍：
1 < N < 10000
0 < Q < 1000
0 < x, y, z < 1000000

輸出格式：
對(duì)于每一個(gè)詢問(wèn)的物種編號(hào)，將他們的祖父物種編號(hào)加總后再輸出。

輸入樣例：
6 3
1000 2000
1000 3000
2000 4000
3000 5000
5000 6000
5000
6000
1234

輸出樣例：
4000

時(shí)間限制：100ms內(nèi)存限制：16000kb

算法實(shí)現(xiàn)

1. 簡(jiǎn)單數(shù)組下標(biāo)查找法

通過(guò)題目的要求，這里可以使用最簡(jiǎn)單的方法，因?yàn)檩斎氲膞 , y中，y的值是確定不變的，所以這里可以定義一個(gè)y的取值范圍那么大的數(shù)組，下標(biāo)就是y的值，內(nèi)容就是x的值，這樣查找起來(lái)十分方便，時(shí)間復(fù)雜度是O(1)，但是空間上就會(huì)浪費(fèi)比較多了。

#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表實(shí)現(xiàn)

因?yàn)榉椒?中，浪費(fèi)空間嚴(yán)重，所以這里使用Hash表實(shí)現(xiàn)。

#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來(lái)實(shí)現(xiàn)

看著用C實(shí)現(xiàn)起來(lái)，相對(duì)來(lái)說(shuō)實(shí)現(xiàn)的各個(gè)功能都要自己寫，這里看一下用C++的STL里面的map來(lái)實(shí)現(xiàn)上面的題目，非常簡(jiǎn)單（不得不說(shuō)STL真的很好用，但是不如HashTable速度快，空間上也不如HashTable占用的?。?/p>

#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;
}

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章: