DA02

Size: px

Start display at page:

Download "DA02"

あゆみあると
5 years ago
Views:

1 線形構造データ構造とアルゴリズム ( 第 2 回 ) ー線形構造ー用語 : レコード : ひとまとまりのデータ ( 構造体 ) 線形リスト :n 0 個のレコードの 1 次元並び順配置 : 表リンク配置 : 連鎖リスト順配置された線形リスト : 表要素の位置の順序関係をアドレスの値の順序関係で表現する方法表に対する操作 : 要素の挿入削除表に対する操作 : アクセスリンク配置された線形リスト : 連鎖リスト N 番目の要素 N=5 N 番目の要素のアドレス = 先頭番地 +(N-1) 要素サイズ実際記法 100 null

2 連鎖リストに対する操作 : 要素の挿入削除連鎖リストに対する操作 : 要素の挿入削除連鎖リストに対する操作 : アクセス N 番目の要素 N-1 回リンクを辿る連鎖リストの変種 N=5 の表現法 ( ) = 線形リスト = 順配置 ( 表 ) アクセスが速い追加削除などの変更に弱いリンク配置 ( 連鎖リスト ) アクセスが遅い追加削除などの変更に適するスタックと待ち行列 : データ抽象化データ構造 + 操作手続き例 : スタック PUSH POP 待ち行列 Enquu Dquu 2

3 スタックの操作 ( 表を用いた場合 ) キューの操作 ( 表を用いた場合 ) スタック / キューは何のために用いるか系統的な記憶と想起のメカニズム l スタック (LIFO) l 環境の保存と参照ー > 再帰呼び出し l 木グラフの縦型探索 l キュー (FIFO) l バッファ ( 緩衝用 ) メモリ装置間の速度差の吸収 l 木グラフの横型探索迷路の探索 : スタックの利用の例 :1 探索木迷路の探索アルゴリズム 3

4 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

5 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

計算機ソフトウエア

計算機ソフトウエアデータ構造とプログラミング技法 ( 第 2 回 ) ー線形構造ー線形構造用語 : レコード : ひとまとまりのデータ ( 構造体 ) 線形リスト :n 0 個のレコードの1 次元並び順配置 : 表リンク配置 : 連鎖リスト順配置された線形リスト : 表論理構造物理構造 a b c d f 要素の位置の順序関係をアドレスの値の順序関係で表現する方法 0000 0001 0002 0003