數(shù)據(jù)結(jié)構(gòu)與算法第一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Chapter1第二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Section1數(shù)據(jù)結(jié)構(gòu)討論的范疇第三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三計(jì)算機(jī)程序設(shè)計(jì)的兩大要素程序=數(shù)據(jù)結(jié)構(gòu)+算法程序→為計(jì)算機(jī)解題而編寫的一組指令集數(shù)據(jù)結(jié)構(gòu)→問題的數(shù)學(xué)模型算法→處理問題的策略（計(jì)算的方法）第四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三計(jì)算機(jī)如何解題要處理的現(xiàn)實(shí)問題怎么表示？即怎樣用數(shù)學(xué)形式（函數(shù)、公式、符號(hào)）抽象地表示現(xiàn)實(shí)問題？也就是問題的數(shù)學(xué)模型是什么？這就是數(shù)據(jù)結(jié)構(gòu)要討論的問題。怎樣對(duì)問題進(jìn)行信息處理？也就是處理問題的策略是什么？這就是算法要討論的問題。第五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三計(jì)算機(jī)解題的步驟從現(xiàn)實(shí)問題中抽象出一個(gè)具體的數(shù)學(xué)模型設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的合適算法使用某種編程語(yǔ)言將算法“翻譯”成程序并調(diào)試正確通過多方位的測(cè)試，使程序投入實(shí)際運(yùn)行，即使問題獲得目標(biāo)結(jié)果第六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三計(jì)算機(jī)的兩大應(yīng)用領(lǐng)域數(shù)值計(jì)算（科學(xué)與工程計(jì)算）數(shù)據(jù)：數(shù)值數(shù)據(jù)計(jì)算：解方程（組）、函數(shù)求值、概略統(tǒng)計(jì)、運(yùn)籌等非數(shù)值計(jì)算（邏輯計(jì)算/數(shù)值處理）數(shù)據(jù)：文字、符號(hào)、表格、圖象、聲音、視頻等計(jì)算：比較、歸類、統(tǒng)計(jì)、查找、排序、轉(zhuǎn)換以及傳輸?shù)鹊谄唔?yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)值計(jì)算對(duì)于數(shù)值計(jì)算問題的解決方法，主要是用各種數(shù)學(xué)方程建立數(shù)學(xué)模型，例如：天氣預(yù)報(bào)的數(shù)學(xué)模型為二階橢圓偏微分方程，預(yù)測(cè)人口增長(zhǎng)的數(shù)學(xué)模型為常微分方程。求解這些數(shù)學(xué)方程的方法是計(jì)算數(shù)學(xué)（數(shù)值分析）研究的領(lǐng)域，例如差分算法、有限元算法、無(wú)限元算法等。第八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-1：雞兔同籠問題數(shù)學(xué)模型算法二元一次方程如：x+y=m2x+4y=n(m≥2,n≥6且n%2=0)枚舉法for(x=1;x<=m-1;x++)for(y=1;y<=m-1;y++)if((x+y==m)and(2*x+4*y==n)){print(“雞＝”x”,兔子＝”y)；

break;}第九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三非數(shù)值計(jì)算當(dāng)今計(jì)算機(jī)能夠處理的應(yīng)用問題90%以上是非數(shù)值計(jì)算問題——包括數(shù)據(jù)的比較、歸類、統(tǒng)計(jì)、查找、排序、轉(zhuǎn)換以及傳輸?shù)?。而絕大多數(shù)非數(shù)值計(jì)算問題是無(wú)法用數(shù)學(xué)方程式來描述的，它們需要使用特定的離散數(shù)學(xué)模型，如線性表樹圖這些模型及其算法就是數(shù)據(jù)結(jié)構(gòu)學(xué)科所要研究的內(nèi)容。第十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-2圖書數(shù)目檢索數(shù)學(xué)模型：各種書目表（線性結(jié)構(gòu)）書目信息如：書名、作者、出版社、出版日期、書號(hào)、分類號(hào)、內(nèi)容提要等。問題：如何表示和組織書目信息？算法：按照某個(gè)特定要求（如給定書名）對(duì)相關(guān)書目表進(jìn)行查詢的方法。第十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三001數(shù)據(jù)結(jié)構(gòu)張山清華出版社T01……002高等數(shù)學(xué)李司高教出版社S01……003數(shù)據(jù)結(jié)構(gòu)王武清華出版社T02……004經(jīng)濟(jì)學(xué)原理馬魯三聯(lián)出版社J01……………………………

