第3章の演習

ソースのダウンロード

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

演習(SLList)

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

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

int main(){
  ods::SLList<int> l;
  for (int i = 0; i < 10; i++){
    l.add(i);
  }
  // [0 1 2 3 4 5 6 7 8 9]
  for (int i = 10; i < 20; i++){
    l.push(i);
  }
  // [19 18 17 16 15 14 13 12 11 10 0 1 2 3 4 5 6 7 8 9]
  std::cerr << l.pop() << std::endl;
  // [18 17 16 15 14 13 12 11 10 0 1 2 3 4 5 6 7 8 9]
  for (int i = 0; i < 10; i++){
    std::cerr << l.remove() << std::endl;
  }
  // [1 2 3 4 5 6 7 8 9]
  return 0;
}

なお，スライドに書いたように，SLList.hは

		Node(T x0) {
			x = 0;
			next = NULL;
		}

を

		Node(T x0) {
			x = x0;
			next = NULL;
		}

と修正する必要がある．これを，

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

でコンパイルし，

./sllistTest

で実行する．

このプログラムの

  return 0;

の前に，

  for (int i = 0; i < 3; i++){
    std::cerr << l.pop() << (i == 2 ? "\n" : ",");
  }

を入れ実行した時, 出力の最後の行に表示されるのは，次のどれか?

0,1,2
1,2,3
7,8,9
9,8,7
19, 18, 17

演習(DLList)

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

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

void print(std::ostream& os, ods::DLList<int> & l){
  os << "[";
  for (int i = 0; i < l.size(); ++i){
    os << (i == 0 ? "" : ",") << l.get(i);
  }
  os << "]" << std::endl;
}

int main(){
  ods::DLList<int> l;
  for (int i = 0; i < 10; i++){
    l.add(i, i * 2);
  }
  // l = [0,2,4,6,8,10,12,14,16,18]
  print(std::cerr, l); 
  for (int i = 0; i < 10; i++){
    l.add(5, 100 + i);
  }
  // l = [0,2,4,6,8,109,108,107,106,105,104,103,102,101,100,10,12,14,16,18]
  print(std::cerr, l); 
  for (int i = 0; i < 10; i++){
    l.set(i * 2, 200 + i);
  }
  // l = [200,2,201,6,202,109,203,107,204,105,205,103,206,101,207,10,208,14,209,18]
  print(std::cerr, l); 
  l.remove(1);
  // l = [200,201,6,202,109,203,107,204,105,205,103,206,101,207,10,208,14,209,18]
  print(std::cerr, l); 
  return 0;
}

これを，

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

でコンパイルし，

./dllistTest

で実行する．

このプログラムの

  return 0;

の前に，

  l.add(1, 10);
  for (int i = 0; i < 3; i++){
    std::cerr << l.remove(i) << (i == 2 ? "\n" : ",");
  }

を入れ実行した時, 出力の最後の行に表示されるのは，次のどれか?

10,6,109
10,201,6
200,10,201
200,201,6
200,201,202

演習(SEList)

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

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

void print(std::ostream& os, ods::SEList<int> & l){
  os << "[";
  for (int i = 0; i < l.size(); ++i){
    os << (i == 0 ? "" : ",") << l.get(i);
  }
  os << "]" << std::endl;
}

int main(){
  ods::SEList<int> l(10);
  for (int i = 0; i < 10; i++){
    l.add(i, i * 2);
  }
  // l = [0,2,4,6,8,10,12,14,16,18]
  print(std::cerr, l); 
  for (int i = 0; i < 10; i++){
    l.add(5, 100 + i);
  }
  // l = [0,2,4,6,8,109,108,107,106,105,104,103,102,101,100,10,12,14,16,18]
  print(std::cerr, l); 
  for (int i = 0; i < 10; i++){
    l.set(i * 2, 200 + i);
  }
  // l = [200,2,201,6,202,109,203,107,204,105,205,103,206,101,207,10,208,14,209,18]
  print(std::cerr, l); 
  l.remove(1);
  // l = [200,201,6,202,109,203,107,204,105,205,103,206,101,207,10,208,14,209,18]
  print(std::cerr, l); 
  return 0;
}

これを，

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

でコンパイルし，

./selistTest

で実行する．

このプログラムの

  return 0;

の前に，

  l.add(10, 10);
  for (int i = 0; i < 3; i++){
    std::cerr << l.remove(i * 5 + 3) << (i == 2 ? "\n" : ",");
  }

を入れ実行した時, 出力の最後の行に表示されるのは，次のどれか? [200,201,6,202,109, 203,107,204,105,205, 10, 103,206,101,207, 10,208,14,209,18]

20,201,6
202,105,101
202,105,207
202,205,10
202,205,208