數據結構：第1章 緒論

1數據結構2課程相關信息教材：《數據結構》，劉大有等編著，高等教育出版社，2010年9月.參考書目：清華大學出版社、高等教育出版社和機械出版社等出版的數據結構教材.教學形式：理論＋實驗考核方式：考試3參考書

1、《數據結構》

嚴蔚敏、吳偉民編著清華大學出版社。

2、《數據結構》

（用面向對象方法與C++描述）

殷人昆、陶永雷等編著清華大學出版社4教學計劃第一章緒論(算法分析基礎)第二章線性表、堆棧、隊列第三章數組、字符串第四章樹第五章圖第六章遞歸第七章排序第八章查找5第一章緒論1.1為什么要學習數據結構1.2數據結構概念1.3算法1.4算法的正確性證明1.5算法分析基礎61.1為什么學習數據結構計算機學科中一門重要的專業(yè)基礎課。提高計算機的工作效率。是程序設計的重要基礎；是許多計算機專業(yè)課的基礎，如算法分析、編譯原理、操作系統(tǒng)、數據庫系統(tǒng)等。7最短路徑算法在物流配送問題中的應用；樹結構在數據挖掘領域中的應用；散列技術在數據加密領域中的應用；查找技術在數據庫領域中的應用；倒排文件、查找算法在搜索引擎中的應用。8第一章緒論1.1為什么要學習數據結構1.2數據結構概念1.3算法1.4算法的正確性證明1.5算法分析基礎9[例]

個人書庫管理程序所要處理的數據可能是如下的表格。101.2數據結構概念

1.數據數據是對象的表示。計算機程序要處理的“原料”，它可以被計算機識別、存儲和加工處理。包括：數值、文字、表格、圖像、聲音、源程序等。11數據元素是組成數據的基本單位。在程序中通常把一個數據元素作為一個整體來考慮和處理。數據元素還可被稱為結點或頂點。例如，在上表中，把其中的每一行（代表一本書）作為一個基本單位來考慮。12數據項一個數據元素含有若干個數據項。例如，在上表數據中，每個數據元素由登錄號、書號、書名、作者、出版社和價格六個數據項構成。數據項是構成數據的最小單位。13

[例]電話號碼薄的查詢問題。

((a1，b1),(a2，b2),…(an，bn))

張…王…張王…索引表14

[例2]

學生自然情況查詢問題。。。?！?吉林大學信息部計算機….軟件硬件23012302。。。通信152.邏輯結構數據的邏輯結構是指數據元素及其間的邏輯關系。在個人書庫管理程序中，各數據元素之間在邏輯上有一種線性關系，它指出了10個數據元素在表中的排列順序。16有些書也將數據的邏輯結構分為集合、線性結構、樹和圖等四種類型。其中，集合的特點是：結構中的數據元素之間除了同屬于一個集合的關系外，別無其他關系。集合線性結構樹圖17邏輯結構的形式化表示邏輯結構表示為二元組L=(N,R)，——N是結點的有限集合——R是N上的關系集合18例

L=(N,R)，

N={a,b,c,d,e},R={r}，

r={<a,b>,<b,c>,<c,d>,<d,e>}

abcde

若a，b∈N，且關系<a,b>r，則稱a是b的前趨結點，稱b是a的后繼結點，稱a和b是相鄰結點；如果不存在aN，使<a,b>r，則稱b為始結點；如果不存在bN，使<a,b>r，則稱a為終結點；既非始結點又非終結點的結點被稱為內結點。19[例]L=(N,R)，N={k1,k2,…,k9},R={r}，r={<k1,k2>,<k1,k3>,<k1,k4>,<k1,k7>,<k1,k8>,<k4,k5>,<k4,k6>,<k8,k9>}k1k2k3k4k7k8k5k6k920邏輯結構的分類線性結構

