第一章：緒論
1.1什么是數(shù)據(jù)結(jié)構(gòu)
1.2基本概念與術(shù)語
1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)
1.4算法與算法分析
1.1什么是數(shù)據(jù)結(jié)構(gòu)
定義：數(shù)據(jù)結(jié)構(gòu)(data structure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
基本的數(shù)據(jù)結(jié)構(gòu)：
? (1) 集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，沒有其他關(guān)系；
? (2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對一個(gè)的關(guān)系;(一對一)
? (3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系;(一對多)
? (4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對多個(gè)的關(guān)系(多對多)
1.2 基本概念和術(shù)語
數(shù)據(jù)(data)：是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱。對計(jì)算機(jī)科學(xué)而言，數(shù)據(jù)的含義極為廣泛，如圖像、聲音等都可以通過編碼而歸于數(shù)據(jù)的范疇。
數(shù)據(jù)元素(data element)：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(data item)組成，例如把一本書的目錄作為一個(gè)數(shù)據(jù)元素，書目錄信息中的每一項(xiàng)為一個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。
數(shù)據(jù)對象(data object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集，例如整數(shù)數(shù)據(jù)對象是集合N={0,±1,±2,±,3±,4……},字母字符數(shù)據(jù)對象是集合C={A,B,C,D……,Z};
數(shù)據(jù)結(jié)構(gòu)(data structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)
抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。
抽象數(shù)據(jù)類型 rectangle(矩形) 的表示和實(shí)現(xiàn)(C++方式)。
class rectangle {
public:
int w,h; //成員變量，寬和高
void init (int w_,int h_); //成員函數(shù)，設(shè)置寬高
int area(); //成員函數(shù)，求面積
int perimeter(); //成員函數(shù)，求周長
}
1.4算法和算法分析
什么是算法
算法(algorithm)是對特定問題求解步驟的一種，描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作；此外，一個(gè)算法還具有下列5個(gè)重要特性：
(1):有窮性 一個(gè)算法必須總是(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。
(2):確定性 算法中每一條指令必須有確切的含義，讀者理解時(shí)不會產(chǎn)生二義性。并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出。
(3):可行性 一個(gè)算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。
(4):輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對象的集合。
(5):輸出 一個(gè)算法有一個(gè)或多個(gè)的輸出，這些輸出是同輸入有著某些特定關(guān)系的量。
算法設(shè)計(jì)的要求
通常一個(gè)”好”的算法應(yīng)該考慮到以下目標(biāo)。
(1):正確性 算法應(yīng)當(dāng)滿足具體問題的需求。通常一個(gè)大型問題的需求，要以特定的規(guī)格說明方式給出，而一個(gè)實(shí)習(xí)問題或練習(xí)題，往往就不那么嚴(yán)格，目前多數(shù)是用自然語言描述需求，它至少應(yīng)當(dāng)包括對于輸入、輸出和加工處理等的明確的無歧義性的描述。設(shè)計(jì)或選擇的算法應(yīng)當(dāng)能正確地反映這種需求；否則，算法的正確與否的衡量準(zhǔn)則就不存在了。
“正確”一詞的含義在通常的用法中有很大差別，大體可分為以下4個(gè)層次；
a.程序不含語法錯(cuò)誤；
b.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；
c.程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；
d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。
顯然，達(dá)到d層意義下的正確是極為困難的，所有不同輸入數(shù)據(jù)的數(shù)量非常大，逐一驗(yàn)證的方法是不現(xiàn)實(shí)的，對于大型軟件需要進(jìn)行專業(yè)測試，而一般情況下，通常以c層意義的正確性作為衡量一個(gè)程序是否合格的標(biāo)準(zhǔn)
（2):可讀性 算法主要是為了人的閱讀與交流，其次才是機(jī)器執(zhí)行?？勺x性好有助于對算法的理解；晦澀難懂的程序易于隱藏較多錯(cuò)誤，難以調(diào)試和修改。
(3):健壯性 當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。
(4):效率與低存儲量需求 通俗地說，效率指的是算法執(zhí)行的時(shí)間，對于同一個(gè)問題如果有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高。存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。效率與低存儲量需求這兩者都與問題的規(guī)模有關(guān)。就像求100個(gè)人的平均分與求1000個(gè)人的平均分所花的執(zhí)行時(shí)間或運(yùn)行空間顯然有一定的差別。
算法效率的度量
算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。而度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法。
(1)事后統(tǒng)計(jì)的方法 因?yàn)橛?jì)算機(jī)內(nèi)部都有計(jì)時(shí)功能，有的甚至可以精確到毫秒級，不同算法的程序可通過一組或若干組相同的統(tǒng)計(jì)數(shù)據(jù)以分辨優(yōu)劣。但這種方法有兩個(gè)缺陷:一是必須運(yùn)行依據(jù)算法編制的程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。因此人們常常用另一種事前分析估值的方法。
(2)事前分析估值的方法 一個(gè)高級程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素:
① 依據(jù)的算法選用何種策略；
② 問題的規(guī)模，例如求100以內(nèi)還是1000以內(nèi)的素?cái)?shù)；
③ 書寫程序的語言，對于同一個(gè)算法，實(shí)現(xiàn)語言的級別越高，執(zhí)行效率就越低；
④ 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；
⑤ 機(jī)器執(zhí)行指令的速度；
時(shí)間復(fù)雜度
顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，效率均不同。這表明使用絕對的時(shí)間單位衡量算法的效率時(shí)不合適的。拋開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模(通常用整數(shù)量n表示)，或者說，它是問題規(guī)模的函數(shù)。
一個(gè)算法是由控制結(jié)構(gòu)(順序、分支和循環(huán)3種)和原操作(指固有數(shù)據(jù)類型的操作)構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果，為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題(或算法類型)來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)算法的時(shí)間度量記作:
它表示隨問題規(guī)模n增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱做算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。
顯然，被稱做問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同，語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)，例如，下下列3個(gè)程序中:
這三個(gè)程序段的時(shí)間復(fù)雜度分別為O(1)，O(n)，O(n2)。
一般情況下，對一個(gè)問題(或一類算法)只需選擇一種基本操作來討論算法的時(shí)間復(fù)雜度即可，有時(shí)也需要同時(shí)考慮幾種基本操作，甚至可以對不同的操作賦予不同的權(quán)重值，以反映執(zhí)行不同操作所需的相對時(shí)間，這種做法便于綜合比較解決同一問題的兩種完全不同的算法。
由于算法時(shí)間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率，則在難以精確計(jì)算基本操作執(zhí)行次數(shù)(或語句頻度)的情況下，只需要求出它關(guān)于n的增長率或階即可。例如:
++x執(zhí)行的頻度表達(dá)式應(yīng)該是(n-1)(n-2)/2；n2是其增長最快的項(xiàng)，所以其時(shí)間復(fù)雜度為O(n2) 。
算法的存儲空間需求
類似算法的時(shí)間復(fù)雜度，我們以空間復(fù)雜度作為算法所需存儲空間的度量，記作:
其中n為問題的規(guī)模大小，一個(gè)上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所使用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外空間，否則應(yīng)同時(shí)考慮輸入本身所需空間(和輸入數(shù)據(jù)的表示形式有關(guān))。若額外空間對于輸入數(shù)據(jù)來說是常數(shù)，則稱此算法為原地工作。如果所占空間依賴于特定的輸入，則除特別指明外，均按最壞情況來分析。
