線形構造 データ構造とアルゴリズム ( 第 2 回 ) ー線形構造ー 用語 : レコード : ひとまとまりのデータ ( 構造体 ) 線形リスト :n 0 個のレコードの 1 次元並び 順配置 : 表 リンク配置 : 連鎖リスト 順配置された線形リスト : 表 要素の 位置 の順序関係を アドレスの値の順序関係で表現する方法 表に対する操作 : 要素の挿入 削除 表に対する操作 : アクセス リンク配置された線形リスト : 連鎖リスト N 番目の要素 N=5 N 番目の要素のアドレス = 先頭番地 +(N-1) 要素サイズ 実際 記法 100 null 0008 0032 000 0106 001 0032 000 0106 001 100 0008 1
連鎖リストに対する操作 : 要素の挿入 削除 連鎖リストに対する操作 : 要素の挿入 削除 連鎖リストに対する操作 : アクセス N 番目の要素 N-1 回リンクを辿る 連鎖リストの変種 N=5 の表現法 ( ) = 線形リスト = 順配置 ( 表 ) アクセスが速い 追加 削除 などの変更に弱い リンク配置 ( 連鎖リスト ) アクセスが遅い 追加 削除などの変更に適する スタックと待ち行列 : データ抽象化 データ構造 + 操作手続き 例 : スタック PUSH POP 待ち行列 Enquu Dquu 2
スタックの操作 ( 表を用いた場合 ) キューの操作 ( 表を用いた場合 ) スタック / キューは何のために用いるか 系統的な記憶と想起のメカニズム l スタック (LIFO) l 環境の保存と参照ー > 再帰呼び出し l 木 グラフの縦型探索 l キュー (FIFO) l バッファ ( 緩衝用 ) メモリ 装置間の速度差の吸収 l 木 グラフの横型探索 迷路の探索 : スタックの利用の例 :1 探索木 迷路の探索アルゴリズム 3
list にスタックを用いた場合 木の縦型探索とスタック 0, i=0 (i)= 1, i=1 (i-1)+(i-2), i 2 Fioni 数 int Fi(int i) swit(i) s 0: rturn(0);rk; s 1: rturn(1);rk; ult: rturn(fi(i-1)+fi(i-2)); int Fi(int i) swit(i) s 0: rturn(0);rk; s 1: rturn(1);rk; ult: rturn(fi(i-1)+fi(i-2)); Fi(3) Fi(2)+Fi(1) (Fi(1)+Fi(0))+1 (1+0)+1 同じ変数名であっても 関数呼び出しの度に 別の記憶領域が確保される ( スタックを利用している ) 変数の内容は 他の関数呼び出しによって破壊されることはない Avn-1Fioni 数を再帰呼び出しで求めるプログラム #inlu <stio.> int i(int x) swit(x) s 0: rturn 0; rk; s 1: rturn 1; rk; ult: rturn i(x-1)+i(x-2); 実行例 : %./i 15 Fi 15 = 610 int min(int r, r *rv[]) int x; wil(--r) x=toi(*++rv); print("fi % = % n",x,i(x)); rturn 0; 4
Avn-2 環状連鎖リストを使った電光掲示板風表示ログラム #inlu <stio.> #inlu <strin.> #inlu <unist.> //Sl rrntil strutur typ inition typ strut no r ; strut no *nxt; NODE; 実行例 : %./link1 Tis is pn 与えた文字列が横スクロールする NODE *AlloNos(int num) //Mmory llotion NODE *rt; int i; rt=(node *)mllo(sizo(node) *num ); or (i=0; i<num; i++) i (i<num-1) (rt+i)->nxt = (rt+i+1); ls (rt+i)->nxt = rt;//o n n t til to rturn rt; voi StCr(NODE *p, r *r) wil(*r) p->=*r; p=p->nxt; r++; PrintNo(NODE *p,int n) wil(n--) print("%",p->); p=p->nxt; lus(stout); Avn-2 続き int min(int r, r *rv[]) int ln; r lin[300]; NODE *s; lin[0]=(r)null; wil(--r)//ontint rs strt(lin,*++rv); strt(lin," "); ln=strln(lin);//strin lnt s=(node *)AlloNos(ln); StCr(s,lin); wil(1) //Enlss Loop PrintNo(s,ln); putr (' r'); //Crri rturn s=s->nxt; uslp(8); #inlu <stio.> #inlu <stli.> //# in QUEUE // キュー #in STACK // スタック #in SIZ 10 Avn -2 STACK/QUEUE /* * * * * * * * * キューの定義 **************/ #i QUEUE #in A(Q,x) n_quu(&q,x) #in Gt_An_Dlt(Q) _quu(&q) #in Not_Empty(Q) Q.QF!=Q.QR #in Init(Q) Q.QF=Q.QR=0 #in Stk_or_Quu quu #in QUEUE_SIZ SI // キューのサイズ strut Quu int Bu[QUEUE_ SIZ]; int QF; int QR; ; ty p stru t Qu u q u u ; /* QUEUE 用 */ voi n_quu(); voi n_quu(quu * Q, int v) Q->QR = (Q->QR+1)%QUEUE_SIZ; i (Q->QR == Q->QF) print(strr,"quu Ovrlow n"); xit(1); ls Q->Bu[Q->QR] = v; _quu(quu * Q) i (Q->QR == Q->QF) print(strr,"quu Unrlow n"); xit(1); ls Q->QF = (Q->QF+1)%QUEUE_SIZ; rturn Q->Bu[Q->QF]; #ni /* * * * * * * * キューの定義終わり *************/ /* * * * * * ** スタックの定義 *****************/ #i STACK #in A(S,x) pus(&s,x) #in Gt_An_Dlt(S) pop(&s) #in Not_Empty(S) S.SP>0 #in Init(S) S.SP=0 #in Stk_or_Quu stk #in STACK_SIZ SIZ // スタックのサイズ strut Stk in t Bu [STACK_ SIZ]; in t SP; ; typ strut Stk stk ; voi pus(stk* S,int ) i (S->SP<STACK_SIZ-1) S->Bu[S->SP++]=; ls print(strr,"stk ovrlow. n"); xit(1); pop(stk* S) i (S->SP > 0) rturn S->Bu[--(S->SP)]; ls print(strr,"stk unrlow. n"); xit(1); #ni /* * * * * * * スタックの定義終わり ***********/ Avn -2 続き min() int i,; Stk_or_Quu X; Init(X); or (i=0; i< SIZ-1; i++) =(int)('a'+i); A(X,);putr(); putr(' n'); wil(not_empty(x)) putr(gt_an_dlt(x)); putr(' n'); 実行例 : % stk-quu ABCDEFGHI IHGFEDCBA 5