數據結構與算法謝頌華whxiesonghua@163.com12數據結構課程的地位——針對非數值計算的程序設計問題，研究計算機的操作對象以及它們之間的關系和操作。——是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。關系對象關系操作數學軟件硬件對象關系操作Data_Structure=（D,R）3學時數：40學分：

2.5

教材：

嚴蔚敏等，數據結構（C語言版），清華大學出版社（配題集）

參考書：[1]（美）霍羅維茲等，《數據結構基礎（C語言版）》，清華大學出版社，2009[2]嚴蔚敏等，《數據結構(C語言版)》，人民郵電出版社，2011[3]殷人昆等，數據結構（用面向對象方法與C++描述），清華大學出版社，2002教材與參考書4內容安排章內容學時章內容學時1緒論37圖52線性表48動態存儲管理略3棧和隊列39查找44串210內部排序55數組和廣義表211外部排序略6樹和二叉樹612文件略5第1章緒論第2章線性表第3章棧和隊列

第4章串第5章數組和廣義表第6章樹和二叉樹

第7章圖第9章查找第10章排序目錄6第1章緒論討論5個問題：1.1什么是數據結構1.2學習數據結構的意義1.3數據結構涵蓋的主要內容1.4什么是抽象數據類型1.5算法效率的度量71.1什么是數據結構是相互之間存在一種或多種特定關系的數據元素的集合，表示為：（數值或非數值）Data_Structure=（D,R）——是指同一數據元素類型中各元素之間存在的關系。元素有限集關系有限集8數據(data)——所有能被計算機識別、存儲和處理的符號的集合（包括數字、字符、聲音、圖像等信息）。數據元素(dataelement)——是數據的基本單位，具有完整確定的實際意義(又稱元素、結點，頂點、記錄等）。數據項(Dataitem)——構成數據元素的項目。是具有獨立含義的最小標識單位（又稱字段、域、屬性等）。三者之間的關系：數據>數據元素>數據項例：班級通訊錄>個人記錄>姓名、年齡……數據、數據元素和數據項術語簡介：91.2學習數據結構的意義計算機內的數值運算依靠方程式，而非數值運算（如表、樹、圖等）則要依靠數據結構。

數據結構是一門學科，針對非數值計算的程序設計問題，研究計算機的操作對象以及它們之間的關系和操作等等。程序設計＝好算法＋好數據結構同樣的數據對象，用不同的數據結構來表示，運算效率可能有明顯的差異。101.3數據結構涵蓋的內容11集合結構：僅同屬一個集合線性結構:一對一（1:1)

樹結構:一對多（1:n)

圖結構:多對多(m:n)非線性線性邏輯結構可細分為4類：答：指數據元素之間的邏輯關系。即從邏輯關系上描述數據，它與數據的存儲無關，是獨立于計算機的。解釋1：什么叫數據的邏輯結構？12數據的邏輯結構分類線性結構（反映一對一的邏輯關系）邏輯特征：有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。實現：線性表非線性結構（反映一對多或多對多的邏輯關系）邏輯特征：一個結點可能有多個直接前趨和直接后繼。實現：樹、圖（或網絡）13學生成績表結點數據結構bindevetclibuser線性結構142114131211234678910315871011998745662313155樹形結構

樹二叉樹二叉排序樹15文件系統結構圖/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp16例如:在迷宮問題中,計算機之間所以能夠找到迷宮的出口,是因為人們已將搜索出口的策略事先存入計算機中.在迷宮中,每走到一處,接下來可走的通路有三條,如圖:計算機處理的這類對象之間通常不存在線性關系,若將從迷宮入口處到出口的過程中所有可能的通路都畫出來,則可以得到一棵倒長的”樹”.”樹根”是迷宮入口,”樹葉”是出口或死路.”樹”可以是某些非數值計算問題的數學模型.如下圖：現實中的問題：迷宮17入口死路死路死路死路死路死路死路死路死路死路出口死路死路死路死路18現實中的問題：計算機和人的對弈井字棋的一個格局19125643125436113318146651921

圖結構

網絡結構20現實中的問題：多叉路口交通燈的管理

在多叉路口需設幾種顏色的交通燈才能既使車輛之間不碰撞，又能達到車輛的最大流通呢？ABCDEC，E為單行道可同時通行：A->BE->C不能同時通行：E->BA->D21101582552175081092010現實中的問題：在N個城市之間建立通信網絡問題：如何使該網絡造價最低？22在應用程序中涉及到各種各樣的數據，如何在計算機中組織、存儲、傳遞數據，需要討論它們的歸類及它們之間的關系，從而建立相應的數據結構，依此實現軟件功能。綜上，描述這類非數值計算問題的數學模型不是數學方程，而是樹、表和圖之類的數據結構。因此從廣義上講，數據結構描述現實世界實體的數學模型及其上的操作在計算機中的表示和實現。23（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達式可用圖形表示為：bcaefd此結構為線性的。例：用圖形表示下列數據結構，并指出它們是屬于線性結構還是非線性結構。24d1d5d2d4d3該結構是非線性的。解：上述表達式可用圖形表示為：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}25答：物理結構亦稱存儲結構，是數據的邏輯結構在計算機存儲器內的表示（或映像）。它依賴于計算機。存儲結構可分為4大類：例：復數3.0－2.3i的兩種存儲方式：順序、鏈式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址內容法2：地址內容2字節解釋2：什么叫數據的物理結構？26存儲結構的描述雖然存儲結構涉及數據元素及其關系在存儲器中的物理位置，但我們是在高級語言的層次上討論數據結構的操作。因此我們不用具體的內存地址來描述存儲結構，而是借助于高級語言中提供的“數據類型”來描述。27答：在數據的邏輯結構上定義的操作算法。它在數據的存儲結構上實現。最常用的數據運算有5種：插入、刪除、修改、查找、排序解釋3：什么是數據的運算？281.4什么是抽象數據類型1.4.1數據類型與抽象數據類型的區別？1.4.2抽象數據類型如何定義？1.4.3抽象數據類型如何表示和實現？

討論：抽象數據類型和偽碼是學習數據結構的工具291.4.1數據類型與抽象數據類型的區別數據類型：是一個值的集合和定義在該值上的一組操作的總稱。變量的數據類型決定了如何將代表這些值的位存儲到計算機的內存中。抽象數據類型：由用戶定義，用以表示應用問題的數據模型。它由基本的數據類型構成，并包括一組相關的服務（或稱操作）。它與數據類型實質上是一個概念，但其特征是使用與實現分離，實行封裝和信息隱蔽（獨立于計算機）301.4.2抽象數據類型如何定義抽象數據類型可以用以下的三元組來表示：

ADT=（D，R，P）ADT抽象數據類型名{數據對象：<數據對象的定義>數據關系：<數據關系的定義>基本操作：<基本操作的定義>}ADT抽象數據類型名ADT常用定義格式數據對象D上的關系集D上的操作集31例：給出自然數(NaturalNumber

)的抽象數據類型定義。ADT

Natural_Number

isobjects:

一個整數的有序子集合，它開始于0，結束于機器能表示的最大整數(MAXINT)functions:

對于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,<,==,=等都是可用的服務。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUE

else返回FALSEAdd(x,y)：NaturalNumber

if(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumber

if(x<y)返回0else返回x-yEqual(x,y):Boolean if(x==y)返回TRUEelse返回FALSESuccessor(x):NaturalNumber

if(x==MAXINT)返回xelse返回x+1end

Natural_Number

321.4.3抽象數據類型如何表示和實現抽象數據類型可以通過固有的數據類型（如整型、實型、字符型等）來表示和實現。注1：它有些類似C語言中的結構體（struct)類型，但增加了相關的操作。注2：教材中用類C語言（介于偽碼和C語言之間）作為描述工具。其描述語法匯總在教材P10-11上。但上機時要用具體語言實現，如C或C++等33提示：教材中例1-6和例1-7分別給出了抽象數據類型“三元組”的定義、表示和實現，請自己先試讀一遍。當課程內容學習到50%以后，你再回頭看這個例子，會發現自己已能完全看懂了！341.5算法效率的度量1.5.1什么是算法？如何評判算法的好壞？1.5.2時間復雜度和空間復雜度如何表示？1.5.3計算舉例討論：351.5.1什么是算法？如何評判一個算法的好壞？常用時間復雜度來衡量算法的基本特性：算法評價指標：有窮性、確定性、可行性、必有輸出正確性、可讀性、健壯性、效率與低存儲量需求常用空間復雜度來衡量程序設計的實質：好算法＋好數據結構

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉換為輸出的計算步驟。4個層次36算法分析定義：為了解決某類問題而規定的一個有限長的操作序列。特性：有窮性執行有窮步，有窮時間內完成確定性每條指令的含義都必須明確,無歧義可行性算法中描述的操作都是可以通過已經實現的基本運算執行有限次實現輸入有0個或多個輸入輸出有一個或多個輸出37例子：選擇排序問題：遞增排序解決方案：逐個選擇最小數據算法框架：

