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

1.1.1.基本概念和術(shù)語(yǔ)

-1.數(shù)據(jù)

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

數(shù)據(jù)是計(jì)算機(jī)程序加工的原料。

-2. 數(shù)據(jù)元素

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常作為一個(gè)整體進(jìn)行考慮和處理。

一個(gè)數(shù)據(jù)元素可由若干數(shù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。

例如，學(xué)生記錄就是一個(gè)數(shù)據(jù)元素，學(xué)號(hào)、姓名、性別等數(shù)據(jù)項(xiàng)組成。

-3. 數(shù)據(jù)對(duì)象

數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

例如，整數(shù)數(shù)據(jù)對(duì)象是集合 N= {0,±1,±2,…}。

-4. 數(shù)據(jù)類(lèi)型

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

1) 原子類(lèi)型。其值不可再分的數(shù)據(jù)類(lèi)型。

2) 結(jié)構(gòu)類(lèi)型。其值可以再分解為若干成分(分量)的數(shù)據(jù)類(lèi)型。

3) 抽象數(shù)據(jù)類(lèi)型。抽象數(shù)據(jù)組織及與之相關(guān)的操作。

-5. 數(shù)據(jù)結(jié)構(gòu)

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

在任何問(wèn)題中，數(shù)據(jù)元素都不是孤立存在的，它們之間存在某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱(chēng)為結(jié)構(gòu)(Structure)。

數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。

數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。

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

1.數(shù)據(jù)的邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，即從邏輯關(guān)系上描述數(shù)據(jù)。

它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的邏輯結(jié)構(gòu)分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)，線(xiàn)性表是典型的線(xiàn)性結(jié)構(gòu)；

集合、樹(shù)和圖是典型的非線(xiàn)性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類(lèi)如下所示。

<數(shù)據(jù)的邏輯結(jié)構(gòu):<線(xiàn)性結(jié)構(gòu)>,<非線(xiàn)性結(jié)構(gòu)>>

-<線(xiàn)性結(jié)構(gòu):<一般線(xiàn)性表>,<受限線(xiàn)性表>,<線(xiàn)性表推廣>>

-<非線(xiàn)性結(jié)構(gòu):<集合>,<樹(shù)形結(jié)構(gòu)>,<圖狀結(jié)構(gòu)>>

--<受限線(xiàn)性表：<棧>,<隊(duì)列>,<串>>

--<線(xiàn)性表推廣：<數(shù)組>>

--<樹(shù)形結(jié)構(gòu)：<一般樹(shù)>,<二叉樹(shù)>>

--<圖狀結(jié)構(gòu)：<有向圖>,<無(wú)向圖>>

2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱(chēng)映像),也稱(chēng)物理結(jié)構(gòu)。

它包括數(shù)據(jù)元素的表示和關(guān)系的表示。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)的邏輯結(jié)構(gòu)，它依賴(lài)于計(jì)算機(jī)語(yǔ)言。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。

-順序存儲(chǔ)。

把邏輯上相鄰的元素存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元中， 元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。

其優(yōu)點(diǎn)是可以實(shí)現(xiàn)隨機(jī)存取，每個(gè)元素占用最少的存儲(chǔ)空間；

缺點(diǎn)是只能使用相鄰的一整塊存儲(chǔ)單元，因此可能產(chǎn)生較多的外部碎片。

【簡(jiǎn)言之：不會(huì)會(huì)產(chǎn)生額外空間的占用，但是會(huì)產(chǎn)生碎片化存儲(chǔ)。】

-鏈?zhǔn)酱鎯?chǔ)。

不要求邏輯上相鄰的元素在物理位置上也相鄰，借助指示元素存儲(chǔ)地址的指針來(lái)表示元素之間的邏輯關(guān)系。

其優(yōu)點(diǎn)是不會(huì)出現(xiàn)碎片現(xiàn)象, 能充分利用所有存儲(chǔ)單元；

缺點(diǎn)是每個(gè)元素因存儲(chǔ)指針而占用額外的存儲(chǔ)空間，且只能實(shí)現(xiàn)順序存取。

【簡(jiǎn)言之：會(huì)避免碎片化存儲(chǔ)，但是會(huì)產(chǎn)生額外空間的占用。】

-索引存儲(chǔ)。

在存儲(chǔ)元素信息的同時(shí)，還建立附加的索引表。

索引表中的每項(xiàng)稱(chēng)為索引項(xiàng)，索引項(xiàng)的一般形式是（關(guān)鍵字，地址）。

其優(yōu)點(diǎn)是檢索速度快；

缺點(diǎn)是附加的索引表額外占用存儲(chǔ)空間。

另外，增加和刪除數(shù)據(jù)時(shí)也要修改索引表，因而會(huì)花費(fèi)較多的時(shí)間。

【簡(jiǎn)言之：也會(huì)避免碎片化存儲(chǔ)，檢索速度快，但是會(huì)因?yàn)樗饕淼慕⒍a(chǎn)生額外空間的占用。

增加和刪除數(shù)據(jù)時(shí)也要修改索引表，在修改和刪除上浪費(fèi)時(shí)間，但是查詢(xún)比較快。】

-散列存儲(chǔ)。

根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址，又稱(chēng)哈希（Hash）存儲(chǔ)。

