Download presentation
Presentation is loading. Please wait.
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;
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.