結構中有且僅有一個始結點和一個終結點，始結點只有一個后繼結點，終結點只有一個前趨結點，每個內結點有且僅有一個前趨結點和一個后繼結點。非線性結構（樹、圖）

結構中的結點可能有多個前趨結點和多個后繼結點。213．存儲結構數據的存儲結構是指數據的邏輯結構在計算機中所需的存儲空間、空間的構成結構及對該存儲結構的訪問方式等的總稱。數據的存儲結構是建立一種由邏輯結構到存儲空間的映射。個人書庫數據，在計算機中可以有多種存儲表示。如，可以表示成數組，存放在內存中；也可以表示成文件，存放在磁盤上，等等。

22存儲結構分類1）順序存儲結構把一組結點存放在地址相鄰的存儲單元里，結點間的邏輯關系用存儲單元的自然順序關系表達。A[2]308306304302A[0]A[1]A[3]23232）鏈接存儲結構在結點的存儲結構中附加指針字段，兩個結點的邏輯后繼關系用指針的指向來表達。(a)可用存儲空間free

a0

a2

a1

a3firstlast

24存儲結構分類3）索引存儲結構索引表把整數索引值映射到結點的存儲地址。索引表存儲一串指針，每個指針指向存儲區(qū)域的一個數據結點。0231V0V1V2V325存儲結構分類4）散列存儲結構適用于大數據量、高速檢索的場合。索引存儲的一種延伸和擴展，利用散列函數進行索引值的計算，并通過索引表求出結點的指針地址。0231V0V1V2V3

f(v)

v26存儲結構總結順序、鏈接、索引和散列存儲結構，可以單獨使用，也可以組合使用。存儲結構要正確反映邏輯結構，并便于操作。274.對數據的操作插入刪除修改排序查找28

數據結構的定義：數據結構就是研究數據的邏輯結構和物理結構以及他們之間的關系，并對這種結構定義相適應的運算，設計出相應的算法。5.數據結構的概念29數據結構的概念按某種邏輯關系將一批數據元素組織起來；按一定的存儲方式把它們存儲起來；在數據上定義需要施加的操作。30數據結構課程的目的從對問題抽象和求解的角度來學習常用的數據結構，闡明其內在的邏輯關系和在計算機中的存儲表示，以及刻畫施加于其上之各種操作的算法。學習上述理論知識，綜合運用相關知識，再結合上機實踐，使我們具備求解比較復雜的問題的能力，即掌握問題求解建模，選擇恰當數據結構，或構造新的數據結構，設計較優(yōu)算法，證明算法（或算法之關鍵步驟）正確性，分析算法的時空復雜性，對算法編程、調試等能力。

31數據類型：是一個值的集合以及在這些值上定義的一組操作的集合的總稱。抽象數據類型：由一組數據結構和在該組數據結構上的一組操作所組成。32第一章緒論1.1為什么要學習數據結構1.2數據結構的概念1.3算法1.4算法的正確性證明1.5算法分析基礎33計算機解決問題的步驟：①從具體問題中抽象出一個適當的數學模型；

②設計解此模型的方法；

③編出程序、進行測試、調試，直至得到最終解答。計算機處理問題，以適當的數據結構為基礎，制定出的切實可行的方法和步驟——計算機算法。1.3算法

1.算法的概念34計算機算法與數據結構密切相關:算法無不依附于具體的數據結構，數據結構直接關系到算法的選擇和效率。對數據的操作是由計算機來完成，這就要設計相應的插入、刪除和修改等算法。1976年，沃斯提出：算法+數據結構=程序算法與數據結構的關系35算法由有限條指令構成，規(guī)定了解決特定問題的一系列操作。算法具有5個特性：

(1)有限性：一個算法在執(zhí)行有限步后必然終止。

(2)確定性：算法中的每條指令都必須是清楚的，指令無二義性，相同的輸入必須有相同的輸出。

(3)輸入：具有0個或0個以上由外界提供的量。

(4)輸出：產生1個或多個結果。

(5)可行性：每條指令都十分基本，原則上可由人僅用筆和紙在有限的時間內也能完成。算法與程序的區(qū)別

①表現形式不同。 ②是否具備有窮性。

36算法可以用自然語言、數學語言、程序設計語言或約定的任何符號語言來描述。如類Pascal語言、C語言或偽代碼等。ADL語言直觀方便。

2.算法描述語言——ADL

37算法描述語言ADL的格式①算法<標識符>(變量i1,…,變量im.變量j1,…,變量jn)

//單行注釋（或/*…*/多行注釋）

<步驟名><步驟號>.

[本步驟的概括說明]

<操作1>

…

<操作J>

<步驟名><步驟號>.

[本步驟的概括說明]

語句序列.▌38②表達式

●算術運算符

+,-,*,/,DIV,MOD,

,

●關系運算符

=、≠、<、>、、

●邏輯運算符

AND，OR，NOT●

邏輯常量

true，false

●集合運算符

∩，∪，（差），，③

語句

●每條語句都用“.”作為結束符

●賦值語句

ab.ab.abc.

39

●條件語句1)IF<邏輯表達式>THEN

(語句1.….語句m).2)IF<邏輯表達式>THEN

(語句1.….語句m).ELSE(語句1.….語句n).3)CASEDO

(<邏輯表達式1>:(語句1.….語句n1).…

<邏輯表達式m>:語句1.….語句nm)).

40●循環(huán)語句1)WHILE<邏輯表達式>DO

(語句1.…

.語句n).2)FOR<變量>=<算術表達式1>TO

<算術表達式2>STEP<算術表達式3>DO

(語句1.….語句n).3)FOR<變量>∈<集合>DO

(語句1.….語句n).

41●轉移語句

GOTO(<步驟名><步驟號>).●

EXIT語句

結束本層WHILE或者FOR循環(huán)的執(zhí)行

●

RETURN語句

指出算法執(zhí)行的終點④其它

●輸入語句：READ(x)//讀取輸入值賦給變量x

●

輸出語句：PRINT(<輸出信息>)42[例]A是一個含有n個不同元素的實數數組，給出求A之最大和最小元素的算法。

算法SM(A,n.max,min)SM1.[初始化]max←min←A[1].SM2.[比較]FORI=2TOnDO//求最大和最小元素

(IFA[I]>maxTHENmax←A[I].IFA[I]<minTHENmin←A[I]).▌43ADL的特點書寫簡便不必考慮過多

程序設計語言的細節(jié)例：交換a和b的值易于理解不同編程習慣的人交流算法不必考慮與算法無關的內容（開發(fā)及運行環(huán)境、編譯狀態(tài)）ADLC++a

binttemp;inta;intb;temp=a;a=b;b=temp;443.

算法的評價準則評估算法性能的5條準則正確性時間復雜性占用空間可讀性魯棒性

451)正確性說一個算法是正確的，如果對于一切合法的輸入數據，該算法執(zhí)行有限時間都能產生正確的結果。具體包括兩方面：

一是解決問題的方法；

二是實現這一方法的一系列指令(步驟、語句)。證明相關的引理和定理，以確認一個算法所用方法的正確性；證明一系列語句確實做了符合規(guī)定的操作.

46

