課題3(5/27出題)

課題

教科書の3.4 Discussion and ExercisesのExercise 3.2 - 3.4のうちの1題以上を解きなさい．　
C++言語で回答する時は，回答に利用した環境も書くように．
教育用計算機システムのMac環境で回答する場合は，~~g++~~ g++-mp-4.8 を用いると良い．
一から実装するのではなく，配布プログラム http://opendatastructures.org/ods-cpp.tgz に手を加えて回答することが前提になっている．

ヒント

Exercise 3.2 - 3.4 は配布プログラムの中の SLList.h に手を加えて回答することが前提になっています．それぞれの練習問題をチェックするプログラムの例をあげます．

#include "SLList.h"
#include <iostream>
int main(){
  ods::SLList<int> l;
  for (int i = 0; i < 10; i++){
    l.add(i);
  }
  // l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  std::cout << l.secondLast() << std::endl;
  // output "8"
}

コンパイル, 実行例

bash-3.2$ g++-mp-4.8 -o checkEx3_2 checkEx3_2.cpp
bash-3.2$ ./checkEx3_2
8

checkEx3_3.cpp

#include "SLList.h"
#include <iostream>
int main(){
  ods::SLList<int> l;
  for (int i = 0; i < 10; i++){
    l.add(10+ i);
  }
  // l = [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
  l.set(5, 105);
  // l = [10, 11, 12, 13, 14, 105, 16, 17, 18, 19]
  l.add(2, 22);
  // l = [10, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19]
  l.add(0, 20);
  // l = [20, 10, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19]
  l.add(12, 30);
  // l = [20, 10, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19, 30]
  std::cout << l.remove(1) << std::endl;;
  // output 10
  // l = [20, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19, 30]
  for (int i = 0; i < l.size(); i++)
    std::cout << (i == 0 ? "[" : ", ") << l.get(i);
  std::cout << "]" << std::endl;
  // output [20, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19, 30]
}

コンパイル, 実行例

bash-3.2$ g++-mp-4.8 -o checkEx3_3 checkEx3_3.cpp
bash-3.2$ ./checkEx3_3
10
[20, 11, 22, 12, 13, 14, 105, 16, 17, 18, 19, 30]

checkEx3_4.cpp

#include <iostream>
#include "SLList.h"
int main(){
  ods::SLList<int> l;
  for (int i = 0; i < 10; i++){
    l.add(10+ i);
  }
  // l = [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
  l.reverse();
  // l = [19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
  for (int i = 0; i < l.size(); i++)
    std::cout << (i == 0 ? "[" : ", ") << l.get(i);
  std::cout << "]" << std::endl;
  // output [19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
}

コンパイル，実行例

bash-3.2$ g++-mp-4.8 -o checkEx3_4 checkEx3_4.cpp
bash-3.2$ ./checkEx3_4
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10]

Exercise 3.2 はメンバー変数 n を使わないことが条件になっています．この条件を満たさない誤った回答の例を示します(SLList.hのSLListの定義の中に，行頭に「+」がついている行を「+を取り去って」加える)．

	T peek() {
		return head->x;
	}

+        T secondLast() {
+          Node *u = head;
+          for (int i = 0; i < n - 2; i++) u = u->next;
+          return u->x;
+        }
+
	bool add(T x) {

(注) 要素数が0又は1の時にsecondLast()がどのような挙動を示すべきかは問題には書かれていない．ここでは，エラーチェックを行っていないので，要素数が0の時は，実行時にはSegmentation faultのようなエラーが発生する可能性があり，要素数が1の時はsecondLast() ではなくlast()を返す． Exercise 3.3はSLList.hのSLListの定義の中に，以下の行を入れてから「ここを埋める」のところにコードを書いて完成させる．

        T get(int i) {
// ここを埋める
        }
        T set(int i, T x){
// ここを埋める
        }
        void add(int i, T x){
// ここを埋める
        }
        T remove(int i){
// ここを埋める
        }

Exercise 3.4はSLList.hのSLListの定義の中に，以下の行を入れてから「ここを埋める」のところにコードを書いて完成させる．

        void reverse() {
// ここを埋める
        }

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

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

を

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

と修正する必要がある．

提出方法

作成したすべてのプログラムと，各プログラムに関する簡単な説明をまとめたプレインテキスト形式(テキストエディタで編集可能な形式)またはPDF形式のファイルを1つ作成して，ITC-LMSの「課題3(5/27出題)」(5/27の講義時間中に公開される予定)に提出してください．

締切は，6/6(金) 23:59．締切を過ぎても2014年7月末までは6割を上限に採点する．

オプション課題

課題だけで物足りない人は，以下のオプション課題にも取り組んでください．

第3章の他の練習問題(Exercise 3.1, 3.5 - 3.19)に取り組む