第3章の演習
ソースのダウンロード
今後の演習では，ホームフォルダの下に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からダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．
[投票]連結リスト(liked list)を知っていた?
- 名前をこの講義で初めて知った
- 名前は聞いたことがあるが，どのようなものかは知らない
- どのようなものかは知っているが使ったことはない
- 他の人が作ったライブラリ(forward_list, list等)を使ったことがある．
- 自分で実装したことがある
演習(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;
}
これを，
cd ~/mis2/cpp
g++-8 -o sllistTest sllistTest.cpp
でコンパイルし，
./sllistTest
で実行する．
[演習/投票]第3章の演習のページの「演習(SLList)」をやってみる．
このプログラムの
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++-8 -o dllistTest dllistTest.cpp
でコンパイルし，
./dllistTest
で実行する．
[演習/投票]第3章の演習のページの「演習(DLList)」をやってみる．
このプログラムの
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++-8 -o selistTest selistTest.cpp
でコンパイルし，
./selistTest
で実行する．
[演習/投票]第3章の演習のページの「演習(SEList)」をやってみる．
このプログラムの
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
LeetCodeの関連問題