1. 什么是數(shù)據結構

• 計算機解決一個具體的問題，大致需要以下三個步驟：
• 具體問題抽象出一個適當數(shù)據模型
• 設計一個解此數(shù)據模型的算法
• 編出程序

• 尋求數(shù)據模型的實質就是：==分析問題==蹋绽，從中提取操作的對象芭毙，并找出這些操作對象之間含有的關系，然后用數(shù)學語言加以描述

2. 基本概念和術語

• 數(shù)據（data）是對客觀事物的符號表示卸耘，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱（如：圖像退敦、聲音都是可以通過編碼而歸之于數(shù)據的范疇）

• 數(shù)據元素（data element）是數(shù)據的基本單元，在計算機程序中蚣抗，通常作為一個整體進行考慮和處理侈百。

• 數(shù)據對象（data object）是性質相同的數(shù)據元素的集合，是數(shù)據的一個子集

• 數(shù)據結構 （data structure）是相互之間存在一種或多種特定的數(shù)據元素的集合翰铡。在任何問題中钝域，數(shù)據元素都不是孤立存在的，而是在他們之間存在著某種關系锭魔，這種數(shù)據元素之間的關系稱為結構（structure）

• 根據數(shù)據元素之間關系的不同特性例证，分為4種基本結構

  • 集合：結構中的數(shù)據元素之間除了“同屬于一個集合”的關系外，別無其他關系
  • 線性關系：結構中的數(shù)據元素之間存在一個對一個的關系
  • 樹形結構：結構中的數(shù)據元素之間存在一個對多個的關系
  • 圖狀結構或網狀結構 結構中的數(shù)據元素之間存在多個對多個的關系

• 數(shù)據結構的形式定義：數(shù)據結構是一個二元組Data_Structure=(D,S) 其中D是元素的有限集迷捧，S是D上關系的有限集织咧。結構定義中的“關系”描述的是數(shù)據元素之間的邏輯結構，因此稱為數(shù)據的邏輯結構漠秋。

• 數(shù)據結構在計算機中的表示（又稱映像）稱為數(shù)據的物理結構笙蒙，即存儲結構，它包括數(shù)據元素的表示和關系的表示庆锦。數(shù)據元素之間的關系在計算機中有兩種不同的表示方法捅位，分別為：順序映像和非順序映像，并由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。

  • 順序映像的特點是：借助元素在存儲器中相對位置來表示數(shù)據元素之間的邏輯關系
  • 非順序映像特點是：借助指示元素存儲的指針來表示數(shù)據元素之間的邏輯關系
  • 任何一個算法的設計取決于選定的選定的數(shù)據邏輯結構绿渣，而算法的實現(xiàn)卻依賴于采用的存儲結構

• 數(shù)據類型：是一個值的集合和定義在這個值集上的一組操作的總稱朝群。例如：c語言中的整型變量，其值集為某個區(qū)間上的整數(shù)中符，定義在其上的操作為加姜胖、減、乘淀散、除和取模等算術運算

• 抽象數(shù)據類型（Abstract Data Type簡稱ADT）:是指一個數(shù)據模型以及定義在該模型上的一組操作

  • 抽象數(shù)據類型可用以下三元組表示（D右莱，S，T）其中D是數(shù)據對象 S是D上的關系集档插，P是對D的基本操作慢蜓。可采用一下格式定義抽象數(shù)據類型：

    ADT 抽象數(shù)據類型名 {
    數(shù)據對象:（數(shù)據對象的定義）
    數(shù)據關系:（數(shù)據關系的定義）
    基本操作:（基本操作的定義）
    }ADT 抽象數(shù)據類型名

3. 算法和算法分析

• 算法(algorithm)是對特定問題求解步驟的一種描述郭膛，它是指令的有限序列晨抡，其中每一條指令表示一個或多個操作。算法有5個重要特征

  • 有窮性：一個算法必須總是在執(zhí)行有窮步之后結束则剃，且每一步都可在有窮時間內完成
  • 確定性：算法中每一條指令必須有確切的含義耘柱，讀者理解是不會產生二義，并且棍现，在任何條件下调煎，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出
  • 可行性：一個算法是可行的己肮，即算法中描述的操作都是可以通過已經實現(xiàn)的基本運算執(zhí)行有限此來實現(xiàn)士袄。
  • 輸入：一個算法有0個或多個的輸入，這些輸入取自于某個特定的對象集合
  • 輸出：一個算法有1個或多個輸出谎僻，這些輸出是同輸入有著某些特定關系的量

• 算法設計的要求：通常設計一個好的算法應考慮達到以下目標：

  • 正確性(correctness)：程序對于一切合法的輸入數(shù)據都能產生滿足規(guī)格說明要求的結果
  • 可讀性(readability): 算法主要是為了人的閱讀和交流娄柳，其次才是機器執(zhí)行，可讀性好有助于人對算法的理解艘绍，晦澀難懂的程序易于隱藏較多錯誤西土，難以調試和修改
  • 健壯性(robustness):當輸入數(shù)據非法時，算法也能適當?shù)淖鞒龇磻蜻M行處理鞍盗，而不會產生莫名其妙的輸出結果
  • 效率與低存儲量需求:存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。效率指的的算法的執(zhí)行時間跳昼。這兩者都與問題的的規(guī)模有關般甲。

• 算法效率的度量：時間復雜度

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間度量計作：T(n)=O(f(n))鹅颊。它表示隨問題規(guī)模n的增大敷存，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸進時間復雜度(asymptotic time complexiy)簡稱時間復雜度

• 算法的存儲空間需求：類似與算法的時間復雜度，空間復雜度（space complexity）作為算法所需存儲空間的量度锚烦，記作： S(n)=O(f(n))