第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.8 -o arrayTest -std=c++11 -o arrayTest arrayTest.cpp array.cpp
でコンパイルし， 
./arrayTest
で実行 
100
2
5
88
0
のような入力を与えて実行してみる．

発展

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.8 -o arrayStackTest -std=c++11 -o arrayStackTest arrayStackTest.cpp ArrayStack.cpp
でコンパイルし， 
./arrayStackTest
で実行

発展

addやresizeはiによって，実行時間のオーダが違う．4/15の「演習(C++プログラムの速度計測)」に書かれている方法を使って，同じ回数のaddやresizeの呼び出しで実行時間に差が出るプログラムを作成してみなさい．

演習(FastArrayStack)

~/mis2/cpp 以下にarrayStackTest.cpp というファイルを作成する．FastArrayStackを使うように書き換えて fastArrayStackTest.cpp というファイルを作成する． 
cd ~/mis2/cpp
g++-mp-4.8 -o fastArrayStackTest -std=c++11 -o fastArrayTest fastArrayStackTest.cpp FastArrayStack.cpp
でコンパイルし， 
./fastArrayStackTest
で実行する．

発展

4/15の「演習(C++プログラムの速度計測)」に書かれている方法を使って，ArrayStackとFastArrayStackの速度の違いを計測するプログラムを作成し なさい．元のプログラムのままでは，差が出にくいと思われるので，時間計測中に差 が生じるような操作をなるべく多く行うようにプログラムを書き換えること．

演習(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.8 -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.8 -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.8 -o dualArrayDequeTest -std=c++11 -o dualArrayDequeTest dualArrayDequeueTest.cpp DualAraryDeque.cpp
でコンパイルし， 
./dualArrayDeque
で実行する．

演習(RootishArrayStack)

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