for(inti=0;i<n-1;i++){//n-1趟 從a[i]檢查到a[n-1];

若最小整數在a[k],交換a[i]與a[k];}細化：SelectSort算法設計38voidselectSort(inta[],intn){//對n個整數a[0],a[1],…,a[n-1]按遞增順序排序inti,j,k,temp;for(i=0;i<n;i++) {k=i;//從a[i]查到a[n-1],找最小整數,在a[k]for(j=i+1;j<n;j++) if(a[j]<a[k])k=j; //記錄最小整數的下標k if(k!=i)//交換,最小整數移至本輪最前{temp=a[i];a[i]=a[k];a[k]=temp;}}} 39性能分析與度量算法的性能標準正確性：包括不含語法錯誤對幾組數據運行正確對典型、苛刻的數據運行正確；對所有數據運行正確可讀性效率：高效、低存儲需要（算法執行時間短，同時所占用的存儲空間小）。健壯性：當輸入非法數據時，算法也能作出適當反應，而不會出現莫名其妙的輸出結果。40算法的事前估計(1)空間復雜度度量存儲空間的固定部分

程序指令代碼的空間，常數、簡單變量、定長成分(如數組元素、結構成分、對象的數據成員等)變量所占空間可變部分

尺寸與實例特性有關的成分變量所占空間、遞歸棧所用空間、通過new和delete命令動態使用空間1.5.2時間復雜度和空間復雜度如何表示？41(2)時間復雜度度量運行時間=算法中每條語句執行時間之和。每條語句執行時間=

該語句的執行次數（頻度）*語句執行一次所需時間語句執行一次所需時間取決于機器的指令性能和速度和編譯所產生的代碼質量，很難確定。設每條語句執行一次所需時間為單位時間，則一個算法的運行時間就是該算法中所有語句的頻度之和。42一、時間復雜度:算法中語句重復執行次數的數量級就是時間復雜度。二、表示方法：T(n)=O(f(n))f(n)表示基本操作重復執行的次數，是n的某個函數，隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率屬于同一數量級；O表示f(n)和T(n)只相差一個常數倍。T(n)稱做漸進時間復雜度，簡稱時間復雜度。時間復雜度433n+2=O(n)因為3n+24nforn26*2n+n2=O(2n)因為6*2n+n27*2nforn4例：漸進符號（O）的定義：當且僅當存在一個正的常數C，使得對所有的

nn0，有f(n)Cg(n)，則：f(n)=O(g(n))44幾種時間復雜度O(1):常數時間O(log2n)：對數時間O(n)：線性時間O(nlog2n)：線性對數時間O(n2):平方時間O(n3):立方時間O(2n):指數時間上述的時間復雜度的優劣次序如下（n>=16):O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)45算法的存儲空間需求算法的空間復雜度定義為:

表示隨著問題規模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))46算法的存儲量包括:1．輸入數據所占空間2．程序本身所占空間3．輔助變量所占空間若輸入數據所占空間只取決于問題本身，和算法無關，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。47如何估算算法的時間復雜度？1.5.3計算舉例算法=控制結構+原操作（固有數據類型的操作）算法的執行時間=原操作(i)的執行次數×原操作(i)的執行時間算法的執行時間

與

原操作執行次數之和

成正比

48從算法中選取一種對于所研究的問題來說是

基本操作

的原操作，以該基本操作

在算法中重復執行的次數

作為算法運行時間的衡量準則。49例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數組存儲矩陣元素，c為a和b的乘積for(i=0;i<n;++i)

for(j=0;j<n;++j){c[i,j]=0;for(k=0;k<n;++k)c[i,j]+=a[i,k]*b[k,j];}//for}//mult基本操作:

乘法操作時間復雜度:

O(n3)50例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數序列重新排列成自小至大有序的整數序列。

}//select_sort基本操作:

比較(數據元素)操作時間復雜度:

O(n2)j=i;//選擇第i個最小元素for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;for(i=0;i<n-1;++i