語句正確性，大體可分為四個層次：①算法不含語法錯誤；②算法對于幾組輸入數據能夠得出滿足要求的結果；③算法對于精心選擇的典型、苛刻而帶有刁難性的幾組數據，能夠得出滿足要求的結果；④算法對一切合法的輸入數據，都能產生滿足要求的結果。472)時間復雜性算法的實際執(zhí)行時間是不是時間復雜性的理想度量呢?不是。其原因是：算法的實際執(zhí)行時間依賴于機器。同一個算法在不同機器上的執(zhí)行時間不一定相同。算法的實際執(zhí)行時間還依賴于編寫算法的程序設計語言。一個用C或Pascal編寫的算法可能要比用BASIC語言編寫的算法快20倍。483)占用的存儲空間包括存儲算法本身所占用的存儲空間，算法的輸入、輸出數據所占用的存儲空間和算法運行過程中臨時占用的存儲空間。算法在運行過程中所占用的存儲空間的大小被定義為算法的空間復雜性。它包括局部變量所占用的存儲空間和系統(tǒng)為了實現遞歸所使用的堆棧這兩個部分。算法的空間復雜性一般以數量級的形式給出。494)可讀性最簡單、最直接的算法盡管不一定是最有效的，但卻具有良好的可讀性。可讀性好的算法其正確性證明比較容易（即其正確性易于保證），同時便于設計、修改、閱讀和調試，可見可讀性是十分重要的。對于那些需經常使用的算法來說，高效率比可讀性更為重要。505)魯棒性對有缺失、有噪聲或有錯誤的輸入數據，算法應具有較強的應付能力。如，能對輸入數據語法語義檢驗、提出修改錯誤的建議并提供重新輸入的機會。51

1.4

算法的正確性證明對于一個算法來說正確性是前提，也是最重要的。對明顯是正確的算法，可通過上機調試驗證其正確性。調試用的數據要精心挑選，以保證算法對“所有的”數據都是正確的;只要調試找出一組數據使算法失敗(即計算結果不正確)，就能否定整個算法的正確性;算法的正確性一般通過數學方法進行推理證明，常用的數學方法除了直接證明法外，還有反證法和數學歸納法。52第一章緒論1.1為什么要學習數據結構1.2數據結構的概念1.3算法1.4算法的正確性證明1.5算法分析基礎53

Testing(測試)

BlackBoxMethods黑盒法側重測試程序的功能，不考慮程序是如何實現的，即代碼結構。設計測試用例，檢查能否得到預想的結果。WhiteBoxMethods白盒法側重測試程序的代碼結構StatementCoverage語句覆蓋:使程序中的每一條語句都至少執(zhí)行一次。DecisionCoverage分支覆蓋：使程序中的每一個分枝都至少執(zhí)行一次。54

1.反證法1)要證明定理T是正確的，首先假定T是錯誤的2)使用正確的命題和正確的推理規(guī)則進行推理,若出現下列條件之一，就會得出矛盾的結果：①與已知條件矛盾②與公理矛盾③與證明過的定理矛盾④自相矛盾3)由此推出定理T是正確的。55[例]

證明沒有最大的整數證明：用反證法。(1)反面假設：假設存在一個最大整數，記為N.(2)由假設推出矛盾：設P

N

1，因為P

是兩個整數的和，所以P也是整數，且P

N.與N是最大整數矛盾。(3)肯定原來的結論：因此，沒有最大的整數。證畢。562.數學歸納法數學上證明與自然數N有關的命題的一種特殊方法，它主要用來研究與正整數有關的數學問題。數學歸納法依靠假設的事實來證明定理，是用“有限”步驟解決“無限”問題的一種嚴格證明方法。57數學歸納法：設T是一個定理，

n是T中的正參數.數學歸納法表明，如果下面兩個條件為真，則對于參數n的任何值，T都是正確的：(1)基礎歸納：n

c

時，T成立。(2)歸納步驟：如果n=k

1時T成立，則n=k時T也成立。其中，c是一個較小的常量，n

c.通常，證明初始歸納很容易，而證明歸納步驟很難。

58強歸納法設T是一個定理，

n是T中的正參數.數學歸納法表明，如果下面兩個條件為真，則對于參數n的任何值，T都是正確的：(1)基礎歸納：n

c

時，T成立。(2)歸納步驟：如果n=k

1時T成立，則n=k時T也成立(2)歸納步驟：如果對于所有的k(c

k

n)T都成立，則T對于n

也成立。59例:

證明由遞歸關系式T(n)

T(n

1)1，T(1)0，可推出T(n)n1，其中，n

