課件數(shù)據(jù)結(jié)構(gòu)a-修改-1第一章緒論2013版

教材繆淮扣等.C++實(shí)現(xiàn).北京：科學(xué)出版主要參考書Ftp服務(wù) Password:【【數(shù)據(jù)結(jié)構(gòu)及相關(guān)主干課程間的聯(lián)系】【數(shù)據(jù)結(jié)構(gòu)及相關(guān)主干課程間的聯(lián)系】【數(shù)據(jù)結(jié)構(gòu)及相關(guān)主干課程間的聯(lián)系】數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)操作的算法計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算（數(shù)值計(jì)算），而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。形成階段發(fā)展階段為什么用面向?qū)ο蟮挠^點(diǎn)來(lái)描述數(shù)據(jù)結(jié)構(gòu)面向?qū)ο蠹夹g(shù)是軟件工程領(lǐng)域中的重要技術(shù)，它不僅是一種程序設(shè)計(jì)方法，更重要的是一種對(duì)目前，面向?qū)ο蟮能浖治龊驮O(shè)計(jì)技術(shù)已發(fā)展成為軟件開(kāi)發(fā)的主流方法。為了適應(yīng)軟件開(kāi)發(fā)方法與技術(shù)的發(fā)展以及應(yīng)用領(lǐng)域的要求，就有必要因此，用面向?qū)ο蟮挠^點(diǎn)來(lái)描述數(shù)據(jù)結(jié)構(gòu)就成用面向?qū)ο蟮挠^點(diǎn)來(lái)描述數(shù)據(jù)結(jié)構(gòu)，要涉及目前被廣泛采用作為程序設(shè)計(jì)語(yǔ)言教學(xué)的是的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言。因此我們所采用的教為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)鏈鏈（算法+數(shù)據(jù)結(jié)構(gòu)）=程什么是程序、軟件 計(jì)算機(jī)功能強(qiáng)大，但計(jì)算機(jī)的本領(lǐng)是要人用“程序”來(lái)“教”的。 隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，“程序”越來(lái)越大，越來(lái)越復(fù)雜。因而解題的過(guò)程就不僅僅是編程序，而是一個(gè)包括編程序在內(nèi)的軟那么，軟件包括什么因此，軟件不僅僅是指程序，而且是包括程序以及開(kāi)發(fā)程序的過(guò)程中所產(chǎn)生的各種文檔。軟件開(kāi)發(fā)的目標(biāo)是產(chǎn)生能讓計(jì)算機(jī)有效工作軟件=程序+文檔（軟件工程的觀點(diǎn)程序到底是什么呢瑞士計(jì)算機(jī)科學(xué)家，圖靈

圖靈獲得N.Wirth教授(尼古拉斯·沃斯NiklausWirth,1984年因?yàn)樗麑?duì)計(jì)算機(jī)語(yǔ)言設(shè)計(jì)方面的貢獻(xiàn)而獲獎(jiǎng))給出了一個(gè)著Algorithms+DataStructures=如何理解“好的”數(shù)據(jù)結(jié)構(gòu)＋“好的”算法＝“好的”程序“數(shù)據(jù)結(jié)構(gòu)”與“算法”是統(tǒng)一算法依賴于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是第一位曾經(jīng)產(chǎn)生了深遠(yuǎn)的影響，也是計(jì)算機(jī)科學(xué)的面向?qū)ο蟮挠^點(diǎn)，則可以理解為：(數(shù)據(jù)結(jié)構(gòu)＋算法)＝程20世紀(jì)90年代，面向?qū)ο蟮姆椒ㄊ艿搅撕茉诿嫦驅(qū)ο蟪绦蛟O(shè)計(jì)中，密切相關(guān)的數(shù)據(jù)與過(guò)程（操作）被定義為一個(gè)整體（即對(duì)象），而且一旦作為一個(gè)整體定義了之后，就可以使用它，對(duì)其內(nèi)部的實(shí)現(xiàn)細(xì)節(jié)不需要太多的了解，從而提高軟件開(kāi)發(fā)的效率?？捎梅庋b和數(shù)據(jù)隱算法+數(shù)據(jù)結(jié)構(gòu)=程（算法+數(shù)據(jù)結(jié)構(gòu)）讓我們看看用計(jì)算機(jī)解題（數(shù)值問(wèn)題）的過(guò)程從對(duì)問(wèn)題的分析中提取操作的對(duì)象，并找出這些操作然而，更多的非數(shù)值計(jì)算問(wèn)題無(wú)法用數(shù)學(xué)方程加以描述描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)和圖之類的數(shù)據(jù)結(jié)構(gòu)。1-11-1插入、刪除等例1-2層次型數(shù)據(jù)結(jié)構(gòu)（樹(shù)型結(jié)構(gòu)

