緒論

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)

數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)，字符及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合，數(shù)據(jù)時(shí)計(jì)算機(jī)加工的原料。

數(shù)據(jù)元素 數(shù)據(jù)項(xiàng)

數(shù)據(jù)元素： 數(shù)據(jù)的基本單位
數(shù)據(jù)項(xiàng)： 數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成

數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)對(duì)象

結(jié)構(gòu)： 各元素之間的關(guān)系
數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合
數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合

數(shù)據(jù)結(jié)構(gòu)三要素

邏輯結(jié)構(gòu)
  • 集合： 各元素同屬一統(tǒng)一集合。
  • 線性結(jié)構(gòu)： 一對(duì)一關(guān)系，除第一個(gè)元素都有一個(gè)前驅(qū)；除最后一個(gè)元素都有一個(gè)后繼。
  • 樹形結(jié)構(gòu)： 元素之間一對(duì)多關(guān)系。
  • 圖結(jié)構(gòu)：元素之間多對(duì)多關(guān)系。
物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）
  • 順序存儲(chǔ)：邏輯上相鄰的元素在物理位置上也相鄰（物理上連續(xù)）
  • 連式存儲(chǔ)：邏輯上相鄰的元素在物理位置上可以不相鄰
  • 索引存儲(chǔ)：需要建立索引表 索引表一般形式是（關(guān)鍵字，地址）
  • 散列存儲(chǔ)：又稱哈希存儲(chǔ)，根據(jù)關(guān)鍵字計(jì)算出存儲(chǔ)地址

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)會(huì)影響存儲(chǔ)空間的方便程度
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)會(huì)影響對(duì)數(shù)據(jù)的運(yùn)算速度

數(shù)據(jù)的運(yùn)算

運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的
運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的

數(shù)據(jù)類型 抽象數(shù)據(jù)類型

數(shù)據(jù)類型

數(shù)據(jù)類型：是一個(gè)值的集合和定義在此集合上的一組操作的總稱

  • 原子類型 bool型 int
  • 結(jié)構(gòu)類型 其值可以再分解成若干個(gè)分量 eg：結(jié)構(gòu)體
抽象數(shù)據(jù)類型（Abstract Data Type；ADT）

是抽象數(shù)據(jù)組織及與之相關(guān)的操作。
ADT用數(shù)學(xué)化的語言定義數(shù)據(jù)的邏輯結(jié)構(gòu)和定義運(yùn)算。（與具體實(shí)現(xiàn)無關(guān)）

1.2算法的基本概念

程序=數(shù)據(jù)結(jié)構(gòu)+算法
算法：對(duì)特定問題求解步驟的一種描述。他是指令有限的序列，其中每條指令表示一個(gè)或多個(gè)操作。

算法的特性

  1. 有窮性。算法必須有窮，程序是無窮的
  2. 確定性。每條指令必須有確切的含義，相同的輸入必須得到相同的輸出。
  3. 可行性。算法中描述的每次操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。
  4. 輸入。零個(gè)或多個(gè)輸入
  5. 輸出。一個(gè)或多個(gè)輸出 輸入輸出是有某種特定關(guān)系的量。

好算法的特質(zhì)

  1. 正確性，算法應(yīng)能夠正確的求解解決問題。
  2. 可讀性，算法應(yīng)該具有良好的可讀性，以幫助人們理解。//注釋
  3. 健壯性，當(dāng)輸入非法數(shù)據(jù)時(shí)，算法能適當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。
  4. 高效率與低存儲(chǔ)需求。時(shí)間空間復(fù)雜度低。

算法效率的度量（時(shí)間復(fù)雜度）

事前預(yù)估算法時(shí)間開銷T(n)與問題規(guī)模n的關(guān)系（T表示“time”）
算法時(shí)間開銷只考慮最高階的部分。
大O表示法

  • 加法規(guī)則 多項(xiàng)相加，只保留最高階的項(xiàng)，且系數(shù)變?yōu)橐弧?/li>
  • 乘法規(guī)則 都相乘。

    咒語：常對(duì)冪指階

算法效率的度量（空間復(fù)雜度）