數(shù)據(jù)結(jié)構（C語言版）課件 第1章緒論

數(shù)據(jù)結(jié)構（C語言版）緒論第1章編程基礎為什么要學習數(shù)據(jù)結(jié)構計算機及相關專業(yè)考研考博課程程序員考試課程軟件開發(fā)相關崗位招聘考核內(nèi)容課程學習指導提前預習認真聽課完成作業(yè)課程特點：內(nèi)容抽象、概念性強、內(nèi)容靈活、不易掌握01020304先修課程的知識準備離散數(shù)學C語言C++少量知識注意循序漸進：基本概念、基本思想、基本步驟、算法實現(xiàn)注意培養(yǎng)算法設計的能力理解所講算法對此多做思考：若問題要求不同，應如何選擇數(shù)據(jù)結(jié)構，設計有效的算法平時成績:40%課堂表現(xiàn)作業(yè)單元測驗實驗考核方式1期末成績:60%（閉卷筆試）2了解數(shù)據(jù)結(jié)構研究的主要內(nèi)容掌握算法的時間、空間復雜度及其分析的簡易方法01OPTION02OPTION03OPTIONtarget目標掌握數(shù)據(jù)結(jié)構中涉及的基本概念目錄導航1.11.21.31.4數(shù)據(jù)結(jié)構的研究內(nèi)容基本概念和術語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法與算法分析Contents

N.沃思（NiklausWirth)教授提出：程序=算法+數(shù)據(jù)結(jié)構

電子計算機的主要用途：早期：主要用于數(shù)值計算后來：非數(shù)值計算，復雜的具有一定結(jié)構關系的數(shù)據(jù)數(shù)據(jù)結(jié)構的研究內(nèi)容用計算機求解問題現(xiàn)實世界

計算機

世界需求模型程序數(shù)學模型分析設計編程調(diào)試和維護數(shù)據(jù)結(jié)構＋算法數(shù)據(jù)結(jié)構的研究內(nèi)容書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表人機對奕問題樹……..……..…...…...…...….../(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)的系統(tǒng)結(jié)構圖樹多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖頂點：一條通路連線：不能同時通行染色：有連線的兩個頂點不能具有相同顏色六度空間理論你和任何一個陌生人之間所間隔的人不會超過6個，也就是說，最多通過6個中間人你就能夠認識任何一個陌生人。圖描述非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構。設計出合適的數(shù)據(jù)結(jié)構及相應的算法。即：首先要考慮對相關的各種信息如何表示、組織和存儲？求解非數(shù)值計算的問題數(shù)據(jù)結(jié)構的研究內(nèi)容研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作。形成階段：60年代初期，“數(shù)據(jù)結(jié)構”有關的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構”被列入美國一些大學計算機科學系的教學計劃。數(shù)據(jù)結(jié)構課程的形成和發(fā)展