有查詢、入、刪除等例1-3窮舉法，貪心計(jì)窮舉法，貪心計(jì)算機(jī)處理的對(duì)象是元素間的關(guān)系是復(fù)雜施加于對(duì)象上的操作查詢、插入、刪除數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)（課程）這個(gè)角度，簡(jiǎn)單說(shuō)來(lái)，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。什么是數(shù)據(jù)幾個(gè)概念是信息的載體，是描述客觀事物的數(shù)、字符、圖形、圖象、聲音以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)數(shù)據(jù)元素（data數(shù)據(jù)項(xiàng)（data數(shù)據(jù)的子集。自然數(shù)集合={0,1,2,…}是“數(shù)”的數(shù)據(jù)對(duì)象；所有的字符是數(shù)據(jù)，字母集合AS={A,B,…Z,a,b,…,z}是該數(shù)據(jù)的數(shù)據(jù)對(duì)象。1.2.2什么是數(shù)據(jù)結(jié)構(gòu)“數(shù)”概念比較“大”

字符、圖形 對(duì)具有相同特性的數(shù)據(jù)元

并被計(jì)算機(jī)數(shù)據(jù)元 數(shù)據(jù)的子集。自然數(shù)集合={0,1,2,…}是“數(shù)”的數(shù)據(jù)對(duì)象；所有的字符是數(shù)據(jù)，字母集合AS={A,B,…Z,a,b,…,z}是該數(shù)據(jù)的數(shù)據(jù)對(duì)象。舉例說(shuō)

構(gòu)成（記錄） 數(shù)據(jù)結(jié)構(gòu)(datastructure帶有“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。“結(jié)構(gòu)”指數(shù)據(jù)元集合，結(jié)構(gòu)中的數(shù)據(jù)元素之間就是“同屬于一個(gè)集合”；線性結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在的是一種線樹(shù)型結(jié)構(gòu)圖型結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)，結(jié)構(gòu)中的元素之間存在著多數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是用戶所看到的數(shù)據(jù)結(jié)構(gòu)，是面向問(wèn)題的，也稱機(jī)外表示。它描述的是數(shù)據(jù)元素之間的（固數(shù)據(jù)的物理結(jié)構(gòu)（又稱存儲(chǔ)結(jié)構(gòu)、映像、機(jī)內(nèi)表示），是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的物理存儲(chǔ)方式，它屬于具體實(shí)現(xiàn)的視數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面。一般來(lái)說(shuō)，算法設(shè)計(jì)是基于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法實(shí)現(xiàn)則基于數(shù)據(jù)的順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

存儲(chǔ)地址存儲(chǔ)內(nèi)元素元素元素元素元素元素Lo+（n-

