程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Species Tree 應用HashTable完成實例代碼

Species Tree 應用HashTable完成實例代碼

編輯:關於C++

Species Tree 應用HashTable完成實例代碼。本站提示廣大學習愛好者:(Species Tree 應用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 <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;
}

感激閱讀,希望能協助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved