數據結構和算法教學

什麼是數據結構？

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

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

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

數據結構的特徵

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

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

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

數據結構的需要

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

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

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

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

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

執行時間案例

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

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

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

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

基本術語

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

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

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

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

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

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

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

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

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