算法和數(shù)據(jù)結(jié)構(gòu)第1頁，共39頁。算法和數(shù)據(jù)結(jié)構(gòu)第2頁，共39頁。3.4.1算法第3頁，共39頁。計(jì)算機(jī)求解問題的步驟(1)確定并理解問題；(2)尋找解決問題的方法與步驟，并將其表示成算法(Algorithm)；(3)使用某種程序設(shè)計(jì)語言描述該算法(編程),并進(jìn)行調(diào)試；(4)運(yùn)行程序，獲得問題的解答；(5)進(jìn)行評估，改進(jìn)算法和程序第4頁，共39頁。1.什么是算法？第5頁，共39頁。算法是解決問題的方法與步驟例：有三個硬幣，其中一個是偽造的，另兩個是真的，偽幣與真幣重量略有不同。現(xiàn)在提供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)開始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是第6頁，共39頁。關(guān)于算法的三方面問題如何確定算法（算法設(shè)計(jì)）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？第7頁，共39頁。2.算法設(shè)計(jì)舉例第8頁，共39頁。例：對整數(shù)進(jìn)行排序問題：任給一組(n個)整數(shù)，將它們從小到大進(jìn)行排序粗略的思路：①從所有整數(shù)中選一個最小的，作為已排序的第一個數(shù)②從剩下未排序整數(shù)中選最小的數(shù)，添加到已排序整數(shù)的后面③反復(fù)執(zhí)行步驟②，直到所有整數(shù)都處理完畢進(jìn)一步細(xì)化：把待排序的整數(shù)放在一個數(shù)組A中，每個整數(shù)是數(shù)組A中的一個元素：A[1],A[2],A[3],···],A[n],排好序的元素在A的前面部分，無序的元素留在后面，每“循環(huán)”一次，有序部分增加1個元素，無序部分減少1個元素每次“循環(huán)”只需在數(shù)組的無序元素部分選出最小的數(shù)反復(fù)進(jìn)行n-1次即可得到排序后的結(jié)果第9頁，共39頁?！爸苯舆x擇排序”算法舉例2345789第6次循環(huán)后，排序結(jié)束2937845與首元素交換，第1次循環(huán)結(jié)束4937825數(shù)組的初態(tài)，全部是未排序元素4937825在未排序元素中確定最小數(shù)位置2397845與首元素交換，第2次循環(huán)結(jié)束2937845在未排序元素中確定最小數(shù)位置2347895與首元素交換，第3次循環(huán)結(jié)束2397845在未排序元素中確定最小數(shù)位置第10頁，共39頁。“直接選擇排序”算法的描述將原始數(shù)據(jù)放在數(shù)組A中；設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到i=n：{確定A[i]到A[n]中最小整數(shù)的位置，設(shè)為j；交換A[i]和[j]；i=i+1}原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i=i+1i=n?結(jié)束開始用偽代碼表示算法用流程圖表示算法第11頁，共39頁。直接選擇排序的c語言程序voidsort(intA[],intn)/*sort函數(shù)有2個參數(shù):整型數(shù)組A和數(shù)組元素個數(shù)n*/{inti,j,t,k;/*定義4個整型變量*/for(i=0;i<n-1;i++){/*重復(fù)執(zhí)行n-1次，每次增加1個已排序的數(shù)*/j=i;for(k=i+1;k<n;k++)if(A[k]<A[j])j=k;/*在未排序整數(shù)中確定最小數(shù)的位置*/t=A[i];A[i]=A[j];A[j]=t;/*把未排序數(shù)中的最小數(shù)交換到未排序數(shù)的首位*/}}第12頁，共39頁。3.算法的表示第13頁，共39頁。算法的表示方法文字說明流程圖表示用N-S盒圖表示算法用PAD圖描述算法偽代碼（一種介于自然語言和程序設(shè)計(jì)語言之間的文字和符號表達(dá)工具）第14頁，共39頁。自然語言描述“比較Ａ與Ｂ的重量，若Ａ＝Ｂ，則Ｃ是偽造的；否則再比較Ａ與Ｃ的重量，若Ａ＝Ｃ，則Ｂ是偽造的；否則Ａ是偽造的?！比秉c(diǎn)：容易產(chǎn)生歧義，很難“精確”地進(jìn)行表達(dá)敘述冗長，很難清楚地表達(dá)算法的邏輯流程第15頁，共39頁。算法的流程圖表示流程圖由結(jié)點(diǎn)和有向邊構(gòu)成，它描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖符號：比文字描述簡明，但當(dāng)算法比較復(fù)雜時，理解困難，容易產(chǎn)生錯誤端點(diǎn)符處理判斷預(yù)定義功能原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i=i+1i=n?結(jié)束開始第16頁，共39頁。求最大公約數(shù)的偽代碼表示算法3：輾轉(zhuǎn)相除法求最大公約數(shù)BEGINinputm,n;/*輸入正整數(shù)m和n*/do{r←mmodn;m←n;n←r;}whiler≠0;printm；/*輸出最大公約數(shù)*/ENDYNr不等于0?輸出m的值輸入正整數(shù)m和n開始結(jié)束r←m被n除的余數(shù)m←n;n←r第17頁，共39頁。4.算法的分析第18頁，共39頁。算法分析的基本內(nèi)容正確性：給定有效輸入后，經(jīng)過有限時間的計(jì)算，產(chǎn)生正確的輸出結(jié)果簡單性算法是否容易理解，是否容易驗(yàn)證其正確性，程序是否容易調(diào)試簡單的算法效率不一定高，要在保證一定效率的前提下力求算法簡單時間復(fù)雜性(TimeComplexity)：當(dāng)問題的規(guī)模n充分大時，運(yùn)行該算法所需要的時間的數(shù)量級表示空間復(fù)雜性(SpaceComplexity)：除原始數(shù)據(jù)之外，額外占用的存儲空間的大小第19頁，共39頁。選擇排序算法的時間復(fù)雜性假設(shè)參加排序的整數(shù)有n個（1）比較操作的次數(shù)： 在第i趟排序中選出最小整數(shù)時，需做n-i次比較操作， 因此，總的比較操作次數(shù)為：n(n-1)/2=(n2-n)/2（2）移動操作的次數(shù)： 最好情況(原始數(shù)據(jù)已經(jīng)排序)時，移動次數(shù)為0