Loc(元素i)=LLoc(元素i)=Lo+（i-hhh鏈?zhǔn)酱妗脑卦卦? 元素 元素 元素 元素 示示本書以面向?qū)ο蟮挠^點(diǎn)來(lái)介紹各種數(shù)據(jù)結(jié)構(gòu)以這一章主要介紹數(shù)據(jù)結(jié)構(gòu)以及算法的基本概念，關(guān)于用于描述數(shù)據(jù)結(jié)構(gòu)和算法的C++語(yǔ)言的相關(guān)內(nèi)容不打算再介紹，假設(shè)同學(xué)們已經(jīng)熟悉重點(diǎn)要復(fù)習(xí)：1.3.4,1.3.5,1.3.7,1.3.8這幾節(jié)內(nèi)算法算法性能與復(fù)雜算法 算法的五個(gè)重要特性有窮確定進(jìn)一步的進(jìn)一步的解釋可行輸輸11．4．2算法設(shè)計(jì)的要1．4．2算法設(shè)計(jì)的1．4．2算法設(shè)計(jì)的要①程序不含語(yǔ)法錯(cuò)誤可讀性健壯性1．4．3算法效率的度算法執(zhí)行時(shí)間一個(gè)程序的執(zhí)行時(shí)間有兩種估計(jì)方法事后統(tǒng)計(jì)的方法;(被動(dòng)，效率低事前分析估算的方法.(主動(dòng)，效率高1．4．3算法效率的度①問(wèn)題的規(guī)模②編寫程序所用的語(yǔ)③編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量④機(jī)器執(zhí)行指令的速度這里：②,③,④是不可比因素for(i=1;i<=n;++i)//循for(j=1;j<=n;++j){//循環(huán)c[i,j]=0；//原操作for(k=1;k<=nk)//循環(huán)c[i,j]a[i,k]*b[k,j];//原操}數(shù)作為算法的時(shí)間量度。記為T(n)：T(n)＝c[i,jc[i,j]+=a[i,k]*b[k,j];//原操作，也是基本操作。數(shù)作為算法的時(shí)間量度。記為T(n)：T(n)＝的增長(zhǎng)率相同，稱作算法的漸近時(shí)間雜度(AsymptoticTimeComplexity)，數(shù)作為算法的時(shí)間量度。記為T(n)：T(n)＝c[i,jc[i,j]+=a[i,k]*b[k,j];//原操作，也是基本操作。所謂原操作是指例如，在兩個(gè)N×N矩陣相乘的算法中for(i＝1；i<=n；c[i，j]+＝a[i，k]*for(j＝1；j<=n；++j) c[i，j]c[i，j]+＝a[i，k]*}如何找到哪些原操作是基本操作基本操作的原操作多數(shù)情況下它是最深語(yǔ)句的頻度(FrequencyCount) {++x；s=for(i=1;i<=n;++i)++x；s+=x；for(k=1;k<=n; ++x s+=

{++x；s=for(I=1;i<=n;++i)++x；s+=x；for(k=1；k<=n;++k){++x;s+=注意:n和O(n)的區(qū)別,n是語(yǔ)句頻度,O(n)是時(shí)間復(fù)k次方階立方階平方階

低

算法的時(shí)間復(fù)雜度是衡量一個(gè)算法一般來(lái)說(shuō)，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可接受、可實(shí)際使用的算具有指數(shù)時(shí)間復(fù)雜度的算法，只有空間復(fù)雜元素的取值情況的不同而不同。對(duì)于這種情況，我們例如，下面的算法是用冒泡排序法對(duì)數(shù)組a中的n個(gè)整例1-17voidBubbleSort(inta[intn){這個(gè)算法的時(shí)間復(fù)雜度隨inti,j,intfor(i=1;i<n&&flag==1;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){}

待排序數(shù)據(jù)的不同而不同。當(dāng)某次排序過(guò)程中沒(méi)有任何兩個(gè)數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時(shí)算法將因標(biāo)記flag0不滿足循環(huán)條件而結(jié)束。請(qǐng)見(jiàn)黑板舉例說(shuō)

voidBubbleSort(inta[],intinti,j,intfor(i=1;i<n&&flag==1;{flag=0//for(j=0;j<n-if(a[j]>a[j+1]){//逆序flag=1;//發(fā)生交換

}1)/2次(i從1到n-1，

voidBubbleSort(inta[],intinti,j,intfor(i=1;i<n&&flag==1;{flag=0//for(j=0;j<n-flag=1;//發(fā)生交換}T(n)=O(n2)空間復(fù)雜空間復(fù)雜可以用空間復(fù)雜度（SpaceComplexity）作為算法它表示隨著問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)所需存儲(chǔ)空間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱為算法的漸進(jìn)空間復(fù)雜度（asymptoticSpaceComplexity）,這里所說(shuō)的存儲(chǔ)空間是指解題過(guò)程所需要的輔助空間。例如在排序算法中，為移動(dòng)數(shù)據(jù)元素所需通常，只有完成同一功能的幾個(gè)算法之間例如同樣是排序算法，待排序的數(shù)據(jù)元素是n個(gè)，作為輸入和存放這些數(shù)據(jù)的數(shù)組或鏈表結(jié)點(diǎn)同樣是n個(gè)，則這些輸入數(shù)據(jù)所占用的存儲(chǔ)空間是不需要進(jìn)行比較的，可比算法的描述與實(shí)1.5算法設(shè)計(jì)者在構(gòu)思和設(shè)計(jì)了一個(gè)算法之后，必須準(zhǔn)確清楚地將所設(shè)計(jì)的解題步驟記錄下來(lái)，或提供交流，或編寫成程1.5算法中的分支及循環(huán)等結(jié)構(gòu)表示不能清晰地顯示出來(lái)。1.5規(guī)定式樣的圖形、指向線和文字說(shuō)明組優(yōu)點(diǎn)直觀、清晰