Linked List

陣列與鏈結串列在第四,第五天的時候有講到陣列和鏈結串列，它們都是相當重要的結構化資料型態(Structured Data Type)，也都是線性串列的應用，線性串列也應用在電腦中的資料儲存結構，按照記憶體儲存的方式，可區分為: 靜態資料結構(Static Data Structure) 陣列型態是靜態資料結構，是將有序串列的資料使用連續記憶空間來儲存。它的記憶體配置是在編譯時，就必須配置給相關的變數，因此在建立時，必須事先宣告最大可能的固定空間，容易造成記憶體的浪費，優點是設計時簡單及讀取與修改串列中任何一元素的時間都固定，缺點是刪除或加入資料時，需要移動大量資料。動態資料結構(Sdynamic data structure) 串結鏈結使用不連續記憶空間來... Read more 14 Sep 2023 - 1 minute read

Collision

再雜湊法中，當識別字要放入某bucket時，若該bucket已滿，則發生溢位(overflow)情況，那當雜湊法的理想狀況是所有的資料經過雜湊函數後都得到不同的值，但現實情況是即使所有的關鍵欄位的值都不相同，還是可能得到相同的位址，這就發生了碰撞(collision)。因此在碰撞後處理溢位的問題就是相當的重要，介紹常見的處理方法。線性探測法線性探測法是發生碰撞時，若該索引已有資料，則以線性的方式往後尋找空的儲存位置，一找到位置就把資料放進去。線性探測法通常把雜湊的位置視為環狀結構，這樣後面的位置已被填滿而前面還有位置時，可以將資料放到前面。平方探測法(Sorting) 主要是用平方探測法改善Clustering Problem，在平方探測中，當溢位時，下一次搜尋的位址是(... Read more 13 Sep 2023 - 0 minute read

Hashing

雜湊法是利用雜湊函數來計算一個鍵值所對應的位址，進而建立雜湊表格，然後依賴雜湊函數來搜尋找到各鍵值存放在表格中的位址，搜尋速度與資料多少無關，在沒有碰撞和溢位下，一次讀取即可，且保密性高，因為不事先知道雜湊函數就無法搜尋。除法除法是最簡單的雜湊法是將資料除以某一個常數後，取餘數來當索引。例:有11個位置的陣列中，只使用6個位址。那我們可以把陣列內的值除以11，並以其餘數來當索引。 h(key) = key mod B B=11 索引資料 0 60 1 2 65 ... Read more 12 Sep 2023 - 1 minute read

SearchingII

二分搜尋法(Binary search) 又稱對數搜尋，如果搜尋的資料已經排好即可用二分搜尋法來進行搜尋。它是將資料分割成兩等份，再比較鍵值中間值大小，如果鍵值小於中間值，則可確定要找的資料是在前半段的元素，直到找到或確定不存在為止。以此排序為例: 要搜尋11，先找到8/2=4，第四個元素為9。第四個元素9比11小，所以捨棄第四個元素以前的元素。對剩下的元素搜尋，4/2=2，4+2=6，取得第六個元素為12，比11還大，捨棄11以後的元素。最後11=11，搜尋完成，如果不相等則表示找不到。範例: 用二元搜尋法找出11: [2, 3, 5, 8, 9, 11, 12, 16, 18] fn main() { let data = vec... Read more 11 Sep 2023 - 2 minute read

Searching

搜尋指的是從資料檔案找出滿足某些條件的記錄動作，用以搜尋的條件鍵稱為鍵值(key)，如同排序所用的鍵值一樣。而判斷一個搜尋法的好壞主要是從比較次數及搜尋時間來決定。常見搜尋演算法電腦搜尋資料的優點是快速，但是當資料量很大時，如何在最短時間內有效找到所需資料，是非常重要的。影響搜尋法時間長短主因包括演算法、資料儲存的方式和結構。搜尋法排序法一樣，以搜尋的過程中被搜尋的表格或資料是否異動來區分，分為靜態搜尋和動態搜尋。靜態搜尋:資料在搜尋過程中，該搜尋資料不會增加、刪除或更新等行為，例如:符號表搜尋就屬於一種靜態搜尋。動態搜尋:資料在搜尋中會經常性增加、刪除或更新。搜尋的操作也算是典型的演算法，進行方式和所選擇的資料結構有很... Read more 10 Sep 2023 - 1 minute read

Older Newer