第1章　緒　論

 

1.1　復習筆記

一、什么是數據結構

數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。

二、基本概念和術語

1數據

數據是對客觀事物的符號表示，是計算機科學中所有能輸入到計算機中并能被計算機程序處理的符號的總稱。

2數據元素

數據元素是數據的基本單位。

3數據對象

數據對象是性質相同的數據元素的集合，是數據的一個子集。

4數據結構

數據結構是相互之間存在一種或多種特定關系的數據元素的集合。

（1）數據結構的基本結構

根據數據元素之間關系的不同特性，通常有下列四類基本結構：

①集合。數據元素屬于“同一個集合”，并無其他復雜關系。

②線性結構。數據元素之間存在一個對一個的關系。

③樹形結構。數據元素之間存在一個對多個的關系。

④圖狀結構或網狀結構。數據元素之間存在多個對多個的關系。

【注意】區分這四種基本結構可以根據元素間的對應關系。

如圖1-1所示為上述四類基本結構的關系圖。

圖1-1　四類基本結構的關系圖

（2）數據結構的形式定義

數據結構的形式定義為：

Data_Structure=(D,S)

其中：D表示數據元素的有限集，S表示D上關系的有限集。

（3）數據結構在計算機中的表示

數據結構包括數據元素的表示和關系，在計算機中稱為數據的物理結構（又稱存儲結構）。

其中，關系有兩種表示方法：順序映象和非順序映象。這兩種表示方法對應兩種存儲結構：順序存儲結構和鏈式存儲結構。

a．順序映象：用相對位置來表示數據元素之間的邏輯關系。

b．非順序映象：用指針表示數據元素之間的邏輯關系。

5數據類型

數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。

6抽象數據類型

抽象數據類型（ADT）由一個值域和定義在該值域上的一組操作組成。

【注意】抽象數據類型是對數據類型架構的一種全局體現，使我們能夠更加清晰地看待某一數據類型。

7多形數據類型

多形數據類型是指其值的成分不確定的數據類型。

8數據操作的類型

基本的操作主要有：

（1）插入

（2）刪除

（3）更新

（4）查找

（5）排序

從操作的特性來分，所有的操作可以歸結為兩類：

加工型操作：改變了（操作之前的）結構的值；

引用型操作：即不改變結構的值，只是查詢或求得結構的值。

上述5種操作中除“查找”為引用型操作外，其余都是加工型操作。

9算法

【定義】算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。

【特性】

（1）有窮性

（2）確定性

（3）可行性

（4）輸入

（5）輸出

【注意】在考試中這五個特性可能出現在選擇或者填空題中（通常直接考察其名稱）。

三、抽象數據類型的表示與實現

四、算法和算法分析

1算法的描述

算法需要用一種語言來描述，程序框圖，程序設計語言等都能對算法進行描述。

【注意】考研筆試中，如果在對應語法不確定的情況下，使用偽碼通常也是可以的。

2算法設計的要求

（1）正確性

（2）可讀性

（3）健壯性

（4）效率與低存儲量需求

3算法效率的度量

算法執行時間需通過依據該算法編制的程序在計算機上運行時所消耗的時間來度量，度量一個程序的執行時間通常有兩種方法：

（1）事后統計

（2）事前分析估算

①事先考慮消耗時間的因素

②時間復雜度

時間復雜度是關于問題規模的函數，通常用O表示，常見時間復雜度按照數量級遞增排列為：

O（1）＜O（log₂n）＜O（n）＜O（nlog₂n）＜O（n²）＜O（n³）＜O（n^k）＜O（2ⁿ）

【注意】需能夠對具體的算法進行時間復雜度的分析與計算，尤其在考研中算法時間復雜度的計算不可避免。

4算法的存儲空間需求

算法的空間復雜度是對算法運行所占空間的度量。

在度量時一般只考慮算法運行所需額外開銷的多少，包括算法實現時定義的中間變量，數組等對存儲空間的影響。

原地工作：算法運行所需的額外空間相對輸入數據量是常量。