築夢角落

致力於用最生活化的例子讓所有人都能懂程式,也喜歡分享動漫、小說心得,以及自己的所見所聞、所思所想。

資料結構是什麼?會收衣服就會的資料結構

最後更新時間 : 2022-11-16 | viewed : 20

資料結構就跟收納衣服一樣

在程式設計的世界裡,有一個常見的理論是資料結構 + 演算法 = 程式

那什麼是資料結構呢?其實就是指資料的擺放結構,就像我們把衣服收進衣櫥一樣,隨便亂擺可不行,因為之後會很難找到你要的那件衣服。

今天我們就嘗試用生活化的例子來理解什麼是資料結構吧!

 

目次

 

前言


本文旨在幫助初次接觸資料結構或自學的朋友釐清整體概念,希望大家在利用其他內容完整的書籍或網路資源學習時能更順利。

文中所舉的例子在細節上難免有失真或缺少一些知識點,還望見諒。有任何想法歡迎留言。

 

誰適合閱讀本文?


資訊相關科系學生、程式自學或初學者、跟我一樣曾被資料結構搞昏頭的人、這輩子都不會動手寫程式但還是想瞭解一下的人。

 

典型資料結構


有接觸過資料結構的人一定聽過很多專有名詞,像是堆疊、佇列、鏈結串列、二元樹等等的,這當中有些概念很好理解,有些則不然。

堆疊(Stack)就像疊盤子,我們疊盤子的時候會往最上面放,拿盤子的時候也從最上面先拿,產生所謂先進後出的現象,越早進入堆疊的盤子要等到越晚才能從堆疊取出。

佇列(Queue)就像排隊,先到售票亭的人可以先買票,後到的人只能依序排隊等待,產生所謂先進先出的現象,越早進入佇列的人可以越早離開佇列。

鏈結串列(Linked list)則像火車一樣,一個車廂連接一個車廂,因為列車不是一體成形的,所以每個車廂都可以隨意替換,想要增加車廂、減少車廂也都很容易。

以上三種資料結構都能用貼近生活的例子來說明,所以應該不難理解,但是二元樹就很少會有這麼平易近人的例子,所以初學資料結構時很容易在這裡想放棄。

因為我們往往不是先從宏觀的角度來認識資料結構,所以常常會在中途被專業理論搞得暈頭轉向,最終根本搞不懂那些資料結構有什麼意義。

現在,就讓我們暫時忘記這些專有名詞、拋開程式語言,只用收納衣服的例子來重新理解資料結構的本質

 

資料結構就是資料的擺放結構


資料結構,顧名思義就是資料的結構,更明確一點來說是資料的擺放結構

這裡我們已經知道了兩件事:

(1) 有一種東西被稱作資料
(2) 這些資料需要按某種方式擺放(收納)

在收納衣服的例子中,衣服就是我們的資料衣櫥是我們放衣服(資料)的地方,我們必須把所有衣服都放進空間有限的衣櫥裡。

這時我們會遇到一個問題:該怎麼收納最好?

這裡的最好是有前提的,你必須知道你未來想怎麼找到並取出某件衣服,才知道現在該如何收納

所以這裡我們知道了第三件事:

(3) 收納好的資料會在某個時刻需要被取用

 

收衣服的情境


假如我們的衣櫥很小,只有一個抽屜,所有衣物都只能放進抽屜裡,這時就會有兩種典型的情況:

(1) 如果你希望收納衣服時很方便,那只要有空間就把衣服疊上去、塞進去會是很好的選擇,但是想取出衣服時就得花比較多的時間尋找衣服,甚至還要移開其他堆疊在它上面的衣物才行。

(2) 如果你希望取出衣服時很方便,那收納時就需要花比較多時間找尋、騰出適合的位置,未來才能馬上找到並取出那件衣服。

這是程式設計永遠都在思考的問題,就像收衣、取衣一樣,如果你想收納快速,那取出就會費時費力,如果你想取出快速,那收納就會費時費力,魚與熊掌難以兼得。

