資料結構
陣列array
堆疊stack
佇列queue
連結串列linked list
樹tree
圖graph
推heap
雜湊表hash table
資料結構（英語：data structure）是電腦中儲存、組織資料的方式。
一個資料結構可被視為兩個函式之間的介面 ，或者是由資料類型聯合組成的儲存內容的存取方法封裝。
資料結構可以透過程式語言 提供的data type與reference及其他操作加以實作，盡可能較少的時間與空間
正確的資料結構選擇可以提高演算法的效率 ，程式設計的困難程度與最終成果的品質與表現，取決於是否選擇了最適合的資料結構。
堆疊stack
佇列queue
連結串列linked list
樹tree
圖graph
推heap
雜湊表hash table
一個資料結構可被視為兩個函式之間的介面 ，或者是由資料類型聯合組成的儲存內容的存取方法封裝。
絕大多數的語言都帶有某種程度上的模組化思想，透過將資料結構的具體實作封裝隱藏於使用者介面之後的方法，來讓不同的應用程式能夠安全地重用這些資料結構。C++、Java、Python等物件導向的程式語言可使用類別來達到這個目的。
陣列array
裝固定大小和相同資料型態的容器
arraylist
是一種動態陣列，資料可從中插入或刪除
推疊stack
處理資料後進先出的排成(EX:疊盤子)
住列queue
處理資料先進先出的排程(EX:排隊)
連結串列linked list
每個節點紀錄資料並且指向下一個節點，將節點串連起來
樹tree
一種階層式的資料集合
樹的最開始會有一個根節點，就像樹的樹根一樣，所有的資料都是由這裡開始發展，接著會有一些其他的節點，有些節點可能在最末端，稱之為葉節點，就像樹的樹葉一樣，其他的節點則像樹的樹枝一樣
在資料結構中的實作會有父節點和子節點的分別，所以可以進一步的定義：
- 樹存在一個為根節點，根節點沒有父節點(不可以有迴圈)。
- 每個節點只有一個父節點(子樹不交集)
雜湊表hash table
無論相同或相異的資料只要有相同的索引值，就會儲存到同一個格子
死結deadlock
一個執行緒鎖住一個變數資料，導致其他執行緒無窮等待
要死結必須要滿足以下四個條件
- Mutual exclusion:一個資源一次只能被一個process所使用
- Hold and Wait: process取得一個資源之後等待其他的資源
- No preemption:資源只能由process自己釋放，不能由其他方式釋放
- Circular wait:每個process都握有另一個process請求的資源，導致每一個process都在等待另一個process釋放資源
Deadlock Avoidance死結的避免
為了確保死結不會發生，我們定義一個安全的狀態--能夠分配給所有process資源而不會造成死
結，在不安全的狀態下則有可能發生死結，假設我們知道
- 系統目前可用的資源數量(Available)
- 各process對資源的最大需求量(max)
- 各process目前持有的資源量(allocation)
各系統還需多少資源(need) = max - allocation
Deadlock pretention預防死結
- Mutual exclusion:對不可共用的資源類型而言，互斥一定成立，而可共用的資源類型，因為可以同時讀取相同檔案，所以一定不會產生。
- Hold and Wait:process必須保證一個行程在要求一項資源時，不可以佔用任何其它的資源。
- No preemption:只要某個處理元要不到所要求的資源時，便把它已經擁有的資源釋放，然後再重新要求所要資源。
- Circular Wait:確保循環式等候的條件不成立，我們對所有的資源型式強迫安排一個線性的順序。
=========================相關聯結===============================
講義下載
http://www.cs.pu.edu.tw/~bcc/download.htm
排序(Sorting)
http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm
JAVA - ArrayList用法、與Array的差別
佇列(Queue)
http://emn178.pixnet.net/blog/post/93557502-%E9%80%A3%E7%B5%90%E4%B8%B2%E5%88%97(linked-list)
計算機題庫
沒有留言:
張貼留言