二元搜尋樹靠「左小右大」決定往哪邊找（每個節點左子樹裡的鍵值都比它小，右子樹裡的都比它大），搜尋、插入、刪除都只要沿著一條路往下走，時間是 O(h)，h 是樹高...
目前介紹過的排序方法，有最壞要 O(n²) 的選擇、插入、氣泡排序，平均 O(n log n) 的快速排序，以及最壞 O(n log n) 的合併與累堆排序。收...
兩位助教各自改完一疊考卷，都已經依分數由低到高疊好，現在要合成一疊。最省事的做法是：比較兩疊最上面那張，把分數低的放到新的一疊，一直重複到兩疊都拿完。每比較一次...
以 n 代表資料筆數，選擇、插入、氣泡排序在最壞情況下，比較次數都會隨資料筆數呈平方成長，因此時間是 O(n²)。 換個方式想：老師要全班依身高排隊，可以先請一...
在打鋪克牌時，你會怎麼整理？有人會先找出最小的那張放到最左邊，再從剩下的牌裡找最小的；有人會從左到右一張一張看，把每張牌插進左手邊已經排好的牌之間。這兩種直覺的...
圖上的邊除了表示兩個頂點相連，還可以帶著一個數字，稱為權重（weight）。權重可以是造價、距離、時間或費用，帶有權重的圖就是加權圖（weighted grap...
Day 22 把圖存進了記憶體，接下來要在圖裡「逛一圈」：從某個頂點出發，沿著邊走，把走得到的頂點一個一個拜訪（visit，也就是讀取或印出它）。這件事稱為圖的...
總結 字串這樣的資料結構是由零個或多個字元組成的有限序列。 本質上，它是一種線性串列的擴充，但相對線性串列關注一個個元素來說，我們對字串這種結構更多的是關注它子...
Day 21 認識了圖的頂點、邊、度數和連通。圖畫在紙上一目了然，但電腦只認得記憶體：要怎麼讓程式「記住」誰和誰之間有邊？ 今天介紹兩種常見的存法，一種是做一張...
打開社群軟體，你會看到好友名單；點進朋友的頁面，又能看到他的朋友。有些朋友彼此認識，有些人你追蹤了他、他卻沒有追蹤你。如果要用資料結構把這些人和人之間的關係存起...
字串的比較 兩個數字很容易比較大小， 2 比 1 大，這完全正確，可是兩個字串如何比較呢? 例如 silly、 stupid，這樣同樣表達愚蠢的單字字串時，它們...
字串的定義 早先的電腦在被發明時，主要作用是做一些科學和工程的計算工作，也就是現在我們了解的計算機，只不過它比小小的計算機功能更強大、速度也更快一些。 後來發現...
想像一個猜數字遊戲：對方心裡想了 1 到 100 之間的整數，每猜一次，只會回答「太大」或「太小」。聰明的猜法是先猜 50：如果對方說「太大」，代表答案在 1...
佇列的定義 各位在使用電腦時有沒有經歷過，機器有時候會處於疑似當機的狀態，滑鼠點甚麼似乎都沒用，雙擊任何捷徑都不動彈。 就當你失去耐心打算 reset 時。 突...
前幾天我們認識了樹和二元樹的基本功：專有名詞、建立方式、走訪、引線二元樹，以及把森林轉成二元樹。從今天開始，要把這些基礎拿來應用。第一個應用是累堆（heap，也...
遞迴定義 在高階語言中，呼叫自己和其他函數並沒有本質的不同。 我們把一個直接呼叫自己或是透過一系列的呼叫敘述間接地呼叫自己的函數，稱為遞迴函數。 當然，寫遞迴程...
費式數列 假設我們需要列印出前 40 位的費氏數列數。 程式如下: int main() { int i; int a[40]; a[0...
Day 15 用遞迴寫出了前序、中序、後序三種走訪，程式很短也很直觀。但遞迴看起來簡單，背後其實是程式偷偷幫我們記住「走完左子樹之後要回到哪一個節點」：每往下走...
堆疊的應用: 遞迴 堆疊有一個很重要的應用: 在程式語言中實現了遞迴。 那麼甚麼是遞迴呢? 當妳往鏡子前面一站，鏡子裡面就有一個你的成像。 但你試過兩面鏡子對著...
上一篇最後提到：如果我們只看一種走訪結果，通常無法確定一棵二元樹長什麼樣子。那反過來問，如果手上有兩種走訪結果，能不能把原本的樹畫回來？如果節點資料不重複，選用...
堆疊的作用 有的人可能會覺得用陣列或鏈結串列直接時限功能不就行了嗎? 幹嘛要引入存入堆疊這樣的資料結構呢? 其實這和我們明明有兩隻腳可以走路，幹嘛還要乘坐汽車、...
上一篇用陣列和鏈結把二元樹建立起來了，但要怎麼確定 A 的左邊真的接到 B、B 的右邊真的接到 D，而沒有接錯位置？最直接的檢查方法，就是從根節點出發，把樹裡的...
堆疊與佇列 堆疊的定義: 類似彈匣中的子彈一樣先進去，卻要後出來，反之則是後進去可以先出來的。 在軟體應用中，堆疊這種後進先出的資料結構應用是非常普遍的。 例如...
想像你正在闖一座迷宮：每到一個路口，最多只能選左邊或右邊。有些路口兩條路都通，有些只開一邊，走到盡頭就沒有下一個路口。把路口當成節點、路線當成連結，這種每個節點...
線性串列的鏈式儲存結構 優點: 無須表示串列中元素之間的邏輯關係而增加額外的儲存空間 可以快速地存取串列中任一位置的元素 缺點: 插入和刪除操作需要移動大...
循序儲存結構的插入與刪除 獲得元素操作 對線性串列的循序儲存結構來說，如果要實現 GetElem 的操作，即將線性串列 L 中的第 i 個位置元素值傳回，其實是...
陣列版的堆疊和佇列會先準備一段連續空間，資料放進預留的位置。今天改用鏈結串列：每筆資料各自放在一個節點裡，再用指標把節點接起來。這種做法不必一開始決定固定容量，...
線性串列 線性串列從名字就能感覺到，是具有像線一樣性質的串列。 在廣場上有很多人分散在各處，當中有些是小朋友，也有很多大人，甚至還有一些寵物，這些小朋友的資料對...
想像大家排隊買票：先到的人先買，後來的人排到隊伍最後面。資料結構裡的**佇列（queue）**也是這樣運作：先放進去的資料，會先被取出來。這剛好和上一篇的堆疊相...
那麼下面的這個迴圈巢狀結構，它的時間複雜度是多少呢? int i,j; for (i = 0; i < n; i++) { for (j = i;...
HSIUN
rdnnn
iThome鐵人賽
看影片追技術