Lec06 資料結構 第四週課程

NYCU OCW
75粉絲
2 次觀看·2023年12月3日
Arrays (4/4);Stacks & Queues (1/2)
授課教師:資訊工程學系 彭文志老師
課程資訊:http://ocw.nctu.edu.tw/course_detail.php?bgid=9&gid=0&nid=412
授權條款:Creative Commons BY-NC-SA
更多課程歡迎瀏覽交大開放式課程網站:http://ocw.nctu.edu.tw/ 本課程同時收錄至國立交通大學機構典藏,詳情請見:
http://ir.nctu.edu.tw/handle/11536/108205
大家看一下 KMP 演算法裡面
其實用兩三句話就可以講完它的精神
這兩三句話包含什麼呢
就是大家看一下
其實 KMP 最主要的方法是說
我們在做字串比對的時候
當那個 pattern 如果發現它不 match
就是 P 和 string
就是 S 有一個叫 P
就是 pattern string
T 的話就是你的 source
那個 text 要比對的字串
那第一句話是什麼呢
就是 T 和 P 要去做比對的時候
當我們發現 P 和 T 的某一個字串
不能夠 match 的時候
我希望那個 P 的移動
P 讓它 shift
能夠 shift 多一點
不要每次一格這樣
它的精神就是這樣
KMP 就是它的精神這樣
那怎麼達到
怎麼達到這個精神
兩個
第一個方法 兩個步驟
第一個步驟是什麼
針對自己的 P
針對自己的 P 就 pattern
你也許會覺得很奇怪
老師 這個應該是要在 T 裡面去做 match
為什麼會是在 pattern 裡面
自己跟自己去做比較
然後產生 fill function 呢
因為它要做的目的是幹嘛
它要做的目的是說
它要去看這個 pattern string
看它自己的 pattern string
有哪一些是相同的
那這個動作就是在 phase 1 裡面去達成
phase 1 要注意一下說
它是針對自己的 pattern string
自己做 match
那這樣子的目的是要幹嘛
我要知道說我自己的 pattern string
有哪一些是 repeat
或是說相同的這個
sub string
它是第一個 phase 這樣
那有了第一個 phase 的結果以後呢
有了第一個 phase 的結果以後
你就會導致第二個 phase 這樣
透過這個第一個 phase 所產生的 fill function
那我可以讓它很快速的移動
那所以呢
針對這幾個 phase
第一個 phase
是這張投影片
或者是你們看教科書的時候
這張投影片要看得懂
因為這個就是告訴你說
phase 1 它的 output 就是一個 fill function
那 fill function 就是針對自己的 P
然後去找那個紅色的區塊
它的 pattern 在 S 這樣
然後還有哪一張投影片
你必須要看到
所有投影片你都必須要看到
這是第二個 phase
你可以在這邊上面寫第二個 phase
第二個 phase 就是說
如果當它發現它不 match 的時候
它所要比對
它的這個 pattern 要 shift
要 shift 多少個單位呢
就是要看這個紅色的那個地方
P Fj-1加 1 這樣
就是當它發現不 match 了
你就往前
從那個 pattern 喔
要去看那個 pattern string
它的往前那個 bit
就是 Fj-1 這個 bit 這樣
然後透過 phase 1
你看到 Fj-1 往前看
多少的長度
會跟 pattern 前面那個
前面那個長度是一樣的
那這樣你才知道說
它下一次要移到了
移到哪裡
移到它的
它就會從這個 i 和
這個地方
這個 bit
去做比較
那這個 bit 的位置在哪裡
P Fj-1加 1
這是第二個 phase 這樣
所以第一個 phase 和第二個 phase 中間
KMP 演算法
KMP 精神就是這樣
就不要一次 shift 一格
要 shift 多格一點
怎麼達成兩個 phase 這樣
第一個
照 pattern 方
照 fail function 出來
自己跟自己比
在 pattern 和 pattern string 裡面
去照 fail function
第二個 phase
告訴你怎麼移動
透過 fail function 去做移動
所以呢
這就是 KMP
主要的演算法
那接下來
如果沒有問題的話
我們就直接進入到 stack 和 queue
那在講 stack 和 queue 之前
就是大家看一下 template
什麼叫 template
template 就是會告訴你
有一些的 data type
我把它加入做
某一個 template 的 type
當我這個 template type
變成 integer 或 flow
它都可以適用
它對方法本身
不會有太大的影響
這就叫 template
就是在 C++ 裡面的 template
那大家看一下
這個 template class key type
這地方就有一個 data type 叫 key type
但這 key type 是什麼
看你最後
你在 initial 那個 class 的時候
你宣告它是什麼樣子的 type
所以大家看一下
這有一個 mode
sort
key type 是這個
a pointer
int n
接下來大家看到
裡面所做的事情
就是在做一個
蠻簡單的 sort
注意一下紅色的
紅色就好了
它有沒有告訴你
key type 是 integer 還是 flow
都沒有
那這個事情什麼時候會決定
在下面
這個是真的程式在 run 的時候
比方說 flow
f array
它告訴你說
這 f array
它是 floating 的
menu 是 float
這個 type
那在下第二行
它告訴你是 int array
其實這個 array 是 200
這個大小空間
它的 data type 是 integer
所以不管是
上面 flow 還是 integer
那它都可以套到
上面這個 class
template 上
它不會受到
這個 data type 的影響
因為反正你都是把它統稱
general
就是要 general 的話
這些都叫做 key type
所以這個你會看到
我們的教科書
到後面幾個章節
它的資料型態
把它叫做 key type
它就用 template 來代表它
知道這個以後
接下來我們就看 stack
stack 的話
它是一個 data structure
那這個 data structure
它會符合一個原則
我相信基幹應該都有講
就是 less than or equal to
less than or equal to
就是最後進去
第一個被蹦出來
stack 的話
其實在這張圖
你可以看到
這個 stack 裡面
它應該都會有一個指標
這個指標
這個 pointer 叫 top
那比方說我現在
input 這個字進來
這個字母進來
比方說第一個 input 是 a
其實大家看到
它就 input a 進來
然後接下來
input 是 b 進來
那 top 呢
top 這個 pointer
它永遠指到的是
這個 stack 裡面的
最上面的一個 element
那現在 input 是 c 進來
top 就往前伸
然後 d 進來
又往前伸
e 進來
那接下來呢
在這個 stack 裡面
要取東西
把東西撈出來
就是 pop out
那它 pop out 的話
就是 top 所指的那個元素
比方說這個 top
所指的元素是 e
所以我要從這個 stack 裡面
撈出一個元素出來
這個動作叫 pop
那 e 就會被我撈出來
e 撈出來以後
記得 top 要減
top 要指到下一個 element
所以大家可以看到
e 這個元素
e 這個元素是最後
跟 abcd 比的話
它是最後的 element
被丟進去這個 stack
可是它在取出來的時候
是第一個被取出來的
所以這個是符合
less than first order data structure
那基幹應該都有講
就是說這個 stack 有什麼用
這個用處可能很多
等一下我們還會有
後面還會有一個程式
告訴你說
這個 stack 還可以去做到
迷宮老鼠的程式
有沒有聽過一些比賽
就給你一個迷宮
做一個機器人
就丟進去
迷宮總是有入口和出口
上面就有布設了很多障礙
你要讓電腦鼠或機器人
try an error
最後走到出口那個地方
這個就是會用到 stack 的技術
去設計一個 program
後面會講
那在你的基幹裡面
可能會講說
有一個 function call
比方說 a 這個 procedure
他要 call b 這個 procedure
那這個時候呢
他會做什麼事
他會把 a 這個 procedure
所用到的一些東西
不管是 point
local 的 variable
都把它存起來
所以這地方是
假設你想想看
就是有一個程式
a 這個 procedure
就叫做 main 好了
main 就是主要的程式
那這 main 呢
呼叫了一個 function call
叫做 a1 好了
接下來他就會把
跟 a1 有關的程式
local 變數
return address
他用到的 point 都儲存下來
那這個是一個 stack 的應用
這只是講說他很重要
那接下來大家看一下
就是說 stack 裡面的 ADT
就是 abstract data type
你看這個 stack 的話
他就會跟你講說
stack 他是什麼
他是一個 order 的 list
而且是有限的
有限
是 a finite order list
with zero or more elements
那 finite 是什麼
有限嘛
所以他告訴你什麼
stack 有 stack 的容量
就 stack size
其實 stack 假設無限
就是 infinite 的話
好像不大可能
所以我為什麼說
有時候同學讀 ADT 的時候
這些英文其實都有他
他不是亂寫的
他告訴你說
你看他定義這個 stack
他是一個 object
而且他是有限的集合
那有限集合
就會告訴你說
stack 是有限制
他大小是有限制
所以這件事情也會反映在
你看他的 constructor 上
public stack 他可以描述說
maximum stack size 等於 default size
就是這個 stack
他最多可以容納的 size
就是 maximum stack size
他等於 default
接下來你看
他還有一些 function
是跟 stack 有關
包含了他去問你說
這個 stack 是不是負
因為他既然是有限的
總是可能會滿
就是 stack 都被佔滿了
那我們就會有一個 boolean function
去問你說
這個 stack 是不是負
那同樣的
你也可以對這個 stack
去做加元素進來
加元素進來就好像是 push
就是把一個元素丟進來
那你要丟進一個元素的話
丟進來一個元素的話
你要告訴我是
他丟進來的這個 item
丟進來的元素
他的 item 是什麼
他 key type 是什麼
那 key type 是寫成 template
就是大家看一下
所以第一行
他寫 template class key type
所以不管是 flow 或 integer
他都能夠同時
那接下來看 boolean
其實 is empty 這樣
就是說
他判斷這個 stack 是不是空的
對 空的
一個是滿
一個是滿 一個是空
那為什麼要空
假設你在 pop
就是把 stack 裡面
一直抓東西出來的時候
你可能會去問說
這個 stack 是不是空的
空的話
再怎麼抓
你也是抓不出東西來的
所以 is empty
是要用判斷說
今天如果你要去抓
這個東西出來
你要去 check 說
這個是不是已經把所有的
這個 stack 裡面的東西
都丟出來了
所以要去判斷 empty 這樣
所以這件事情
就是抓出來一個東西的話
key type 就叫 delete
你可以把它講說是 pop
有不同的說法
add 等於小 push
delete 就是把它抓出來
叫 pop
不同的說法
那接下來就看一下
這個 stack
這個 data structure 怎麼 implement
那這個上面
中間看到的是
剛才我們的邏輯示意圖
這叫示意圖
其實邏輯上
看起來 data structure
stack 就長成
反正就是一個容器
你把它想就是一個容器
像堆積木一樣
但實際上它怎麼 implement
它可以用 array 來 implement 它
那 array 來 implement 它的話
大家看一下那 pointer
a0 就指到 array 0 的地方
a1 就指到 a1 的地方
那最高的地方就是 n-1
繼續用 array 來 implement 它
所以 array 它是一個 data structure
stack 也是一個 data structure
stack 可以透過 array 的方式
去 implement 它
那 stack 是不是隻能用 array
不見得
用另一個例子
所以要注意一下
就是說
這只是
這個 title 告訴你說
stack 是一個很常用的 data structure
它可以用 array 來 implement 它
但並不代表
array 是唯一 implement stack 的方式
好
那大家再看一下
就更多比較細的
程式宣告
比方說
constructor stack
maximum stack size
那個
如果有兩個冒號
這個叫做
一個 class
然後有兩個冒號
這邊看到沒有
就是有一個
這兩個冒號 stack
你會知道說
它是一個 member function
那如果一個冒號呢
是什麼
是不是有一個冒號
有沒有人知道
對
其他人知道嗎
有教嗎
金與太老師
應該有教吧
就是一個 class
然後兩個冒號
然後後面就是一個 function
就是 member function
那如果你看到一個冒號
這一個冒號
就代表說
它在初始化
這個 max size
對
就是 maximum stack size
就等於 max size
對
就是類似這樣
那所以呢
大家再看一下
在裡面呢
它就去宣告
new
一個 array 出來
key type
key type 就是
反正就是一個 template
那最多的 size
就是 array
就是開這麼大
那 top 一開始的時候呢
對
等於負一
因為一開始都沒有資料進來
所以
top 是負一
那它也是
透過這個 top 是負一
來判斷說
它是不是 empty
就是大家
跳到最後那個 member function
來看
it's empty
那也是
你看
如果 top 等於負一的時候
就 return true
就代表說它是 empty
所以
top 初始完畢
因為沒有任何資料進來
所以 top 值是負一
那中間這個地方就是負
就是檢查說
它是不是滿了
這個情況會自己看
那接下來我們來看
如果要加一個資料進來呢
加一個資料進來的話
這個資料叫 as
那首先
你要加資料進來的話
先去判斷
if 它是不是負
它是不是負
那負怎麼判斷
前面這裡已經有一個
member function 告訴你說
去判斷它的 top
是不是等於
x size 減一
那如果是等於
就是負
那如果沒有
如果它沒有負呢
你就可以到
這個 else 這個地方
那 else 這個地方
做什麼事
大家看一下
step 加加 top
你想想看
假設我們一開始的時候
top 是負一
那如果我們丟了一個資料進來
叫 a 好了
就剛剛以那個 a 來看
那負一
加加負一就是零
那就是 step 零的地方
就放 a
step 零的地方
就是放 a
那這個時候
它的 top
如果你有資料進來
我就會把 top 先去做
加一的動作
然後就把資料塞進來
就是 add 這樣
它 delete 同樣
就是
首先要去判斷
它是不是 empty
如果是 empty 的話
就要 output 一個 empty 訊息
那如果不是 empty 呢
就是 step
然後 top 減一減
top 先回報
top 的所指的那一個
地方的 element
回報出來
return 回去
return 回去以後呢
再把 top 減一
top 減一減
這應該看得懂吧
所以以此類推
這個 stack 就很簡單
就這樣介紹
那接下來看 q
q 的話呢
它跟 stack 有什麼差別
q 的話有一個
叫 first in first out
first in 就是第一個來的
就會出去
它有這樣子的一個特性
那大家也是看一下
這個老師好像都一樣
stack 看
這個 q 好像都一樣
看起來就像一個容器
可是 q 呢
就是有兩個
為了要達到
first in first out
在這個一個特性
它會有兩個變數
一個叫 first
一個是 real
first 就是指到說
第一個人是誰
那 real 的話
就是指向它的尾巴
一些字出來
它的尾巴是什麼
所以有 front 和 real
那大家看一下
跟剛才那例子一樣
就一直不斷地
加元素進來
假設我加了 a b c d
front 就指向 a
real 就指向 d
今天如果我們要從 q 裡面
抓一個資料出來的話
抓一個資料出來
第一個進去的人
就會被我們抓出來
就是 front
front 所指的那個元素
以這個例子來看是 a
它就會被我 output 出來
所以這個時候
front 就會指向 b
你可以看到
這個人數就變少了
那 q 最常的應用是什麼
這 q 非常符合現實的狀況
大家都有去過郵局吧
郵局如果排隊
或是你去買可麗餅
假設大家都要排隊
那就是 q
先來的就是先走
先來的就是先 serve
先 serve 完先走
這有沒有問題
沒有問題
這就是 q
那 job schedule 的話
就是 q 裡面
也常會去做 job schedule
job schedule 是什麼呢
就是這個 schedule
因為從來都還沒學過 OS
那你自己想想看
在 CPU
或是 disk
或是一些 IO 的裝置
假設以 CPU 為例
你的電腦通常都會同時間
執行很多的 job
比方說有 J1 J2 J3
這個 job 進來
那這個時候
最笨的方法
CPU 要去 serve 這幾個 job
最笨的方法是什麼
誰先進來
誰先在這個系統被執行
那他就先做
這個叫做 job schedule
的應用
就可以用 q
那所以呢
大家可以
這個例子就是
大家可能用 Win 7
你 run 好多的程式
那程式總是有
執行的順序
你先執行這個
先執行 Word
先執行 PowerPoint
先執行 PDF
那根據你執行的時間
就是決定這個 job
進來 q 的時間
那 CPU 有一個
schedule 的方法是什麼
誰先進來
誰就先做
那這個就是符合 q 的性質
這個叫
符合 first in first out
那我們可以再
再多講一點
就是 q
老師你覺得
OS 裡面 first in first out 好嗎
對
first in first out 好嗎
不見得
對
比方說
你去買可麗餅
三個人
前面
可惡的傢伙
他竟然
買了五十個可麗餅
對
你後面那兩三個人怎麼辦
頂那個
可能站了一個小時
都可能等不到
那所以呢
為了要打破這個 rule 怎麼辦
對
有沒有可能
做一些 priority
那這個呢
就引發了
就是所謂的
你未來會看到一個叫做
priority queue
就是 priority queue 的意思是什麼
就是
反正有這些
這些元件都在裡面
可是呢
我會根據這些元件
我們所設定的 priority
來決定說
誰先出來
那比方說
你剛才那個可麗餅的例子
那個第一個同學
這樣
對
他
反正他
他下一節
可能沒課這樣
他有的是時間可以等
那後面那兩三個同學可能
十分鐘以後
就是要去上第三節課這樣
所以
那有沒有可能
我們就先讓後面的同學
先去 serve
那 priority 就是定成什麼
定成說
你每一個同學
上課的時間
當作是一個 priority
距離
現在時間越近的
你 priority 越高
我去先 serve 你這樣
對
那這就是
後來你會看到
所謂的 priority queue
所以 queue 其實是一個
很簡單
你會覺得
超簡單的
這個 stack 也是超簡單
可是它用起來的話
是有很多變化這樣
那 queue
我們剛才講了
這個 first in first out
是其中一個
最簡單的
priority queue 後面會講這樣
好
那
大家看一下就 ADT 齁
ADT 跟
這個 stack 是很像的這樣
對
那
對
就你剛纔看到
這個 queue 和 stack
不是就好像一個容器嗎
它差別是在
差別在哪裡
差別在 queue 裡面
有兩個變數這樣
就是 from 和 real 這樣
好
那上面裡面的
memory function 呢
都很像啊
你看
對
就是判斷說
這 queue 是不是滿了
然後判斷說
這 queue 是不是 empty
然後你可以對這 queue
加一個元素
減一個元素這樣
好
所以 stack 和 queue
其實很像
差別就是說
多了一個 queue
多了一個
perimeter 這樣
就是來控制它
是在 queue 的
前面還是後面這樣
那
這些
很簡單的
function 的話
請同學
回去
自己看一下
頂多是在
參數上面
做一些調教這樣
