応用プログラミングとアプリケーション

データ構造：配列、連結リスト、スタック、キュー

データ構造とは、プログラムが速く簡単に使えるようにデータを並べる方法のことです。

• 配列：大きさが決まっていて、要素が横に並びます。添字（a[3]など）でどの要素にもすぐ届きます。途中に追加するのは遅いです。
• 連結リスト（動的）：各ノードが値と次のノードへのリンクを持ちます。必要に応じて増えたり減ったりしますが、5番目を見るには1番目から4番目まで順にたどる必要があります。
• スタック：片方の端だけで push と pop をします（LIFO）。元に戻す機能、戻るボタン、かっこのチェックに使います。
• キュー：うしろに追加し、前から取り出します（FIFO）。印刷の順番待ちや行列に使います。

ライブラリには、これらの道具がすでに入っています。Pythonでは list がスタックとして使えます（append、pop）。collections.deque は速いキューとして使えます。ライブラリがあるときはそれを使い、自分で作り直さないようにしましょう。

stack = []
stack.append(5); stack.append(8)
stack.pop()      # gives 8
from collections import deque
q = deque([4, 9]); q.append(2)
q.popleft()      # gives 4

IDEを使う：書く、動かす、テストする

IDE（統合開発環境）は、エディタ、実行ボタン、デバッガ、各種ツールを1か所にまとめたものです。コードに色を付け、名前の候補を出し、入力中にエラーを教えてくれます。

• 実行してプログラムを動かし、出力を読みます。
• 簡単な入力、ふつうの入力、意地悪な入力（空のリスト、ゼロ、とても大きな数）でテストします。
• デバッグ：ブレークポイントを置いて1行ずつ進み、変数の変化を見ます。

2D・3Dの可視化とアニメーション

絵を使うと、パターンが見えやすくなります。プログラムは、グラフ（棒、折れ線、散布図）、2Dの図、3Dの場面を描けます。アニメーションとは、少しずつ変えた同じ絵を何度も描き直すことです（1秒に30〜60回ほど）。簡単な方法は、x のような変数を用意し、フレームごとに少し足して描き直すことです。このページの3Dも、3Dライブラリを使って同じようにつくっています。

表計算の応用関数

表計算ソフトは、関数を使ってプログラムのような作業ができます。

• IF(B2>=50,"Pass","Fail") は、2つの結果から1つを選びます。
• SUMIF(B2:B5,">=50") は、条件に合うセルだけを足します。COUNTIF は、その数を数えます。
• VLOOKUP(2, A2:B5, 2, FALSE) は、最初の列から2を探し、同じ行の2列目の値を返します。XLOOKUP も同じことを、もっと簡単にできます。
• ピボットテーブルは、大きなデータをグループごとに集計します。グラフは、その結果を見せます。

リレーショナルデータベースとSQL

リレーショナルデータベースは、行と列でできたテーブルにデータを入れます。各テーブルには主キーがあります。主キーは値が重ならない列です（id）。別のテーブルは、その値を外部キーとして持ち、つながります。よい設計では、1つの事実を1回だけ保存するので、同じデータが繰り返されません。

SQLは、質問をしたりデータを変えたりするための言語です。

SELECT name, score FROM students
JOIN marks ON students.id = marks.id
WHERE score >= 50 ORDER BY score DESC;

INSERT INTO marks (id, score) VALUES (5, 67);
UPDATE marks SET score = 55 WHERE id = 2;
DELETE FROM marks WHERE id = 5;

整合性とは、データが正しいままであることです。キーは重ならず、外部キーは実在する行に合い、値は正しい型を持ちます。セキュリティとは、ユーザーごとのパスワード、必要な権限だけを与えること、バックアップ、そしてユーザーの文字をそのままつなげてSQLを作らないこと（パラメータを使う）です。これでSQLインジェクションを防げます。

オープンな資源への貢献

多くの道具やライブラリはオープンソースです。ライセンスのもとで、だれでも読んで、使って、改良できます。バグを直す、説明を良くする、ページを翻訳する、例を足すなどで協力できます。必ずライセンスを読み、作者の名前を示し、変更を提案するときは、分かりやすく丁寧に書きましょう。

やってみよう

3Dのステップ5で、スタックに3つの値をpushし、それからpopしてみましょう。出てきた順を書きます。キューでも同じことをします。次に、先に予想してから確かめましょう。4、9、2を追加して1つ取り出したあと、キューの先頭とスタックの一番上には、どの値が残るでしょうか。

重要な公式と用語

• スタック = LIFO（後入れ先出し）：push、pop。
• キュー = FIFO（先入れ先出し）：enqueue、dequeue。
• 配列：大きさが固定、添字でアクセス。連結リスト：大きさが可変、リンクをたどる。
• SELECT columns FROM table WHERE condition
• 主キー = 重ならないid。外部キー = ほかのテーブルへのリンク。

例題

よくある間違い

• 大きさが前もって分からないのに配列を使う。リストや連結リストのほうが向いています。
• スタックとキューを混ぜてしまう。スタックは一番新しいものを、キューは一番古いものを取り出します。
• UPDATEやDELETEでWHEREを忘れる。すべての行が変わってしまいます。
• ユーザーの文字をそのままつなげてSQLを作る。パラメータを使いましょう。