課題3(5/21出題)

課題

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

ヒント

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

#include "SLList.h"
#include <iostream>
int main(){
  ods::SLList<double> l;
  for (int i = 0; i < 10; i++){
    l.add(double(i));
  }
  // l = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]
  std::cout << l.secondLast() << std::endl;
  // output "8"
}

コンパイル, 実行例

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

checkEx3_3.cpp

#include "SLList.h"
#include 
int main(){
  ods::SLList<double> l;
  for (int i = 0; i < 10; i++){
    l.add(double(10+ i));
  }
  // l = [10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0]
  l.set(5, 105.0);
  // l = [10.0, 11.0, 12.0, 13.0, 14.0, 105.0, 16.0, 17.0, 18.0, 19.0]
  l.add(2, 22.0);
  // l = [10.0, 11.0, 22.0, 12.0, 13.0, 14.0, 105.0, 16.0, 17.0, 18.0, 19.0]
  l.add(0, 20.0);
  // l = [20.0, 10.0, 11.0, 22.0, 12.0, 13.0, 14.0, 105.0, 16.0, 17.0, 18.0, 19.0]
  l.add(12, 30.0);
  // l = [20.0, 10.0, 11.0, 22.0, 12.0, 13.0, 14.0, 105.0, 16.0, 17.0, 18.0, 19.0, 30.0]
  std::cout << l.remove(1) << std::endl;;
  // output 10
  // l = [20.0, 11.0, 22.0, 12.0, 13.0, 14.0, 105.0, 16.0, 17.0, 18.0, 19.0, 30.0]
  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++-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(5/21修正)

#include <iostream>
#include "SLList.h"
int main(){
  ods::SLList<double> l;
  for (int i = 0; i < 10; i++){
    l.add(double(10 + i));
  }
  // l = [10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0]
  l.reverse();
  // l = [19.0, 18.0, 17.0, 16.0, 15.0, 14.0, 13.0, 12.0, 11.0, 10.0]
  for (int i = 0; i < 10; i++)
    std::cout << (i == 0 ? "[" : ", ") << l.remove();
  std::cout << "]" << std::endl;
  // output [19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
}

コンパイル，実行例

bash-3.2$ g++-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の定義の中に，secondLastの定義を加える)．

	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()を返します．参考のために，変数tailも変数nも使わないlast()の定義を示します．

        T last() {
          if (head == NULL) return null;
          Node *u = head;
          while (u->next != NULL) u = u->next;
          return u->x;
        }

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() {
// ここを埋める
        }

提出方法

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

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

LeetCodeの関連問題

707. Design Linked List Exercise 3.3 と類似．
206. Reverse Linked List Exercise 3.4に対応

オプション課題

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

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