……

數(shù)據(jù)結(jié)構(gòu)001,003,…高等數(shù)學(xué)002,……經(jīng)濟(jì)學(xué)原理004,………………張山001,023李司002,…王武003,……………圖1-1書目表示例T001,003…S002…J004…………第十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-3人機(jī)對(duì)弈數(shù)學(xué)模型：對(duì)弈樹（樹結(jié)構(gòu)）問題：如何表示、組織棋盤和棋子信息，如何表示、組織并保存動(dòng)態(tài)變化的棋局狀態(tài)（格局）算法：對(duì)弈／走棋操作的算法——使格局發(fā)生變化，由一種格局派生出另一種格局，并從多種可選路徑中選擇一種最優(yōu)／合理路徑，最后達(dá)到輸／贏狀態(tài)第十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三圖1-2井字棋對(duì)弈樹的局部

井字棋游戲的規(guī)則：從一個(gè)空的棋盤開始，白子先行，輪流走棋。判定勝負(fù)的標(biāo)準(zhǔn)是：三枚同色棋子占據(jù)了一橫行或一豎行或一對(duì)角線，則獲勝；如果直到棋盤被占滿時(shí)還沒有一方獲勝，則為和局。第十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-4：多叉路口的交通燈管理問題目標(biāo)：如何保證多叉路口的交通暢通有序，并使交通流量達(dá)到最大，且不會(huì)發(fā)生交通事故，數(shù)學(xué)模型：通路狀態(tài)圖（圖／網(wǎng)結(jié)構(gòu)）需解決的問題：①當(dāng)某一條通路通行時(shí)，有哪些通路不能同時(shí)通行？②當(dāng)某一條通路通行時(shí)，有哪些通路可同時(shí)通行？③如何表示和組織通路狀態(tài)信息？算法：結(jié)點(diǎn)的動(dòng)態(tài)分組著色（綠色）策略，相鄰結(jié)點(diǎn)不能同時(shí)為綠色。第十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三ABCDE可通路非通路

A→B:BCBDDAEA

