資料結構1：基本概念

資料結構基本概念

• 基本概念

  • 資料

    ：資料是資訊的載體，是描述客觀事物屬性的數、字元及所有能輸入到計算機中并被計算機程式識别和處理的符号的集合。資料是計算機程式加工的原料。

  • 資料元素、資料項

    ：資料元素是資料的基本機關，通常作為一個整體進行考慮和處理。一個資料元素可由若幹資料項組成，資料項是構成資料元素的不可分割的最小機關。要按不同場景進行确定。

  

  資料元素與資料項

  • 資料結構、資料對象

    ：資料結構是互相之間存在一種或多種特定關系的資料元素的集合。資料對象是具有相同性質的資料元素的集合，是資料的一個子集。

  • 資料類型

    ：資料類型是一個值的集合和定義在此集合上的一組操作的總稱，如int、float類型等。

    原子類型：其值不可再分的資料類型。

    結構類型：其值可以再分解成若幹成分的資料類型。

  • 抽象資料類型（ADT）

    ：是抽象資料組織及與之相關的操作。ADT用數學化的語言定義資料的邏輯結構、運算，且不關注具體實作。
• 三要素

  • 邏輯結構

    ：資料元素之間的邏輯關系。集合、線性結構、樹形結構、圖結構。

  • 實體結構

    ：資料元素的邏輯關系在計算機中的表示。順序存儲、鍊式存儲、索引存儲、散列存儲。

    順序存儲：把邏輯上相鄰的元素存儲在實體位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來展現。

    鍊式存儲：邏輯上相鄰的元素在實體位置上可以不相鄰，借助訓示元素存儲位址的指針來表示元素之間的邏輯關系。

    索引存儲：在存儲元素資訊的同時，還建立附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式是（關鍵字，位址）

    散列存儲：根據元素的關鍵字直接計算出該元素的存儲位址，又稱哈希存儲。

    

    索引存儲

  • 資料的運算

    ：施加在資料上的運算包括運算的定義和實作。運算的定義是針對邏輯結構，指出運算的功能；運算的實作是針對存儲結構的，指出運算的具體操作步驟。

    例如，對于一個隊列（線性結構）來說，我們需要他能夠隊頭元素出列、新元素進入尾部，等需求，這些都是對運算的定義，這些定義是根據邏輯結構來決定的，但是邏輯結構的實作可以有很多種實體結構，針對這些不同的實體結構它們對運算的實作也不一樣，故實作是針對存儲結構的。

算法基本概念

• 什麼是算法
  • 程式=資料結構+算法
  • 資料結構是要處理的資訊，算法是處理資訊的步驟
• 算法的五個特性
  • 有窮性：有窮時間内可以執行完（算法是有窮的，程式可以是無窮的）。
  • 确定性：相同輸入隻會産生相同輸出。
  • 可行性：可以用已有的基本操作實作算法。
  • 輸入：給算法處理的資料。
  • 輸出：算法處理的結果。
• 好算法的特質
  • 正确性：能正确解決問題。
  • 可讀性：對算法的描述要讓其他人也看得懂。
  • 健壯性：算法能處理一些異常狀況。
  • 高效率與低存儲量需求：算法執行省時省記憶體；算法時間複雜度低、空間複雜度低。

算法的時間複雜度

• 如何計算
  1. 找到以一個基本操作（最深層循環）
  2. 分析該基本操作的執行次數x與問題規模n的關系x = f(n)
  3. x的數量級O(x)就是算法複雜度
• 常用技巧
  • 加法規則：O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
  • 乘法規則：O(f(n)) × O(g(n)) = O(f(n) × g(n))
  • O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
• 三種複雜度
  • 最壞時間複雜度
  • 平均時間複雜度
  • 最好時間複雜度

算法的空間複雜度

• 普通程式計算
  • 找到所占空間大小與問題規模相關的變量
  • 分析所占空間x與問題規模n的關系 x = f(n)
  • x的數量級O(x)就是算法空間複雜度
• 遞歸程式計算
  • 找到遞歸調用的深度x與問題規模n的關系x = f(n)
  • x的數量級O(x)就是算法空間複雜度