1.證明：基礎歸納：n

1時，T(1

)1

10，結論成立。歸納步驟：假設T(n1)

n2成立（歸納假設）往證

T(n)

n

1成立。由遞歸關系式可知：

n

1時，有T(n)

T(n

1)1再由歸納假設：

T(n)

T(n

1)1

n

21

n1由數學歸納法推出T(n)

n1成立，證畢?60第一章緒論1.1為什么要學習數據結構1.2數據結構的概念1.3算法1.4算法的正確性證明1.5算法分析基礎61

1.5算法分析基礎在假定算法正確的前提下，用時間復雜性作為評價算法優(yōu)劣的標準。一個算法的時間復雜性是指該算法所執(zhí)行的基本運算的次數。最優(yōu)算法的定義：

某算法A為最優(yōu)，當且僅當解決同一領域同一問題的所有算法集合SA(A∈SA)中沒有一個算法執(zhí)行的基本運算次數比算法A更少。

62●決定運行時間的因素：①、問題的規(guī)模。②、對源程序進行編譯所需時間。③、機器執(zhí)行指令的速度。④、程序中指令重復執(zhí)行的次數。

●頻度：算法執(zhí)行一次，某一語句實際被執(zhí)行的次數，叫該語句在此算法中的頻度。

631.算法時間復雜性的分析方法

例

A是一個含有n個不同元素的實數數組，給出求A之最大和最小元素的算法。

算法SM(A,n.max,min)SM1[初始化]max←min←A[1].

SM2[比較]FORi=2TOnDO(IFA[i]>maxTHENmax←A[i].IFA[i]<minTHENmin←A[i]).?算法SM的時間復雜性為2(n-1)。64

[例]實數數組R由n個元素組成，給定一個實數K，試確定K是否是R的元素。

算法F(R,n,K.i)F1[初始化]i←1.F2[比較]WHILEi≤nDO(IFR[i]=KTHENRETURN.i←i+1).?

最少比較次數：1

最大比較次數：n65定義設一個領域問題的輸入規(guī)模為n，Dn是該領域問題的所有輸入的集合，任一輸入IDn，P(I)是I出現的概率，且滿足

P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本運算次數。我們定義該算法的期望復雜性（即該算法的平均復雜性

）為：

E(n)={P(I)*T(I)}

該算法的最壞復雜性為：

W(n)=max{T(I)}

該算法的最好復雜性為：

W(n)=min{T(I)}66R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]52012730402516K=R[i]q/nK!=R[i]1-q上例中，設q(0≤q≤1)為K在R中的概率q67通過計算我們可以得到算法F的期望復雜性為

E(n)=∑{P(I)*T(I)}

=(q/n)*1+(q/n)*2+…+(q/n)*n+(1-q)*n

n項1項

=q(n+1)/2+(1-q)n

如果已知K在R中，即q=1，則有

E(n)=(n+1)/2由算法F很容易看出該算法的最壞復雜性為

W(n)=max{T(i)|1≤i≤n+1}=n68例

算法SM的改進算法BS算法BS（A,i,j.fmax,fmin）/*在數組A的第i至第j個元素間尋找最大和最小

元素，已知ij;假定A中元素互異*/BS1.[遞歸出口]IFijTHEN(fmaxfminA[i].RETURN.)IFij1THEN

(IFA[i]A[j]THEN(fmaxA[j].fminA[i]).ELSE(fmaxA[i].fminA[j]).RETURN).BS2.[取中值]mid

(ij)/2

BS3.[遞歸調用]

BS(A,i,mid.Gmax,gmin).BS(A,mid1,j.hmax,hmin).BS4.[合并]

fmaxmax{gmax,hmax}. fminmin{gmin,hmin}.?69i=1mid=4

j=8

A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]52012730402516i=1mid=2j=4i=5mid=6

j=8

A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]5

2012730402516i=1j=2i=3j=4A[1]A[2]A[3]A[4]5

20