A→C:BDDADBEAEBA→D:EAEBECB→A:B→C:ABDBEBB→D:ACDAECD→A:ABACBDEBD→B:ACBCECD→C:E→A:ABACADE→B:ACADBCBDDAE→C:ADBDDBE→D:圖1-3五叉路口示意圖第十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三ABACADDCBABCBDEBEDEADADBEC每個(gè)結(jié)點(diǎn)代表一條通路；不能同時(shí)通行的結(jié)點(diǎn)用一條連線連接(相鄰）；相鄰結(jié)點(diǎn)用不同顏色標(biāo)記，表示不能同時(shí)通行；相同顏色的結(jié)點(diǎn)表示這些通路可同時(shí)通行。孤立結(jié)點(diǎn)表示任何時(shí)候都可以通行，恒為綠色。圖1-4通路狀態(tài)圖第十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)研究現(xiàn)實(shí)問題的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的算法在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是一門不斷發(fā)展的核心學(xué)科，隨著計(jì)算機(jī)處理的非數(shù)值計(jì)算問題越來越廣泛、深入和復(fù)雜，數(shù)據(jù)結(jié)構(gòu)需要研究越來越復(fù)雜的結(jié)構(gòu)和算法。第十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Section2基本概念第十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三基本術(shù)語(yǔ)數(shù)據(jù)（Data）客觀事物的符號(hào)表示，是計(jì)算機(jī)可操作的對(duì)象。所有能被輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。信息在計(jì)算機(jī)中的表示。數(shù)據(jù)元素（DataElement）數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。一個(gè)數(shù)據(jù)元素也可以由一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)（DataItem）組成。數(shù)據(jù)項(xiàng)是有意義的數(shù)據(jù)的最小原子單位。數(shù)據(jù)對(duì)象（DataObject）性質(zhì)相同的數(shù)據(jù)元素的集合。第二十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三example數(shù)據(jù)對(duì)象數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)整數(shù)集單個(gè)整數(shù)單個(gè)整數(shù)（不可再分）復(fù)數(shù)集單個(gè)復(fù)數(shù)實(shí)部，虛部學(xué)生檔案單個(gè)學(xué)生記錄多個(gè)數(shù)據(jù)項(xiàng)（學(xué)號(hào)、姓名、性別等）第二十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的定義帶結(jié)構(gòu)的數(shù)據(jù)元素的集合/帶結(jié)構(gòu)的數(shù)據(jù)對(duì)象。這里的結(jié)構(gòu)是指數(shù)據(jù)元素之間的某種約束關(guān)系，即數(shù)據(jù)結(jié)構(gòu)中討論的數(shù)據(jù)元素都不是孤立的，而是相互之間必定存在著一定的關(guān)系。相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。關(guān)系決定了結(jié)構(gòu)。對(duì)于同樣的數(shù)據(jù)元素，不同的關(guān)系將構(gòu)成不同的結(jié)構(gòu)。第二十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的類型邏輯結(jié)構(gòu)（LogicalStructure）存儲(chǔ)結(jié)構(gòu)（StorageStructure）第二十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三邏輯結(jié)構(gòu)“數(shù)據(jù)結(jié)構(gòu)”通常指的只是數(shù)據(jù)的邏輯結(jié)構(gòu)，它描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)元素之間固有的（內(nèi)在的）、本質(zhì)的聯(lián)系，它們反映在人們的概念上，是抽象的，與物理的計(jì)算機(jī)無(wú)關(guān)。集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)第二十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三集合結(jié)點(diǎn)之間不存在關(guān)系，或說僅僅存在“同屬一個(gè)數(shù)據(jù)對(duì)象”的關(guān)系。第二十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三線性結(jié)構(gòu)元素（結(jié)點(diǎn)node）之間存在線性關(guān)系／1:1關(guān)系；除首結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)；除尾結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)后繼。首結(jié)點(diǎn)尾結(jié)點(diǎn)第二十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三樹形結(jié)構(gòu)結(jié)點(diǎn)之間存在層次關(guān)系／1:n關(guān)系；除根結(jié)點(diǎn)無(wú)前驅(qū)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，但任一結(jié)點(diǎn)可以有0~n個(gè)后繼。

根結(jié)點(diǎn)第二十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三※樹和圖統(tǒng)稱“非線性結(jié)構(gòu)”結(jié)點(diǎn)之間存在任意關(guān)系／n:m關(guān)系：可以存在沒有前驅(qū)的結(jié)點(diǎn)或和沒有后繼的結(jié)點(diǎn)，其他的每個(gè)結(jié)點(diǎn)則可以有多個(gè)前驅(qū)，也可以有多個(gè)后繼。（在圖中，元素也稱作“頂點(diǎn)”）

