データ構造とアルゴリズム 第6回 キュー ~ データ構造(2)~.

Slides:



Advertisements
Similar presentations
1 データ構造とアルゴリズム 第 3 回 配列,構造体,ポインタ ~ データ構造について学ぶための基礎~
Advertisements

アルゴリズムとデータ構造 第2回 線形リスト(復習).
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
5.データ構造入門 5-1.連結リスト(Linked List) 5-2.スタック(Stack) 5-3.キュー(Queue)
情報基礎演習B 後半第5回 担当 岩村 TA 谷本君.
数理情報工学演習第一C プログラミング演習 (第3回 ) 2014/04/21
データ構造とアルゴリズム 第10回 mallocとfree
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
基本情報技術概論(第4回) 埼玉大学 理工学研究科 堀山 貴史
Ibaraki Univ. Dept of Electrical & Electronic Eng.
情報工学概論 (アルゴリズムとデータ構造)
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 第3回基本的なデータ構造(リスト) 2015/10/28 アルゴリズムとデータ構造 2015.
第8回 プログラミングⅡ 第8回
プログラミング演習II 2004年12月 21日(第8回) 理学部数学科・木村巌.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
プログラミング論 II 電卓,逆ポーランド記法電卓
データ構造とアルゴリズム 第13回 スタックとキュー
データ構造とアルゴリズム 第5回 スタック ~ データ構造(2)~.
Stack & Queue & List 3.
アルゴリズムと データ構造 第4回 スタック・キュー.
アルゴリズムとデータ構造 第2回 線形リスト(復習その2).
アルゴリズムとデータ構造 第4回 配列によるスタックとキュー.
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
INSERT(x,p,L)の例 (一部) 磯 直行 2009年5月5日
第3回 配列,構造体,ポインタ ~ データ構造について学ぶための基礎~
構造体 構造体, 構造体とポインタの組み合わせ,.
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
データ構造とアルゴリズム 第5回 スタック ~ データ構造(2)~.
精密工学科プログラミング基礎 第10回資料 (12/18実施)
プログラミング 4 記憶の割り付け.
データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和.
アルゴリズムとデータ構造 補足資料11-1 「mallocとfree」
2005年度 データ構造とアルゴリズム 第3回 「C言語の復習:再帰的データ構造」
第7回 プログラミングⅡ 第7回
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
P n ポインタの基礎 5 q m 5 7 int* p; int 型の変数を指すポインタ int* q; int 型の変数を指すポインタ int n=5, m=7; int 型の変数 int array[3]; int* pArray[3]; p = &n; ポインタにアドレスを代入しているのでOK.
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月5日
プログラミング 3 スタックとキュー.
明星大学 情報学科 2012年度 後期   情報技術Ⅱ   第8回
アルゴリズムとデータ構造 2011年7月8日課題の復習
簡易データベース 情報画像工学実験 I : 実験2 担当:関屋大雄(工学部1号棟515室)
スタックとキュー データ構造とプログラミング (第5回).
基本情報技術概論I (第4回) 埼玉大学 理工学研究科 堀山 貴史
精密工学科プログラミング基礎Ⅱ 第5回資料 今回の授業で習得してほしいこと: 構造体 (教科書 91 ページ)
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
15.1 文字列処理の基本 15.2 文字列処理用ライブラリ関数
データ構造とアルゴリズム 第11回 リスト構造(1)
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
アルゴリズムとプログラミング (Algorithms and Programming)
第9回 優先度つき待ち行列,ヒープ,二分探索木
情報基礎演習B 後半第2回 担当 岩村 TA 谷本君.
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
第11回放送授業.
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 補足資料11-3 「線形リストのオペレータ」
ネットワーク・プログラミング Cプログラミングの基礎.
プログラミング論 構造体
アルゴリズムとデータ構造 2010年6月17日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
データ構造と アルゴリズムI 第三回 知能情報学部 新田直也.
プログラミング演習II 2004年11月 16日(第5回) 理学部数学科・木村巌.
プログラミング演習II 2003年12月10日(第7回) 木村巌.
プログラミング入門2 第5回 配列 変数宣言、初期化について
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
Presentation transcript:

データ構造とアルゴリズム 第6回 キュー ~ データ構造(2)~

スタック ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。 スタック ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。 ・ティッシュを間違って2枚取り出したとき使わなかった1枚は再び突っ込みます。次に使うときにはそれを使うのでスタックでしょうか。 ・小学校でよく使う上から入れてどんどんためていくファイル。 ・メジャー。 多数編 ・箪笥の服 ・レポートの提出 ・銃(ハンドガン)のマガジン ・食器 ・コピー機の紙