發(fā)展階段：數(shù)據(jù)結(jié)構的概念不斷擴充，包括了網(wǎng)絡、集合代數(shù)論、關系等“離散數(shù)學結(jié)構”的內(nèi)容。70年代后期，我國高校陸續(xù)開設該課程。數(shù)據(jù)結(jié)構創(chuàng)始人--高德納(DonaldErvinKnuth)程序設計是一門藝術如音樂和文學作品。BillGates“如果你學會了這本書，就直接給微軟發(fā)個簡歷！”1968年，第一卷《基本算法》1969年，第二卷《半數(shù)字化算法》1973年，第三卷《排序與搜索》2011年，第四卷A《組合算法》……計劃七卷雙向鏈表字符串模式匹配算法KMP編譯器LR……TeX，LaTeX數(shù)據(jù)結(jié)構創(chuàng)始人--高德納(DonaldErvinKnuth)1938年出生，斯坦福大學計算機系教授--36歲圖靈獎經(jīng)典著作Knuth撰寫了多部具有里程碑意義的經(jīng)典著作，如《計算機程序設計藝術》，成為計算機科學領域的必讀之作。創(chuàng)立新理論推廣新技術他在算法分析、數(shù)據(jù)結(jié)構等領域創(chuàng)立了新理論，如算法的時間復雜度和空間復雜度分析，為后來的研究提供了重要指導。Knuth積極推廣新技術和新方法，如TeX排版系統(tǒng)和METAFONT字體設計系統(tǒng)，對出版印刷領域產(chǎn)生了深遠影響。數(shù)據(jù)結(jié)構創(chuàng)始人--高德納(DonaldErvinKnuth)數(shù)據(jù)結(jié)構創(chuàng)始人--高德納(DonaldErvinKnuth)Knuth在研究過程中遇到許多困難和挫折，但他始終堅定信念，持之以恒地解決問題。堅持不懈他對自己的研究成果要求極高，不斷追求精益求精，力求做到最好。精益求精Knuth在數(shù)據(jù)結(jié)構領域的研究投入了大量的時間和精力，長期堅持不懈，最終取得了顯著的成果。長期投入練內(nèi)功不要只花功夫?qū)W習各種流行的編程語言和工具，以及一些公司招聘廣告上要求的科目。學好基礎課程離散數(shù)學、數(shù)據(jù)結(jié)構、計算機組成原理、操作系統(tǒng)、計算機網(wǎng)絡、編譯原理、數(shù)據(jù)庫等。試試Knuth的TheArtofComputerProgramming的題目。多實戰(zhàn)通過編程的實戰(zhàn)，積累經(jīng)驗、內(nèi)化知識。建議大家爭取在大學四年中積累編寫十萬行代碼的經(jīng)驗。李開復建議（專研+潛力+創(chuàng)新）介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程數(shù)據(jù)結(jié)構所處的地位數(shù)據(jù)結(jié)構在計算機學科中的地位能夠分析研究計算機加工的對象的特性，獲得其邏輯結(jié)構，根據(jù)需求，選擇合適存貯結(jié)構及其相應的算法；課程目的學習一些常用的算法；復雜程序設計的訓練過程，要求編寫的程序結(jié)構清楚和正確易讀；初步掌握算法的時間分析和空間分析技術。目錄導航1.11.21.31.4數(shù)據(jù)結(jié)構的研究內(nèi)容基本概念和術語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法與算法分析Contents所有能輸入到計算機中去的描述客觀事物的符號。數(shù)值性數(shù)據(jù)：整數(shù)、實數(shù)等；非數(shù)值性數(shù)據(jù)：字符、文本、聲音、圖像、視頻等；數(shù)據(jù)是計算機程序加工的原料，是信息的編碼表示。數(shù)據(jù)的基本單位，在計算機程序中通常作為一個邏輯整體進行處理。不同場合下，也常被稱為元素、結(jié)點、頂點和記錄等。1.數(shù)據(jù)（Data)2.數(shù)據(jù)元素

（DataElement）基本概念和術語三者之間的關系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：學生表

>學生記錄>學號、姓名、性別……當一個數(shù)據(jù)元素包含多個部分信息時，其中每個部分信息為一個數(shù)據(jù)項。如一個學生記錄可能包含學號、姓名、性別等多個數(shù)據(jù)項。數(shù)據(jù)項是構成數(shù)據(jù)元素的不可分割的最小單位，也稱為字段、域或?qū)傩浴?.數(shù)據(jù)項（DataItem）基本概念和術語三者之間的關系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：學生表

>學生記錄>學號、姓名、性別……學號姓名分數(shù)2018001王華902018010劉麗622018006陳明542018009張強952018007許兵762018012李萍882018005李英82數(shù)據(jù)數(shù)據(jù)項數(shù)據(jù)元素基本概念和術語4.數(shù)據(jù)對象(DataObject)相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。整數(shù)的數(shù)據(jù)對象是集合{0,±1,±2,…}。英文字母的數(shù)據(jù)對象是集合{'a','A','b','B',…}。學生數(shù)據(jù)對象是學生記錄的集合。在具體應用中，一個數(shù)據(jù)對象中的元素通常相互之間存在某種關系?；靖拍詈托g語數(shù)據(jù)結(jié)構是帶“結(jié)構”的數(shù)據(jù)元素的集合，“結(jié)構”就是指數(shù)據(jù)元素之間存在的關系。5.數(shù)據(jù)結(jié)構（DataStructure）相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構＝數(shù)據(jù)對象＋結(jié)構數(shù)據(jù)元素之間的關系相同性質(zhì)的數(shù)據(jù)元素的集合基本概念和術語數(shù)據(jù)元素之間的關系

