擁抱「資料結構」的「演算法」(06) - 環狀連結串列 Circular Linked List
前言
接連著甚是單向連結陣列與雙向連結陣列之後,今天要介紹環狀連結串列
,一起來看看它有什麼特色吧
生活常識
說到台灣知名景點,你會想到哪裡呢?許多外國朋友都指名一定要去日月潭,日月潭其中一個特色就是有環湖路線
,可以騎腳踏車或開車盡覽美景,如果你想到達某一個地點,是無法直達的,一定要逐一瀏覽才能到達指定地點
另外小時候的經典團康遊戲,鬼抓人,大家會圍成一個圓圈,先選一個人當鬼,他會在圓圈外圍環遶尋找下手的目標,假設這個鬼拍了你的背一下,你就要趕快站起來追他:
- 如果追到他,他就繼續當鬼,
- 如果讓鬼跑一圈,搶坐在你原本的位置上,那就要換你當鬼
圖片來源:https://www.pexels.com/zh-tw/photo/1164572/
而上述的遊戲,就很像是環狀連節串列,不管鬼從哪邊開始跑,從哪邊開始挑對象,他跑的路徑,一定會經過所有人
專業知識 - 環狀連結串列 Circular Linked List
特色
- 將單向連接串列
最後一個節點
的指標,指向第一個節點
- 不論從哪個節點開始讀取,都能經過所有節點
假設今天我們要從A、B、C、D、E、F、G、H 共 8 名學生中抽出 1 名學生出來上台報告,為了營造緊張的氣氛,我們要來玩報數遊戲
,大家圍成一個圈,並從任意位置從喊 1 開始報數,報到 3 的人就淘汰,並往下重新報數,一直進行到剩下一個人為止,而這麼剩下的人就是要上台報告的人,如下如所示,如果從 A 同學開始順時鐘報數
,依序喊 123 ,喊到 3 的是 C 同學,因此 C 就可以殺青去旁邊領便當了,接下來換 D 開始喊 1 ,最後留下的人會是誰呢?你猜到了嗎?就是G 同學
上述的小遊戲,其實就是常常聽到約瑟夫問題
,可參考維基百科的說明,裡面描述的故事其實有點殘酷,另外將單向連節串列最後一個節點
的指標,指向第一個節點
,就會形成環狀連節串列
,如下圖
今日小結
帶大家回想一下生活情境,火車可以單向行駛,也可雙向行駛,根據鐵軌的設計,甚至可以提供環湖行程,而對應到資料結構中的 3 種連結串列,單向、雙向、環狀連結也有異曲同工之妙,希望這些例子可以增加大家的記憶,!明天要來講其他類型的資料結構
今日謎題
小美到遊樂園玩的時候,突然發現摩天論的車廂外側有神祕的英文字母,你幫助小美猜到其中隱含的訊息嗎?
昨日解謎
解謎說明:從左而右,或由右而左,都會得到20200202
直接 google 20200202,就會查到 2020020 是 900 年難得一遇的世界回文日
留言
張貼留言