キュー ユニークな回答と多かった回答 ユニーク編 ・学校:基本的に先に入った人から出ていく(卒業していく) ・観覧車 キュー ユニークな回答と多かった回答 ユニーク編 ・学校:基本的に先に入った人から出ていく(卒業していく) ・観覧車 ・髪の毛:先に生えたところから切られるから ・「便通」←食べたものは下から出る(笑) 多数編 ・自動販売機 ・スーパー(コンビニを含む)商品の品だし ・シャープペンシル ・エスカレーター ・行列

キュー(待ち行列、Queue)

本日の内容:キュー キュー 抽象データ型としてのキュー 単方向リストによるキューの実現 循環配列(リングバッファ)によるキューの実現 英国では行列することをqueueingという。 The verb queue means to form a line, and to wait for services. Queue is also the name of this line.

待ち行列 レジ A君の レポート B君の レポート C君の レポート

キュー (Queue)   キュー:要素の挿入がいつも一方の端(   )からしかできず,要素の削除はその反対の端(    )からしかできないリスト 先に入れた要素ほど,先に出る 別名 先入れ先出しリスト        (first-in first-out) 先頭 ↓ 末尾 ↓ a1 a2 a3 a4

抽象データ型としてのキュー 抽象データ型: データ構造+操作 キュー 操作 要素の挿入 (            ) 要素を 並べたもの 要素の取出し (             )

キューの操作   CREATE(Q ) TOP(Q )

キューの操作 Enq (x, Q ):要素xをキューQの( )に入れる. Deq (Q ):キューの( )の要素を削除する キューの操作      Enq (x, Q ):要素xをキューQの(    )に入れる. Deq (Q ):キューの(    )の要素を削除する <同時にSの先頭の要素を返す場合もある>

例  末尾 ↓ 先頭 ↓ Q 初期状態 Enq(A, Q) Enq(B, Q) Enq(C, Q) Deq(Q) Enq(Deq(Q), Q)

例 Q 末尾 ↓ 先頭 ↓ 初期状態 Enq(A, Q) A Enq(B, Q) B A Enq(C, Q) C B A Deq(Q) C 例  末尾 ↓ 先頭 ↓ Q 初期状態 Enq(A, Q) A Enq(B, Q) B A Enq(C, Q) C B A Deq(Q) C B A Enq(Deq(Q), Q) B C

単方向リストによるキューの実現 Queue型 front rear a0 a1 an-1 構造体 struct queue型 rear->element front->element キューの末尾要素 rear->nextはNULL キューの先頭要素

キューの型定義とEnqueueのプログラム例(p38) /* セルを表わす構造体の定義 */ struct cell { int element; struct cell *next; }; … main() struct queue struct cell *front; struct cell *rear; } セルのデータ構造はリストのときと同じ。 ここではint型の要素としたが、どのような型でも良い。 先頭を指すfrontと末尾を指すrearの2つのポインタから成る構造体でキューを定義

Enqのプログラム例(p38) … Main() { struct queue Q; Q.front =Q.rear =NULL; } void enqueue(init x, struct queue *S) struct cell *p; p=(struct cell *)malloc(sizeof(struct cell)); if(S ->rear != NULL) S ->rear->next = p; S ->rear = p; if(S ->front == NULL) S ->front = p; S ->rear->element = x; S ->rear->next = NULL; return;

Enqの実現(単方向リスト版) S 初期状態 Q front rear front, rearともにNULL struct queue型の変数Q struct queue型を指すポインタ S 初期状態 front, rearともにNULL 関数enqueueにおいて、仮引数Sは、struct queue 型を指すポインタ Q front rear struct queue Q; Q.front =Q.rear =NULL; 教科書では、両方とも Qなので混乱する。 スライドでは、ポインタをSとしておく … void enqueue(init x, struct queue *S)

① p = (struct cell *)malloc(sizeof(struct cell)); Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] ①新しいセル用のメモリを確保し, S Q a0 a1 an-1 front rear p ① p = (struct cell *)malloc(sizeof(struct cell));

②if(S ->rear != NULL) S ->rear->next = p; Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] ① 新しいセル用のメモリを確保し, pはそのセルを指すポインタとする ② Sが指しているキューQが S ②if(S ->rear != NULL) S ->rear->next = p; Q a0 a1 an-1 front rear p

Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] S Q p ② Sが指しているキューQが空でなければ、 S->rear->nextが新しいセルを指す(pを代入) ③ S Q a0 a1 an-1 front rear ③ S ->rear = p; p