結(jié)構現(xiàn)實世界的結(jié)構是紛繁復雜的

微觀世界―DNA結(jié)構

宏觀世界―建筑物的結(jié)構基本概念和術語數(shù)據(jù)結(jié)構的兩個層次邏輯結(jié)構存儲結(jié)構（物理結(jié)構）從具體問題抽象出來的數(shù)學模型數(shù)據(jù)元素間抽象化的邏輯關系與數(shù)據(jù)存儲無關，獨立于計算機數(shù)據(jù)元素及其關系在計算機存儲器中的存儲方式邏輯結(jié)構在計算機中的存儲實現(xiàn)邏輯結(jié)構與存儲結(jié)構的關系存儲結(jié)構是邏輯結(jié)構在計算機中的映射。存儲所有元素；存儲數(shù)據(jù)元素間的關系。

邏輯結(jié)構存儲結(jié)構映射邏輯結(jié)構是數(shù)據(jù)關系的抽象描述，存儲結(jié)構是這些關系的具體實現(xiàn)。同一邏輯結(jié)構可以有不同的存儲結(jié)構（順序存儲、鏈式存儲）實現(xiàn)。存儲結(jié)構的選擇影響操作效率。劃分方法一邏輯結(jié)構

線性結(jié)構有且僅有一個開始和一個終端結(jié)點，并且

所有結(jié)點都最多只有一個直接前趨和一個后繼。例如：線性表、棧、隊列、串非線性結(jié)構

一個結(jié)點可能有多個直接前趨和直接后繼。例如：樹、圖02OPTION01OPTION線性結(jié)構一個對一個，如線性表、棧、隊列。樹形結(jié)構一個對多個，如樹。集合數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系。圖形結(jié)構多個對多個，如圖。邏輯結(jié)構劃分方法二存儲結(jié)構順序存儲結(jié)構借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關系。1鏈式存儲結(jié)構借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關系。2元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容順序存儲Loc(元素i)=Lo+（i-1)*m1536元素21400元素11346元素3∧元素41345h

鏈式存儲h存儲地址存儲內(nèi)容指針1345

元素114001346

元素4∧…….……..…….

1400

元素2

1536…….……..…….1536

元素31346邏輯結(jié)構和存儲結(jié)構都相同，但運算不同，

則數(shù)據(jù)結(jié)構不同。例如，棧與隊列。數(shù)據(jù)的運算1234插入查找刪除修改排序5對于一種數(shù)據(jù)結(jié)構,常見的運算：數(shù)據(jù)類型決定了變量或常量的取值范圍及可以對其進行的操作。數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型(DataType)charintfloatdoublevoid數(shù)組結(jié)構體共用體文件C語言Pyhton語言Number（數(shù)字）String（字符串）List（列表）Tuple（元組）Set（集合）Dictionary（字典）Complex（復數(shù)）C語言#include<iostream> usingnamespacestd; intmain(){intx,y,m;//若換成：floatx,y,m;cin>>x>>y; m=x%y;

cout<<m<<endl; return0; }數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)類型：值的集合+一組操作int：

值域[-231，231-1]操作：+

-

*

/

%等float:值域：[-3.40282×1038，3.40282×1038]操作：+-*/等（不包括

%

