擁抱「資料結構」的「演算法」(04) - 單向連結串列 Singly Linked List

 

前言

陣列有一個很大的特色，就是一定要預留一段的連續空間來儲存資料，所以當有空間已經用完，且有額外的資料想要存入時，就會非常不方便，所以今天要來介紹另外一種線性串列，這一種資料結構稱為連結串列 Linked List，不用像陣列那樣需要在一開始就保留連續空間，串列的資料可以存在任意的位置，然後透過連結將資料一個一個串起來，讓我們一起來看看生活中的例子吧

生活常識

保健盒

你還記得小美吃保健食品的故事嗎？有沒有哪些情境是讓你印象深刻的，像我自己覺得保健食品盒雖然格子很多很方便，但是如果遇到放錯格子或想調整保健品的順序，真的會很崩潰，因為可能要把保健品通通拿出來再重新放一遍，很曠日廢時，但其實有一種保健盒很方便，提供了組裝功能，我們一起來看看下面的圖：


圖片來源:momo

透過上圖，可以觀察到，每個盒子左右兩邊，分別做了凸槽與凹槽設計，意思也就是說，每個盒子都是獨立的，可以單獨一格使用，也可以把很多格串再一起使用，增加了很多彈性，如果想要調整順序或數量都是很容易的事情，如果放錯格子或放錯順序，完全不需要把保健品拿出來，只需要將小格子拆下來，再重新組合即可，不像一體成形的盒子那樣，要調整就只能大搬風，保健品通通要拿出來

車廂

生活中會接觸到交通工具，像是火車，也是將很多車廂串在一起，今天要增加車廂或是減少車廂，都可以處理，因為車廂可以放在倉庫，需要用到在去挪出來並串到火車上，用講的可能不好理解，一起來欣賞一下網友提供的youtube影片

加掛車廂

維修車廂

兔子舞

童年回憶XD，每個人將雙手搭在前者的肩膀看，然後進行左跳右跳、跳跳跳的團康活動，透過我們的雙手可以快速的將人串再一起，讓活動氣氛達到最高點XD


圖片來源:百度百科

人脈弱連結

不知道你有沒有這樣的經驗，當今天認識一個新朋友的時候，互相加 Facebook 好友時，才發現其實你與對方有很多共同朋友，但之前都不知道；亦或是從對方的朋友清單中，發現他認識某某領域的朋友，是你也很想認識，想請他引薦的，其實人與人之間也存在某種連結，或是我們常常說的緣分，如果今天跟對方沒有緣分，就像兩條平行線，永遠沒有交集XD，如果想要有交集，就必須創造連結

如果今天小美，想邀請祖克伯來公司演講，但小美不認識祖克伯，但小美曾聽過自己的朋友小明說，他朋友小華的爸爸是祖克伯，所以今天小美在不認識小華的情況下，想要聯繫到祖克伯，就必須先拜託小明，小明再去拜託小華，小華再去拜託自己的爸爸祖克伯，才能成功讓小美直接聯繫到祖克伯

專業知識 - 單向連結串列 Singly Linked List

連結串列有細分單向、雙向與環狀連結串列，今天先來講單向連結串列

特性

  1. 不需要預留固定數量且一段連續的儲存空間
  2. 一個節點包含資料與指標
  3. 必須單向依序讀取節點，透過指標，才知道下一個要讀取哪個節點(無法像陣列透過索引就能讀取資料)
  4. 插入或新增節點很方便，只要改變指標即可

火車例子

  1. 不需要指定大小，不需要預留一段連續的儲存空間
    車廂數量沒有固定值，車廂可隨意調整，不需要連續

  2. 一個節點包含資料與指標
    每個車廂都可以載人，並且會以連接器串接下一個車廂

  3. 必須依序讀取節點，透過指標，才知道下一個要讀取哪個節點(無法像陣列透過索引就能讀取資料)
    火車進站時，一定會先看到第一車廂、第二車廂，依序到最後一節車廂，你一定要站在月台看到最後面，才會知道這個車次的最後一個車廂是什麼，可能是夜間婦女車廂也不一定

  4. 插入或新增節點很方便，只要改變指標即可
    如果今天鐵路局發現，下班時間搭乘人數很多，就可以考慮加掛車廂。如果進廠維修時，發現第四車廂發生故障，可直接將故障車廂卸下，並將正常的第三車廂繼續串接第五車廂，只要調整車廂與車廂之間的連結器即可

今日小結

可能會覺得串列好像比陣列更好用，其實兩者還是要依照實際需求來使用，雖然串列中的節點，可快速的新增或移除，但如果今天想快速存取某一個節點，則非常不方便，因為串列之間的節點必須依序讀取才會知道節點的指標指向哪裡，不像陣列可以透果索引直接存取資料，例如小美想到找到祖柏克，就只能透過朋友間的層層聯繫，才能找到人，但如果小美今天知道祖柏克住在哪，就能直接找到他，就不需要透過朋友穿針引線的幫忙囉，同一件事情根據情況不同，所使用的方式也會不同

今日謎題

小美發現之前的神祕客就是小乖，他想跟小乖開啟對話，但他們兩個人並不認識，必須逐一請小明、小華、小草與小英轉達，才能將訊息傳達給小乖，請問你有發現神秘圖形嗎？



昨日解謎

解謎說明：要清楚二維陣列的存取使用方式，透過索引找到相對應的儲存位置，答案就呼之欲出囉

Maps[2,2] = D
Maps[0,1] = I
Maps[3,0] = M
Maps[1,3] = E
Maps[4,0] = N
Maps[5,0] = S
Maps[5,3] = I
Maps[4,1] = O
Maps[7,1] = N

答案就是DIMENSION，維度 Dimension，你答對了嗎XD


留言

張貼留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

Visual Studio 自動排版格式化程式碼

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »