數據結構和算法教程


什麼是數據結構?

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

  • 接口 − 每個數據結構有一個接口。接口表示一個數據結構支持的操作集合。一個接口僅提供支持的操作的列表,參數類型,他們可以接受並返回這些操作的類型。

  • 實現 − 實現提供了數據結構的內部表示。實現還提供了在數據結構的操作中使用的算法的定義。

數據結構的特徵

  • 正確性 − 數據結構的實現應該正確地實現它的接口。

  • 時間複雜度 − 運行時間或數據結構的操作的執行時間必須儘可能的小。

  • 空間複雜度 − 數據結構操作的內存使用量應儘可能少。

數據結構的需要

隨着應用程序越來越複雜和數據豐富,有三種常見的問題應用要面臨。

  • 數據搜索 − 考慮100萬(106)物品商店的清單。如果應用程序搜索一個項目。它需要搜索項目100萬次(106) 項目每次減慢搜索。隨着數據的增長,搜索將變得更加緩慢。

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

  • 多個請求 − 隨着成千上萬的用戶可以同時搜索Web服務器上的數據,甚至是非常快的服務器,也有可能搜索數據失敗。

爲了解決上述問題,使用數據結構來解救。數據可以組織在數據結構中,使得在一種方式在所有的項目可以不要求搜索和所需的數據,可幾乎立即搜索。

執行時間案例

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

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

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

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

基本術語

  • 數據 − 數據值或設定值。

  • 數據項 − 數據項是指值的一個單元。

  • 組項 − 被劃分爲子項數據項被稱爲組項目。

  • 基本項目 − 不能分割數據項被稱爲基本項目。

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

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

  • 字段 − 字段是信息表示一個實體的屬性單個基本單元。

  • 記錄 − 記錄是一個給定的實體的字段值的集合。

  • 文件 − 文件是在給定實體集的實體記錄的集合。