第4章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って， そこで作業することを前提とする．作成していない時は，ターミナルから 
mkdir ~/mis2
を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は， 
cd ~/mis2
tar zxvf ods-cpp.tgz
ods-cpp.tarというファイルができた時は， 
cd ~/mis2
tar xvf ods-cpp.tar
を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]スキップリストを知っていた?

  1. 名前をこの講義で初めて知った
  2. 名前は聞いたことがあるが，どのようなものかは知らない
  3. どのようなものかは知っているが使ったことはない
  4. 他の人が作ったライブラリを使ったことがある．
  5. 自分で実装したことがある

演習(SkiplistList)

~/mis2/cpp 以下にskiplistListTest.cpp というファイルを 作成する． 
#include "SkiplistList.h"
#include <iostream>

int main(){
  int n = 10;
  ods::SkiplistList<int> sl;
  for (int i = 0; i < n; i++){
    sl.add(i, i); 
  }
  // [0 1 2 3 4 5 6 7 8 9]
  for (int i = 0; i < n; i++){
    sl.add(i, -i); 
    sl.remove(0);
    sl.set(i, i * i);
    // [0 1 2 3 4 5 6 7 8 9]
    // [-1 1 2 3 4 5 6 7 8 9]
    // [1 -2 2 3 4 5 6 7 8 9]
    // [2 2 -3 3 4 5 6 7 8 9]
    // 
    // [-5, 25, -6, 36, -7, 49, -8, 64 -9, 81]
  }
  for (int i = 0; i < sl.size(); i++){
    std::cout << sl.get(i) << std::endl;
  }
  return 0;
}
これを， 
cd ~/mis2/cpp
g++-8 -std=c++11 -o skiplistListTest skiplistListTest.cpp
でコンパイルし， 
./skiplistListTest
で実行する．

このプログラムの 

  return 0;
の前に， 
  for (int i = 0; i < 3; i++){
    sl.add(4, i * 3);
    std::cerr << sl.get(5) << (i == 2 ? "\n" : ",");
    sl.remove(5);			      
  }
を入れ実行した時, 出力の最後の行に表示されるのは，次のどれか?
  1. -7,-7,-7
  2. -7,0,3
  3. 0,3,6
  4. 49,-7,36
  5. 49,49,49