Comments
Description
Transcript
スタックのノードの宣言
今日の内容 アルゴリズムとデータ構造 スタック 第3回講義:スタックとキュー キュー Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 1 スタックは特殊の連結リスト Push-down stackとも言う アクセス制限 削除と挿入は先頭でやる 挿入:push, push-down 削除:pop, pop-up Last-in-first-out (LIFO) memory 抽象データの考え方 2 スタックのノードの宣言 制限を導入するメリット: 操作は簡単、実現も簡単 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) キューの定義 キューの操作 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) スタックとはなに? スタックの定義 スタックの挿入:push スタックの削除:pop スタックの応用:逆ポーランド記法 struct node{ int key; struct node * next; }; 3 typedef struct node* StackPointer; struct node{ ItemType item; StackPointer next; }; 左は教科書31ページにある 右は一般的宣言 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 4 1 Pushのソースコード スタックのC言語による表現 定義: リストと同様,先頭と末尾は、 二つのダミーノードheadとzで 定義する. 最初にリストは空なので, headの次はzとなる. zの次は自分です. void push(int v){ struct node* head,* z; 初期化: stackinitialize(){ head malloc(sizeof * head); next item head z head- next x; head- next z; z- next z; next x malloc(sizeof * x); x- key v; x- next head- next; z malloc(sizeof * z); item struct node* x; } } まず新しいノードxのメモ リを確保する. xのitem領域に与えられ たデータを入れる. headのnextをxのnextに 入れる. headのnextにxのアドレ スを入れる. (p.31) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 5 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 6 popのソースコード スタックの挿入:push int pop(){ X int key; A L I S struct node* x; T head z x head- next; head- next x- next; key x- key; X A L I S head z return key; } Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) free(x); T 削除するノードをxに入れる headのnextにxのnextを入れる 取得したいデータをkeyに代入 xのメモリを開放する Keyを返す 7 (p.31) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 8 2 スタックの削除:pop スタックの応用例(1) A L I S T head z L I S T head z スタックを利用して算術式を計算する 5*(((9+8)*(4*6))+7) 考え方:中間結果をスタックに保存する push(5); push(pop()* pop()); push(9); push(8); push(7); push(pop() pop()); push(pop() pop()); push(pop()* pop()); push(4); push(6); printf("%d \ n", pop()); push(pop()* pop()); Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 9 逆ポーランド記法 10 逆ポーランド記法の特徴 算術式の計算では、演算子に出会った時に、被演算子 がスタックにのっているようにしておく必要がある。 算術式もこのように書き換えることができる すなわち、 5*(((9+8)*(4*6))+7) は、 598+46**7+* になる この書き方は、逆ポーランド記法(reverse Polish notation),或は後置記法(post-fix)という。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 11 逆ポーランド記法は日本語に似ている。 例えば、1 + 2 を逆ポーランド記法で表すと 、1 2 + に なる。 これは日本語で「1 と 2 を足す(+)」 と書いたときの語 順と同じである。 逆ポーランド記法にすると括弧が不要となる。 人間には読みにくいが、コンピュータが処理をする場合 にはとても都合が良い。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 12 3 スタックの応用例 (2) スタックを用いて普 通の算術式を逆 ポーランド記法に書 きなおせる。 右のプルグラムは, 完全に括弧をつけ た算術式を逆ポー ランド記法に変換 するものです。 キュー (queue) char c; for(stackinit(); scanf("%1s" ,&c)! EOF; ){ if(c ' )' ) printf(%1c" , (char)pop()); キューも特殊なリスト 2つ基本的な操作 if(c ' ' ) push(int(c)); if(c '*' ) push(int(c)); while(c '0'& & c '9' ) { printf("%1c", c); scanf("%1c" ,&c); } if(c ' (' ) continue; } (p. 32) printf("\n" ) FIFO (first-in-first-out) メモリ 2つのポインタが必要 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 13 headとtail あるいは frontとrear Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 配列による表現 #define MAX 100 int queue[MAX+1], head, tail; void queueInit() { head =0; tail = 0; } void enqueue(int v) { queue[tail++] = v; if (tail > MAX) tail =0; } int dequeue() { int t = queue[head++]; if (head > MAX) head = 0; return t; } int QueueEmpty() { return head == tail; } enqueue: キューの末尾 に挿入すること dequeue: キューの先頭 を削除すること 14 抽象データ型 基本的な考え方 典型的な例: データ構造が行うことをその実現法から切り離す。 スタックとキュー 線形リスト (p.35) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 15 たいていのプログラムでは、きちんと定義された基本操作だ けを利用して、リンクや添字などの実現法の詳細に関知しな い。 配列や連結リストは、「線形リスト」という抽象データ型を詳細 化したものとみなすことができる。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 16 4 抽象データ型の特徴と利点 クイズ 目的:大きいプログラムの開発用の道具にする。 特徴:データ構造とそのアルゴリズムの定義を与える内部のものに、 外部から参照できない。 ただし、内部で定義された操作は、関数または手続きを通しての み、外部から参照することが許される。 利点: (いくらでも複雑になりうる)データ構造とアルゴリズムと、(いくら でも多くなりうる)それを利用するプログラムとの間のインター フェースの複雑さを相対的に限定することができる。 こうして、大きいプログラムが相対的に理解しやすくなり、基本ア ルゴリズムの変更や改良が行いやすくなる。 (1)以下の式を逆ポーランド記法で表しなさい。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 17 (1)の説明 1. 2. 3. 4. 1+2*3 (1+2)*3 (1+2)*(3+4) 1+(2+3)*4+5 (2) (1) の 4 で逆ポーランド記法で表したものを、 スタックを使って計算しなさい。ただし、計算過 程でのスタックの状態も書くこと。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 18 (2) では、下の図を参考にして書いてみてください (1) は逆ポーランド記法(アルゴリズムC 第1巻 p.31)に変換する問題です。 逆ポーランド記法は他にも「後置記法」「RPN (Reverse Polish Notation)」「IPN (Inverse Polish Notation)」などと呼ばれます。 逆ポーランド記法は日本語表記と似ています。例え ば、1 + 2 を逆ポーランド記法で表すと 1 2 + にな ります。これは日本語で「1 と 2 を足す(+)」 と書い たときの語順と同じです。 逆ポーランド記法にすると括弧が不要になります。 人間様には読みにくいかもしれませんが、コン ピュータが処理をする場合にはとても都合が良い表 記方法です。 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 19 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 20 5