網(wǎng)狀結(jié)構(gòu)（圖）第二十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映象(image)。即邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示順序存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu)第二十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三順序存儲(chǔ)結(jié)構(gòu)通過數(shù)據(jù)元素在存儲(chǔ)器中的一個(gè)固定的相對(duì)位置來表示元素之間的前驅(qū)或后繼關(guān)系。采用順序映象的物理結(jié)構(gòu)稱作順序結(jié)構(gòu)。a0a1a2a3102104106108第三十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三鏈接順序結(jié)構(gòu)通過在元素的存儲(chǔ)單元中附加“指針”的方式來表示前驅(qū)或后繼關(guān)系。采用鏈?zhǔn)接诚蟮奈锢斫Y(jié)構(gòu)稱作鏈?zhǔn)浇Y(jié)構(gòu)。a0a1a2a3first第三十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面。一般地，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可用多種物理結(jié)構(gòu)來存儲(chǔ)，而采用不同的物理結(jié)構(gòu)，其數(shù)據(jù)處理的算法及其效率往往是不同的。算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)算法的實(shí)現(xiàn)依賴于采用的物理結(jié)構(gòu)第三十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)常見的運(yùn)算創(chuàng)建運(yùn)算清除運(yùn)算插入運(yùn)算刪除運(yùn)算搜索運(yùn)算更新運(yùn)算訪問運(yùn)算遍歷運(yùn)算第三十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Section3數(shù)據(jù)抽象和抽象數(shù)據(jù)類型第三十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)抽象和抽象數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)集合上的一組操作的總稱數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語(yǔ)言所定義的某類數(shù)據(jù)的集合和定義在該集合上的一組原操作的總稱。原操作是指可對(duì)集合中的數(shù)據(jù)元素進(jìn)行的運(yùn)算，其算法已由語(yǔ)言系統(tǒng)或計(jì)算機(jī)硬件實(shí)現(xiàn)，并用特定的符號(hào)（運(yùn)算符）表示。

數(shù)據(jù)類型＝集合＋原操作集第三十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Example整形數(shù)據(jù)類型（int）值的范圍：-232~232-1（-32768~32767）元素映像：4字節(jié)存儲(chǔ)單元算數(shù)運(yùn)算：+,-,×,/關(guān)系運(yùn)算：<,>,<=,>=,!=,==賦值運(yùn)算：=第三十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三AbstractDataType抽象數(shù)據(jù)類型（ADT）是數(shù)據(jù)類型的擴(kuò)展或是廣義的數(shù)據(jù)類型，它可定義各種類型的邏輯數(shù)據(jù)結(jié)構(gòu)，包括線性表、樹、圖等。抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)結(jié)構(gòu)和定義在這個(gè)數(shù)據(jù)結(jié)構(gòu)上的一組操作的總稱。ADT=數(shù)據(jù)結(jié)構(gòu)＋操作集這里的“操作”非原操作，需要自定義。ADT可用一個(gè)三元組表示：ADT=(D,R,P)D—數(shù)據(jù)對(duì)象，R—D上的關(guān)系集，P—對(duì)D的基本操作集第三十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三

ADT<抽象數(shù)據(jù)類型名>isDataObject:

<數(shù)據(jù)對(duì)象描述>Relation

:

<關(guān)系描述>Operation

:

<操作聲明>End<抽象數(shù)據(jù)類型名>在面向?qū)ο笳Z(yǔ)言中，ADT可用“類”來實(shí)現(xiàn)，其中的操作用“方法”（C++中稱為“成員函數(shù)”）實(shí)現(xiàn)。ADT的定義格式第三十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三復(fù)數(shù)運(yùn)算的構(gòu)造方法ADT1-1Complexe{

數(shù)據(jù)：由一對(duì)實(shí)數(shù)（x,y）構(gòu)成

運(yùn)算：兩個(gè)復(fù)數(shù)分別為a（a1,a2）和b（b1,b2） ComplexCreateComp(floatx,floaty)%構(gòu)造復(fù)數(shù) ComplexAdd(Complexa,Complexb)%求和 ComplexSub(Complexa,Complexb)%求差 ComplexMul(Complexa,Complexb)%求積 ComplexDiv(Complexa,Complexb)%求除數(shù) }第三十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三#include<stdio.h>#include<stdlib.h>typedefstructcomplex{ float

