iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 6
0
Software Development

擁抱「資料結構」的「演算法」系列 第 6

擁抱「資料結構」的「演算法」(06) - 環狀連結串列 Circular Linked List

前言

接連著甚是單向連結陣列與雙向連結陣列之後,今天要介紹環狀連結串列,一起來看看它有什麼特色吧


生活常識

說到台灣知名景點,你會想到哪裡呢?許多外國朋友都指名一定要去日月潭,日月潭其中一個特色就是有環湖路線,可以騎腳踏車或開車盡覽美景,如果你想到達某一個地點,是無法直達的,一定要逐一瀏覽才能到達指定地點
https://ithelp.ithome.com.tw/upload/images/20200922/20129841pf2SuyQNHJ.png

另外小時候的經典團康遊戲,鬼抓人,大家會圍成一個圓圈,先選一個人當鬼,他會在圓圈外圍環遶尋找下手的目標,假設這個鬼拍了你的背一下,你就要趕快站起來追他:

  • 如果追到他,他就繼續當鬼,
  • 如果讓鬼跑一圈,搶坐在你原本的位置上,那就要換你當鬼

https://ithelp.ithome.com.tw/upload/images/20200919/20129841zD1LgbLDDK.png
圖片來源:https://www.pexels.com/zh-tw/photo/1164572/

而上述的遊戲,就很像是環狀連節串列,不管鬼從哪邊開始跑,從哪邊開始挑對象,他跑的路徑,一定會經過所有人


專業知識 - 環狀連結串列 Circular Linked List

特色

  1. 將單向連接串列最後一個節點的指標,指向第一個節點
  2. 不論從哪個節點開始讀取,都能經過所有節點

假設今天我們要從A、B、C、D、E、F、G、H 共 8 名學生中抽出 1 名學生出來上台報告,為了營造緊張的氣氛,我們要來玩報數遊戲,大家圍成一個圈,並從任意位置從喊 1 開始報數,報到 3 的人就淘汰,並往下重新報數,一直進行到剩下一個人為止,而這麼剩下的人就是要上台報告的人,如下如所示,如果從 A 同學開始順時鐘報數,依序喊 123 ,喊到 3 的是 C 同學,因此 C 就可以殺青去旁邊領便當了,接下來換 D 開始喊 1 ,最後留下的人會是誰呢?你猜到了嗎?就是G 同學

https://ithelp.ithome.com.tw/upload/images/20200920/20129841eYpDNqnahZ.png

上述的小遊戲,其實就是常常聽到約瑟夫問題,可參考維基百科的說明,裡面描述的故事其實有點殘酷,另外將單向連節串列最後一個節點的指標,指向第一個節點,就會形成環狀連節串列,如下圖
https://ithelp.ithome.com.tw/upload/images/20200920/201298413jG9aKfiyq.png


今日小結

帶大家回想一下生活情境,火車可以單向行駛,也可雙向行駛,根據鐵軌的設計,甚至可以提供環湖行程,而對應到資料結構中的 3 種連結串列,單向、雙向、環狀連結也有異曲同工之妙,希望這些例子可以增加大家的記憶,!明天要來講其他類型的資料結構


今日謎題

小美到遊樂園玩的時候,突然發現摩天論的車廂外側有神祕的英文字母,你幫助小美猜到其中隱含的訊息嗎?
https://ithelp.ithome.com.tw/upload/images/20200920/20129841V2iQrCftrq.png

昨日解謎

解謎說明:從左而右,或由右而左,都會得到20200202
直接 google 20200202,就會查到 2020020 是 900 年難得一遇的世界回文日


上一篇
擁抱「資料結構」的「演算法」(05) - 雙向連結串列 Doubly Linked List
下一篇
擁抱「資料結構」的「演算法」(07) - 堆疊 Stack
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言