總的來說,資料結構其實就是指在衣櫥裡擺放衣服的方式。衣服就是資料,衣櫥就是電腦的記憶體,會收衣服就會資料結構

然後因為目的不同,所以擺放資料的方式也會不同,並且擺放的方式也會直接影響之後存入新資料、取出舊資料的方式,換句話說,資料結構跟演算法(收衣、取衣的步驟)其實是高度相關的。

資料結構限制了你能採用的演算法、演算法決定了你需要使用什麼資料結構,這部份我們有機會再細講。

 

時間複雜度、空間複雜度


資料結構跟演算法經常會討論時間複雜度空間複雜度,聽起來好像很複雜,但透過前面收衣、取衣的例子,我們可以知道時間複雜度就是指存、取資料所需的時間

換句話說,根據你收衣、取衣的策略不同,你會花多少時間收納衣服、花多少時間取出衣服,就是時間複雜度想討論的事情。

但為什麼要說是時間複雜度,而不直接說耗時多久呢?這是因為在定義上,我們想知道的是當衣服越來越多之後,同樣的存取策略會不會突然變得很慢

舉例來說,如果收一件衣服要 1 秒,收兩件衣服要 2 秒,收三件衣服要 3 秒,那收一百件衣服只需要 100 秒嗎?

這就要看你的收納方式了,也許你還是可以維持 1 秒收一件,100 秒收一百件,但也可能收到第十件之後,每件都要花 5 秒,收到第五十件之後,每件都要花 10 秒,這就是時間複雜度

除此之外,不同電腦執行同一段程式的耗時也會不同,這也是我們不直接討論耗時的原因。

 

空間複雜度呢?其實就是指你衣櫥的大小跟空間利用率

如果你的衣櫥很大,還可以吊衣服,那你收衣、取衣就會很方便快速,時間複雜度會下降(不容易因為衣服變多而增加收衣、取衣的時間成本),但缺點就是空間利用度很低,很多空間是被浪費掉的(原本可以用來堆疊衣服的空間沒有被使用)。這時候我們會說空間複雜度很高

如果你的衣櫥很小,所有衣服都只能擠在小小的空間裡,那時間複雜度會上升(衣服變多就要花更多時間移動空間收衣、取衣),但優點是空間利用度很高,幾乎沒有浪費空間。這時候我們會說空間複雜度很低

 

時間複雜度跟空間複雜度幾乎是負相關的,一邊高一邊就低。空間大、好收納,花費的時間就少;空間小、難收納,花費的時間就多。

但通常我們都沒有無限大的衣櫥(記憶體),所以只能在這兩者之間取得平衡。

還有就是,高低是相對概念,學術上會用 O(1)、O(n)、O(n2) 的方式來表達複雜度,因為相關書籍跟網路文章很多,這裡就不多提了,有問題的話可以留言討論。

 

結論


堆疊、佇列、鏈結串列、二元樹都屬於典型的資料結構,在實務上經常會用到,而且是被驗證過、十分有效的通用方法,所以非常值得學習。

但是廣義來說,只要存在一個以上的資料,就一定存在某種結構,也就是有資料就有結構,資料結構是無所不在的,無論你是否有意識到它。

同時,資料結構會直接影響我們能夠使用的演算法,這是它為何很重要的原因之一。

然而,只要你知道

(1) 為什麼按照某種結構擺放資料很重要

(2) 儲存結構會如何影響你存取資料

(3) 你選擇的儲存結構,對存取時間和空間會有什麼影響

那你就已經瞭解資料結構的核心理念了,可以直接針對自己的需求去思考要使用什麼樣的資料結構,透過實作去驗證它是否真的如預期般有效,而不必過度在意自己是否熟知所有典型資料結構

也說不定你早就在不知不覺中,運用過典型資料結構了,只是你不知道它在學術上還有個專有名詞而已。

 

希望這次的介紹會對大家自學典型資料結構時有所幫助~

 

 
我要留言!
 

X
暱稱(選填)
email(選填,僅站長可見。)
留言 To:#