數(shù)據(jù)結(jié)構(gòu)選講DATASTRUCTURE課件

36、“不可能”這個(gè)字(法語(yǔ)是一個(gè)字)，只在愚人的字典中找得到。--拿破侖。37、不要生氣要爭(zhēng)氣，不要看破要突破，不要嫉妒要欣賞，不要托延要積極，不要心動(dòng)要行動(dòng)。38、勤奮，機(jī)會(huì)，樂(lè)觀是成功的三要素。(注意：傳統(tǒng)觀念認(rèn)為勤奮和機(jī)會(huì)是成功的要素，但是經(jīng)過(guò)統(tǒng)計(jì)學(xué)和成功人士的分析得出，樂(lè)觀是成功的第三要素。39、沒(méi)有不老的誓言，沒(méi)有不變的承諾，踏上旅途，義無(wú)反顧。40、對(duì)時(shí)間的價(jià)值沒(méi)有沒(méi)有深切認(rèn)識(shí)的人，決不會(huì)堅(jiān)韌勤勉。數(shù)據(jù)結(jié)構(gòu)選講DATASTRUCTURE課件數(shù)據(jù)結(jié)構(gòu)選講DATASTRUCTURE課件36、“不可能”這個(gè)字(法語(yǔ)是一個(gè)字)，只在愚人的字典中找得到。--拿破侖。37、不要生氣要爭(zhēng)氣，不要看破要突破，不要嫉妒要欣賞，不要托延要積極，不要心動(dòng)要行動(dòng)。38、勤奮，機(jī)會(huì)，樂(lè)觀是成功的三要素。(注意：傳統(tǒng)觀念認(rèn)為勤奮和機(jī)會(huì)是成功的要素，但是經(jīng)過(guò)統(tǒng)計(jì)學(xué)和成功人士的分析得出，樂(lè)觀是成功的第三要素。39、沒(méi)有不老的誓言，沒(méi)有不變的承諾，踏上旅途，義無(wú)反顧。40、對(duì)時(shí)間的價(jià)值沒(méi)有沒(méi)有深切認(rèn)識(shí)的人，決不會(huì)堅(jiān)韌勤勉。數(shù)據(jù)結(jié)構(gòu)選講DATASTRUCTURE課件數(shù)據(jù)結(jié)構(gòu)選講

DATASTRUCTURE主講教師：羅熊Instructor:LUOXiongE-mail:xluomail.qgzxol2021/3/162課程內(nèi)容：計(jì)算機(jī)軟件的基礎(chǔ)知識(shí)———數(shù)據(jù)結(jié)構(gòu)課時(shí)安排：數(shù)據(jù)結(jié)構(gòu)——32學(xué)時(shí)教材：嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，1997.參考書：數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語(yǔ)言篇）李春葆數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用—C++語(yǔ)言描述（英文版）SartajSahniMcGraw-Hill&機(jī)械工業(yè)出版社2021/3/163數(shù)據(jù)元素：是數(shù)據(jù)的最小單位，有時(shí)一個(gè)數(shù)據(jù)元素由數(shù)據(jù)項(xiàng)組成（具有獨(dú)立含義的最小標(biāo)識(shí)單位）

數(shù)據(jù)類型：具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)集合及在這個(gè)集合上的一組操作。數(shù)據(jù)結(jié)構(gòu)：由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：

Data_Structure={D,R}

其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。2023/6/66數(shù)據(jù)結(jié)構(gòu)依據(jù)視點(diǎn)的不同，分為數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)：邏輯結(jié)構(gòu)：從解決問(wèn)題的需要出發(fā)，為實(shí)現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)，它屬于用戶的視圖，是面向?qū)ο蟮?。物理結(jié)構(gòu)：指數(shù)據(jù)該如何在計(jì)算機(jī)中存放，是數(shù)據(jù)邏輯結(jié)構(gòu)的物理存儲(chǔ)方式，是屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。關(guān)系：物理結(jié)構(gòu)是邏輯數(shù)據(jù)的存儲(chǔ)映象2023/6/67邏輯結(jié)構(gòu)：線性結(jié)構(gòu)非線性結(jié)構(gòu)物理結(jié)構(gòu)：順序存儲(chǔ)鏈接存儲(chǔ)索引存儲(chǔ)散列存儲(chǔ)2023/6/68“學(xué)生”表格2023/6/69“課程”表格2023/6/610線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系:有直接前驅(qū)和直接后繼(除最前、最后一個(gè)元素)例：電話號(hào)碼查詢問(wèn)題方法1：順序存儲(chǔ)，順序查找2023/6/611方法2：有序順序存儲(chǔ)，二分查找姓名地址李1李2……張1張2……王1王2……2023/6/612方法3：部分有序，建立索引表姓名地址李1李2……張1張2……王1王2……姓地址李張……2023/6/613非線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的沒(méi)有線性關(guān)系:前驅(qū)和后繼可能多于一個(gè)

選課單包含如下信息

學(xué)號(hào)課程編號(hào)成績(jī)時(shí)間

學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)系2023/6/614UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖2023/6/615樹(shù)形結(jié)構(gòu)樹(shù)二叉樹(shù)二叉搜索樹(shù)2023/6/616堆結(jié)構(gòu)“最大”堆“最小”堆2023/6/617圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)2023/6/618例：田徑賽的時(shí)間安排問(wèn)題姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁1跳高跳遠(yuǎn)100M馬2標(biāo)槍鉛球張3標(biāo)槍100M200M李4鉛球200M跳高王5跳遠(yuǎn)200M跳高跳遠(yuǎn)標(biāo)槍鉛球200M100M1、任一選手所選中的項(xiàng)目中應(yīng)該兩兩有邊相連；2、任一兩個(gè)有邊相連的頂點(diǎn)顏色（時(shí)間）不能相同。2023/6/619在解決問(wèn)題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）邏輯結(jié)構(gòu)的存儲(chǔ)映象（存儲(chǔ)實(shí)現(xiàn)）數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)。2023/6/6201.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型

定義：一個(gè)數(shù)據(jù)的集合,以及定義于這個(gè)數(shù)據(jù)集合上的一組操作的總稱。C語(yǔ)言中的數(shù)據(jù)類型

基本數(shù)據(jù)類型、指針類型、數(shù)組類型、結(jié)構(gòu)體類型、公用體類型、枚舉類型2023/6/621抽象數(shù)據(jù)和抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離（物理實(shí)現(xiàn)封裝）2023/6/622ADT：抽象數(shù)據(jù)類型名

數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義

數(shù)據(jù)關(guān)系：數(shù)據(jù)邏輯關(guān)系的定義

基本操作：基本操作的定義抽象數(shù)據(jù)類型的定義：操作名（參數(shù)表）

操作結(jié)果：操作結(jié)果描述基本操作的定義：2023/6/623抽象數(shù)據(jù)類型2023/6/624好的和壞的數(shù)據(jù)結(jié)構(gòu)？

如果一個(gè)DS可以通過(guò)某種“線性規(guī)則”被轉(zhuǎn)化為線性的DS（例如線性表），則稱它為好的DS。好的DS通常對(duì)應(yīng)于好的（高效的）算法。這是由計(jì)算機(jī)的計(jì)算能力決定的，因?yàn)橛?jì)算機(jī)本質(zhì)上只能存取邏輯連續(xù)的內(nèi)存單元，因此如果沒(méi)有線性化的結(jié)構(gòu)邏輯上是不可計(jì)算的。

樹(shù)是好的DS——它有非常簡(jiǎn)單而高效的線性化規(guī)則，因此可以利用樹(shù)設(shè)計(jì)出許多非常高效的算法。樹(shù)的實(shí)現(xiàn)和使用都很簡(jiǎn)單，但可以解決大量特殊的復(fù)雜問(wèn)題，因此樹(shù)是實(shí)際編程中最重要和最有用的一種數(shù)據(jù)結(jié)構(gòu)。樹(shù)的結(jié)構(gòu)本質(zhì)上有遞歸的性質(zhì)。

2023/6/6251.3C語(yǔ)言的數(shù)據(jù)類型1、基本數(shù)據(jù)類型intshort;long;unsignedfloatfloat;double;longdouble2、指針類型3、數(shù)組類型4、字符串5、結(jié)構(gòu)體類型6、共用體類型7、枚舉類型8、自定義類型2023/6/6261.4用C語(yǔ)言編寫算法的注意事項(xiàng)1、避免使用出現(xiàn)二義性的表達(dá)式i++;i=++i;i=1;j=i+++i--;2、避免使用轉(zhuǎn)向語(yǔ)句3、避免使用預(yù)處理4、避免函數(shù)返回值隱含說(shuō)明2023/6/6271.5算法設(shè)計(jì)目標(biāo)和算法效率度量定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列特性：輸入

有0個(gè)或多個(gè)輸入輸出有一個(gè)或多個(gè)輸出(處理結(jié)果)確定性每步定義都是確切、無(wú)歧義的有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性每一條運(yùn)算應(yīng)足夠基本算法的描述:c++,c,PASCAL等語(yǔ)言2023/6/628算法有這樣一些特點(diǎn)：1、有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。2、確定性：算法中的每一個(gè)步驟都必須是確定的，而不應(yīng)當(dāng)含糊、模棱兩可。3、有零個(gè)或多個(gè)輸入4、有一個(gè)或多個(gè)輸出5、有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。例如：被零除的計(jì)算動(dòng)作是不能被有效執(zhí)行的。2023/6/629設(shè)計(jì)算法的基本方法:把一個(gè)具體問(wèn)題轉(zhuǎn)變成一個(gè)算法事例學(xué)習(xí)：選擇排序問(wèn)題明確問(wèn)題：非遞減排序解決方案：逐個(gè)選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-2;i++){//n-1趟

從a[i]檢查到a[n-1];

若最小的整數(shù)在a[k],交換a[i]與a[k];

}細(xì)化程序：程序SelectSort

算法設(shè)計(jì)

自頂向下，逐步求精

2023/6/630性能分析與度量算法的性能標(biāo)準(zhǔn)算法的后期測(cè)試算法的事前估計(jì)2023/6/631分析評(píng)價(jià)算法時(shí)應(yīng)考慮的因素：1、正確性在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過(guò)有窮時(shí)間的計(jì)算能給出正確的答案。2、復(fù)雜度時(shí)間復(fù)雜度3、簡(jiǎn)單性4、最優(yōu)性算法A是最優(yōu)的是指：在給定問(wèn)題的所有算法中，A執(zhí)行的進(jìn)步運(yùn)算次數(shù)最少5、可讀性要求算法易于理解，便于分析6、可修改可擴(kuò)展性如果問(wèn)題P的一個(gè)算法是A，為了解答一個(gè)與P類似的問(wèn)題，希望對(duì)A稍做改動(dòng)就可正確運(yùn)行，如算法A滿足這一點(diǎn)，則說(shuō)A的可修改性好。2023/6/632與算法效率有關(guān)的因素程序設(shè)計(jì)語(yǔ)言編譯的代碼質(zhì)量機(jī)器執(zhí)行指令的速度問(wèn)題的規(guī)模2023/6/633求解同樣一個(gè)問(wèn)題可能會(huì)有許多不同的算法，如何評(píng)價(jià)這些算法的好壞呢？首先算法必須是正確的。此外還需考慮：1、算法易于理解，易于編程（在計(jì)算機(jī)上實(shí)現(xiàn)），易于調(diào)試。2、要求算法高效，節(jié)省時(shí)間與空間。一個(gè)算法運(yùn)行所需時(shí)間的長(zhǎng)短、空間的大小具有非常重要的意義。時(shí)間和空間相互之間有一種制約關(guān)系，何者為重需視具體情況而定。2023/6/634算法高效與算法易理解、易編程之間也有一種制約關(guān)系這兩個(gè)要求有時(shí)互相矛盾。因此，對(duì)反復(fù)運(yùn)行的算法，首先考慮的是高效性，對(duì)偶爾運(yùn)行的算法，則需突出算法易理解和易編程（以排序?yàn)槔芭菖判蚝涂焖倥判颍?/p>

2023/6/635我們重點(diǎn)考慮時(shí)間因素。一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)該是該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和，而每條語(yǔ)句的執(zhí)行時(shí)間又是該語(yǔ)句的執(zhí)行次數(shù)（頻度）與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。我們假定，每條語(yǔ)句一次執(zhí)行的時(shí)間都是相同的，為單位時(shí)間。這樣我們對(duì)時(shí)間的分析就可以獨(dú)立于軟硬件系統(tǒng)。

2023/6/636

我們將算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模，用一個(gè)整數(shù)來(lái)表示，一個(gè)算法的時(shí)間復(fù)雜度是該算法的時(shí)間耗費(fèi)，一般地說(shuō)，時(shí)間復(fù)雜度是問(wèn)題規(guī)模的函數(shù)－T(n)。當(dāng)問(wèn)題的規(guī)模n趨于無(wú)窮大時(shí)，把時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度（有時(shí)簡(jiǎn)稱為時(shí)間復(fù)雜度）。嚴(yán)格的數(shù)學(xué)定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)存在兩個(gè)正的乘數(shù)C和n0時(shí)，使得對(duì)所有的成立，則都有這時(shí)稱T(n)的時(shí)間復(fù)雜度為f(n)數(shù)量級(jí)。2023/6/637算法運(yùn)行所需要的時(shí)間與兩個(gè)因素有關(guān)：1、問(wèn)題實(shí)例的大小

（如1000個(gè)數(shù)的排序）；2、實(shí)例的具體情況

（如1000個(gè)數(shù)的排列情況）

2023/6/638算法分析1、假定每條語(yǔ)句的執(zhí)行時(shí)間為單位時(shí)間。算法的時(shí)間復(fù)雜度是該算法中所有語(yǔ)句的執(zhí)行頻度之和。2023/6/639例：求兩個(gè)方陣的乘積C＝A*B＃definen自然數(shù)MATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti,j,k;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]//⑤}}2023/6/6402、一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只考慮循環(huán)體語(yǔ)句的執(zhí)行次數(shù)，而忽略該語(yǔ)句中部長(zhǎng)加一、終值判別、循環(huán)轉(zhuǎn)移等成份。因此，當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度所決定的。2023/6/641例：x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)//n*ny++;

一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，而忽略循環(huán)體中步長(zhǎng)加1、終值判斷、控制轉(zhuǎn)移等成分。2023/6/642例：x=1;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;2023/6/6433、選擇執(zhí)行的成分，如if語(yǔ)句的執(zhí)行時(shí)間，決定于then子句、else子句耗時(shí)較多的部分4、如果算法的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)，則算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。