N.沃思（Niklaus Wirth)教授提出：
程序=算法+數據結構
以上公式說明了如下兩個問題：
（1）算法決定如何構造和組織數據（算法→數據結構）。
（2）算法的選擇依賴於作為基礎的數據結構（數據結構→算法）。
軟件=程序+文檔（軟件工程的觀點）
主要考慮的是設計出合適的數據結構及相應的算法。
即：首先要考慮對相關的各種信息如何表示、組織和存儲？
因此，可以認為：數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作的學科。
幾個概念：
數據(Data):是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中並被計算機程序處理的符號的總稱。
數據元素(Data Element):是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數據項是數據的不可分割的最小單位。一個數據元素可由若干個數據項組成。
數據對象(Data Object)：是性質相同的數據元素的集合。是數據的一個子集。
什麼是數據結構？
定義1—-
是相互之間存在一種或多種特定關系的數據元素的集合。
定義2—-
按某種邏輯關系組織起來的一批數據（或稱帶結構的數據元素的集合）應用計算機語言並按一定的存儲表示 方式把它們存儲在計算機的存儲器中，並在其上定義了一個運算的集合。
數據元素間抽象化的相互關系（簡稱為邏輯結構）。
與數據的存儲無關，獨立於計算機，它是從具體問題抽象出來的數學模型。
存儲結構（物理結構）—-
數據元素及其關系（數據的邏輯結構）在計算機存儲器中的存儲形式。
是邏輯結構用計算機語言的實現，它依賴於計算機語言。
運算（算法）
邏輯結構—劃分方法一
（1）線性結構—-
有且僅有一個開始和一個終端結點，並且所有結點都最多只有一個直接前趨和一個後繼。
例如：線性表、棧、隊列、串
（2）非線性結構—-
一個結點可能有多個直接前趨和直接後繼。
例如：樹、圖等。
邏輯結構—劃分方法二
一、集合 結構中的數據元素除了同屬於一種類型外，別無其它關系。
二、線性結構 結構中的數據元素之間存在一對一的關系。
三、樹型結構 結構中的數據元素之間存在一對多的關系。
四、圖狀結構或網狀結構 結構中的數據元素之間存在多對多的關系。
存儲結構兩方面的內容：
（1）數據元素自身值的表示（數據域）
（2）該結點與其它結點關系的表示（鏈域）
兩種基本的存儲方法：
（1）順序存儲方法（順序存儲結構）
（2）鏈接存儲方法（鏈式存儲結構）
同一種邏輯結構可采用不同的存儲方法（以上兩種之一或組合），這主要考慮的是運算方便及算法的時空要求。
⑴ 建立(Create)一個數據結構；
⑵ 消除(Destroy)一個數據結構；
⑶ 從一個數據結構中刪除(Delete)一個數據元素；
⑷ 把一個數據元素插入(Insert)到一個數據結構中；
⑸ 對一個數據結構進行訪問(Access)；
⑹ 對一個數據結構(中的數據元素)進行修改(Modify)
⑺ 對一個數據結構進行排序(Sort)；
⑻ 對一個數據結構進行查找(Search)。
數據類型：在一種程序設計語言中，變量所具有的數據種類。
例1、 在FORTRAN語言中，變量的數據類型有整型、實型、和復數型
例2、在C語言中
數據類型：基本類型和構造類型
基本類型：整型、浮點型、字符型
構造類型：數組、結構、聯合、指針、枚舉型、自定義
注意：數據結構不同於數據類型，也不同於數據對象，它不僅要描述數據對象的數據類型，而且要描述數據對象各元素之間的相互關系。
抽象數據類型(Abstract Data Type ，簡稱ADT)：是指一個數學模型以及定義在該模型上的一組操作。
ADT的定義僅是一組邏輯特性描述， 與其在計算機內的表示和實現無關。因此，不論ADT的內部結構如何變化，只要其數學特性不變，都不影響其外部使用。
ADT的形式化定義是三元組：ADT=(D，S，P)
其中：D是數據對象，S是D上的關系集，P是對D的基本操作集。
ADT的一般定義形式是：
ADT <抽象數據類型名>{
數據對象： <數據對象的定義>
數據關系： <數據關系的定義>
基本操作： <基本操作的定義>
} ADT <抽象數據類型名>
其中數據對象和數據關系的定義用偽碼描述。
基本操作的定義是：
<基本操作名>(<參數表>)
初始條件： <初始條件描述>
操作結果： <操作結果描述>
初始條件：描述操作執行之前數據結構和參數應滿足的條件;若不滿足，則操作失敗，返回相應的出錯信息。
操作結果：描述操作正常完成之後，數據結構的變化狀況和 應返回的結果。
算法的概念和描述：
什麼是算法？
所謂算法（Algorithm)是對特定問題求解方法(步驟)的一種描述。
為解決某一特定問題而由若干條指令組成的有窮序列。
適合於計算機程序實現的求解問題的方法
算法的概念和描述：
一個算法必須滿足以下五個准則：
（1）有窮性—執行了有限條指令後一定要終止。
（2）確定性（無二義）—
算法的每一步操作都必須有確切定義，不得有任何歧義性。
（3）可（能）行性—
算法的每一步操作都必須是可行的，即每步操作均能在有限時間內完成。
（4）輸入數據—
一個算法有n（n>=0)個初始數據的輸入。
（5）輸出數據—
一個算法有一個或多個與輸入有某種關系的有效信息的輸出。
? 常見函數的時間復雜度按數量遞增排列及增長率。
常數階O(1)
對數階O(log2n)
線性階O(n)
線性對數階O(nlog2n)
平方階O(n2)
立方階O(n3)
……
k次方階O(nk)
指數階O(2n)
：是指算法編寫成程序後，在計算機中運行時所需存儲空間大小的度量。記作： S(n)=O(f(n))
其中： n為問題的規模(或大小)
該存儲空間一般包括三個方面：
指令常數變量所占用的存儲空間;
輸入數據所占用的存儲空間;
輔助(存儲)空間。
一般地，算法的空間復雜度指的是輔助空間。
一維數組a[n]： 空間復雜度 O(n)
二維數組a[n][m]： 空間復雜度 O(n*m)
