第9章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って，そこで作業することを前提とする．作成していない時は，ターミナルから

mkdir ~/mis2

を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( http://opendatastructures.org/ods-cpp.tgz ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は，

cd ~/mis2
tar zxvf ods-cpp.tgz

ods-cpp.tarというファイルができた時は，

cd ~/mis2
tar xvf ods-cpp.tar

を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

この中の，RedBlackTree.hは教育用計算機システムのg++-mp-4.9ではコンパイルできないので，RedBlackTree.h(修正版)からダウンロードしたものを使うこと．

演習(RedBlackTree)

~/mis2/cpp 以下にredBlackTreeTest.cpp というファイルを作成する．

#include "RedBlackTree.h"
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int null = -1;
  ods::RedBlackTree1<int> primes;
  for(int i = 2; i < 1000; i++)  primes.add(i);
  std::cout << "Tree height=" << primes.height() << std::endl;
  for(int i = 2; i < 1000; i++){
    if(primes.find(i) == i){
      std::cout << i << std::endl;
      for(int j = i + i; j < 1000; j += i){
        primes.remove(j);
      }
    }
  }
  std::cout << "Tree height=" << primes.height() << std::endl;
  std::cout << "Tree size=" << primes.size() << std::endl;
}

これを，

cd ~/mis2/cpp
g++-mp-4.9 -Wall  -o redBlackTreeTest redBlackTreeTest.cpp

でコンパイルし，

./redBlackTreeTest

で実行する．