x,y;}complex;ComplexCreateComp(floatx,floaty){ Complexc; c.x=x;c.y=y; returnc;}ComplexAdd(Complexa,Complexb){ Complexc; c.x=a.x+b.x;c.y=a.y+b.y; returnc;}程序1-1Complex的實(shí)現(xiàn)第四十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三VoidPrintComplex(Complexa){ printf(“%3.2f+%3.2fi\n”,a.x,a.y);}Voidmain(){ Complexa,b,c; a=CreateComp(1.0f,2.0f); b=CreateComp(3.0f,4.0f); c=Add(a,b); PrintComplex(a); PrintComplex(b); PrintComplex(c);}程序1-2測(cè)試復(fù)數(shù)加法運(yùn)算第四十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三Section4算法和算法分析第四十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三算法和算法分析算法（Algorithm）是求解特定問題的方法，它是指令的有限序列。算法是對(duì)特定問題求解步驟進(jìn)行描述的一組指令集。這里的“指令”不是指計(jì)算機(jī)的機(jī)器指令，它可以是高級(jí)語(yǔ)言的一條或多條語(yǔ)句，也可以是偽碼語(yǔ)句，或用自然語(yǔ)言編寫的操作命令。第四十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三算法的特征輸入輸出確定性能行性有窮性第四十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三算法的描述算法不是程序，而是實(shí)現(xiàn)程序的方法（模型），設(shè)計(jì)算法也稱程序建模。自然語(yǔ)言：容易，但不簡(jiǎn)潔和嚴(yán)謹(jǐn)、有二義性。流程圖：算法邏輯直觀清晰，但轉(zhuǎn)換成高級(jí)語(yǔ)言程序需要一定的開銷。如程序流程圖、N-S圖、UML活動(dòng)圖。偽碼語(yǔ)言（算法語(yǔ)言）：介于自然語(yǔ)言和高級(jí)程序設(shè)計(jì)語(yǔ)言之間，保留了高級(jí)語(yǔ)言的語(yǔ)法骨架，但對(duì)具體語(yǔ)法和語(yǔ)法細(xì)節(jié)不做非常詳盡的要求，如忽略變量定義和輸入/出格式等。特點(diǎn)是簡(jiǎn)潔、易讀、嚴(yán)謹(jǐn)、易被轉(zhuǎn)換成高級(jí)語(yǔ)言。流行的如PDL等。高級(jí)語(yǔ)言：開銷大，不靈活，不符合軟件工程思想，不是現(xiàn)代軟件設(shè)計(jì)風(fēng)格。第四十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期三算法和程序的主要區(qū)別程序不一定滿足有窮性，可以出現(xiàn)有意義的無(wú)窮循環(huán)；算法則必須滿足有窮性。程序中的指令必須是機(jī)器可執(zhí)行的；而算法中的指令則無(wú)此限制，算法只是程序的模型。設(shè)計(jì)算法是軟件開發(fā)過程中詳細(xì)設(shè)計(jì)階段的工作，由高級(jí)程序員完成；編程的實(shí)質(zhì)是算法的編程語(yǔ)言翻譯，是編碼階段的工作，由普通程序員完成。第四十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期三軟件開發(fā)過程

系統(tǒng)分析員系統(tǒng)設(shè)計(jì)員高級(jí)程序員程序員系統(tǒng)測(cè)試員需求分析概要設(shè)計(jì)詳細(xì)設(shè)計(jì)編碼測(cè)試設(shè)計(jì)ADT是概要設(shè)計(jì)階段的工作，由系統(tǒng)設(shè)計(jì)員完成；算法設(shè)計(jì)是詳細(xì)設(shè)計(jì)階段的工作，由高級(jí)程序員完成；用編程語(yǔ)言編程則是編碼階段的工作，由程序員完成。第四十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期三本課程的要求

系統(tǒng)設(shè)計(jì)員——設(shè)計(jì)ADT

