第1章 緒論電子課件

第1章緒論入門即上路，本章引導(dǎo)上路。要求掌握數(shù)據(jù)結(jié)構(gòu)和算法概念；理解算法分析方法。鐵鍋里摻適量水燒開，放入秋葵，兩根筷子架起放了鱈魚和香料的盤子，轉(zhuǎn)微火蓋鍋蓋蒸。好香！10分鐘內(nèi)要回來，這之前發(fā)個說說：處處皆結(jié)構(gòu)，處處皆算法！哦原來，鍋里架構(gòu)是數(shù)據(jù)結(jié)構(gòu)，烹飪步驟是算法。提綱1.1數(shù)據(jù)結(jié)構(gòu)1.2算法概念1.3算法分析1.4緒論總結(jié)1.1

數(shù)據(jù)結(jié)構(gòu)1.1.1基本概念概念數(shù)據(jù)（Data）：能夠被計算機(jī)程序識別、存儲、加工和處理的描述客觀事物的符號集合的總稱。數(shù)據(jù)是信息的載體，數(shù)據(jù)賦予含義成為信息。數(shù)據(jù)項（DataItem）：又稱為字段或域，是數(shù)據(jù)元素的組成部分，具有不可分割性和獨立含義。數(shù)據(jù)元素（DataElement）：又稱為元素，是數(shù)據(jù)的基本單位，是一個數(shù)據(jù)整體的基本表示。數(shù)據(jù)對象（DataObject）：又稱為數(shù)據(jù)元素類，是性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)元素是數(shù)據(jù)對象的實例。數(shù)據(jù)結(jié)構(gòu)（DataStructure）：相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。抽象數(shù)據(jù)類型（AbstractDataType，ADT）：從數(shù)學(xué)模型角度抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)以及其上的運算，不考慮具體存儲結(jié)構(gòu)和實現(xiàn)細(xì)節(jié)；它反映的是定義與實現(xiàn)相分離的設(shè)計哲學(xué)，包含數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本運算。1.1.1基本概念比如定義復(fù)數(shù)抽象數(shù)據(jù)類型Complex：ADTComplex{數(shù)據(jù)對象：D={e1，e2|e1，e2均為實數(shù)}數(shù)據(jù)關(guān)系：R={<e1，e2>|e1是復(fù)數(shù)的實部，e2是復(fù)數(shù)的虛部}基本運算：AssignComplex(&z，v1，v2)：構(gòu)造復(fù)數(shù)Z。GetReal(z，&real)：返回復(fù)數(shù)z的實部值。GetImag(z，&Imag)：返回復(fù)數(shù)z的虛部值。Add(z1，z2，&sum)：返回兩個復(fù)數(shù)z1、z2的和。}ADTComplex1.1.1基本概念舉例地球是裝人的容器，人是數(shù)據(jù)對象，張三是數(shù)據(jù)元素，人的某個屬性如膚色是數(shù)據(jù)項，人與人之間存在的關(guān)系與人一道在地球上構(gòu)成了數(shù)據(jù)結(jié)構(gòu)，而地球上有人，人與人之間有直接或間接關(guān)系發(fā)生，就是抽象數(shù)據(jù)類型的表示。1.1.2邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹狀結(jié)構(gòu)、圖形結(jié)構(gòu)4類。集合具有相同性質(zhì)元素構(gòu)成集合。集合中元素的關(guān)系極為松散，關(guān)系為“屬于同一個集合”。舉例：這之前，我們都不認(rèn)識，是數(shù)據(jù)結(jié)構(gòu)這門課程讓我們有緣走到了一起，來到這間教室學(xué)習(xí)。教室看作集合，教室里的人看作元素，有些同學(xué)一學(xué)期也不說話交流（沒有關(guān)系），但他們歸屬于同一個教室。1.1.2邏輯結(jié)構(gòu)線性結(jié)構(gòu)數(shù)據(jù)元素之間是線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。特點是元素之間為“一對一”關(guān)系。舉例1：甲用暗號1聯(lián)系乙，乙用暗號2聯(lián)系丙，丙用暗號3聯(lián)系丁。保密工作只能單線聯(lián)系。甲乙丙丁這些元素之間的關(guān)系是單一的、一個對一個的。舉例2：教室里坐了n個同學(xué)，按照學(xué)號順序依次回答問題：什么是數(shù)據(jù)結(jié)構(gòu)？n個學(xué)生數(shù)據(jù)元素這種依次關(guān)系，就是一對一的關(guān)系。1.1.2邏輯結(jié)構(gòu)樹狀結(jié)構(gòu)數(shù)據(jù)元素之間是層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)。特點是元素之間可以為“一對多”關(guān)系。舉例1：舊樓房的樓梯間，有線電視同軸電纜從1樓到頂樓通過分支器連接和分戶，使得家家有電視看。這種分支器輸入為1個通道輸出為n個通道，構(gòu)成了一對多關(guān)系；層層分支整個線路構(gòu)成了樹狀結(jié)構(gòu)。舉例2：單位的組織結(jié)構(gòu)，是典型的層次樹狀結(jié)構(gòu)！倒立的樹狀結(jié)構(gòu)！1.1.2邏輯結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系更復(fù)雜，可以包含一對一、一對多、多對一，多對多的關(guān)系。特點是元素之間可以為“多對多”關(guān)系。舉例：新同學(xué)找進(jìn)校門找不到路，沒有老同學(xué)在身邊帶沒關(guān)系，打開手機(jī)校園地圖，房屋線路一目了然吧；打開百度地圖、高德地圖看城市交通雷同。從宿舍到教室有多條路，從教室到食堂有多條路，從食堂回宿舍還是有很多條路??！在這個例子中，體現(xiàn)了元素之間多對多的關(guān)系。1.1.2邏輯結(jié)構(gòu)1.1.3存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是在連續(xù)的存儲單元中存放數(shù)據(jù)元素，元素的物理存儲次序與邏輯次序一致，即物理位置相鄰的元素在邏輯上也是相鄰的。舉例：大學(xué)英語四六級考試考場座位編號，是按照準(zhǔn)考證號的順序連續(xù)編號的。在這個例子中，相鄰準(zhǔn)考證號在物理座位上也是相鄰的。1.1.3存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)使用地址分散的存儲單元存放數(shù)據(jù)元素，即物理上相鄰的數(shù)據(jù)元素邏輯上不一定相鄰，數(shù)據(jù)元素之間的邏輯關(guān)系通常用指針表示，記錄前驅(qū)和后繼的存儲地址。舉例：大學(xué)教室里，同學(xué)們來上課可以隨便坐，不一定學(xué)號相鄰的同學(xué)坐在一起。當(dāng)老師讓學(xué)生按照學(xué)號從小到大舉手/站立報號考勤時，這種亂坐現(xiàn)象并不影響考勤。在這個例子中，雖然學(xué)號連續(xù)，但是學(xué)生可以分散坐，體現(xiàn)了鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.1.3存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)時在存儲數(shù)據(jù)元素的基礎(chǔ)上增加了索引表，可以用它來實現(xiàn)快速查找數(shù)據(jù)元素。舉例：班干部名單，叫到某個班干部如“2組組長張三”，其職責(zé)和管理對象也就呼之而出！這個例子中，班干部名單可以看作索引表。1.1.3存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)又叫哈希存儲結(jié)構(gòu)，數(shù)據(jù)元素的存儲地址是由該數(shù)據(jù)元素關(guān)鍵字散列函數(shù)計算出來。舉例：學(xué)生照畢業(yè)照，按照個子高矮站位，中間站高個子兩邊站矮個子；若有相同身高則站另一邊，依此類推。在這個例子中，散列函數(shù)就是對身高求值，從而決定所站位置（存儲地址）。1.1.3存儲結(jié)構(gòu)1.2算法概念1.2.1算法定義算法是對問題求解的步驟描述。算法處處皆在，讀者思想馳騁，能否信手拈來？舉例1：同學(xué)們跨進(jìn)大學(xué)校門報到，從健康碼檢查、x處注冊繳費、y處安排住宿、z處集合領(lǐng)書等流程是合理的，不能是住宿費學(xué)費還沒有繳就可以住宿、領(lǐng)書和上課了，也不能說沒有檢查健康碼就進(jìn)學(xué)校了，這些原則上是不允許的。在這個例子中，學(xué)生的執(zhí)行流程體現(xiàn)了算法的執(zhí)行步驟。舉例2：作者要完成這本書的編寫，首先要市場調(diào)研：目前流行的教材特點和高校開設(shè)這門課程的教學(xué)情況，主要是發(fā)現(xiàn)存在的問題；然后構(gòu)思如何編寫一本通俗易懂而實用的教材以及如何在課堂教學(xué)中實施；接下來就是寫出目錄框架；再接下來就是查閱和搜集眾多參考文獻(xiàn)和素材；最后才是花大量時間和精力去撰寫內(nèi)容，并反復(fù)檢查、打磨和優(yōu)化，以及責(zé)編辛勤校驗、排版。倘若作者不了解市場而盲目出書，則不會寫出讀者歡迎的書。在這個例子中，作者懷揣情懷編寫一本付出心血的教材體現(xiàn)了算法的執(zhí)行步驟。1.2.2算法特性算法具有以下5個特性。有窮性算法是由若干條指令組成的有窮序列，而非永不停止。在算法1.1中，while(true)是“永動機(jī)”，循環(huán)永遠(yuǎn)跳不出來導(dǎo)致后面的語句無法執(zhí)行（事實上打開注釋，報錯“語句不可達(dá)”），注釋掉之后，該算法具有有窮性。確定性算法的每一條語句有特定的含義，無歧義?？尚行运惴ㄔ诋?dāng)前環(huán)境條件下可以通過有限次運算實現(xiàn)。輸入性算法有零個或多個輸入。算法1.1的algorithm1_1方法有2個輸入?yún)?shù)，在設(shè)計算法時也可以沒有輸入?yún)?shù)或更多輸入?yún)?shù)。輸出性算法有一個或多個輸出。一般地，算法都有輸出；若輸出是多個，則在程序設(shè)計時可以把多個輸出放到集合中再逐個輸出。1.2.2算法特性【算法1.1】理解算法5個特性。

publicStringalgorithm1_1(intx,inty){//輸入性：2個

//while(true){}//無窮性：破壞了算法后續(xù)語法

for(inti=1;i<=10;i++){//有窮性：算法運行時間有限

System.out.println("先循環(huán)10次再說"+i);

}

intz=x+y; //確定性：語法沒問題

StringoutPut=z+"";//確定性：語法沒問題

returnoutPut; //輸出性：1個

}//可行性：運行之后能實現(xiàn)

1.2.3算法目標(biāo)算法設(shè)計目標(biāo)，就是設(shè)計出好的算法。好的算法具有下列5個特性。正確性算法能夠滿足具體問題的需求，程序運行正常，通過測試能夠達(dá)到預(yù)期目標(biāo)。健壯性算法對非法數(shù)據(jù)和操作有處理機(jī)制。易讀性算法遵循標(biāo)識符命名規(guī)則，簡潔易懂，適當(dāng)注釋，方便閱讀和理解，也便于后期維護(hù)和擴(kuò)展。高效性算法運行的時間短。低存儲性算法所需的存儲空間低。前3點是算法的基本要求，后2點是好算法的評判標(biāo)準(zhǔn)。1.2.4算法描述自然語言自然語言即接近口頭描述。用自然語言描述算法簡單易懂，但嚴(yán)謹(jǐn)性較差。程序語言程序語言如Java、C#、Python等。用某種具體的程序設(shè)計語言來描述算法較嚴(yán)謹(jǐn)，算法可直接在計算機(jī)上執(zhí)行，但非專業(yè)人士難以理解。偽代碼偽代碼是介于自然語言和程序語言之間的描述方式。用偽代碼描述算法可以忽略嚴(yán)格的語法規(guī)則，接近用戶理解，且容易將其轉(zhuǎn)換為程序語言執(zhí)行。1.2.4算法描述例如：根據(jù)學(xué)號查找學(xué)生。（1）用自然語言描述：從學(xué)號列表第1個元素開始，與給定學(xué)號進(jìn)行比較：若相等則查找成功；若不相等則比較下一個元素，直到最后一個元素比較完若前面都沒有找到。這個過程要么查找成功，要么查找失敗。（2）用程序語言描述：如算法1.2?！舅惴?.2】用程序語言描述算法。publicintalgorithm1_2(intkey){//key為給定學(xué)號

int[]studentNo={101,102,103,104,105};//學(xué)號列表for(inti=0;i<studentNo.length;i++)if(studentNo[i]==key)//比較

return1;//查找成功

return0; //查找失敗}

（3）用偽代碼描述key=100for(學(xué)號in學(xué)號列表){ if(學(xué)號==key)

查找成功，結(jié)束}查找失敗，結(jié)束1.3算法分析算法分析主要是分析算法的執(zhí)行時間和存儲空間，它們是評判一個算法好與壞的重要指標(biāo)。從執(zhí)行時間上分析就是算法的時間復(fù)雜度；從存儲空間上分析就是算法的空間復(fù)雜度。1.3.1算法時間復(fù)雜度

1.3.1算法時間復(fù)雜度

1.3.1算法時間復(fù)雜度1.3.1算法時間復(fù)雜度

舉例1：1個窗口，8個人排隊做核酸。若做核酸1個人的平均時間為5秒，則大約需40秒；假設(shè)人數(shù)增加為800，則需4000秒。顯然，問題規(guī)模n從8到800，時間隨之增加。舉例2：1000個窗口，不超過1000人做核酸。來一個做一個不用排隊，同時來也無妨！顯然只需1個人做核酸的時間：5秒。做1個人和做1000個人的核酸所花時間皆5秒，這種情形的時間復(fù)雜度與問題規(guī)模無關(guān)。1.3.1算法時間復(fù)雜度【算法1.4】疫情下做核酸檢查所花時間與問題規(guī)模之間的關(guān)系，假設(shè)檢查1個人需花5秒。publicvoidalgorithm1_4(intn,intwindows){//n為問題規(guī)模，windows為窗口數(shù)

inttotalTime=0;//所花總時間，初始值為0

if(windows==1)//只有1個窗口

while(n--!=0){totalTime+=5;//執(zhí)行n次

} elseif(windows>=n)//窗口數(shù)不少于人數(shù)

totalTime=5; //執(zhí)行1次 }

在算法1.4中，分析了算法時間復(fù)雜度與問題規(guī)模之間的關(guān)系，可能要取決于其他條件因素具有不確定性，這里為窗口數(shù)：當(dāng)窗口數(shù)大于等于人數(shù)（問題規(guī)模）時，時間復(fù)雜度與問題規(guī)模無關(guān)；反之相關(guān)。之所以一個算法的時間復(fù)雜度可能不確定，是因為其有最好情況、最壞情況和平均情況。看一個算法好與壞，最壞情況是主要考慮因素。1.3.1算法時間復(fù)雜度【思考與練習(xí)1.1】舉一些時間復(fù)雜度與問題規(guī)模無關(guān)的算法例子。答：例如“秒殺”系統(tǒng)，系統(tǒng)設(shè)置了只過濾5個名額，5千、5萬、50萬去搶都無關(guān)，執(zhí)行時間不受影響。分析下面的算法，其時間復(fù)雜度與問題規(guī)模n是否相關(guān)，為什么？publicintthinkPad1_1(intn){//n為問題規(guī)模

intx=0,y=0;

while(x<n){

x++;

returny;

}

returnx;

}

答：無關(guān)。因為無論問題規(guī)模是多少，算法中核心語句只執(zhí)行1次。1.3.1算法時間復(fù)雜度語句頻度語句頻度是指語句重復(fù)執(zhí)行的次數(shù)。我們在計算時間復(fù)雜度時，不必將每條語句執(zhí)行的次數(shù)相加，一般只考慮執(zhí)行次數(shù)最多的語句，如循環(huán)最內(nèi)層的語句對時間復(fù)雜度貢獻(xiàn)最大，這樣的語句我們稱為關(guān)鍵語句。在算法1.3中，"俺在循環(huán)之內(nèi)！"語句對算法時間復(fù)雜度貢獻(xiàn)最大，故其執(zhí)行次數(shù)可以代表該算法的時間復(fù)雜度。算法優(yōu)化實現(xiàn)同一個功能，采用不同的算法往往時間復(fù)雜度不同。舉例：畢業(yè)設(shè)計文檔若干，包括論文和過程材料共11個；假設(shè)1個指導(dǎo)老師帶了10個學(xué)生，師生共同打磨修改優(yōu)化完成了所有文檔之后，最后要求按照文檔清單順序裝袋，裝袋前師生在有些文檔上須簽字，每個袋子裝1個學(xué)生的材料。如何高效完成裝袋，不同算法思想其效率即時間復(fù)雜度是不一樣的。1.3.1算法時間復(fù)雜度【思考與練習(xí)1.2】針對上面的舉例，分析下面的算法1和算法2的時間復(fù)雜度，若是你，會選擇哪一種算法，為什么？算法1：指導(dǎo)老師建11個文件夾，分別對應(yīng)11種材料，如“任務(wù)書”、“開題報告”、“指導(dǎo)記錄表”等等，按材料歸類，完成打印、簽字、裝訂、裝袋。算法2：指導(dǎo)老師建10個文件夾，分別對應(yīng)10個學(xué)生，如“888-張三”、“999-李四”等等，按學(xué)生歸類，完成打印、簽字、裝訂、裝袋。1.3.1算法時間復(fù)雜度答：算法1描述：Step1.新建11個材料文件夾；Step2.10個學(xué)生的所有文檔以材料文件夾歸類；Step3.按照文檔清單順序裝袋要求，依次打印“任務(wù)書”、“開題報告”、“指導(dǎo)記錄表”等文件夾中所有文檔；（這一步若按學(xué)生為單位打印，打印操作要跳轉(zhuǎn)，繁瑣）Step4.完成簽字后將紙質(zhì)文檔整理歸類