）數(shù)據(jù)類型是一組性質(zhì)相同的值的集合，以及定義于這個集合上的一組運算的總稱。Error:invalidoperandsoftypes'float'and'float'tobinary'operator%'抽象數(shù)據(jù)類型(ADT:AbstractDataType)由用戶定義，從應用問題抽象出來的數(shù)據(jù)模型（邏輯結(jié)構）。由基本的數(shù)據(jù)類型組成，并包括一組相關操作（抽象運算）。不考慮計算機內(nèi)的存儲結(jié)構及運算的具體實現(xiàn)。數(shù)據(jù)類型和抽象數(shù)據(jù)類型線性表、棧、隊列、樹、圖等數(shù)據(jù)結(jié)構不能直接用數(shù)據(jù)類型表示抽象數(shù)據(jù)類型的定義格式抽象數(shù)據(jù)類型使用三元組來表示：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關系：<數(shù)據(jù)關系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名

基本操作名（參數(shù)表）

初始條件：<初始條件描述>//若“初始條件”為空，則省略

操作結(jié)果：<操作結(jié)果描述>//說明操作完成后返回的結(jié)果基本操作的定義格式：數(shù)據(jù)對象和數(shù)據(jù)關系的定義格式：

采用自然語言和數(shù)學符號進行描述ADTComplex{

數(shù)據(jù)對象

：D={e1,e2|e1,e2∈R,R是實數(shù)集}數(shù)據(jù)關系：S={<e1,e2>|e1是復數(shù)的實部,e2是復數(shù)的虛部}基本操作:

Creat(&C,x,y)

操作結(jié)果：構造復數(shù)C，其實部和虛部分別被賦予參數(shù)x和y的值。

GetImag(C)

初始條件：復數(shù)C已存在。

操作結(jié)果：返回復數(shù)C的虛部值。

Add(C1,C2)

初始條件：C1，C2是復數(shù)。

操作結(jié)果：返回兩個復數(shù)C1和C2的和。

Sub(C1,C2)

初始條件：C1，C2是復數(shù)。

操作結(jié)果：返回兩個復數(shù)C1和C2的差。

}ADTComplex抽象數(shù)據(jù)類型的定義示例（復數(shù)）ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象

：<數(shù)據(jù)對象的定義>數(shù)據(jù)關系

：<數(shù)據(jù)關系的定義>基本操作:

操作1

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>

操作2

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>......

}ADT抽象數(shù)據(jù)類型名小結(jié)

數(shù)據(jù)

數(shù)據(jù)元素

數(shù)據(jù)對象個體性質(zhì)相同的元素加上數(shù)據(jù)元素之間的關系數(shù)據(jù)結(jié)構邏輯模型邏輯結(jié)構種類集合結(jié)構線性結(jié)構樹結(jié)構圖結(jié)構映射到存儲器存儲結(jié)構順序存儲結(jié)構鏈式存儲結(jié)構抽象數(shù)據(jù)類型加上操作構成的集合數(shù)據(jù)對象數(shù)據(jù)關系基本操作小結(jié)

數(shù)據(jù)的邏輯結(jié)構

數(shù)據(jù)的存儲結(jié)構數(shù)據(jù)的運算：插入、刪除、修改、查找、排序

線性結(jié)構

非線性結(jié)構

順序存儲

鏈式存儲線性表樹形結(jié)構圖形結(jié)構邏輯結(jié)構唯一存儲結(jié)構不唯一運算的實現(xiàn)依賴存儲結(jié)構棧、隊列串、數(shù)組以下說法正確的是（

）A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B、數(shù)據(jù)項是數(shù)據(jù)的基本單位C、數(shù)據(jù)結(jié)構是帶有結(jié)構的各數(shù)據(jù)項的集合D、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構練習

D數(shù)據(jù)元素是數(shù)據(jù)的基本單位數(shù)據(jù)項是數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構是帶有結(jié)構的各數(shù)據(jù)元素的集合目錄導航1.11.21.31.4數(shù)據(jù)結(jié)構的研究內(nèi)容基本概念和術語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法與算法分析Contents抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。它有些類似C語言中的結(jié)構（struct)類型，但增加了相關的操作。教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具。但上機時要用具體語言實現(xiàn)，如C或C++等。抽象數(shù)據(jù)類型的表示和實現(xiàn)抽象數(shù)據(jù)類型（概念層）查找插入刪除修改線性表接口或用戶界面數(shù)據(jù)類型的物理實現(xiàn)封裝信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離C++的類（實現(xiàn)層）采用類C語言，精選了C語言的一個核心子集進行算法描述(1)預定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;抽象數(shù)據(jù)類型的表示和實現(xiàn)