其優(yōu)點(diǎn)是檢索、增加和刪除結(jié)點(diǎn)的操作都很快；

缺點(diǎn)是若散列函數(shù)不好，則可能出現(xiàn)元素存儲(chǔ)單元的沖突，而解決沖突會(huì)增加時(shí)間和空間開(kāi)銷(xiāo)。

【簡(jiǎn)言之：修改和刪除和查詢(xún)都很快，但是依賴(lài)散列函數(shù)的優(yōu)化性，若優(yōu)化性不好會(huì)出現(xiàn)數(shù)據(jù)存儲(chǔ)沖突?！?/p>

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

施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)。

運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的，指出運(yùn)算的功能；

運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的，指出運(yùn)算的具體操作步驟。

1.2.算法和算法的基本概念

1.2.1.算法的基本概念

算法(Algorithm)是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個(gè)或多個(gè)操作。

此外，一個(gè)算法還具有下列5個(gè)重要特性：

(1).有窮性。一個(gè)算法必須總在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。

(2).確定性。算法中每條指令必須有確切的含義，對(duì)于相同的輸入只能得出相同的輸出。

(3).可行性。算法中描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。

(4).輸入。一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。

(5).輸出。一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是與輸入有著某種特定關(guān)系的量。

通常，設(shè)計(jì)一個(gè)“好"的算法應(yīng)考慮達(dá)到以下目標(biāo)：

(1).正確性。算法應(yīng)能夠正確地解決求解問(wèn)題。

(2).可讀性。算法應(yīng)具有良好的可讀性，以幫助人們理解。

(3).健壯性。輸入非法數(shù)據(jù)時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。

(4).高效率與低存儲(chǔ)量需求。效率是指算法執(zhí)行的時(shí)間，存儲(chǔ)量需求是指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間，這兩者都與問(wèn)題的規(guī)模有關(guān)。

1.2.2.算法效率的度量

算法效率的度量是通過(guò)時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)描述的。

1.時(shí)間復(fù)雜度

一個(gè)語(yǔ)句的頻度是指該語(yǔ)句在算法中被重復(fù)執(zhí)行的次數(shù)。

算法中所有語(yǔ)句的頻度之和記為T(mén)(n),它是該算法問(wèn)題規(guī)模n的函數(shù)，

時(shí)間復(fù)雜度主要分析T(n)的數(shù)量級(jí)。

算法中基本運(yùn)算(最深層循環(huán)內(nèi)的語(yǔ)句)的頻度與T(n)同數(shù)量級(jí)，

因此通常采用算法中基本運(yùn)算的頻度f(wàn)(n)來(lái)分析算法的時(shí)間復(fù)雜度。

因此，算法的時(shí)間復(fù)雜度記為T(mén)(n) = O(f(n)),【例如：例如:f(n) = an^3 + bn^2 + cn的時(shí)間復(fù)雜度為O(n3).】

式中，O的含義是T(n) 的數(shù)量級(jí)，其嚴(yán)格的數(shù)學(xué)定義是：

若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，

則存在正常數(shù)C和n0,使得當(dāng)n≥n0時(shí)，都滿(mǎn)足0≤T(n)≤Cf(n),

算法的時(shí)間復(fù)雜度不僅依賴(lài)于問(wèn)題的規(guī)模n,也取決于待輸入數(shù)據(jù)的性質(zhì)(如輸入數(shù)據(jù)元素的初始狀態(tài))。

例如，在數(shù)組A[0...n-1]中，查找給定值k的算法大致如下：

(1)i=n-1;

(2)while(i>=0&&(A[i]!=k))

(3) i--;

(4)return i;

該算法中語(yǔ)句3 (基本運(yùn)算)的頻度不僅與問(wèn)題規(guī)模”有關(guān)，而且與輸入實(shí)例中A的各元素的取值及k的取值有關(guān)：

若A中沒(méi)有與k相等的元素，則語(yǔ)句3的頻度f(wàn)(n) =n。

若A的最后一個(gè)元素等于k,則語(yǔ)句3的頻度f(wàn)(n) =常數(shù)0。

最壞時(shí)間復(fù)雜度是指在最壞情況下，算法的時(shí)間復(fù)雜度。

平均時(shí)間復(fù)雜度是指所有可能輸入實(shí)例在等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。

最好時(shí)間復(fù)雜度是指在最好情況下，算法的時(shí)間復(fù)雜度。

一般總是考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。

在分析一個(gè)程序的時(shí)間復(fù)雜性時(shí)，有以下兩條規(guī)則：

(a).加法規(guī)則

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))

(b).乘法規(guī)則

T(n)=T1(n)×T2(n)=O(f(n))×O(g(n)=O({f(n)×g(n))

常見(jiàn)的漸近時(shí)間復(fù)雜度為

O(1)<O(log_2_n)<O(n)<O(n(log_2_n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

2.空間復(fù)雜度

算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它是問(wèn)題規(guī)模n的函數(shù)。記為

S(n)= O(g(n))

一個(gè)程序在執(zhí)行時(shí)除需要存儲(chǔ)空間來(lái)存放本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，

還需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。

若輸入數(shù)據(jù)所占空間只取決于問(wèn)題本身，和算法無(wú)關(guān)，則只需分析除輸入和程序之外的額外空間。

算法原地工作是指算法所需的輔助空間為常量，即O(1)。