高級(jí)程序員——設(shè)計(jì)算法

程序員——編寫C++程序并上機(jī)調(diào)試測(cè)試員——找程序的毛病

第四十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期三算法評(píng)價(jià)的標(biāo)準(zhǔn)正確性：算法的運(yùn)行結(jié)果應(yīng)當(dāng)滿足系統(tǒng)需求。一個(gè)算法的正確性必須通過測(cè)試才能驗(yàn)證健壯性：是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反映和處理能力。當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理?？勺x性：算法是寫給其他人（程序員、測(cè)試人員及維護(hù)人員）看的??！效率：包括時(shí)間性和空間性，即運(yùn)行該算法程序所需花費(fèi)的時(shí)間和占用存儲(chǔ)空間的大小。對(duì)于同一個(gè)問題如果有多個(gè)算法可以解決，運(yùn)行時(shí)間短的算法效率高，這是評(píng)價(jià)算法效率最主要的度量。第四十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期三時(shí)間復(fù)雜度時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的時(shí)間一個(gè)算法的時(shí)間復(fù)雜度是該算法中各條原指令的重復(fù)執(zhí)行次數(shù)之和，記為T(n)，它是問題規(guī)模n的函數(shù)，與問題規(guī)模成正比。算法的執(zhí)行時(shí)間=Σ[語(yǔ)句(i)的執(zhí)行次數(shù)*語(yǔ)句(i)的執(zhí)行時(shí)間]問題規(guī)模是指算法對(duì)求解問題所要處理的數(shù)據(jù)量。例如，求100以內(nèi)還是10000以內(nèi)的素?cái)?shù)，就說后者規(guī)模比前者大。第五十頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-5

算法:兩數(shù)交換

s=a;

//1次

a=b;

//1次

b=s;

//1次

∴T(n)=３例1-6算法:求累加和

s=0;//1次

for(i=0;i<n;i++)//n+1次

s+=a[i];

//n次

∴T(n)=2n+2第五十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-7

算法:矩陣相加

for(i=0;i<n;i++)

//n+1次

for(j=0;j<n;j++)

//n(n+1)次

c[i][j]=a[i][j]+b[i][j];

//n*n次

∴T(n)=2n2+2n+1第五十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期三漸進(jìn)時(shí)間復(fù)雜度一個(gè)算法的時(shí)間復(fù)雜度的計(jì)算是比較繁瑣的，特別對(duì)于較復(fù)雜的算法更是如此。實(shí)際上，一般也沒有必要精確地計(jì)算出算法的時(shí)間復(fù)雜度，只要大致計(jì)算出相應(yīng)的數(shù)量級(jí)／階（order）即可。假如，隨著問題規(guī)模n的增長(zhǎng)，時(shí)間復(fù)雜度的增長(zhǎng)率和某個(gè)函數(shù)f(n)的增長(zhǎng)率相同；換言之，當(dāng)n→∞時(shí)，T(n)與f(n)同階無(wú)窮大且f(n)是T(n)的上界，則可記作：T(n)=O(f(n))并稱T(n)為為算法的漸進(jìn)時(shí)間復(fù)雜度（通常也簡(jiǎn)稱為時(shí)間復(fù)雜度），其值用大O表示。第五十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-8

算法:矩陣相乘voidmult(inta[],intb[],int&c[]){//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積 for(i=1;i<=n;++i) \\n+1 for(j=1;j<=n;++j) \\n(n+1) { c[i,j]=0; \\n2 for(k=1;k<=n;++k) \\n2(n+1) c[i,j]+=a[i,k]*b[k,j]; \\n3 }}∴T(n)=2n3+3n2+2n+1∴漸進(jìn)時(shí)間復(fù)雜度：O(n3)第五十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期三例1-9算法：選擇排序voidselect_sort(Typea[],intn)//將數(shù)組a中的數(shù)值序列排列成小→大的有序序列{

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

min=i;