(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況

，自行定義該數(shù)據(jù)類型。(3)算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語句序列

}抽象數(shù)據(jù)類型的表示和實現(xiàn)（4）內(nèi)存的動態(tài)分配與釋放使用new和delete動態(tài)分配和釋放內(nèi)存空間：分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（5）賦值語句（6）選擇語句（7）循環(huán)語句（8）使用的結(jié)束語句形式有：函數(shù)結(jié)束語句return;循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）;抽象數(shù)據(jù)類型的表示和實現(xiàn)（9）輸入輸出語句形式有：輸入語句cin(scanf);輸出語句cout(printf);（10）擴展函數(shù)有：求最大值max求最小值min抽象數(shù)據(jù)類型的表示和實現(xiàn)ADTComplex{數(shù)據(jù)對象

：D={e1,e2|e1,e2∈R,R是實數(shù)集}數(shù)據(jù)關系

：S={<e1,e2>|e1是復數(shù)的實部,e2是復數(shù)的虛部}基本操作:Creat(&C,x,y)操作結(jié)果：構造復數(shù)C，其實部和虛部分別被賦予參數(shù)x和y的值。GetImag(C)

初始條件：復數(shù)C已存在。操作結(jié)果：返回復數(shù)C的虛部值。Add(C1,C2)

初始條件：C1，C2是復數(shù)。

操作結(jié)果：返回兩個復數(shù)C1和C2的和。

Sub(C1,C2)

初始條件：C1，C2是復數(shù)。

操作結(jié)果：返回兩個復數(shù)C1和C2的差。}ADTComplex復數(shù)---抽象數(shù)據(jù)類型的定義typedefstruct//復數(shù)類型{floatRealpart;//實部floatImagepart;//虛部}Complex;

