資料結構和演算法教學


什麼是資料結構?

資料結構是組織資料,以便有效地使用它的系統方法。下列術語的資料結構的基礎方面。

  • 介面 ? 每個資料結構有一個介面。介面表示一個資料結構支援的操作集合。一個介面僅提供支援的操作的列表,引數型別,他們可以接受並返回這些操作的型別。

  • 實現 ? 實現提供了資料結構的內部表示。實現還提供了在資料結構的操作中使用的演算法的定義。

資料結構的特徵

  • 正確性 ? 資料結構的實現應該正確地實現它的介面。

  • 時間複雜度 ? 執行時間或資料結構的操作的執行時間必須盡可能的小。

  • 空間複雜度 ? 資料結構操作的記憶體使用量應盡可能少。

資料結構的需要

隨著應用程式越來越複雜和資料豐富,有三種常見的問題應用要面臨。

  • 資料搜尋 ? 考慮100萬(106)物品商店的清單。如果應用程式搜尋一個專案。它需要搜尋專案100萬次(106) 專案每次減慢搜尋。隨著資料的增長,搜尋將變得更加緩慢。

  • 處理器速度 ? 處理器速度雖然是非常高的,屬於有限的,如果資料增長到十億的記錄。

  • 多個請求 ? 隨著成千上萬的使用者可以同時搜尋Web伺服器上的資料,甚至是非常快的伺服器,也有可能搜尋資料失敗。

為了解決上述問題,使用資料結構來解救。資料可以組織在資料結構中,使得在一種方式在所有的專案可以不要求搜尋和所需的資料,可幾乎立即搜尋。

執行時間案例

有三種情況通常用於相對地對各種資料結構的執行時間進行比較。

  • 最壞的情況 ? 這是一個特定的資料結構操作,需要採取的最大時間的方案。如果一個操作的最壞情況下的時間是:?(n),那麼這個操作不會花時間超過?(n)的時間,其中: ?(n)表示n個函式。

  • 平均情況 ? 這是該方案描繪的資料結構的一個操作的平均執行時間。如果一個操作需要:?(n)時間執行,則 m 的操作將採取m?(n)的時間。

  • 最佳案例 ? 這是該方案描繪的資料結構的一個操作,至少可能的執行時間。如果一個操作需要?(n)的時間,然後執行實際操作可能需要一段時間的亂數,這將是最大到 ?(N)。

基本術語

  • 資料 ? 資料值或設定值。

  • 資料項 ? 資料項是指值的一個單元。

  • 組項 ? 被劃分為子項資料項被稱為組專案。

  • 基本專案 ? 不能分割資料項被稱為基本專案。

  • 屬性和實體 ? 實體是含有某些屬性或可被分配的值的屬性。

  • 實體集 ? 類似屬性的實體構成的實體集。

  • 欄位 ? 欄位是資訊表示一個實體的屬性單個基本單元。

  • 記錄 ? 記錄是一個給定的實體的欄位值的集合。

  • 檔案 ? 檔案是在給定實體集的實體記錄的集合。