Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和.

Similar presentations


Presentation on theme: "データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和."— Presentation transcript:

1 データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和

2 第2章 基本的なデータ構造 2.1 配列 2.2 リンク配置 2.3 連結リスト 2.4 スタック 2.5 キュー 2.6 木構造

3 2.4スタック 線形構造の片方だけから追加(push)と取り出し (pop)が出来るデータ構造.(データ抽象化)
コンピュータの基本ソフトウエア(OS)や, ミドルウエア(コンパイラなどの言語処理系) で多用される.

4 2.4.1スタックの基本操作 線形構造の片方だけから追加(push)と取り出し (pop)が出来るデータ構造.
⇒Last In First Out (LIFO)とも呼ばれる

5 2.4.2スタックの実装 配列で表した場合: topは次にpushする場所.top>n-1で満杯の状態 を表している.

6 2.4.2スタックの実装 pushとpop

7 twada$ ./a.out akasakA twada$
C プログラムの例 #include <stdio.h> #include <stdlib.h> #define Num 10 char Stack[Num]; int top=0; void push(char c) { if (top>Num-1) { perror("Stack overflow\n"); exit(1); } Stack[top++]=c; char pop() if (top==0) { perror("Stack underflow\n"); return Stack[--top]; int main() {    char *str="Akasaka";    while(*str) { push(*str); str++;    }    while(top) printf("%c",pop());    printf("\n"); } twada$ ./a.out akasakA twada$

8 2.5キュー 配列の片方から追加(enqueue)し,反対側から 取り出し(dequeue)が出来るデータ構造.
プリンタのバッファなど速度緩衝用メモリや, 木やグラフな どの横型探索に 使われる.

9 2.5.1キューの基本操作 最初にenqueueしたデータが最初に取り出され るので,First In First Out (FIFO)とも呼ばれる.

10 2.5.2キューの実装 配列を用いた実装 rearは次にenqueueする場所,frontは次に dequeueする場所.

11 2.5.2キューの実装 rear>n-1でOverflow front==rearでUnderflow

12 twada$ ./a.out Akasaka twada$
C プログラムの例 #include <stdio.h> #include <stdlib.h> #define Num 10 char Queue[Num]; int front=0; int rear=0; void enqueue(char c) { if (rear>Num-1) { perror("Queue overflow\n"); exit(1); } Queue[rear++]=c; char dequeue() if (front==rear) { perror("Queue underflow\n"); return Queue[front++]; int main() {    char *str="Akasaka";    while(*str) { enqueue(*str); str++;    }    while(front!=rear) printf("%c",dequeue());    printf("\n"); } twada$ ./a.out Akasaka twada$

13 2.5.3リングバッファ(改良されたキュー) キューではenqueしてもdequeueしてもfrontも rearも増加する一方.
キューを環状ににしたのがリングバッファ

14 スタック/キューは何のために用いるか 系統的な記憶と想起のメカニズム スタック(LIFO) キュー(FIFO)
環境の保存と参照ー>再帰呼び出し 木・グラフの縦型探索 キュー(FIFO) バッファ(緩衝用)メモリ、装置間の速度差の吸収 木・グラフの横型探索

15 スタックの利用の例:1 迷路の探索:

16 探索木

17 迷路の探索アルゴリズム

18 list にスタックを用いた場合

19 木の縦型探索とスタック

20 再帰的構造 0, i=0 f(i)= 1, i=1 f(i-1)+f(i-2), i≧2 Fibonacci 数
int Fib(int i) { switch(i){ case 0: return(0);break; case 1: return(1);break; default: return(Fib(i-1)+Fib(i-2));} }

21 再帰的構造 Fib(3)→Fib(2)+Fib(1) →(Fib(1)+Fib(0))+1 →(1+0)+1 int Fib(int i)
{ switch(i){ case 0: return(0);break; case 1: return(1);break; default: return(Fib(i-1)+Fib(i-2));} } Fib(3)→Fib(2)+Fib(1) →(Fib(1)+Fib(0))+1 →(1+0)+1

22 再帰的構造 同じ変数名であっても、関数呼び出しの度に、別の記憶領域が確保される(スタックを利用している。) 変数の内容は、他の関数呼び出しによって破壊されることはない。

23 演習問題 設問3 5,4,8がこの順にpopされ,底から2,7,6 がスタックに残る.
設問4 5,2がこの順にdequeueされ,7,3が queueの中身(次にdequeueすると3が取り出さ れる.)

24 演習問題 設問5(レポートの提出) if ((front-rear+n)%n==1) rear=(rear+1)%n;
front=(front+1)%n;


Download ppt "データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和."

Similar presentations


Ads by Google