Lec11 資料結構 第七週課程

NYCU OCW
75粉絲
4 次觀看·2023年12月3日
Lists (4/4)
授課教師:資訊工程學系 彭文志老師
課程資訊: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
我們開始上課了
上禮拜二的時候
禮拜二的時候我們當然有講一下
Sparks Matrix
如果用 list node
用 list 來存的話
大概會長什麼樣子
在這地方的話
同學要注意一下
他的表示方法
是他的 class 的宣告
class 的宣告
稍微再複習一下
在這個 matrix 裡面
在 Sparks Matrix
如果用 list 來表示的話
他的 node
分成兩種類型
一個叫 head node 一個叫 entry node
那 head node 的話呢
head node 他的任務是要幹嘛
head node 他的任務呢
你可以把他想說
每一個 row 或每一個 column 的頭端
head node
他可能是一個 row
或一個 column 的頭端
一個 row 或一個 column 的頭端
所以大家看一下
在上面他有講 head node
這 head node
有一個欄位叫 head
告訴你說
他應該是一個 boolean 的變數
告訴你說他是不是 head node
他有 right 和 down
right 和 down
right 和 down 分別指的是什麼呢
right 的話是一個 pointer
他指向同一列的
同一個 row
down 的話指向同一行
同一個 column
所以 right 和 down
分別對應到的是
同一個行
或是一個列
他的 entry node
所構成的一個 pointer
那 next 呢
next 的話就是
head node 的 linked list
所以嚴格來說
他有三個 pointer
嚴格來說他有三個 pointer
right 和 down
分別指向 entry node
next 指向 head node
next 指向
下一個 head node
所以大家想想看
如果是 m by n 的 matrix 的話
m by n 的 matrix 的話
他的 head node 就是 maxima
的 m
head node 就是 maxima
head node 的個數
就是 maxima 的 m 和 m
大家看一下
你看
是 row 比較大
還是 column 比較大
那 row 比較大還是 column 比較大
就他
選最大的
那同樣的在 entry node 的話
大家看一下
這個資料
這個資料在 spider matrix 裡面
這個資料
他會記載
他屬於哪一個 row 哪一個 column
他在第幾個 row 第幾個 column
大家看一下
就是 entry node 的地方
有一個叫 row column value
這個跟 array 裡面
的那個表示方法
很像
他還是要記載的
他是在哪一個 row 在哪一個 column
他的值是多少
然後 right 和 down
他指向的是什麼
right 是指向
跟他同一個 row
的非0的元素
down 是指向
down 是指向跟他同一個 column
non-zero
non-zero 的 entry node
大家還看到
他的欄位還有一個叫 head
那這 head 要幹嘛
對
這地方的話
大家注意一下
這 head 要幹嘛
他其實在這張圖片
他已經鋪了一個路
有一個假設
假設什麼呢
我的 head node 和 entry node
他把他宣告成同一個 class
宣告成同一個 class
同一個 class 的 node
所以呢
他必須要有一個欄位
到底是 head node 還是 entry node
那接下來
大家可以看說
可是這兩個 node 的
某些欄位還是不一樣
有些欄位是一樣
down
head right
都有
那不一樣的地方在哪裡
entry node 裡面他有
row column 和 value
那 head node 裡面有 nest
所以這是不一樣的地方
那不一樣的地方在
如果你要把他宣告成同一個 class
有一種方法
用什麼方法
union
有一個變數
就是用
就叫 union
紅色這個字同樣注意一下
所以
這張 slide
其實還蠻重要的
那為什麼重要
因為他告訴你說
事作是什麼
都是一個 class 叫做 matrix node
都是叫做 matrix 的 node
那黑色的部分
你看 matrix node 裡面
會包含幾個
基本元件
不管是 head node 或是 entry node
他都會有 down right
那還有一個欄位叫 head
這叫共同的部分
就是黑色的部分
大家看一下
matrix node down right 和 head
那紅色的部分
就是不一樣的地方
其中有一個叫做
matrix node next
matrix node next 指的是什麼
假設這個 node 被宣告
他的 head 是 true 的話
那他這個 union 的部分
他就會選擇 matrix node
就是他的 next
就等同於
他是 head node
所以他的下面這個欄位
是必須要存在的
同樣的道理就是
假設他的 head
這個部分是 form
那他這個兩個欄位
會選一個 選哪一個呢
叫 triple
那這 triple 的定義是什麼呢
大家看一下
triple 裡面就是包含了
raw value 和 color
所以這還蠻有意思的
就是不見得要
每一個 node 去定義
他的 class
你可以讓你的程式再更精簡一點
看起來就是 class 的宣告
反正他都是 matrix node
雖然他的角色不一樣
但可以透過 union 這個紅色
去做一些區別
那為了要這個紅色的出現
所以你必須要有一個 head 的欄位
所以這張圖
要同樣知道
H0
黃色的 H0 H1 H2 H3
和左邊所看到的黃色
其實是同樣的 node
那只是為了表示
方便
我們用
copy effect 畫出來
感覺起來像是 matrix
感覺起來是一個 matrix
裡面大家看一下
這個 link
那個 entry node
會記載了
他的 raw color
還有他的 value
那也許你會說
那 head 的欄位
為了節省空間
就補畫出來
head 其實還有一個欄位
像這個黑色的部分就叫做 fold
這個欄位的
有一個欄位叫 head
就是叫 fold
這不必要
我們就用顏色來代表
黃色就是 head node
黑色就是 entry node
這有沒有問題
有沒有問題
那如果沒有問題的話
其實大家再看一下
像這個 matrix
可以看一下他的程式
就是他的
operator
其實他有
為他去做一個
動作
你看到這個符號
箭頭的符號
是為他量身定做的
你可以看一下課本
那你輸入的時候就用這個
這樣子一個表示方法就好
444021101221
-433-15
這是 matrix
如果你要從檔案裡面
把它讀出來
那你可以很簡單的
用這個 input 來
當作是輸入
詳細的話請同學再看一下
4.8.2、4.8.3
請同學回去複習一下
看 要看
那4.8.2呢
教科書上有
那為什麼這樣
4.8.2
不要影印
影印是
印整本是違法的
4.8.2、4.8.3在做什麼事呢
就是在 matrix node 裡面
你再想想看
他可能會去做乘法
或去做 transpose
就是去做 transpose
請同學再看一下
那接下來我們進入到
重點
double linked list
這個講完
linked list 就結束了
接下來我們來上
double linked list
同樣的
double linked list 在幹嘛
他是一個 linked list
那為什麼有個叫 double
上去的話就代表說
他比 linked list 還強
從哪個方面來看呢
是從他的 link 的部分
從他的 link
的數目的部分還強
等一下我們會看一下
double linked list
他除了
link 的 number of link
就比原來的 single linked list 還多
那多在哪裡呢
大家看一下
下面有一個示意圖
就是一個說明
double linked list 裡面
通常會有兩個 link 的欄位
一個欄位叫做
along link
那這個 link 是什麼呢
就是 left link 的 field
這是一個欄位
這個 pointer 專門指向
這個 node 的左邊
data field 就是存放資料
right link field 的話
就是 right link
他是一個欄位
指向他的右邊
有了左邊的 pointer
和右邊的 pointer
接下來大家看一下
宣告的話
不外乎就是
double linked list 的 node
都還蠻雷同的
不同的地方
只是在於說
double linked list 的 node
他有兩個 pointer
一個叫 along link
一個叫 right link
同樣的 double linked list 裡面
也會有他的頭端
指向他的第一個 node
接下來大家看一下
double linked list 會長什麼樣子呢
他同樣會有一個 hidden node
假設你允許他有 hidden node 的話
在這張圖裡面
這是一個 hidden node
這個地方
right link
就是他的右邊
hidden node 的 right link
他會指向
這個 linked list 的
第一個 node
你看一下紅色的地方
就是他的 right link
這個 node 的右邊
就是紅色的 link
指向他的第二個 node
所以這個 hidden
大家注意一下
他指向的是
這個 linked list 的
第一個 node
接下來那個第一個 node
紅色的
你就可以把它想作是
右邊指標
往右走所串接起來的
linked list
那 hidden node 的 left link
他指向的是什麼呢
這個 linked list 裡面
可以說是
最後那個 node
也可以說是
最右邊的那個 node
那為什麼呢
因為 left link
他所構成的 linked list
你看
這藍色指標
都是往左
往左所指的
那 hidden node 的 left link
指向的是
左邊指的 linked list
的第一個 element
所以在 hidden node 那個地方
可能要注意一下
他的 right link 和 left link
分別指向的是
看他的指標
如果 right link
right link 就是指向
往右邊指的 linked list
的第一個 element
紅色的第一個
左邊指的第一個 element
那其他的 node
我覺得都還好
因為你看
中間那個 node
他的紅色和藍色
他們的指標就很明顯
指向前後
前面那個 node 和後面那個 node
所以這個頭
head node 裡面
你要注意一下 left link 和 right link
他指向哪裡
每個 node 都會有雙向指標
分別指的是
左邊和右邊
那如果他是 empty
empty 的話他只有一個 head node
指向自己
自己指向自己
這有沒有問題
有沒有問題
那接下來
大家可以看一下
這個 node 如果要插進來
insert 進來
就變成一個環狀的
環狀的 linked list
可不可以
這是一個示意圖
因為現在只有一個 node
所以不管左邊或右邊的指標
不管左邊或右邊的指標
都是指向一個 node
那這個 node
這個 node 他的左邊或右邊
也只能夠
指向他的 head
所以
示意圖是會這樣
那接下來
我們再用幾張投影片
就會講完
這個 doubling list
他的 insert
和 delete
就結束了
那所以在 doubling list 裡面
怎麼 insert
同樣的
就是把圖畫出來
這個的話
是一個示意圖
這個是 node x
藍色
相對於藍色的 node
然後呢
我們要 insert 是這個 node p
那上面呢
城市的部分
比方說紅色 p
對應到的藍位
就是這個 node p
的 left link
那藍色那個 node
這個 node 你看看上面有個指標
x 的 right link 的 left link
有沒有看到一個叫
x 的 right link
這指的是什麼
你看我們特別把
x 的 right link
mark 成藍色的
就代表說 x 是這個 node
他的 right link
指的是這個 node
就藍色
那這個藍色 node 的 left link
就是指向
這邊
所以這個藍色呢
這個藍色 x 的 right link
代表的是我所看到的這個
這個藍色的 node
好
這是一個稍微說明一下
那現在就是我們要
把一個 p node p
把他 insert 到 node x 的後面
node p
要把他 insert 在
node x 的後面
那他會做什麼事
最後的結果會長什麼樣
最後的結果就是
把這個幹掉
你自己想想看
最後的結果
link list 其實就是把圖畫出來
接下來就是做 point assignment
你想想看
把這個 p 加入到這個 x
最後的結果你會看到什麼
當然是這個 node 指向這個 node
然後這個黑色的都不見了
最後的結果會長成這個 node
領到這邊來
領上去
然後這邊的這個 node 指向他
所以
圖
最後結果的示意圖
先想像一下
把他畫出來
那接下來呢
這個動作
牽涉到有四個 link
上面有標號
有四個 link
我必須要去做 point assignment
因為最後的結果就是要把這個幹掉
黑色幹掉
他指向他
這邊的這個 node 指向他
他指向他
這是最後的結果
為了要達到這樣
大家可以看一下第一個步驟
第一個步驟是什麼
node p
的 left link
就是這個
第一個 statement
然後第二個 statement 是什麼呢
這個
p 的 right link
指向
x 的 right link
p 的 right link 就是這部分
指向 x 的
right link
代表這個藍色的 node
他的記憶體
他的位置
那第二個步驟
那第三個步驟呢
大家再看一下
第三個步驟是要幹嘛
是要把那藍色的 left link
left link 的指標指向 node p
所以呢
你怎麼知道那藍色的 node 在哪裡
那藍色的 node 就是
x 的 right link
x 的 right link 就是那藍色的
他的左邊指標 left link
對 就是這一塊
指向 p 這樣
那第四步驟
對 第四步驟在做什麼事
就第四個指令這樣
其實 node x
自己本身他的 right link
會指向 node p 這樣
指向 node p
這樣就結束了這樣
對 然後
給同學一個問題
順序可不可以顛倒
這個地方順序可不可以顛倒
為什麼要先做 1
可不可以先做 2 再做 3
順序可不可以顛倒
對
旁邊這些註解一下
順序顛倒會怎麼樣
先回答一個問題
順序可不可以顛倒
你要回答老師這個問題
很明顯就是幹嘛
你就自己把 3 掉到 1
1 掉到 3 這樣
順序顛倒一下
你看結果會不會一樣
所以
請同學回去想想看
比較有趣的是
這個 link 的指標
他可以串接起來
x 的 right link
的 left link
第三個 statement
x 的 right link
的 left link
這沒問題
沒問題
大家老師問的是順序可不可以顛倒
那第二個問題
我可不可以寫一個 insert
要 insert 在
後面的第 k 個
假如我要 insert node x
那這個
我的 insert 現在做的是什麼
insert 在
那個 node 的後面
那如果
我這樣說 我要 insert 在
這個 node x 後面的
下下個
就第二個
直接就是他的下一位
那意思是什麼呢
就是
我們可以出一個題目
node x 在這邊
我要 insert 這個紅色
不會在這邊
是在這邊
代表意思是
這個紅色的距離
那個 node x
他有中間卡一個人
第一個位置
第二個位置才會是他
所以你可以寫一個
我們也可以想像一下
假如我要寫一個叫 insert k
就是要把
node p insert 在
node x 後面的第 k 個
那你怎麼做
這個也是
洩題之一
有機會
我沒有告訴你機率
那接下來我們看一下
delete
對
那這個 delete 是會
怎麼做
今天我們要把 x delete 掉
他原來長法是
原來是長這樣
這是一個
我們要 delete 的東西
我們要把他 delete 掉
那 delete 掉以後呢
後來的結果是什麼
我要把這個 delete 掉
後來的結果當然就是
這個紅色和綠色
他們的 pointer
要互相指到對方
綠色的這個
要指到紅色
紅色的這個要指到
綠色
所以
如果你知道這樣的話
簡不簡單做到
其實還滿簡單的
綠色的
這個欄位
指到
這個指到這個
我們只要加紅色
這個欄位進來
那大家看一下
要做到這樣的話你看第一個步驟
第一個步驟是什麼
x 的 left link
node x 的 left link
的 right link
你看第一行
node x 的
left link 指向這邊
他的 left link
指到紅色的 node
那紅色 node 的 right link
這個地方
要指到這個位置
那這個位置呢
綠色這個 node 的位置在哪裡
在 x 的
right link
因為
這就是 1
那同樣的就是
大家看一下
x 的 right link 的 left link
x 的
right link
的 left link 指向這個欄位
他指向哪裡
他指向紅色的
那紅色的資訊在哪裡
在哪裡會有
在 node x 的 left link 就有了
所以第二行
就是在講說
x 的 left link
要等於 x 的 right link 的 left link
所以這兩行
delete 其實滿簡單的
刪除一個東西
但你看這兩行
的最右邊
的 statement 其實就代表什麼
他的
right link 和 x link
所指的這個元素要給別人指
他的 right link
和 left link
所指到的那一個
node 的位置
要給別人指
要 assign 給別人
assign 給誰呢
assign 給那些紅色
還有綠色這兩個 node
他們所對應到的
right link 和 left link 的位置
就這樣 delete
這有沒有問題
有沒有問題
沒問題
那如果沒問題的話
我們
link list 就講到這邊
link list 就
講到這邊
那 link list 裡面
link list 就是
表示方法
同樣大家知道
他可能就是
透過 pointer 連結上來
有他的頭端
first 然後有他的 end
最近大家有沒有看到
很多應用 比方說多項式
那 double link list
大概就是長這樣
多了一個 link list 出來
那 double link list
有什麼好處
也許你會說
老師這個 double link list
這個 link 如果斷掉的話
還可以透過別的
這是一個好處
就是 link 如果斷掉的話
還可以還原回來
同學可以想想看
double link list 上
你如果要在上面找一個
找一個
找一個 element 的話
用 double link list 上
去實作 你會怎麼做
對
如果要找一個 element
你會怎麼做
假設你看 double link list 裡面
我們的 value
就是給他數字
然後接下來
你可以想想看
如果你要在 double link list 裡面
要找某一個數字 比方說數字 7
他有沒有出現在這個 double link list 裡面
你會怎麼做
對
如果沒條件的話
反正不管是從
左邊或右邊
反正就是一個一個檢查
那可不可以做得更好
可不可以做得更好
因為剛才講的是沒條件
可不可以做得更好
有沒有可能
我在 insert 的時候
可以讓這個 link list 排序過
從大到小
去做一個適當的排序
然後可能要再動一些手腳
然後就是
也許給你找一個數字
你會判斷
這個數字的大小
從左邊或右邊找
會比較快
所以這個是一個
一個就是
同學可以想想看
那 double link list 在
database 裡面
我們會講
後來你上 DB 你就會知道
我們會講到一個叫做 file
什麼叫做一個 file
檔案
檔案是什麼樣子的構成
你有沒有想過檔案是什麼樣的構成
檔案就是 disk
老師如果存在這個
磁碟機裡面呢
檔案就是 disk
那 disk 裡面最小的組成單位是什麼
block
b-l-o-c-k
那檔案呢
他有所謂的檔案的 structure
檔案 structure 會長什麼樣子
double link list
為什麼是 double link list
你大概想想看
我現在這個 item
item 你感覺好像只有存
數字
簡單的字串
如果真的在 implement
在檔案上的時候
這個 item 他存的是什麼
一個 disk 的 block
其實真的在存的話
他是一個 disk 的 block
一個 disk 的 block
所以一個檔案
比方說他的檔案叫做
101.txt
那上面就有好多的文字
那可能這個文字的
前半段部分
就是放在這個紅色的
這個 disk block
那接下來呢
這個文字的
中間的部分
放在第二個 block 裡面
那接下來
這段文字最後當然是放在第三個
那你要想想看
在上面
要去做檔案 開啟檔案
去做文字的搜索
那都會用到 double link list
就像我剛纔跟你說的
如果要找一個文字
是在 disk 裡面哪個地方
他牽涉到的會是檔案
是怎麼去搜索
你知道為什麼
在 disk 裡面要用 double link list
如果用 single link list
可不可以
他也是可以的啦
可是呢 single link list
也許你會想說
老師那個硬碟不小心
一個停電
那個磁頭針壞掉了
那磁頭針壞掉呢
如果是一個 single link list 的話
把一個 pointer 指標幹掉
那你可能這個檔案就找不到下一個
disk block
在 disk 裡面
他找不到
那也許用 double link list
多一些 link
那比較不會有這種
失誤
missing node 的情況
這個會銜接到同學
db 檔案
這其實很重要
你會覺得說老師那個 ds 是沒什麼了不起的
1234
item 其實是一個字串
那這個都是基礎
db
他就是跟你講
跟檔案是有關係的
那我們就先上課到這邊
