數(shù)據(jù)結(jié)構(gòu)第01章概論

數(shù)據(jù)結(jié)構(gòu)與算法謝頌華whxiesonghua@163.com12數(shù)據(jù)結(jié)構(gòu)課程的地位——針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作?！墙橛跀?shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。關(guān)系對象關(guān)系操作數(shù)學(xué)軟件硬件對象關(guān)系操作Data_Structure=（D,R）3學(xué)時數(shù)：40學(xué)分：

2.5

教材：

嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社（配題集）

參考書：[1]（美）霍羅維茲等，《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語言版）》，清華大學(xué)出版社，2009[2]嚴(yán)蔚敏等，《數(shù)據(jù)結(jié)構(gòu)(C語言版)》，人民郵電出版社，2011[3]殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社，2002教材與參考書4內(nèi)容安排章內(nèi)容學(xué)時章內(nèi)容學(xué)時1緒論37圖52線性表48動態(tài)存儲管理略3棧和隊(duì)列39查找44串210內(nèi)部排序55數(shù)組和廣義表211外部排序略6樹和二叉樹612文件略5第1章緒論第2章線性表第3章棧和隊(duì)列

第4章串第5章數(shù)組和廣義表第6章樹和二叉樹

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

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

樹結(jié)構(gòu):一對多（1:n)

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

樹二叉樹二叉排序樹15文件系統(tǒng)結(jié)構(gòu)圖/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp16例如:在迷宮問題中,計(jì)算機(jī)之間所以能夠找到迷宮的出口,是因?yàn)槿藗円褜⑺阉鞒隹诘牟呗允孪却嫒胗?jì)算機(jī)中.在迷宮中,每走到一處,接下來可走的通路有三條,如圖:計(jì)算機(jī)處理的這類對象之間通常不存在線性關(guān)系,若將從迷宮入口處到出口的過程中所有可能的通路都畫出來,則可以得到一棵倒長的”樹”.”樹根”是迷宮入口,”樹葉”是出口或死路.”樹”可以是某些非數(shù)值計(jì)算問題的數(shù)學(xué)模型.如下圖：現(xiàn)實(shí)中的問題：迷宮17入口死路死路死路死路死路死路死路死路死路死路出口死路死路死路死路18現(xiàn)實(shí)中的問題：計(jì)算機(jī)和人的對弈井字棋的一個格局19125643125436113318146651921

圖結(jié)構(gòu)

網(wǎng)絡(luò)結(jié)構(gòu)20現(xiàn)實(shí)中的問題：多叉路口交通燈的管理

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

D={di|1≤i≤5}

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

討論：抽象數(shù)據(jù)類型和偽碼是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的工具291.4.1數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別數(shù)據(jù)類型：是一個值的集合和定義在該值上的一組操作的總稱。變量的數(shù)據(jù)類型決定了如何將代表這些值的位存儲到計(jì)算機(jī)的內(nèi)存中。抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）。它與數(shù)據(jù)類型實(shí)質(zhì)上是一個概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）301.4.2抽象數(shù)據(jù)類型如何定義抽象數(shù)據(jù)類型可以用以下的三元組來表示：

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

)的抽象數(shù)據(jù)類型定義。ADT

Natural_Number

isobjects:

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

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

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

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

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

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

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

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

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

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

與

原操作執(zhí)行次數(shù)之和

成正比

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

基本操作

的原操作，以該基本操作

在算法中重復(fù)執(zhí)行的次數(shù)

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

//以二維數(shù)組存儲矩陣元素，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基本操作:

乘法操作時間復(fù)雜度:

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

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

}//select_sort基本操作:

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

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