復數(shù)---抽象數(shù)據(jù)類型的表示voidCreate(Complex&C,floatx,floaty){//構造一個復數(shù)C.Realpart=x;C.Imagepart=y;}floatGetReal(ComplexC){//取復數(shù)C=x+yi的實部returnC.Realpart;}floatGetImag(ComplexC){//取復數(shù)C=x+yi的虛部returnC.Imagepart;}復數(shù)---抽象數(shù)據(jù)類型的實現(xiàn)ComplexAdd(ComplexC1,ComplexC2){//求兩個復數(shù)C1和C2的和sumComplexsum;sum.Realpart=C1.Realpart+C2.Realpart;sum.Imagepart=C1.Imagepart+C2.Imagepart;returnsum;}ComplexSub(ComplexC1,ComplexC2){//求兩個復數(shù)C1和C2的差differenceComplexdifference;difference.Realpart=C1.Realpart-C2.Realpart;difference.Imagepart=C1.Imagepart-C2.Imagepart;returndifference;}復數(shù)---抽象數(shù)據(jù)類型的實現(xiàn)目錄導航1.11.21.31.4數(shù)據(jù)結(jié)構的研究內(nèi)容基本概念和術語抽象數(shù)據(jù)類型的表示與實現(xiàn)算法與算法分析Contents算法和算法分析0102一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列算法定義算法的描述自然語言流程圖程序設計語言偽代碼①

輸入方陣a和方陣b，獲得方陣的維數(shù)n。②

創(chuàng)建一個n行n列的方陣m，并將其初始化為零方陣。③

循環(huán)遍歷m各元素，并將該元素值置為方陣a和b對應位置元素和。④

返回m。算法的描述---自然語言優(yōu)點：通俗易懂。缺點：描述過程則較為冗長和煩瑣。問題：方陣的加法算法的描述---流程圖算法定義優(yōu)點：直觀、形象，描述順序結(jié)構、選擇結(jié)構和循環(huán)結(jié)構基本結(jié)構。缺點：靈活性不如自然語言，嚴密性不如偽代碼或程序設計語言。算法的描述---偽代碼算法定義采用某一程序語言的基本語法，具體的操作指令可結(jié)合自然語言來設計。輸入：方陣a，方陣b輸出：a+b的和m1n←方陣的維數(shù)2m←03fori←0ton-14forj←0ton-15m[i][j]=a[i][j]+b[i][j]6returnm優(yōu)點：比自然語言更精確，更簡潔，容易轉(zhuǎn)換成計算機程序。缺點：不夠直觀、不容易排查錯誤。算法的描述---程序設計語言voidaddMatrices(intn,inta[][n],intb[][n],intm[][n]){//方陣的加法for(inti=0;i<n;i++)for(intj=0;j<n;j++)m[i][j]=0;//初始化為零for(inti=0;i<n;i++)for(intj=0;j<n;j++)m[i][j]=a[i][j]+b[i][j];//計算和//通過數(shù)組參數(shù)直接修改原數(shù)組，無需顯式返回}優(yōu)點：能由計算機直接執(zhí)行。缺點：抽象性差，在描述過程中拘泥于算法的具體實現(xiàn)細節(jié)。算法的特性：算法的特性12345輸入

有0個或多個輸入。輸出有一個或多個輸出(處理結(jié)果)。確定性每步定義都是確切、無歧義的。有窮性算法應在執(zhí)行有窮步后結(jié)束?？尚行运胁僮鞫伎梢酝ㄟ^已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)，即算法描述中的每條指令都是可執(zhí)行的。正確性算法的評價可讀性健壯性高效性時間代價空間代價正確性不含語法錯誤；對于若干組輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果；對于精心選擇的典型、苛刻而帶有刁難性的輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果（通常以此層意義的正確性作為衡量程序是否合格的標準）；對于一切合法的輸入數(shù)據(jù)，都能夠得出滿足要求的結(jié)果。算法的評價一個好的算法，首先應便于人們理解和相互交流，其次才是機器可執(zhí)行性。可讀性強的算法有助于人們對算法的理解，而難懂的算法容易隱藏錯誤，且難于調(diào)試和修改?？勺x性算法的評價

注釋：給算法添加注釋，以方便閱讀和查錯。命名：對函數(shù)、變量等對象進行合理命名。算法應具有容錯處理的功能，當輸入的數(shù)據(jù)不合法或運行環(huán)境改變時，算法都能恰當?shù)刈龀龇磻蜻M行處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。處理出錯的方法，不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。健壯性（魯棒性）算法的評價高效性（時間代價和空間代價）算法的效率分為時間效率和空間效率；時間效率高：運行速度快的算法；空間效率高：算法執(zhí)行過程中占用內(nèi)存空間少；時間效率和空間效率常不能同時兼顧，時間效率較高的算法可能是犧牲了部分空間效率而獲得，通常更關注時間效率。算法的評價算法與程序算法：解決問題的一種方法或一個過程，考慮如何將輸入轉(zhuǎn)換成輸出，一個問題可以有多種算法。程序：用某種程序設計語言對算法的具體實現(xiàn)。算法和算法分析數(shù)據(jù)結(jié)構通過算法實現(xiàn)操作算法根據(jù)數(shù)據(jù)結(jié)構設計程序程序=數(shù)據(jù)結(jié)構+算法用依據(jù)該算法編制的程序在計算機上執(zhí)行所消耗的時間來度量。算法時間效率的度量事后統(tǒng)計事前分析估計1.事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分。缺點必須先運行依據(jù)算法編制的程序。所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣。算法時間效率的度量2.事前分析估計一個高級語言程序在計算機上運行所消耗的時間取決于：依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同———使用絕對時間單位衡量算法效率不合適。算法時間效率的度量一個算法的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和。語句的執(zhí)行時間為該條語句的重復執(zhí)行次數(shù)和執(zhí)行一次所需時間的乘積。一條語句的重復執(zhí)行次數(shù)稱作語句頻度（FrequencyCount）。算法時間效率的度量設每條語句執(zhí)行一次所需的時間均是單位時間，則一個算法的執(zhí)行時間可用該算法中所有語句頻度之和來度量。for(i=1;i<=n;i++)

