《數(shù)據(jù)結(jié)構(gòu)》學習筆記

第1章 緒論

1.1 數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

計算機計算數(shù)值時，一般經(jīng)過一下步驟：
1.從具體問題抽象出數(shù)學模型（實質(zhì)是分析問題）。
2.設(shè)計一個解次數(shù)學模型的算法。
3.編寫程序，進行測試、調(diào)試，直到問題解決。

數(shù)據(jù)結(jié)構(gòu)要研究非數(shù)值計算問題，非數(shù)值計算問題無法用數(shù)學方程建立數(shù)學模型。

1.2 基本概念和術(shù)語

1.2.1
數(shù)據(jù)項(Data Item)：是組成數(shù)據(jù)元素、有獨立含義的、不可分割的最小單位。
數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，也稱為元素、記錄等；用于完整地描述一個對象。
數(shù)據(jù)對象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，只要集合內(nèi)元素的性質(zhì)均相同，都可稱之為一個數(shù)據(jù)對象；是數(shù)據(jù)的一個子集。
數(shù)據(jù)(Data)：是客觀事物的符號表示，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。
（數(shù)據(jù)項<數(shù)據(jù)元素<數(shù)據(jù)對象<數(shù)據(jù)）

1.2.2 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(Data Structure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指元素之間存在的關(guān)系。

-1.邏輯結(jié)構(gòu)
從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。
分為兩個要素：

數(shù)據(jù)元素

關(guān)系

常見的四類基本結(jié)構(gòu)：
圖1.3
(1)集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“屬于同一個集合”的關(guān)系外，別無其它關(guān)系。
(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對一的關(guān)系。
(3)樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多的關(guān)系。
(4)圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對多的關(guān)系。

-2. 存儲結(jié)構(gòu)
數(shù)據(jù)對象在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。
(1)順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助數(shù)組來描述。要求所有元素依次存放在一片連續(xù)的存儲空間中。
表1.2

(2)鏈式存儲結(jié)構(gòu)：無需占用一整塊存儲空間。給每個結(jié)點附加指針字段，用于存放后繼元素的存儲地址，從而來表示結(jié)點之間的關(guān)系。
圖1.5

1.2.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型
-1. 數(shù)據(jù)類型(Data Type)
是高級程序設(shè)計語言中的一個基本概念，在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定來數(shù)據(jù)的取值范圍，存儲方式以及允許進行的運算，數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。

-2. 抽象數(shù)據(jù)類型(Abstract Data Type, ADT)
一般指由用戶定義的、表示應用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱，具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合、數(shù)據(jù)對象的基本操作的集合。
在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型，如整形、實型、字符型等，可以進一步利用這些類型構(gòu)造出線性表、棧、隊列、樹、圖等復雜的抽象數(shù)據(jù)類型。

1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)
表示和實現(xiàn)抽象數(shù)據(jù)類型，最好用面向?qū)ο蟮姆椒ā?/p>

1.4 算法和算法分析

1.4.1 算法的定義及特性
算法(Algorithm)是為了解決某類問題而規(guī)定的一個有限長的操作序列。五個重要特征：

有窮性

確定性

可行性

輸入

輸出

1.4.2 評價算法優(yōu)劣的基本標準

正確性

可讀性

健壯性

高效性

1.4.3 算法的時間復雜度
算法效率分析的目的是看算法實際是否可行，并在同一問題存在多個算法時，可進行時間和空間性能上的比較，以便從中挑選出較優(yōu)算法。

-1. 問題規(guī)模和語句頻度。
問題規(guī)模：算法求解問題輸入量的多少，是問題大小的本質(zhì)表示，一般用整數(shù)n表示。n越大算法的執(zhí)行時間越長。
語句頻度(Frequency Count)：一條語句的重復執(zhí)行次數(shù)。

算法中基本語句重復執(zhí)行的次數(shù)是問題規(guī)模n度某個函數(shù)f(n)；算法的時間復雜度為：T(n)=O(f(n))
算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸進時間復雜度，簡稱時間復雜度(Time Complexity)。
為了方便比較不同算法的時間效率，我們僅比較它們的數(shù)量級(最高次冪)，數(shù)量級越小，算法越優(yōu)。

-2. 計算時間復雜度基本方法

找出語句頻度最大的語句（也就是執(zhí)行次數(shù)最多的語句）。

執(zhí)行次數(shù)表示為關(guān)于問題規(guī)模n的某個函數(shù)f(n)。

取其數(shù)量級(最高次冪)。

-3. 算法的時間復雜度分析舉例
例1.

x=0, y=0; #執(zhí)行1次 for(int k=0; k<n; k++) #從0～n，結(jié)束循環(huán)要多判斷一次，所以執(zhí)行n+1次x++; #從0～n，執(zhí)行n次 for(int i=0; i<n; i++) #執(zhí)行n+1次for(int j=0; j<n; j++) #外層沒執(zhí)行一次，內(nèi)層執(zhí)行n+1次，所以n(n+1)次y++; #n乘以n次

上述代碼，數(shù)量級最大的為二次方，所以T(n)=O(n*2)

例2.

例3.

例4.

1.4.4 算法的空間復雜度

…持續(xù)修改完善中

總結(jié)

以上是生活随笔為你收集整理的第1章 绪论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。