最壞情況(原始數(shù)據(jù)逆序排列)時，每趟均要執(zhí)行交換操作(3次傳送)，總的移動次數(shù)取最大值為：3(n-1)所以，直接選擇排序的時間復(fù)雜性為O(n2)設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到I=n：{確定A[i]到A[n]中最小的整數(shù)元素的位置，設(shè)為j；交換A[i]和[j]；i=i+1}第20頁，共39頁。4.小結(jié)第21頁，共39頁。計(jì)算機(jī)中處處是算法！例1：Word程序如何在文檔中查找用戶指定的詞語？例2：在Word文檔的表格中如何將表格內(nèi)容排序？例3：如何把一幅彩色圖片轉(zhuǎn)換為灰度(黑白)圖片？例4：Windows如何在硬盤中找到用戶指定的文件？例5：媒體播放器如何把MP3文件轉(zhuǎn)換成動聽的音樂？例6：搜索引擎如何在WWW網(wǎng)中找到用戶需要的網(wǎng)頁？第22頁，共39頁。算法是計(jì)算機(jī)軟件的靈魂計(jì)算機(jī)的通用性是因?yàn)樗苓\(yùn)行各種各樣的程序，而程序之所以能解決問題，是因?yàn)樗w現(xiàn)了正確的算法 算法所解決的是一類問題而不是一個特定的問題，例如排序(sort)可以是表格內(nèi)容的排序，也可以是文件夾中文件的排序，可以按數(shù)字或文字排序，也可以按日期排序，等等查找(search)，可以在文檔中查找某個單詞或在硬盤中查找某個文件，也可在Web上查找某個網(wǎng)頁，等等開發(fā)計(jì)算機(jī)應(yīng)用的核心是：根據(jù)實(shí)際問題給出解題的算法，然后再將該算法在計(jì)算機(jī)上實(shí)現(xiàn)(即開發(fā)成為軟件)第23頁，共39頁。計(jì)算機(jī)算法的4個特點(diǎn)目的：完成某個特定的信息處理任務(wù)必須滿足的性質(zhì)：①確定性：算法中每一步操作的含義必須清楚明確，無二義性②能行性：算法中有待實(shí)現(xiàn)的操作都是計(jì)算機(jī)可執(zhí)行的，即必須在計(jì)算機(jī)的能力范圍之內(nèi)，且在有限時間內(nèi)能夠完成③有窮性：算法在執(zhí)行了有限步操作后必須結(jié)束④算法結(jié)束后至少產(chǎn)生一個輸出（包括參量或狀態(tài)的變化）第24頁，共39頁。3.4.2數(shù)據(jù)結(jié)構(gòu)第25頁，共39頁。算法(程序)的組成算法(程序)由2個部分組成：進(jìn)行的操作所涉及的操作對象(數(shù)據(jù))算法操作對象操作步驟與條件程序說明所要處理的數(shù)據(jù)的名字和類型描述所要執(zhí)行的算法說明語句命令語句第26頁，共39頁。什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)研究如何在計(jì)算機(jī)中表示被處理的對象及對象之間的關(guān)系，即如何組織數(shù)據(jù)。例如：選擇排序中，未排序整數(shù)和已排序整數(shù)如何表示？排序算法中，排序的對象若不是整數(shù)而是姓名如何表示？是文件夾中的文件名又如何表示？是表格中的“行”又如何表示？Word文檔中插入的表格和圖片如何表示？Windows操作系統(tǒng)中菜單如何表示？對話框如何表示？窗口如何表示？計(jì)算機(jī)下棋時，棋盤和棋局如何表示？精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)可使算法獲得更高的時間效率或空間效率第27頁，共39頁。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容1數(shù)據(jù)的抽象(邏輯)結(jié)構(gòu)，即數(shù)據(jù)結(jié)構(gòu)中包括哪些元素，相互之間有什么關(guān)系等。例如：2數(shù)據(jù)的物理(存儲)結(jié)構(gòu)，即數(shù)據(jù)的抽象結(jié)構(gòu)如何在實(shí)際的存儲器中予以實(shí)現(xiàn)，數(shù)據(jù)元素如何表示，相互關(guān)系如何表示等3定義在數(shù)據(jù)結(jié)構(gòu)上的一組運(yùn)算(操作)及其實(shí)現(xiàn)方法線性結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹形結(jié)構(gòu)集合結(jié)構(gòu)第28頁，共39頁。2.線性數(shù)據(jù)結(jié)構(gòu)