//頻度為n+1for(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]=c[i][j]+a[i][k]*b[k][j];//頻度為n3}算法時間效率的度量n階方陣的乘積算法：該算法中所有語句頻度之和，是矩陣階數(shù)n的函數(shù)，用f(n)表示。f(n)=2n3+3n2+2n+1算法時間效率的度量為了便于比較不同算法的時間效率，我們僅比較它們的數(shù)量級：若兩個不同的算法，時間消耗分別是：f1(n)=1000n2f2(n)=10n3與哪個好？當n充分大時，f(n)和n3之比是一個不等于0的常數(shù)，即f(n)和n3是同階的，或者說，f(n)和n3的數(shù)量級相同?；菊Z句重復執(zhí)行的次數(shù)

時間復雜度的漸進表示法算法中重復執(zhí)行次數(shù)和算法的執(zhí)行時間成正比的語句對算法運行時間的貢獻最大問題規(guī)模n排序：n為記錄數(shù)矩陣：n為矩陣的階數(shù)多項式：n為多項式的項數(shù)集合：n為元素個數(shù)樹：n為樹的結(jié)點個數(shù)圖：n為圖的頂點數(shù)或邊數(shù)n越大算法的執(zhí)行時間越長算法中基本語句重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作：T(n)=O(f(n))。時間復雜度的漸進表示法數(shù)學符號“O”的定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)

=

O(f(n))表示存在正的常數(shù)C和n0，使得當n≥n0時都滿足0≤T(n)≤Cf(n)。表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復雜度。n階方陣的加法：for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=a[i][j]+b[i][j];

語句的頻度：f(n)=n*n T(n)=O(n2)即：方陣的加法的運算量和問題的規(guī)模n的平方是同一個量級。時間復雜度的漸進表示法x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;找出語句頻度最大的那條語句作為基本語句；計算基本語句的頻度得到問題規(guī)模n的某個函數(shù)f(n)；取其數(shù)量級用符號“O”表示。分析算法時間復雜度的基本方法O(n2)O(1)加法規(guī)則T(n)=O(f(n))＋O(g(n))=O(max(f(n),g(n)))O(n)f(n)=n*n

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){

sum[i]=0.0;

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

sum[i]+=x[i][j];

}for(i=0;i<m;i++)

cout<<i<<“:”<<sum[i]<<endl;

}時間復雜度計算示例f(n)=m*nT(n)=O(m*n)乘法規(guī)則T(n)=O(f(n))×O(g(n))=O(f(n)×g(n))例1：n階方陣相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0; for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];} 算法中的基本操作語句為c[i][j]=c[i][j]+a[i][k]*b[k][j]時間復雜度計算示例例2：for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)

x=x+1;語句頻度=定理1.1若f(n)=amnm+am-1nm-1++a1n+a0是m次多項式，則T(n)=O(nm)。忽略所有低次冪項和最高次冪系數(shù)，體現(xiàn)出增長率的含義時間復雜度計算示例例3：分析以下程序段的時間復雜度

i=1;①while(i<=n)

i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時間復雜度T(n)=O(log2n)。時間復雜度計算示例算法的特性：總結(jié)：時間復雜度的計算過程1確定輸入規(guī)模n：通常是數(shù)據(jù)的大?。ㄈ鐢?shù)組長度、矩陣維度等）。2確定基本語句：算法中執(zhí)行次數(shù)最多的語句，最內(nèi)層的循環(huán)體或遞歸調(diào)用。3計算基本語句頻度：分析基本語句的執(zhí)行次數(shù)與規(guī)模

n

的關系，得到函數(shù)

f(n)。4簡化頻度函數(shù)：忽略低次冪項和最高次冪系數(shù)，只留對增長率影響最