第2章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下に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からダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

演習(array)

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

#include "array.h"
#include <iostream>

int main(){
  int n;
  std::cin >> n;
  ods::array<int> a(n);
  for (int i = 0; i < n; i++){
    a[i] = i * i; 
  }
  for (int m; std::cin >> m && m > 0;){
    if (m < n){
      std::cout << a[m] << std::endl;
    }
  }
  return 0;
}

これは，最初に入力した大きさの配列aを作り，n番目の中身をn*nで埋め，その後，入力されたmが正の間，aのm番目の要素を返すだけのプログラムである．これを，

cd ~/mis2/cpp
g++-mp-4.9 -o arrayTest -std=c++11 -O3 arrayTest.cpp array.cpp

でコンパイルし，

./arrayTest

で実行

のような入力を与えて実行してみる．

発展

array.h, array.cpp を読んで， arrayTest.cppの中で使われていなかった関数を探しなさい． arrayTest.cppを改造してこれらの関数を呼び出して動くことを確かめなさい．また， array.hの実装でメモリーリーク(今後，使われないのにメモリ上に存在し続ける領域) がないかどうか，実験するコードを書いてみてください．

演習(ArrayStack)

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

#include "ArrayStack.h"
#include <iostream>

int main(){
  int n = 100;
  ods::ArrayStack<int> as;
  for (int i = 0; i < n; i++){
    as.add(i, i); 
  }
  as.set(88, 199);
  as.add(87, 133);
  std::cout << as.remove(98) << std::endl;
  for (int i = 0; i < 80; i++){
    std::cout << "removed = " << as.remove(0) << std::endl;
  }
  for (int i = 0; i < as.size(); i++){
    std::cout << "as.get(" << i << ")=" << as.get(i) << std::endl;
  }
  return 0;
}

cd ~/mis2/cpp
g++-mp-4.9 -o arrayStackTest -std=c++11 -O3 arrayStackTest.cpp ArrayStack.cpp

でコンパイルし，

./arrayStackTest

で実行

発展

addやresizeはiによって，実行時間のオーダが違う． ~/mis2/cpp 以下にarrayStackSpeed.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-mp-4.9 -o arrayStackSpeed -std=c++11 -O3 arrayStackSpeed.cpp

でコンパイルし，

./arrayStackSpeed

で実行する．プログラム中のnの値を1000, 10000 に変更してからコンパイル実行してみる．

演習(FastArrayStack)

~/mis2/cpp 以下にarrayStackTest.cpp というファイルを作成する．FastArrayStackを使うように書き換えて fastArrayStackTest.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-mp-4.9 -o fastArrayStackTest -std=c++11 -O3 fastArrayStackTest.cpp FastArrayStack.cpp

でコンパイルし，

./fastArrayStackTest

で実行する．

発展

addやresizeはiによって，実行時間のオーダが違う． ~/mis2/cpp 以下にfastArrayStackSpeed.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-mp-4.9 -o fastArrayStackSpeed -std=c++11 -O3 fastArrayStackSpeed.cpp

でコンパイルし，

./fastArrayStackSpeed

で実行する．プログラム中のnの値を10000 に変更してからコンパイル実行してみる．

演習(ArrayQueue)

http://opendatastructures.orgのc++ edition, c++ sources ( http://opendatastructures.org/ods-cpp.tgz ) からダウンロードしたArrayQueueはGNU C++コンパイラでコンパイルできないので，代わりに田中が修正したArrayQueue.hを使う．

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

#include "ArrayQueue.h"
#include <iostream>

int main(){
  int n = 10;
  ods::ArrayQueue<int> aq;
  for (int i = 0; i < n; i++){
    aq.add(i); 
  }
  for (int i = 0; i < n * 10; i++){
    std::cout << aq.remove() << std::endl;
    aq.add(i * i); 
  }
  return 0;
}

cd ~/mis2/cpp
g++-mp-4.9 -o arrayQueueTest -std=c++11 -o arrayQueueTest arrayQueueTest.cpp ArrayQueue.cpp

でコンパイルし，

./arrayQueueTest

で実行する．

演習(ArrayDeque)

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

#include "ArrayDeque.h"
#include <iostream>

int main(){
  int n = 10;
  ods::ArrayDeque<int> aq;
  for (int i = 0; i < n; i++){
    aq.add(i, i); 
  }
  for (int i = 0; i < n; i++){
    aq.add(i, -i); 
    aq.remove(0);
    aq.set(i, i * i);
  }
  for (int i = 0; i < aq.size(); i++){
    std::cout << aq.get(i) << std::endl;
  }
  return 0;
}

cd ~/mis2/cpp
g++-mp-4.9 -o arrayDequeTest -std=c++11 -o arrayDequeTest arrayDequeTest.cpp ArrayDeque.cpp

でコンパイルし，

./arrayDequeTest

で実行する．

演習(DualArrayDeque)

~/mis2/cpp 以下にarrayDequeTest.cppを，DualArrayDequeを使うように書き換えて dualArrayDequeTest.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-mp-4.9 -o dualArrayDequeTest -std=c++11 -o dualArrayDequeTest dualArrayDequeueTest.cpp DualAraryDeque.cpp

でコンパイルし，

./dualArrayDeque

で実行する．

演習(RootishArrayStack)

~/mis2/cpp 以下のarrayStackTest.cppを，RootishArrayStackを使うように書き換えて rootishArrayStackTest.cpp というファイルを作成して，実行してみなさい．

RootishArrayStack.hの先頭に

#include <iostream>

を入れ，以下の赤字の2行を加えてみる．

template<class T>  
void RootishArrayStack<T>::grow() {
  std::cerr << "grow() is called" << std::endl;
    blocks.add(blocks.size(), new T[blocks.size()+1]);
}
template<class T>
void RootishArrayStack<T>::shrink() {
  std::cerr << "shrink() is called" << std::endl;
    int r = blocks.size();
    while (r > 0 && (r-2)*(r-1)/2 >= n) {
            delete [] blocks.remove(blocks.size()-1);
            r--;
    }
}

rootishArrayStackTest を実行した時に，grow, shrinkは何回呼ばれるか?

0, 0
4, 8
8, 4
7, 14
14, 7