データ構造とプログラミング技法 ( 第 2 回 ) ー線形構造ー
線形構造 用語 : レコード : ひとまとまりのデータ ( 構造体 ) 線形リスト :n 0 個のレコードの1 次元並び 順配置 : 表 リンク配置 : 連鎖リスト
順配置された線形リスト : 表 論理構造 物理構造 a b c d f 要素の 位置 の順序関係を アドレスの値の順序関係で表現する方法 0000 0001 0002 0003 0004 0005 0006 0007 a b c d f
表に対する操作 : 要素の挿入 削除 0000 0001 0002 0003 0004 0005 0006 0007 a b c d f a b c f d 論理構造物理構造 b c f d 0000 0001 0002 0003 0004 0005 0006 b c d f
表に対する操作 : アクセス N 番目の要素 a N 番目の要素のアドレス = 先頭番地 +(N-1) 要素サイズ b N=5 c d f 0004 0000 0001 0002 0003 0004 0005 0006 0007 a b c d f
リンク配置された線形リスト : 連鎖リスト 論理構造 a b c d f 物理構造実際 0000 a 100b 0003 null 0008 c 0032 000d 0106 001a 0003 0032 d 000d 0106 f 001a 100b b 0008 記法 a b c d f
連鎖リストに対する操作 : 要素の挿入 削除 論理構造 物理構造 a b c d f b c d f a b c d f
連鎖リストに対する操作 : 要素の挿入 削除
連鎖リストに対する操作 : アクセス N 番目の要素 N-1 回リンクを辿る a b a b c c d d f N=5 f
連鎖リストの変種
論理構造の表現法 ( 物理構造 ) 論理構造 = 線形リスト 物理構造 = 順配置 ( 表 ) アクセスが早い 追加 削除 などの変更に弱い リンク配置 ( 連鎖リスト ) アクセスが遅い 追加 削除などの変更に適する
スタックと待ち行列 : データ抽象化 データ構造 + 操作手続き例 : スタック待ち行列 PUSH POP Enquu a d c b a b c d Dquu
スタックの操作 ( 表を用いた場合 )
キューの操作 ( 表を用いた場合 )
スタック / キューは何のために用いるか 系統的な記憶と想起のメカニズム スタック (LIFO) 環境の保存と参照ー > 再帰呼び出し 木 グラフの縦型探索 キュー (FIFO) バッファ ( 緩衝用 ) メモリ 装置間の速度差の吸収 木 グラフの横型探索
迷路の探索 : スタックの利用の例 :1
探索木
迷路の探索アルゴリズム
list にスタックを用いた場合
木の縦型探索とスタック
再帰的構造 0, i=0 f(i)= 1, i=1 f(i-1)+f(i-2), i 2 Fibonacci 数 int Fib(int i) { switc(i){ cas 0: rturn(0);brak; cas 1: rturn(1);brak; dfault: rturn(fib(i-1)+fib(i-2));
再帰的構造 int Fib(int i) { switc(i){ cas 0: rturn(0);brak; cas 1: rturn(1);brak; dfault: rturn(fib(i-1)+fib(i-2)); Fib(3) Fib(2)+Fib(1) (Fib(1)+Fib(0))+1 (1+0)+1
再帰的構造 同じ変数名であっても 関数呼び出し の度に 別の記憶領域が確保される ( スタックを利用している ) 変数の内容は 他の関数呼び出しに よって破壊されることはない
Advancd-1Fibonacci 数を再帰呼び出しで 求めるプログラム #includ <stdio.> int fib(int x) { switc(x){ cas 0: rturn 0; brak; cas 1: rturn 1; brak; dfault: rturn fib(x-1)+fib(x-2); int main(int arc, car *arv[]) { int x; wil(--arc){ x=atoi(*++arv); printf("fib %d = %d n",x,fib(x)); rturn 0; 実行例 : %./fib 15 Fib 15 = 610
Advancd-2 環状連鎖リストを使った 電光掲示板風表示ログラム #includ <stdio.> #includ <strin.> #includ <unistd.> //Slf rfrntial structur typ dfinition typdf struct nod{ car c; struct nod *nxt; NODE; NODE *AllocNods(int num) {//Mmory allocation NODE *rt; int i; rt=(node *)malloc(sizof(node) *num ); for (i=0; i<num; i++){ if (i<num-1) (rt+i)->nxt = (rt+i+1); 実行例 : %./link1 Tis is a pn 与えた文字列が横スクロールする ls (rt+i)->nxt = rt;//connct tail to ad rturn rt;
Advancd-2 続き void StCar(NODE *p, car *rf) { wil(*rf){ p->c=*rf; p=p->nxt; rf++; PrintNod(NODE *p,int n) { wil(n--){ printf("%c",p->c); p=p->nxt; fflus(stdout); int main(int arc, car *arv[]) { int ln; car lin[300]; NODE *s; lin[0]=(car)null; wil(--arc){//concatinat ars strcat(lin,*++arv); strcat(lin," "); ln=strln(lin);//strin lnt s=(node *)AllocNods(ln); StCar(s,lin); wil(1){ //Endlss Loop PrintNod(s,ln); putcar (' r'); //Carrid rturn s=s->nxt; uslp(80000);
Advancd -2STACK/QUEUE #includ <stdio.> #includ <stdlib.> //#dfin QUEUE #dfin STACK #dfin SIZ 10 // キュー // スタック /********* キューの定義 **************/ #ifdf QUEUE #dfin Add(Q,x) n_quu(&q,x) #dfin Gt_And_Dlt(Q) d_quu(&q) #dfin Not_Empty(Q) Q.QF!=Q.QR #dfin Init(Q) Q.QF=Q.QR=0 #dfin Stack_or_Quu quu #dfin QUEUE_SIZ SI // キューのサイズ struct Quu { int Buf[QUEUE_SIZ]; int QF; int QR; ; typdf struct Quu quu; /* QUEUE 用 */ void n_quu(); void n_quu(quu * Q, int v) { Q->QR = (Q->QR+1)%QUEUE_SIZ; if (Q->QR == Q->QF) { fprintf(stdrr,"quu Ovrflow n"); xit(1); ls{ Q->Buf[Q->QR] = v; d_quu(quu * Q) { if (Q->QR == Q->QF) { fprintf(stdrr,"quu Undrflow n"); xit(1); ls{ Q->QF = (Q->QF+1)%QUEUE_SIZ; rturn Q->Buf[Q->QF]; #ndif /******** キューの定義終わり *************/
/******** スタックの定義 *****************/ #ifdf STACK #dfin Add(S,x) pus(&s,x) #dfin Gt_And_Dlt(S) pop(&s) #dfin Not_Empty(S) S.SP>0 #dfin Init(S) S.SP=0 #dfin Stack_or_Quu stack #dfin STACK_SIZ SIZ // スタックのサイズ struct Stack { int Buf[STACK_SIZ]; int SP; ; typdf struct Stack stack; void pus(stack* S,int d) { if (S->SP<STACK_SIZ-1) { S->Buf[S->SP++]=d; ls{ fprintf(stdrr,"stack ovrflow. n"); xit(1); pop(stack* S) { if (S->SP > 0) { rturn S->Buf[--(S->SP)]; ls{ fprintf(stdrr,"stack undrflow. n"); xit(1); #ndif /******* スタックの定義終わり ***********/ Advancd -2 続き main() { int i,c; Stack_or_Quu X; Init(X); for (i=0; i< SIZ-1; i++) { c=(int)('a'+i); Add(X,c);putcar(c); putcar(' n'); wil(not_empty(x)) putcar(gt_and_dlt(x)); putcar(' n'); 実行例 : % stack-quu ABCDEFGHI IHGFEDCBA