④ if(S ->front == NULL) S ->front = p; Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *Q)] ① 新しいセル用のメモリを確保し, pはそのセルを指すポインタとする ② Sが指しているキューQが空でなければ、 S->rear->nextが新しいセルを指す(pを代入) ③ S->rearが新しいセルを指す(pを代入) ④ Sが指しているキューQが空ならば、 S ④ if(S ->front == NULL) S ->front = p; S p Q Q front front rear rear

Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *Q)] S Q p … ④ Sが指しているキューQが空ならば、 S->frontが新しいセルを指す(pを代入) ⑤新しいセルに ⑥新しいセルは S Q a0 a1 an-1 front rear ⑤ S ->rear->element = x; ⑥ S ->rear->next = NULL; p

Deqのプログラム例(p38) void dequeue(struct queue *S) { struct cell *q; if(S->front == NULL) printf(“Error: Queue is empty. ¥n);exit(1); } else q = S->front; S->front = S->front->next; free(q); if(S->front == NULL) S->rear = NULL; return;

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S Q Sが指すQのfront がNULLならキューが空  ① エラーメッセージを表示して関数を終了 S ① if(S->front == NULL) { printf(“Error: Queue is empty. ¥n); exit(1); } Q front rear

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …  ② qにS->frontを代入する(= ) S q ② q = S->front; a0 a1 an-1 front Q rear

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …  ② qにS->frontを代入する(=前の先頭要素へのポインタをqに保持しておく)  ③ S->frontを S q a0 a1 an-1 front Q ③ S->front = S->front->next; rear

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …  ② qにS->frontを代入する(=前の先頭要素へのポインタをqに保持しておく)  ③ S->frontを前の先頭要素の次(=前の2番目)へのポインタとする ④ 削除するセルの領域を解放 S q ④ free(q); a0 a1 an-1 front rear Q

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] q S S Q Q (= S->front がNULLの場合は)  ⑤ キューQは空とする( ) ⑤ if(S->front == NULL) S->rear = NULL; q S S a0 front Q front Q rear rear

Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S S Q Q ・いずれの場合も先頭要素が削除される ・教科書p38のプログラムはvoid関数なので、戻り値はなし 元のキューQが要素1個だった場合 元のキューQが要素2個以上だった場合 S S a1 an-1 front front Q rear rear Q

配列によるキューの実現 element [0] [1] データがある部分 front p [p] a0 a1 rear k [k] an-1

先頭と末尾の要素の位置を格納するためのメンバー キューの型の定義 (配列版) #define N 7 struct QUEUE/* 構造体queueの定義 */ { int element[N]; int front; int rear; }; 先頭と末尾の要素の位置を格納するためのメンバー

配列によるキューの実現 element [0] Deq (キューの先頭の要素を返す場合もある) Enq [1] front p [p] a0 rear k [k] an-1 [k+1] [N-1]

Enq,Deqを繰り返すとどうなるか? N=7の場合 element ⇒これを防ぐ手法の一つが, [0] [1] [2] 3 front [3] A [4] B [5] C 6 rear [6] D

循環配列(Ring Buffer)  element[N-1] element[0] front rear a0 a1 an-1 …

循環配列(Ring Buffer) element element element [0] [0] [0] G 1 front 1 rear [1] A [1] [1] H [2] B [2] [2] 3 front [3] C [3] C [3] 4 rear [4] D [4] D [4] 5 front [5] [5] E [5] E 6 rear [6] [6] F [6] F

循環配列の問題点 このままでは,「 」と「 」の区別がつかない [0] rear an-1 front a0 a1 [N-1] このままでは,「             」と「            」の区別がつかない キューがFULLの状態   ⇒ 一見問題無いように思えるが… [0] rear an-1 front a0 a1 [N-1]

循環配列の問題点(続き) [0] an-1 [0] [1] [1] front rear rear front ここからDeqを行うとキューは空になる frontとrearの関係が, キューがFULLの時と同じ! [0] an-1 [0] [1] [1] front rear rear Deq front [N-1] [N-1]

解決方法 「キューがFULLの状態」と「キューが空の状態」をどう区別するか? 方法2: 待ち行列が配列いっぱいにならないようにする etc.

方法2: 待ち行列が配列いっぱいにならないようにする例 解決方法 方法2: 待ち行列が配列いっぱいにならないようにする例 (          ) (          ) [0] [0] rear rear an-1 front front a0 a1 [N-1] [N-1]