程式=演算法+資料結構
演算法必須符合:
輸入、輸出、明確性、有限性、有效性。
資料結構:
如何把原始的「資料」(data),組織、安排、存放到電腦中,並可使記憶體空間有效利用,且可加快CPU處理時間等等的效益。
陣列(Array):
一連串的資料,有一維陣列、二維陣列....等。
串列(List):
有序串列(指陣列),是資料儲存在連續記憶空間;無序串列(透過指標Pointer),資料乃是儲存在非連續性的記憶空間,以達成資料的鏈結。
堆疊(Stack):先進後出(LIFO)(Last in First Out)
只允許元素在單一位置端增添或刪減。在堆疊中增添資料稱為『推進Push』,刪去元素稱為『移出Pop 』。也即利用一個頂端指標,標定堆疊內最頂端的資料位址,當堆疊內的資料變動時,該指標亦同步變動。例如副程式的呼叫,或是記憶體的使用。
佇列(Queue):先進先出(FIFO)(First in First out)
資料由一端增加,由另一端移出。如果佇列雙向均可以進出資料,稱為雙佇列。首先規劃一段連續的記憶體空間,再利用兩個指標,指向取出元素的一端稱為前端指標,指向元素進入的一端為後端指標。 如果元素要加入或是刪除,加入或刪除端的指標便指向下一個未使用的記憶體空間(加入時),或是下一個元素的位址(刪除時)。
所以經過一段時間後,佇列便有可能超過原先所規劃的記憶體空間,導致佇列無法操作。為改善此現象,遂有環狀佇列的應用。
遞迴(Recursio):
程序本身具有再呼叫自己的能力。
樹(Tree):
樹的結構,一般由最頂端稱為根(Root),開始延伸節點(node),所延伸出的其他節點稱為支節點(Branch Node)。在最底端不再延伸的節點稱為終止節點(Terminal node) 。上下相互兩層節點間的關係可以稱為兄弟節點(Twins),而下節點稱為上節點的子節點(Children node)。常見的資料結構便是計算機組織間的檔案系統或是資料庫結構,均存有樹狀結構的應用,亦即組織層級架構(Hierarchic)。
圖(Graph):
圖形理論。
排序(Sort):
將一組資料依據特性或需求,呈現規則性的序列之演算法。基本上可分為:
內部排序法:把資料完全放在主記憶體內進行排序的方式。此種方法對於少量資料特別有效。
外部排序法:當資料量多, 無法一次全部讀入主記憶體內進行排序,而必須借助外部的儲存裝置,將排序的部分結果暫時存放在該記憶體內,待全部排序完成後,再將所有排序結果顯示的一種排序方法。
搜尋(Search):
為取得特殊或是指定的資料,而必須掃描一範圍的資料,此掃描的方法便是搜尋。