第29頁，共39頁。舉例：線性表(Liner-List)定義：若干個相同類型的數(shù)據(jù)元素組成的一個有限序列，其中每個數(shù)據(jù)元素可由多個數(shù)據(jù)項(xiàng)組成。表中有且僅有一個開始元素和一個結(jié)束元素，且所有元素都最多只有一個直接前趨和一個直接后繼例：考生成績登記表(table)數(shù)據(jù)元素已經(jīng)排了序的線性表稱為有序線性表，簡稱有序表34681張雷64834682王寧68234683周光明58834684李霞霞61534685錢欣608………………34700趙剛658準(zhǔn)考證號姓名總分表中的每一行是1個數(shù)據(jù)元素每個數(shù)據(jù)元素包含3個數(shù)據(jù)項(xiàng)：準(zhǔn)考證號、姓名、總分開始元素結(jié)束元素前趨元素后繼元素第30頁，共39頁。線性表的運(yùn)算(操作)增加1個新的數(shù)據(jù)元素刪除1個指定數(shù)據(jù)元素查找指定的數(shù)據(jù)元素最高分考生最低分考生將表中的數(shù)據(jù)元素排序?qū)Ρ碇械臄?shù)據(jù)進(jìn)行計(jì)算計(jì)算平均分···34681張雷64834682王寧68234683周光明58834684李霞霞61534685錢欣608………………34700趙剛658準(zhǔn)考證號姓名總分第31頁，共39頁。數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)——存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系鏈接表存儲結(jié)構(gòu)：利用地址指針來表示元素之間的邏輯關(guān)系a1a2低地址高地址a2是a1的后繼元素a1a2a2是a1的后繼元素第32頁，共39頁。假設(shè)下面的有序表中姓名已按拼音排序例：線性表的實(shí)現(xiàn)方法之1使用數(shù)組實(shí)現(xiàn)，在內(nèi)存中順序存放元素：如果要在表中加一個姓名:馬明，結(jié)果為：程紅李軍劉林劉建平王曉林張小明010016022028034040046

程紅李軍劉林劉建平王曉林張小明010016022028034040046馬明分析：尋找指定的數(shù)據(jù)元素很容易插入元素或刪除元素很不方便程紅李軍劉林劉建平王曉林張小明內(nèi)存地址第33頁，共39頁。線性表的實(shí)現(xiàn)方法之2使用鏈接表(linkedlist)實(shí)現(xiàn)：數(shù)據(jù)元素在內(nèi)存中可不按順序存放，它們之間的順序用“指針”來表示指針實(shí)際上就是后繼數(shù)據(jù)元素的地址演示2種實(shí)現(xiàn)方法的對比：數(shù)組實(shí)現(xiàn)的空間開銷少；存取指定元素的速度比較塊鏈表實(shí)現(xiàn)時插入/刪除指定元素的速度快，表的長度不受限制第n個考生準(zhǔn)考證號、姓名、…∧第1個考生準(zhǔn)考證號、姓名、…Link第2個考生準(zhǔn)考證號、姓名、…Link第3個考生準(zhǔn)考證號、姓名、…Link第34頁，共39頁。3.非線性數(shù)據(jù)結(jié)構(gòu)

第35頁，共39頁。樹(Tree)“樹”是一種與線性表不同的數(shù)據(jù)結(jié)