はじめに

プログラム言語の文法：Cに組み込まれたアルゴリズムとデータ構造
↓
本講義：プログラム言語に組み込まれていないデータ構造
↓
アルゴリズム論:プログラム言語に組み込まれていないアルゴリズム
space.gif
line.gif
space.gif
図
Fig1S.gif
space.gif
line.gif
space.gif

データ構造


データ構造：”データ要素”（文字、数、・・・、真理値など）の集まり
集合、群、体、半群、graph(2項関係),オートマトン
★主題１.　データ構造にはなにがあるのか？
★主題２.　データ構造を計算機上にいかに実現するか？
空間計算量は？
ある問題に対する計算量は？
★主題３.　与えられた抽象構造を利用可能な論理構造で、いかに実現するか？

☆記法　データ構造は２項組（対象、対象上の関係（演算））と書かれる。

例　データ構造の例
群 G=(S,O)
自然数　N = (N, {+, -, /, ×,　↑})
配列処理系　＝　({配列},{配列要素の参照、指数計算})
集合処理系　＝　(集合,{∪,∩,...})
space.gif
line.gif
space.gif
グラフとリスト
gralist.GIF
グラフ：ネットワークを表現
グラフ処理系：({グラフ},{∪,∩,探査など})
graph1S.gif
space.gif
line.gif
space.gif
グラフとリストの基本概念
用語
定義
Vを有限集合とする
G＝（V,E）
をgraphという。ここで、 E⊆V×Vの元をedge(辺)
Vの元をvertex(頂点)又はnodeという

例　グラフとその図示
G1 = {{a,b,c},{(a,b), (b,c)}}
graph_g1S.gif
と書かれる。
G2 = {{a,b,c},{(a,b),(b,c),(c,b)}}は
graph_g1_2S.gif
と書かれる。
space.gif
line.gif
space.gif
用語
”List”は"record"の集まり。
ここで、recordは次のような形
structS.gif
で、各menberS.gif は"field"といい
各fieldには次の２種類のいずれかが入る：
他レコードへの"ポインタ"、
数または文字列、真理値

例
st_ex_S.gif
G1に対応
space.gif
line.gif
space.gif
例　データ構造
i 抽象レベル（グラフ）
graph_g3S.gif
G3 = (V3,E3)
V3 = {COBOL, FORTRAN, Basic, PL/I, ada,
ALGOL. C, PASCAL, Modula2, アセンブラ語}
E3 = {(COBOL, PL/I), (FORTRAN, PL/I), ... }
手続き型言語の系譜
space.gif
line.gif
space.gif
ii 中間言語レベル（リスト）
G3に対応するリストの例
List_g3S.gif
space.gif
line.gif
space.gif
iii 言語レベル（C言語の場合）
[テーブル表現]
struct Languages{
space.gif char[10] Name;
space.gif int suc1;
space.gif int suc2;
space.gif int suc3;
}

struct Languages program_languages[20];
space.gif
line.gif
space.gif
実現例
program_languages[20]
table.GIF