3.1 ユークリッドの互除法
四条にあるジュンク堂で、暗号理論入門を購入。少し読んでみた。
- 作者: 林芳樹
- 出版社/メーカー: 丸善出版
- 発売日: 2012/04/20
- メディア: 単行本
- この商品を含むブログを見る
最初の方は、微積の教科書を思い出すような感じだった。実数や整数の定義や性質から始まる。暗号理論なので、整数がメイン。整数の性質について、非常に詳しく述べられている。む、難しい…。
御約束ともいえるが、ユークリッドの互除法が出てきた。
最大公約数(gcd)を求めるアルゴリズムで、明示的に書かれた最古のアルゴリズムである(らしい)。
自然数 a, b の最大公約数は、b, a mod b の最大公約数に等しい。
これを利用したgcd(a,b)なる関数は、これまで何度も書いてきた。
…のだが、実はこのアルゴリズムが何故成立するのか、という証明は、恥ずかしながら理解していなかった。この機会に日本酒を煽りながら様々な文献を漁り、ようやく自分的に納得のいく証明が得られたので、ここに書いておく。
[証明]*1
全ての文字は整数とする。
a = bq + r とする。また、ある m, n が存在して、a = mx, b = nx とする。すなわち、x は a, b の公約数である。
このとき、
r = a - bq
r = mx - nxq
r = (m - nq)x
より、x は r の約数である。すなわち、「a, b の全ての公約数は、b, r の公約数でもある」ことが示せた。
また、r < b より、
int gcd(int a, int b){ return (b == 0 ? a : gcd(b, a%b)); }
なる関数gcdの第2引数は強い意味で単調減少であり、いずれ0になる*2。
ところで、ある整数 c について、gcd(c, 0) = c である。なぜなら、c は c の最大の約数であり、0 = 0*c が成立するからである。よって、上記アルゴリズムで a, b の最大公約数が求まる。
次回は拡張ユークリッドアルゴリズムについて学ぶ。
0.1 二分探索(binary search)
ムラサちゃんとskypeで雑談してたら、こんな問題が飛んできた。
ｎ個の整数の集合Sとある整数ｘが与えられたとき、Sの中の２個の要素でそれらの和がちょうどｘになるものの組を見つける、実行時間Θ（ｎｌoｇ2(ｎ)）のプログラムを作れ。
整数は面倒なので、10億程度までの自然数で考える。0は含めても含めなくても良い。
普通に考えると、以下のような探索が思いつく。
for(int i=0; i<n-1; ++i){ for(int j=i+1; j<n; ++j){ if(s[i] + s[j] == x){ ... } } }
これの(時間)計算量はO(n^2)*1である。計算量のお話はまた今度する。
まぁ、これでも十分なんだけど、nが1,000になると計算量が1,000,000となり、実行時間的には少し怪しげになる。
そこで、O(nlogn)のアルゴリズムを考えてみる。これだと、nが1,000になっても計算量は32,000程度である。すごい。
O(logn)を見ると真っ先に思い浮かぶのが、二分探索(binary search)であった。ので、二重めのループで二分探索を用いたコードを書いた。
二分探索は、あらかじめソートされたデータ群を前提とする探索方法である。
たとえば、以下のようなデータ群から''13''をサーチしたいとする。
{1,2,4,6,7,9,10,13,15,16}
このデータ群の真ん中に位置するデータをチェックする。「真ん中」は真ん中付近であれば大雑把で良い。今回は、データ群の個数kが偶数のときは、左から(k/2)+1番目を見ることにしよう。
上の例で、真ん中のデータは''9''である。サーチデータ''13''ではなかった。ここで、サーチデータ''13''は、少なくとも''9''より右側に存在することが分かる*2。
よって、今度は以下のデータ群で再び同様のチェックを行う。
{10,13,15,16}
真ん中のデータは''15''である。サーチデータ''13''は、少なくとも''15''より左側に存在することが分かる。
今度は、以下のデータ群で見てみる。
{10,13}
真ん中のデータは''13''である。サーチデータ''13''と一致し、めでたく探索が終了する。
この探索の凄い所は、1回の探索で探索せねばならないデータ数が半分に減ることである。よって、n個のデータ群の探索で最悪O(logn)の計算量である*3。
二重めのループで二分探索を用いることで、探索アルゴリズムの計算量はO(nlogn)となる。
#include <iostream> using namespace std; const int max_n = 10000; int s[max_n]; //集合S int culc_num; //計算回数(比較回数) //二分探索 //見つかった:0 見つからなかった:-1 int binary_search(int *data, int data_num, int target){ int m = data_num / 2; ++culc_num; /* if(m >= 0){ cout << "\t("; for(int i=0; i<data_num; i++){ cout << data[i]; if(i < data_num-1) cout << ","; else cout << ")" << endl; } cout << "\tcheck:" << data[m] << endl; } */ if(data_num < 1) return -1; else if(data[m] == target) return 0; else{ if(data_num == 1) return -1; else if(data[m] < target) return binary_search(&data[m+1], data_num-m-1, target); else return binary_search(&data[0], m, target); } } int main(){ //見つけたい解を入力 int x; cin >> x; //データ数の入力 int n; cin >> n; //n個のデータを入力。昇順入力じゃないとぉこだょ for(int i=0; i<n; ++i) cin >> s[i]; //s[i] + s[j] = xなる解を探索 int ans_num = 0; //解の個数 for(int i=0; i<n-1; ++i){ int target = x - s[i]; //どの数値を見つければ良いか // cout << "search:" << target << endl; if(binary_search(&s[i+1], n-i-1, target) == 0){ cout << "(" << s[i] << "," << target << ")" << endl; ++ans_num; } } //解の出力 if(ans_num == 0) cout << "NA" << endl; cout << "ans_num:" << ans_num << endl; cout << "culc_num:" << culc_num << endl; return 0; }
コメント化している命令を解除すれば、どのような動きで探索が為されているか見れる。
たとえば、x=13,n=10,S={1,3,4,4,5,6,7,8,9,10}なる入力を与えると、その結果は以下のようになる。
入力:
13
10
1
3
4
4
5
6
7
8
9
10出力:
(3,10)
(4,9)
(4,9)
(5,8)
(6,7)
ans_num:5
culc_num:20
同じことを、最初のO(n^2)アルゴリズムで行うと、culc_numは45となる。
2.3 AOJ-0006 to 0010
今日もAOJの問題を解いていた。
0006
文字列の反転問題。
0007
毎週5%の利子がついて、しかも1000円未満は切り上げられるという闇金業者の借金が、n週間後にはいくらになるか、という教育上よろしいのか疑われる問題。
1000円未満の切り上げ処理がポイント。むしろそこしかポイントが無い。
//一の位から数えてketa桁未満で繰り上げる void keta_up(int &num, int keta){ int p = pow(10, keta); int n = num / p; if(num-n*p > 0){ num /= p; num += 1; num *= p; } }
0008
0~9なる整数a,b,c,dで、a+b+c+d=nなる組み合わせは何通りか、という問題。
探索系の問題だけど、この場合はコレで解ける。
#include <iostream> using namespace std; int main(){ int n; while(cin >> n){ int ans_num = 0; for(int a=0; a<10; ++a){ for(int b=0; b<10; ++b){ for(int c=0; c<10; ++c){ for(int d=0; d<10; ++d){ if(a+b+c+d == n) ++ans_num; } } } } cout << ans_num << endl; } return 0; }
こんな問題もあったねぇ。
0009
n以下の素数はいくつあるか、という問題。範囲が決められているのでエラトステネスの篩を使う。これ以外の選択肢は無い。篩のために使う変数は、グローバルにしておくこと(スタック領域じゃオーバーフローを起こす)。
#include <iostream> #include <vector> using namespace std; const int MAX_NUM = 1000000; bool prime_flag[MAX_NUM]; vector<int> prime; void check_prime(){ prime_flag[0] = false; for(int i=1; i<MAX_NUM; ++i){ if(prime_flag[i] == true){ int num = i+1; for(int j=2*num; j<MAX_NUM+1; j+=num){ prime_flag[j-1] = false; } prime.push_back(i+1); } } } int main(){ for(int i=0; i<MAX_NUM; ++i) prime_flag[i] = true; check_prime(); int n; while(cin >> n){ int i; for(i=0; i<(int)prime.size(); ++i){ if(prime[i] > n) break; } cout << i << endl; } return 0; }
0010
三点が与えられるので、それで作られる三角形の外接円の中心座標と半径を求めよ、とのこと。
中心座標の導出がめっちゃめんどい。2弦の垂直二等分線の交点がそれなので、それを導出してみる。
まず、(x1,y1)と(x2,y2)の垂直二等分線は以下のような直線である。
この時点で割と吐き気がする。
よって、
この連立方程式を解けば良い。ゲェ～ッ。
行列使って解いて、解は以下のようになる。
これはひどい。
一応、ちゃんと正解は出せる。動作も非常に高速である。見た目はともかく。
半径の導出は簡単なので省略。
2.2 AOJ-0000 to 0005
POJが重すぎて繋がらないので、AOJ(http://judge.u-aizu.ac.jp/onlinejudge/index.jsp)に浮気した。問題文も日本語だし、難易度も低いし。あの会津大学が主催してるらしい。
で、練習問題を数問解いた後、レーティングに反映される問題を6問ほど解いた。
0000
九九の表を出力する問題。懐かしい。
0001
入力された10整数のうち、大きいものから3つ出力する問題。
バブルソートをちゃちゃっと書けるようになっておけば楽勝。バブルソートは4行で書けるので、それで解ける問題なら実装が面倒なクイックソートとかより経済的。ただ、ライブラリは存在する気がする。
大きい順でソートするバブルソート。
void bubble_sort(int *data, const int data_num){ for(int i=0; i<data_num; ++i){ for(int j=0; j<data_num-i-1; ++j){ if(data[j] < data[j+1]) swap(data[j], data[j+1]); } } }
0002
入力した2整数の和の桁数を表示する問題。
以下の関数で8ケタまで求められる。
int check_keta(int n){ int i; for(i=1; i<9; ++i){ if(n/(int)pow(10, i) == 0) break; } return i; }
ホントはbreakをreturnに変えて、intをforの中で宣言してもっとスマートにしたかったが、「returnせずに終了する可能性がある」ってg++に怒られた(警告)ので泣く泣く書き換えた。
0003
入力した3整数で直角三角形が作れるか、という問題。
最も大きい数を斜辺とした直角三角形を考えれば良い。バブルソートで3整数を整理すればスムーズに処理できる。
0004
連立方程式を解いてください。ただし、解は一意に与えられますよ、とのこと。
行列使って計算するのが早い。即座に、以下のように解が導き出せる。
解は一意に与えられるとのことなので、ae-bd=0は無いと考えれば良い。
さて、解は小数第3位まで表示するのだが、その関係で「-0.000」なる出力が為されることがある。これはWrong Answerとなるので、abs(x) < 0.0005のときはx=0とするなどすると良い。
0005
GCDとLCMを求める問題。
GCDに関しては、ユークリッドの互除法が有名なので、それを使う。
LCMに関しては、2数をA,B、GCD=Gとすると、
となることを用いて導出する。
GCDは再帰関数の良い練習問題として有名。
LCMのこの計算順序は、オーバーフローを防ぐため。
int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a%b); } int lcm(int a, int b){ return a/gcd(a,b)*b; }
2.1 POJ-1068
整数ナンバリング2は、蟻本関連にしようかなぁ、と思う。
蟻本に載ってた、POJ(http://poj.org/)っていうオンラインジャッジシステムのあるプログラミングコンテスト練習サイトに、ちょっと足を運んでいる。
Solvedは今の所、1000、1001、1068の3問。1000は「a,b2つの入力が与えられる。a+bの結果を出力せよ」っていう練習用問題で、1001は「R(0 < R < 99.9)とn(0 < n <= 25)が与えられる。R^nを「正確に」出力せよ」っていうちょっと骨のある問題。問題文が英語ってのもあって、R^nを見た時は「いきなりn次元ユークリッド空間の問題か…ヤバ」って思ってしまった。
で、これを解くのに色々と疲れたので、次は正答率の最も高い奴を解くことにした。それが1068だった。
ID.1068
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
Source
Tehran 2001
要は、カッコ(parentheses)で表現された文字列があって、その数列での表し方が2通りあるんだけど、一方の表現方法をもう一方の表現方法に変換してね、っていう問題。
アルゴリズムはいろいろあると思うけど、まずはカッコを用いた文字列に変換して、それを基にもう一方の表現方法に変換するようにした。
そんなに面白い問題ではないし、これ以上解説しても無意味っぽいので、練習問題がてらコードを載せてこの記事を締める。
#include <iostream> using namespace std; const int MAX_N = 20; const int MAX_STRING = 64; int main(){ int t; cin >> t; for(int i=0; i<t; ++i){ int n; cin >> n; int p[MAX_N]; for(int j=0; j<n; ++j) cin >> p[j]; //()に変換 char st[MAX_STRING]; for(int j=0,k=0,left_num=0; j<2*n; ++j){ if(left_num == p[k]){ st[j] = ')'; if(k < n-1) ++k; } else{ st[j] = '('; ++left_num; } } //W-sequenceに変換 int w[MAX_N]; for(int j=0,check_num=0; j<2*n; ++j){ if(st[j] == ')'){ for(int k=j-1,ok=0,left_num=0; k>=0; --k){ if(st[k]=='(' && ok==0){ ++left_num; w[check_num] = left_num; break; } else if(st[k]=='('){ --ok; ++left_num; } else ++ok; } cout << w[check_num] << " "; ++check_num; } } cout << endl; } }
1.3.2 動的確保のスタック・キューへの適用
//dynamic_stack #include <iostream> template <class T> class stack{ class set_of_datum{ private: T value; set_of_datum *next; public: set_of_datum(T value){ this->value = value; next = NULL; } void set_next(set_of_datum *next){ this->next = next; } set_of_datum *get_next(){return next;} T get_value(){return value;} }; private: set_of_datum *data; //スタックの本体 public: stack(); //コンストラクタ ~stack(); //デストラクタ void clear(); //スタックの中身を空にする void push(T obj); //スタックにobjを追加する T pop(); //スタックからobjを取り出す void show(); //スタックの中身を見せる int get_data_num(); //スタックデータの数を返す }; template <class T> stack<T>::stack(){ data = NULL; } template <class T> stack<T>::~stack(){ clear(); } template <class T> void stack<T>::clear(){ while(data != NULL){ set_of_datum *target = data; //delete対象 data = (*data).get_next(); delete target; } } template <class T> void stack<T>::push(T obj){ set_of_datum *new_datum = new set_of_datum(obj); (*new_datum).set_next(data); data = new_datum; } template <class T> T stack<T>::pop(){ T dummy; //error発生時に返すダミーデータ if(data != NULL){ T value = (*data).get_value(); set_of_datum *target = data; //delete対象 data = (*data).get_next(); delete target; return value; } else{ std::cout << "error: this stack is EMPTY! -- in stack<T>::pop()" << std::endl; return dummy; } } template <class T> void stack<T>::show(){ set_of_datum *ptr = data; //表示するデータ for(int i=0; ptr!=NULL; i++){ std::cout << i << ":" << (*ptr).get_value() << std::endl; ptr = (*ptr).get_next(); } } template <class T> int stack<T>::get_data_num(){ int value = 0; set_of_datum *ptr = data; while(ptr != NULL){ value ++; ptr = (*ptr).get_next(); } return value; }
まぁ、こんなものだろう。
同様に、キューも。
//dynamic_queue #include <iostream> template <class T> class queue{ class set_of_datum{ private: T value; set_of_datum *before; set_of_datum *next; public: set_of_datum(T value){ this->value = value; before = NULL; next = NULL; } void set_before(set_of_datum *before){ this->before = before; } void set_next(set_of_datum *next){ this->next = next; } set_of_datum *get_before(){return before;} set_of_datum *get_next(){return next;} T get_value(){return value;} }; private: set_of_datum *data; //キューの本体(先頭) set_of_datum *pop_target; //キューの本体(末尾) public: queue(); //コンストラクタ ~queue(); //デストラクタ void clear(); //キューの中身を空にする void enqueue(T obj); //キューにobjを追加する T dequeue(); //キューからobjを取り出す void show(); //キューの中身を見せる int get_data_num(); //キューのサイズを返す }; template <class T> queue<T>::queue(){ data = NULL; pop_target = NULL; } template <class T> queue<T>::~queue(){ clear(); } template <class T> void queue<T>::clear(){ while(data != NULL){ set_of_datum *target = data; //delete対象 data = (*data).get_next(); delete target; } } template <class T> void queue<T>::enqueue(T obj){ set_of_datum *new_datum = new set_of_datum(obj); if(get_data_num() == 0) pop_target = new_datum; else{ (*new_datum).set_next(data); (*data).set_before(new_datum); } data = new_datum; } template <class T> T queue<T>::dequeue(){ T dummy; //error発生時に返すダミーデータ if(data != NULL){ T value = (*pop_target).get_value(); set_of_datum *target = pop_target; //delete対象 if(data == target) data = NULL; else (*(*target).get_before()).set_next(NULL); pop_target = (*target).get_before(); delete target; return value; } else{ std::cout << "This queue is EMPTY! -- error in queue<T>::pop()" << std::endl; return dummy; } } template <class T> void queue<T>::show(){ set_of_datum *ptr = data; for(int i=0; ptr!=NULL; i++){ std::cout << i << ":" << (*ptr).get_value() << std::endl; ptr = (*ptr).get_next(); } } template <class T> int queue<T>::get_data_num(){ int value = 0; set_of_datum *ptr = data; while(ptr != NULL){ value++; ptr = (*ptr).get_next(); } return value; }
queue< T >::dequeue()のif文の中身が若干汚いけど、他に書き方はあるのだろうか。
1.3.1 動的確保
動的確保についてのお話。
今回、スタックやキューに動的確保を適用するところまで行かなかった(記事が長くなり過ぎる)ので、1.3.1という番号を振った。次回はスタック・キューに動的確保を導入する。
CやC++において、配列を宣言する時は以下のようにしなくてはならない。
float hoge[10]; const int num = 5; float fuga[num];
つまり、宣言時に配列のサイズを確定させなくてはならないということ。
で、以下のような宣言サイズに変数を用いるケースではコンパイルエラーが発生する。
int num = 5; float fuga[num]; //error!
これは、C/C++のコンパイラがコンパイル時に配列に必要なメモリを確保する為であるらしい。
しかし、場合によっては配列の要素数を可変長にしたいこともある。データ数が未知である場合などである。そういう時は、少し特殊な形式で配列を宣言する必要がある。占有メモリ数が固定である今までの例が静的確保と呼ばれるのに対して、このように占有メモリ数が可変長である配列を宣言することは、動的確保と呼ばれる。
動的確保では、メモリの管理はプログラマに任される。今までコンパイラが自動化していた処理をプログラマが担うということである。メモリ管理では、メモリの確保と解放が大切である。
Cの場合
こちらは自分があまり利用する機会が無いだろうが、一応書いておく。
Cの場合、stdlib.h内にあるmalloc()とfree()を用いて確保と解放を行う。
//mallocによる動的確保 #include <stdio.h> #include <stdlib.h> int main(){ int *lst; int lst_size; int i; scanf("%d", &lst_size); lst = (int *)malloc( sizeof(int)*lst_size ); for(i=0; i<lst_size; i++) scanf("%d", &lst[i]); for(i=0; i<lst_size; i++) printf("%d:%d\n", i, lst[i]); free(lst); return 0; }
動的に確保したい配列を、ポインタ変数として宣言する(int *lst)。
malloc()の返り値はvoid*型なので、キャストによって正しい形式に揃える。確保メモリは引数で指定する。
最後に、確保したメモリをfree()で解放するのを忘れないこと。
C++の場合
Cでいうmalloc()とfree()を、newとdeleteが肩代わりする。これらは関数では無く演算子である点に注意する。
//newによる動的確保 #include <iostream> using namespace std; int main(){ int *lst; int lst_size; cin >> lst_size; lst = new int[lst_size]; for(int i=0; i<lst_size; i++) cin >> lst[i]; for(int i=0; i<lst_size; i++) cout << i << ":" << lst[i] << endl; delete[] lst; return 0; }
「new (型)[確保サイズ]」で「(型*)malloc(sizeof(型)*確保サイズ)」と同じ意味を表す。解放にはdelete[ ]を用いる。確保サイズが1で良い場合は、[ ]を省く。このとき、解放はdeleteを用いる点に注意([ ]が要らない)。*1
listの表現
さて、動的確保を用いてlistを表現しよう。
listの要求仕様は以下であるとする。
データ(型未定)は動的に確保される。
push(obj)でデータをリストの先頭に追加。
pop(num)でnum番目の要素を取り出す。
pop_element(elem)でリストからelem要素を削除し、削除数を返す。
find(value)でリストからvalue要素を検索し、最近pushされた要素番号を返す。
clear()でリストを初期化。
size()でリストサイズを返す。
show()でリストの内容を展開する。
//list #include <iostream> template<class T> class list{ class set_of_datum{ //valueとnextのセット private: T value; set_of_datum *next; public: set_of_datum(T value){ this->value = value; next = NULL; } int set_next(set_of_datum *next){ this->next = next; } set_of_datum *get_next(){return next;} T get_value(){return value;} }; private: set_of_datum *data; //先頭データ public: list(); //コンストラクタ ~list(); //デストラクタ void clear(); //メモリの全解放 int size(); //listサイズを返す void push(T value); //valueをpushする T pop(int num); //num番目の要素をpopする int pop_element(T elem); //elementを消去する int find(T value); //valueを持つデータが何番目にあるか void show(); //listの要素を見せる }; template<class T> list<T>::list(){ data = NULL; std::cout << "list<T>::list()" << std::endl; } template<class T> list<T>::~list(){ clear(); std::cout << "list<T>::~list()" << std::endl; } template<class T> void list<T>::clear(){ set_of_datum *next = data; //listの次のポインタを示す while(next != NULL){ set_of_datum *target = next; //delete対象 next = (*next).get_next(); delete target; } data = NULL; } template<class T> int list<T>::size(){ int value = 0; set_of_datum *next = data; //listの次のポインタを示す while(next != NULL){ next = (*next).get_next(); value++; } return value; } template<class T> void list<T>::push(T value){ set_of_datum *new_datum = new set_of_datum(value); (*new_datum).set_next(data); data = new_datum; } template<class T> T list<T>::pop(int num){ T dummy; //エラー発生時に返すもの if(num<0){ std::cout << "invalid num:" << num << " -- error in list<T>::pop" << std::endl; return dummy; } set_of_datum *target = data; set_of_datum *before = NULL; for(int i=0; i<num; i++){ if(target == NULL) break; before = target; target = (*target).get_next(); } if(target == NULL){ std::cout << "invalid num:" << num << " -- error in list<T>::pop" << std::endl; return dummy; } if(before == NULL){ //listの最初をpopした data = (*target).get_next(); } else{ (*before).set_next((*target).get_next()); } T value = (*target).get_value(); delete target; return value; } template<class T> int list<T>::pop_element(T elem){ int value = 0; while(true){ int num = find(elem); if(num == -1) return value; pop(num); value++; } } template<class T> int list<T>::find(T value){ set_of_datum *d = data; for(int i=0; d!=NULL; i++){ if((*d).get_value() == value) return i; d = (*d).get_next(); } return -1; } template<class T> void list<T>::show(){ set_of_datum *d = data; for(int i=0; d!=NULL; i++){ std::cout << i << ":" << (*d).get_value() << std::endl; d = (*d).get_next(); } }
簡単に仕組みを説明すると、listの本体である*dataは、値であるvalueと次要素へのポインタであるnextを持っている。初期*dataはNULLである。
リストのn番目がpopされた場合、n-1番目の要素のnextをn+1番目の要素に繋ぎ、n番目の要素をdeleteすれば平和的に解決される。
口で言うのは簡単だが、これをコーディングするのはなかなか骨が折れた。大学の実験でもC言語でlistを組んだが、一発合格が貰えたのはクラスの優秀な人たち3人ほどだった(私はもちろん入っていない)。興味が持てた人は一度自分で組んでみることを薦める。
上記listの利用例は以下の通りである。やや長くなっているので、「続きを読む」で格納しておく。