127i=5j=6i=7j=8A[5]A[6]A[7]A[8]30

40

2516算法SM的改進70BS(A,i1,j8.fmax,fmin)BS1.BS2.mid4.BS3.BS(A,i1,j4.gmax,gmin)BS1.BS2.mid2.BS3.BS(A,i1,j2.gmax,gmin)BS1.gmax20.gmin5.RETURN.

BS(A,i3,j4.hmax,hmin)BS1.hmax12.hmin7.RETURN.BS4.gmax20.gmin5.

BS(A,i5,j8.hmax,hmin)BS1.BS2.mid6.BS3.BS(A,i5,j6.gmax,gmin)BS1.gmax40.gmin30.RETURN.

BS(A,i7,j8.hmax,hmin)BS1.hmax25.hmin16.RETURN.BS4.hmax40.hmin16.BS4.fmax40.fmin5.▌

71容易看出，BS對A[i]到A[j]的不同的輸入都有相同的基本運算次數。設T(n)表示其基本運算次數，則根據算法BS的遞歸過程，有如下的遞歸表達式：若n

是2的冪(即存在正整數k,使得n2k)則有T(n)2T(n/2)22(2T(n/4)2)24T(n/4)424(2T(n/8)2)428T(n/8)8422k1T(2)(21222k1)(3n/2)272BS與SM的比較算法SM和BS的時間復雜性均為線性，但因3n/222(n1)，故算法BS優(yōu)于算法SM.算法BS是遞歸算法，因此它的實現需要額外的輔助空間棧。73[例]

求下列各程序段時間復雜性。

①

for(i=1;i<=n;i++)

x++;

②for(j=1;j<=n;j++)

for(k=1;k<=n;k++)

x++;

●計算時間復雜度算法的計算時間＝∑個語句頻度記做T(n)

74

●算法運行時間復雜度：指某算法的基本操作次數。●基本操作次數：最里層循環(huán)體內簡單操作的執(zhí)行次數或遞歸調用的調用次數。

[例3]for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;

75確定算法基本運算次數的目的在于能比較功能相同的兩個算法之間的時間復雜性；預測隨實例特性的改變，運行時間的增減情況。在很多情況下，特別當輸入規(guī)模n較大時，確定一個算法的基本運算次數T，得到T和n之間的函數關系非常困難。算法分析中通常采用大O、大和大來漸近表示算法的基本運算次數。

2.復雜性函數的漸近表示761892年，保羅巴赫曼(PaulBachmann)提出了大O表示法，主要用于估計函數的增長速率。定義設f(n)和g(n)是正整數集到正實數集上的函數，稱f(n)是O(g(n))，當且僅當存在正的常數C和n0，使得對任意的nn0

，有f(n)

Cg(n).f和g之間關系的含義是“f(n)的階至多為g(n)”或“f至多與g增長得一樣快”.大O表示法77例

f(n)3n2是O(n).

證明：由大O的定義，存在C

3，n0

1，使得對任意的n

n0

，有

3n

23n

即f(n)

Cg(n).例

f(n)3logn

loglogn

是O(logn)

證明：由大O的定義，存在C

4，n0

2，使得對任意的n

n0

，有

3logn

loglogn

4logn

即f(n)

Cg(n).78一個算法的時間復雜性為O(g(n))，表明它的基本運算次數至多是g(n)的某個常數倍.O(1)表示算法的時間復雜性為一常數.O(n)、O(n2)、O(n3)、O(nm)和O(2n)分別表示算法時間復雜性為線性階的、平方階的、立方階的、多項式階的和指數階的，其中m

1，且m

為常數。

79定義設f(n)和g(n)是正整數集到正實數集上的函數，稱f(n)是

(g(n)),當且僅當存在正的常數C和n0

,使得對任意的nn0

，有f(n)

Cg(n).f(n)(g(n))

的含義是

f(n)的階至少為g(n)或f的增長速率不低于g

.

大表示法