數(shù)據(jù)結(jié)構(gòu)與算法分析新視角（第2版） 課件 第1-3章 緒論、線性表、棧和隊(duì)列

數(shù)據(jù)結(jié)構(gòu)與算法分析

新視角前言Chapter

0DatastructuresandAlgorithms從新視角來(lái)看待舊問(wèn)題，需要有創(chuàng)造性的思維，這標(biāo)志著科學(xué)的真正進(jìn)步?！獝?ài)因斯坦數(shù)據(jù)結(jié)構(gòu)與其他課程的關(guān)系4Web信息處理人工智能數(shù)據(jù)庫(kù)操作系統(tǒng)編譯原理圖形圖像算法分析與設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)計(jì)算復(fù)雜性理論概率統(tǒng)計(jì)計(jì)算概論集合與圖論教學(xué)內(nèi)容1緒論3運(yùn)算特殊的線性表——棧和隊(duì)列4內(nèi)容特殊的線性表——字符串和多維數(shù)組2結(jié)點(diǎn)邏輯關(guān)系為線性的結(jié)構(gòu)——線性表5結(jié)點(diǎn)邏輯關(guān)系分層次的非線性結(jié)構(gòu)——樹(shù)7數(shù)據(jù)的處理方法——排序技術(shù)8數(shù)據(jù)的處理方法——索引與查找技術(shù)6結(jié)點(diǎn)邏輯關(guān)系任意的非線性結(jié)構(gòu)——圖9經(jīng)典算法緒論Chapter

1DataStructuresandAlgorithmAnalysis主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的概念算法設(shè)計(jì)的基本要求從時(shí)間和空間角度分析算法效率的方法學(xué)習(xí)目標(biāo)了解數(shù)據(jù)結(jié)構(gòu)課程的意義掌握數(shù)據(jù)結(jié)構(gòu)的概念掌握算法設(shè)計(jì)與程序設(shè)計(jì)的步驟掌握算法效率的分析評(píng)價(jià)方法1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.1從編程說(shuō)起程序的公式表達(dá)12算法+數(shù)據(jù)結(jié)構(gòu)

=程序尼古拉斯·沃斯NiklausWirth1934年2月15日——算法是處理問(wèn)題的策略，數(shù)據(jù)結(jié)構(gòu)是描述問(wèn)題信息的數(shù)據(jù)模型，程序則是計(jì)算機(jī)按照處理問(wèn)題的策略處理問(wèn)題信息的一組指令集計(jì)算機(jī)解決問(wèn)題的過(guò)程1314程序的開(kāi)發(fā)程序解題軟件工程具體工作建模型需求分析階段提取問(wèn)題要完成的功能；分析問(wèn)題涉及的數(shù)據(jù)對(duì)象，找出數(shù)據(jù)對(duì)象之間的關(guān)系。設(shè)計(jì)設(shè)計(jì)階段數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、軟件的結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)

編程編碼階段編寫(xiě)程序代碼驗(yàn)證測(cè)試軟件測(cè)試與調(diào)試1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.2程序要處理的數(shù)據(jù)17數(shù)值與非數(shù)值問(wèn)題數(shù)值計(jì)算非數(shù)值計(jì)算數(shù)值計(jì)算，具體地說(shuō)就是有效利用計(jì)算機(jī)求解數(shù)學(xué)問(wèn)題近似解的方法與過(guò)程，可以通過(guò)抽象出合適的數(shù)學(xué)模型，然后設(shè)計(jì)相應(yīng)的算法來(lái)解決。數(shù)值計(jì)算問(wèn)題，以浮點(diǎn)算術(shù)運(yùn)算為主，算法成熟所謂“非數(shù)值計(jì)算”問(wèn)題，是為了區(qū)分前面提到的“數(shù)值問(wèn)題”而言。非數(shù)值問(wèn)題涉及到的數(shù)據(jù)及數(shù)據(jù)間的相互關(guān)系，一般無(wú)法用數(shù)學(xué)公式、方程等來(lái)描述，如排序問(wèn)題、檢索問(wèn)題等，需要另外設(shè)計(jì)數(shù)據(jù)的描述方法和相應(yīng)的算法來(lái)處理。18從下面的無(wú)限序列中計(jì)算出π的值。輸出一個(gè)表格，在該表格中顯示根據(jù)這個(gè)序列中的1項(xiàng)、2項(xiàng)、3項(xiàng)等等所得的近似π值。在第一次得到3.14之前，必須使用這個(gè)序列的多少項(xiàng)？如果是得到3.141呢？3.1415呢？3.14159呢？數(shù)值問(wèn)題的例子通用公式數(shù)據(jù)對(duì)象數(shù)據(jù)間關(guān)系數(shù)據(jù)初始化建模型m=1;i=1-1偶數(shù)1奇數(shù)m取值i取值項(xiàng)數(shù)：當(dāng)前已經(jīng)用到的項(xiàng)數(shù)i系數(shù)：控制序列項(xiàng)的正負(fù)號(hào)

m4+（-1）*m*4/(2*i+1)例19算法頂部偽代碼描述賦初值：累加和x=4;m=1;項(xiàng)數(shù)i=1；根據(jù)通用公式,x做循環(huán)累加直到x=3.14時(shí)中斷循環(huán)輸出x及i值；算法細(xì)化描述累加和x=4;m=1;i=1；dox=x+（-1）*m*4/(2*i+1)

i增加1；

m=m*(-1)直到x=3.14時(shí)中斷循環(huán)輸出x及i值；設(shè)計(jì)數(shù)值問(wèn)題的例子20數(shù)值問(wèn)題的例子voidmain(){floatx=4;inti=1,m=1;while(1){ x=x+(float)(-1)*m*4/(2*i+1); i++; m=m*(-1); if(x>=3.14-0.000001&&x<=3.14+0.000001)break;} printf("i=%d,x=%f\n",i,x);}編程要求對(duì)任意給出的一個(gè)姓名，查找電話號(hào)碼非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢客戶姓名電話身份證號(hào)地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******………"表""關(guān)鍵字""數(shù)據(jù)項(xiàng)"關(guān)鍵字關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)"數(shù)據(jù)元素"或"結(jié)點(diǎn)"例方法1客戶姓名電話身份證號(hào)地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******王2138*****6101131986******………順序結(jié)構(gòu)順序查找非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢問(wèn)題涉及的對(duì)象每客戶及其相應(yīng)的數(shù)據(jù)項(xiàng)；對(duì)象之間的關(guān)系數(shù)據(jù)元素順序排列；查找指定數(shù)據(jù)項(xiàng)，輸出相應(yīng)數(shù)據(jù)項(xiàng)建模型設(shè)計(jì)非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢方法1順序結(jié)構(gòu)順序查找有序結(jié)構(gòu)折半查找方法2客戶姓名電話身份證號(hào)地址李1188*****6101131976******李2152*****6101131981******王1139*****6101131990******王2138*****6101131986******張1138*****6101131980******張2139*****6101131972******………非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢問(wèn)題涉及的對(duì)象每客戶及其相應(yīng)的數(shù)據(jù)項(xiàng)；對(duì)象之間的關(guān)系數(shù)據(jù)元素有序排列；折半查找指定數(shù)據(jù)項(xiàng)，輸出相應(yīng)數(shù)據(jù)項(xiàng)建模型設(shè)計(jì)非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢有序結(jié)構(gòu)折半查找方法2索引結(jié)構(gòu)分級(jí)查找客戶姓名電話身份證號(hào)地址李1188*****6101131976***0x2000李2152*****6101131981******………張1138*****6101131980***0x4000張2139*****6101131972******………王1139*****6101131990***0x6000王2138*****6101131986******………姓氏表內(nèi)地址數(shù)量李0x2000***張0x4000***王0x6000***………索引表數(shù)據(jù)表方法3非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢問(wèn)題涉及的對(duì)象索引表客戶姓氏、對(duì)應(yīng)數(shù)據(jù)表中的地址數(shù)據(jù)表每個(gè)客戶及其相應(yīng)的數(shù)據(jù)項(xiàng)；對(duì)象之間的關(guān)系索引表數(shù)據(jù)元素有序排列數(shù)據(jù)表數(shù)據(jù)元素順序排列；建模型先索引表，后數(shù)據(jù)表設(shè)計(jì)非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢索引結(jié)構(gòu)分級(jí)查找方法328非數(shù)值問(wèn)題例子1——電話號(hào)碼查詢數(shù)據(jù)的組織方式和數(shù)據(jù)的存儲(chǔ)方式，都會(huì)影響算法的效率結(jié)論29在十字路口，要設(shè)置幾種顏色的交通燈才可保持正常的交通秩序？BCDA十字路口交通燈管理問(wèn)題非數(shù)值問(wèn)題的例子2問(wèn)題涉及的對(duì)象對(duì)象之間的關(guān)系表示AC、BD不能同時(shí)通行BDAC用表示AC間有一條通路AC建模型某方向通行時(shí)，另外某些方向不能通行四個(gè)路口ABCD，及相應(yīng)的通路；例30ACABADBDBABCCACDCBDBDCDABCDA“圖”“數(shù)據(jù)元素”或“結(jié)點(diǎn)”對(duì)圖中的圓圈上色，同一連線上的兩個(gè)圓圈不同色且顏色種類最少設(shè)計(jì)非數(shù)值問(wèn)題的例子231非數(shù)值問(wèn)題的例子3rootbinlibuseretcmathdsswsunzhouzhaoStack.cppTree.cppQueue.cpp……"樹(shù)"“數(shù)據(jù)元素”或“結(jié)點(diǎn)”計(jì)算機(jī)文件系統(tǒng)結(jié)構(gòu)的表示與管理例1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.3數(shù)據(jù)結(jié)構(gòu)的引入問(wèn)題解決信息表述信息處理計(jì)算機(jī)解題過(guò)程先找出問(wèn)題中要處理的數(shù)據(jù)及數(shù)據(jù)間的聯(lián)系、組織形式、存儲(chǔ)方式、表示方法等，設(shè)計(jì)適合計(jì)算機(jī)解題的模型按要求有效地解決問(wèn)題

數(shù)據(jù)結(jié)構(gòu)研究的問(wèn)題

經(jīng)典數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)表示方法數(shù)據(jù)存儲(chǔ)形式數(shù)據(jù)運(yùn)算1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.4數(shù)據(jù)結(jié)構(gòu)的要素1.4.11.4.2數(shù)據(jù)結(jié)構(gòu)基本術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素?cái)?shù)據(jù)的基本單位可包含多個(gè)數(shù)據(jù)項(xiàng)38基本概念和術(shù)語(yǔ)數(shù)據(jù)元素由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成數(shù)據(jù)元素中的不可分割的最小單位客觀對(duì)象在計(jì)算機(jī)中的符號(hào)表示數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)項(xiàng)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)基本術(shù)語(yǔ)1.4數(shù)據(jù)結(jié)構(gòu)的要素1.4.11.4.2數(shù)據(jù)結(jié)構(gòu)基本術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素?cái)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)體現(xiàn)各結(jié)點(diǎn)間的相鄰關(guān)系，由數(shù)據(jù)本身內(nèi)在特性所決定，獨(dú)立于計(jì)算機(jī)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素及其邏輯關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示數(shù)據(jù)的運(yùn)算對(duì)數(shù)據(jù)施加的操作數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素?cái)?shù)據(jù)結(jié)構(gòu)的三個(gè)要素?cái)?shù)據(jù)邏輯結(jié)構(gòu)集合結(jié)點(diǎn)間無(wú)關(guān)系線性結(jié)構(gòu)結(jié)點(diǎn)間一對(duì)一關(guān)系樹(shù)形結(jié)構(gòu)結(jié)點(diǎn)間是一對(duì)多關(guān)系圖形結(jié)構(gòu)結(jié)點(diǎn)間是多對(duì)多關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)42數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)點(diǎn)的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)的邏輯關(guān)系由附加的指針字段表示索引存儲(chǔ)索引項(xiàng)：（關(guān)鍵字，地址）散列存儲(chǔ)結(jié)點(diǎn)地址＝F（關(guān)鍵字）數(shù)據(jù)的運(yùn)算43數(shù)據(jù)運(yùn)算運(yùn)算的定義建立在數(shù)據(jù)的邏輯結(jié)構(gòu)上運(yùn)算的實(shí)現(xiàn)以數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)為基礎(chǔ)常見(jiàn)運(yùn)算：初始化

判空

求長(zhǎng)度

查找

遍歷

取值

置值

插入

刪除

1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.5如何設(shè)計(jì)算法1.5.11.5.2算法的定義及表示方法算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系1.5.31.5.4軟件設(shè)計(jì)描述算法設(shè)計(jì)的一般步驟1.5如何設(shè)計(jì)算法1.5.11.5.2算法的定義及表示方法算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系1.5.31.5.4軟件設(shè)計(jì)描述算法設(shè)計(jì)的一般步驟47算法

在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的操作序列，能夠在有限時(shí)間內(nèi)，對(duì)一定的規(guī)范的輸入獲得所要求的輸出。算法算法特征1有窮性：一個(gè)算法必須保證在執(zhí)行有限步驟后結(jié)束，而不是無(wú)限的。3可行性：每一個(gè)操作步驟都必須在有限的時(shí)間內(nèi)完成。4輸入：一個(gè)算法可以有多個(gè)輸入，也可以沒(méi)有輸入。2確定性：算法中每一條指令必須有明確的含義，而不能是含糊不清的有歧義。5輸出：一個(gè)算法可以有一個(gè)或多個(gè)輸出，沒(méi)有輸出的算法是沒(méi)有實(shí)際意義的。算法的表示49可以幫助程序員開(kāi)發(fā)算法的，由字符組成的非正式語(yǔ)言?？梢砸萌魏尉哂斜磉_(dá)力的方法來(lái)最清晰、最簡(jiǎn)潔地表達(dá)算法。偽代碼本書(shū)對(duì)算法的描述采用偽代碼的方式1.5如何設(shè)計(jì)算法1.5.11.5.2算法的定義及表示方法算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系1.5.31.5.4軟件設(shè)計(jì)描述算法設(shè)計(jì)的一般步驟longfactorial(intn);

有關(guān)函數(shù)的概念函數(shù)類型函數(shù)名（形參類型說(shuō)明表）{

聲明部分； 語(yǔ)句部分；}函數(shù)的定義形式函數(shù)類型函數(shù)名（形參類型說(shuō)明表）;函數(shù)的聲明形式函數(shù)名(實(shí)參表);函數(shù)的調(diào)用形式longfactorial(intn){

inti;

long

t=1;

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

t=t*i;

return(t);}intm;longc；scanf(“%d”,&m);c=factorial(m);輸入的數(shù)據(jù)輸出的結(jié)果輸出結(jié)果的類型實(shí)際參數(shù)C函數(shù)實(shí)際參數(shù)與形式參數(shù)的關(guān)系52函數(shù)類型函數(shù)名（形式參數(shù)表）

{聲明部分;語(yǔ)句部分;}函數(shù)定義格式函數(shù)名（實(shí)際參數(shù)表）函數(shù)調(diào)用格式形式參數(shù)表中放參數(shù)的定義形式如基本變量：intx如指針：int*ptr如數(shù)組：inta[]如結(jié)構(gòu)：structnodestu實(shí)際參數(shù)表中放參數(shù)的使用形式如基本變量：x如指針：ptr如數(shù)組：a如結(jié)構(gòu)：stuC函數(shù)實(shí)際參數(shù)與形式參數(shù)的關(guān)系算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系功能描述輸入信息輸出信息函數(shù)名形參函數(shù)類型接口及功能描述此處輸出的含義，是指函數(shù)傳遞給調(diào)用者的，不是輸出到顯示器上的此處信息輸入方式是調(diào)用者傳遞給函數(shù)，不是通過(guò)鍵盤等方式輸入1.5如何設(shè)計(jì)算法1.5.11.5.2算法的定義及表示方法算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系1.5.31.5.4軟件設(shè)計(jì)描述算法設(shè)計(jì)的一般步驟軟件設(shè)計(jì)方法55根據(jù)問(wèn)題的功能要求，按照輸入數(shù)據(jù)的正常情形、邊界或特例情形、異常情形等各種情形，給出測(cè)試樣例。測(cè)試用例設(shè)計(jì)1給出問(wèn)題包含信息與信息聯(lián)系的存儲(chǔ)結(jié)構(gòu)，用C語(yǔ)言數(shù)據(jù)類型描述。數(shù)據(jù)結(jié)構(gòu)描述2根據(jù)問(wèn)題的功能、輸入、輸出，對(duì)應(yīng)確定函數(shù)類型、形參、返回值。函數(shù)結(jié)構(gòu)設(shè)計(jì)3按照自頂向下逐步求精的方法，描述問(wèn)題的解決步驟。算法描述4按照細(xì)化的偽代碼給出代碼實(shí)現(xiàn)，必要時(shí)按照測(cè)試樣例給出測(cè)試結(jié)果。程序?qū)崿F(xiàn)5分析問(wèn)題的時(shí)間復(fù)雜度、空間復(fù)雜度。算法效率分析61.5如何設(shè)計(jì)算法1.5.11.5.2算法的定義及表示方法算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系1.5.31.5.4軟件描述方法算法設(shè)計(jì)的一般步驟算法設(shè)計(jì)的一般步驟571設(shè)定算法初始條件3按問(wèn)題的普遍規(guī)律給出算法處理的流程4考慮臨界點(diǎn)或特殊點(diǎn)的處理2確定算法的結(jié)束條件5考慮異常情況算法設(shè)計(jì)實(shí)例5858算法設(shè)計(jì)的例子——求n！遞推公式S=S*Tn!1n<=1n*(n-1)!n>1step11*2=>sstep2s*3=>sstep3s*4=>sstep4s*5=>sS：累乘之積T：乘數(shù)遞推法定義例59算法設(shè)計(jì)實(shí)例——

求n！功能描述輸入信息輸出信息factorialintnint值異常：-1正常：n！的結(jié)果測(cè)試用例設(shè)計(jì)1接口及功能描述2情形測(cè)試數(shù)據(jù)預(yù)期結(jié)果問(wèn)題的一般情形n>1按照n！一般定義得出的值臨界點(diǎn)或特殊點(diǎn)n=0，n=1按照n！邊界定義得出的值異常情況n<0給出錯(cuò)誤提示信息

60算法設(shè)計(jì)實(shí)例——

求n！頂部偽代碼描述輸入n求n！輸出結(jié)果第一步細(xì)化輸入n初始化S=1，T=1由1乘2開(kāi)始結(jié)果放到乘積S中，乘數(shù)T每次增1當(dāng)T>n結(jié)束輸出結(jié)果S第二步細(xì)化輸入n設(shè)S=1，乘數(shù)T=1

doS=S*TT增加1

Until(T>n)輸出：S算法描述3算法設(shè)計(jì)實(shí)例——求n！61

一般情形邊界值異常情形測(cè)試值51001-1測(cè)試結(jié)果120362880011-1floatfactorial(intn){inti;floatt=1;if(n<0)return(-1);for(i=1;i<=n;i++)

t=t*i;return(t);}函數(shù)實(shí)現(xiàn)4測(cè)試結(jié)果562偽代碼描述要點(diǎn)簡(jiǎn)潔明晰按程序結(jié)構(gòu)特點(diǎn)描述算法步驟，注意格式縮進(jìn)。內(nèi)容完整算法開(kāi)始階段初始化信息輸入信息算法處理階段循環(huán)要素、判斷條件等算法結(jié)束階段輸出信息程序結(jié)構(gòu)：順序、循環(huán)、分支63n!的例子#include<stdio.h>floatfactorial(intn);floatfactorial(intn){inti;floatt=1;for(i=1;i<=n;i++)t=t*i;return(t);}main(){floatc;intm;printf(〞inputm〞);scanf(〞%d〞,&m);c=factorial(m);printf(〞The%d!is%8.1f〞,

m，c);}函數(shù)說(shuō)明函數(shù)調(diào)用函數(shù)定義1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量1.6如何評(píng)價(jià)算法的優(yōu)劣1.6.11.6.2算法設(shè)計(jì)的要求算法效率的度量方法1.6如何評(píng)價(jià)算法的優(yōu)劣1.6.11.6.2算法設(shè)計(jì)的要求算法效率的度量方法67算法設(shè)計(jì)的要求正確性程序不含語(yǔ)法錯(cuò)誤對(duì)輸入數(shù)據(jù)能得出滿足要求的結(jié)果隨意的數(shù)據(jù)精心選擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)一切合法的輸入數(shù)據(jù)可讀性程序員的效率第一健壯性算法對(duì)不合理數(shù)據(jù)輸入應(yīng)該有反應(yīng)能力和處理能力高效性時(shí)間效率高效率指的是算法執(zhí)行的時(shí)間（時(shí)間復(fù)雜性）；存儲(chǔ)空間少存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間（空間復(fù)雜性）空間和時(shí)間可以互相轉(zhuǎn)化1.6如何評(píng)價(jià)算法的優(yōu)劣1.6.11.6.2算法設(shè)計(jì)的要求算法效率的度量方法69算法性能的事后統(tǒng)計(jì)#include<time.h>longstart,stop;time(&start);

/*******************

此處放要測(cè)定運(yùn)行時(shí)間的函數(shù)********************/time(&stop);

longrunTime=stop-start;printf("%ld\n",runTime);例

硬件的速度

程序選用語(yǔ)言目標(biāo)代碼質(zhì)量

問(wèn)題的規(guī)模

算法選用的策略算法效率因素算法時(shí)間效率相關(guān)因素分析算法性能的事前分析71時(shí)間效率空間效率算法性能分析算法的時(shí)間效率分析——找出與算法運(yùn)行時(shí)間相關(guān)的因素與特征函數(shù)，從時(shí)間角度來(lái)評(píng)價(jià)算法。算法的空間效率分析——找出算法運(yùn)行所需的輔助存儲(chǔ)空間特征函數(shù)，從空間角度來(lái)評(píng)價(jià)算法。1.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量

硬件的速度

程序選用語(yǔ)言目標(biāo)代碼質(zhì)量

問(wèn)題的規(guī)模

算法選用的策略算法效率因素算法時(shí)間效率相關(guān)因素分析與算法執(zhí)行時(shí)間相關(guān)的因素中，哪些是關(guān)鍵因素？算法時(shí)間效率相關(guān)因素分析算法運(yùn)行時(shí)間=算法中每條語(yǔ)句執(zhí)行時(shí)間之和每條語(yǔ)句執(zhí)行時(shí)間==>該語(yǔ)句的執(zhí)行次數(shù)74語(yǔ)句頻度將程序的運(yùn)行時(shí)間表示為其輸入的函數(shù)若問(wèn)題的規(guī)模為n，一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度，記為T(n)。1.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法1.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法77問(wèn)題的規(guī)模與算法的策略每個(gè)卡片只看一次，共100次將數(shù)字1～100寫(xiě)在卡片上，亂序后再按序排好。排序時(shí)所有卡片的查找次數(shù)是多少？先找1、再找2、找3、…最多要看(100+1)*100/2次法一法二問(wèn)題規(guī)模為n時(shí)的比較次數(shù)f(n)=n2/2+n/2問(wèn)題規(guī)模為n時(shí)的比較次數(shù)

f(n)=n例78問(wèn)題的規(guī)模與算法的策略結(jié)論一般地，算法所需時(shí)間是和輸入規(guī)模n同步增長(zhǎng)的：對(duì)于同一算法

輸入量小，速度快；

輸入量大，速度慢。對(duì)于不同的算法

有可能在n的某一區(qū)間，一個(gè)算法的速度高于另一個(gè)；

而在n的另一區(qū)間，情況可能就會(huì)相反。對(duì)于不同的算法

規(guī)模較小時(shí)，算法效率接近；

規(guī)模擴(kuò)大，算法效率通常呈上升趨勢(shì)，各算法之間的差距就比較明顯了。791.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法81算法分析規(guī)則1234596979899100…例將數(shù)字1～100寫(xiě)在卡片上，亂序后再按序排好。排序時(shí)所有卡片的查找次數(shù)是多少？T(n)=n=1001009998979654321…23614578521627789310…最好情形最壞情形平均情形T(n)=(n+1)*n/2=5050T(n)=257582在n張卡片中找一個(gè)指定卡片i的平均查找次數(shù)ASLn（AverageSearchLength）Pi——查找表中第i個(gè)記錄的概率Ci——找到該記錄時(shí)已經(jīng)比較過(guò)的卡片數(shù)在n張卡片中找n個(gè)指定卡片i的平均查找次數(shù)ASLn=100時(shí)，T(n)=2575算法分析規(guī)則算法效率典型情形83最好效率：算法在最優(yōu)情況下的效率最差效率：算法在最壞情況下的效率平均效率：“典型”或“隨機(jī)”輸入的情況下，算法具有的效率算法效率典型情形84算法的上限&下限算法運(yùn)行時(shí)間慢快算法運(yùn)行的時(shí)間上限算法運(yùn)行的時(shí)間下限O表示法Ω表示法Θ表示法同一算法算法分析是為了得知近似的執(zhí)行時(shí)間，一般考察的是當(dāng)問(wèn)題規(guī)模n增加時(shí)，運(yùn)算所需時(shí)間的上下界。85漸進(jìn)表示法記號(hào)記號(hào)定義含義O定義：f(n)＝O(g(n))若存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≧n0時(shí)，f(n)≦c*g(n)f(n)的漸進(jìn)上限為g(n)Ω定義：f(n)＝Ω(g(n))若存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≧n0時(shí)，f（n）≧c*g(n)f(n)的漸進(jìn)下限為g(n)Θ定義：f(n)＝Θ(g(n))若存在正常數(shù)c1，c2和n0，使得當(dāng)n≧n0時(shí)，c1*g(n)≦f(n)≦c2*g(n)f(n)的漸進(jìn)確界為g(n)o定義：f(n)＝o(g(n))對(duì)任意正常數(shù)c，若存在n0，使得當(dāng)n≧n0時(shí)，f(n)<cg(n)g(n)為f(n)的非緊卻漸進(jìn)上界ω定義：f(n)＝ω(g(n))對(duì)任意正常數(shù)c，若存在n0，使得當(dāng)n≧n0時(shí)，f(n)>cg(n)g(n)為f(n)的非緊卻漸進(jìn)下界說(shuō)明：f(n)、g(n)均為非負(fù)函數(shù)

86cg(n)f(n)n0f(n)

O(g(n))cg(n)f(n)n0f(n)

Ω(g(n))f(n)

θ(g(n))BigO算法的漸進(jìn)運(yùn)行時(shí)間記號(hào)注：n0、c、c1、c2均為正數(shù)n0c2g(n)f(n)c1g(n)漸進(jìn)上限漸進(jìn)下限漸進(jìn)確界大O符號(hào)（BigOnotation）是用于描述函數(shù)漸近行為的數(shù)學(xué)符號(hào)。它是用另一個(gè)（通常更簡(jiǎn)單的）函數(shù)來(lái)描述一個(gè)函數(shù)數(shù)量級(jí)的漸近上界。87大O表示法的例子1f(n)=7*2n+n2+n=O(2n)，∵可以找到c=8,n0=4，使得7*2n+n2+n<8*2n

f(n)=10n2+5n+1=O(n2)，∵可以找到c=11,n0=6，使得10n2+5n+1<11n2

f(n)=3n+2=O(n)，∵可找到c=4，n0=2，使得3n+2<4n例88利用極限比較階數(shù)極限值f(n)與g(n)比較結(jié)果表示含義存在0f(n)是比g(n)低階的無(wú)窮大f(n)＝o(g(n))f(n)在數(shù)量級(jí)上嚴(yán)格小于g(n)c≤1f(n)與g(n)是同階的無(wú)窮大（稱f與g是同數(shù)量級(jí)的）f(n)＝O(g(n))f(n)在數(shù)量級(jí)上小于等于g(n)c=1f(n)=Θ(g(n))f(n)在數(shù)量級(jí)上等于g(n)c≥1f(n)=Ω(g(n))f(n)在數(shù)量級(jí)上大于等于g(n)不存在∞f是比g高階的無(wú)窮大f(n)=ω(g(n))f(n)在數(shù)量級(jí)上嚴(yán)格大于g(n)振蕩設(shè)f(n)、g(n)是在同一個(gè)自變量n的變化過(guò)程中的無(wú)窮大兩個(gè)函數(shù)的比率求極限c為常數(shù)89大O表示法的例子2（3）f(n)=7*2n+n2+n=O(2n)（2）f(n)=10n2+5n+1=O(n2)（1）f(n)=3n+2=O(n)當(dāng)

n充分大時(shí)，該程序的運(yùn)行時(shí)間和n成正比，用O(n)表示；稱f(n)和n是同階的（數(shù)量級(jí)相同）。當(dāng)

n充分大時(shí)，該程序的運(yùn)行時(shí)間和n2成正比，用O(n2)表示；稱f(n)和n2是同階的。當(dāng)

n充分大時(shí)，該程序的運(yùn)行時(shí)間和2n成正比，用O(2n)表示；稱f(n)和2n是同階的。例1.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法91時(shí)間復(fù)雜度

如果O(f(n))是某個(gè)算法的語(yǔ)句執(zhí)行次數(shù)f(n)的上限，那么我們可以說(shuō)此算法的漸進(jìn)時(shí)間復(fù)雜度（簡(jiǎn)稱時(shí)間復(fù)雜度)或是執(zhí)行時(shí)間為O(f(n))定義92矩陣相乘算法時(shí)間復(fù)雜度f(wàn)(n)=O(n3)程序語(yǔ)句頻度f(wàn)(n)1for(i=1;i<=n;i++)2for(j=1;j<=n;j++)3{c[i][j]=0;4for(k=1;k<=n;k++)5c[i][j]+=a[i][k]*b[k][j]}

n階矩陣相乘算法的時(shí)間復(fù)雜度分析（C=A*B）例算法的時(shí)間復(fù)雜度的例子1n+1n(n+1)n2n2(n+1)n3

頻度和

f(n)=2n3+3n2+2n+193時(shí)間復(fù)雜度結(jié)論

算法的漸進(jìn)分析，關(guān)心的是數(shù)據(jù)規(guī)模n逐步增大時(shí)資源開(kāi)銷T(n)的增長(zhǎng)趨勢(shì)，具體是考察數(shù)量級(jí)大小的比較。如果一個(gè)算法的最壞情況運(yùn)行時(shí)間的階要比另外一個(gè)算法的低，我們就常常認(rèn)為前者更為有效。結(jié)論94例程序段頻度f(wàn)(n)與規(guī)模n時(shí)間復(fù)雜度O(f(n))1x=x+1;y=x+2234分析下面各程序段的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度的例子2for(i=0;i<n;i++)x++;f(n)123…k…f(n)i12222k-12f(n)-1i=i*2222232k2f(n)i=1;while(i<=n)i=i*2;for(i=0;i<n;i++)for(j=0;j<n;j++)x++;O(log2n)2f(n)=nO(n2)f(n)=(n+1)+n*(n+1)+n2O(n)f(n)=2n+1O(1)f(n)=2語(yǔ)句i=i*2執(zhí)行次數(shù)最后一次執(zhí)行：i=n時(shí)

2f(n)-1

=

n1.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法算法時(shí)間復(fù)雜度的實(shí)際意義96查找的效率問(wèn)題對(duì)于一組有序的數(shù)列（5,13,19,21,37,56,64,75,80,88,92），如何查找效率更高？數(shù)據(jù)513192137566475808892順序查找次數(shù)1234567891011折半查找次數(shù)34234134234可能的概率pi1/n1*202*213*22i*2i-1561952113^h=1h=2h=3h=[log2n]+1層37^80648875^92^每層查找次數(shù)例一個(gè)結(jié)點(diǎn)查找成功的平均次數(shù)查找的平均時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度的實(shí)際意義98算法時(shí)間復(fù)雜度的實(shí)際意義小規(guī)模的輸入在運(yùn)行時(shí)間上的差別不足以將高效的算法和低效的算法區(qū)分開(kāi)。時(shí)間復(fù)雜度并不表示一個(gè)程序解決問(wèn)題具體需要花多少時(shí)間，而是表示當(dāng)問(wèn)題規(guī)模擴(kuò)大后程序運(yùn)行需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。99對(duì)于算法分析具有重要意義的函數(shù)值c<log2n<n<nlog2n<n2<n3<2n<3n<n!從漸進(jìn)意義上說(shuō)更有效的算法是基于大規(guī)模輸入的比較對(duì)于算法分析具有重要意義的函數(shù)值常數(shù)階對(duì)數(shù)階線性階線性對(duì)數(shù)階平方階立方階指數(shù)階階乘階O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)O(2n)O(n!)高效算法不可計(jì)算多項(xiàng)式級(jí)的復(fù)雜度非多項(xiàng)式級(jí)1001加法準(zhǔn)則T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))2乘法準(zhǔn)則T(n)=T1(n)*T2(n)=O(f1(n))*O(f2(n))=O(f1(n)×f2(n))3特例情形

算法平均時(shí)間復(fù)雜度

算法在最壞情況下的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的計(jì)算規(guī)則設(shè)程序段1和程序段2的時(shí)間分別為T1(n)和T2(n)，總的運(yùn)行時(shí)間為T(n)——針對(duì)并列程序段——針對(duì)嵌套程序段——基本操作執(zhí)行次數(shù)與問(wèn)題的輸入數(shù)據(jù)有關(guān)時(shí)對(duì)于復(fù)雜算法，可分成幾個(gè)容易估算的部分。102問(wèn)題的輸入數(shù)據(jù)影響算法效率的情形在數(shù)組A[N]中查找給定值k的算法intsearch（intk）{inti=N-1;//i為要查找的下標(biāo)

while(i>=0&&A[i]!=k)i--;

returni;}平均情形最壞情形f(n)=nO(f(n))=O(n)f(n)=(1/n)*(1+n)*n/2=(1+n)/2O(f(n))=O(n)時(shí)間復(fù)雜度的例子基本語(yǔ)句的執(zhí)行次數(shù)是否只和問(wèn)題規(guī)模有關(guān)？例103算法效率一般性分析方法非遞歸算法決定用哪個(gè)(些)參數(shù)作為輸入規(guī)模的度量找出算法的基本操作(作為一個(gè)規(guī)律，它總是位于算法的最內(nèi)層循環(huán))檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。如它還依賴一些其他的特性，如輸入順序等，則最差效率、平均效率以及最優(yōu)效率需要分別研究。建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式遞歸算法用遞推式的形式來(lái)表達(dá)基本操作次數(shù)決定用哪些參數(shù)作為輸入規(guī)模的度量找出算法的基本操作檢查一下，對(duì)于相同規(guī)模的不同輸入，基本操作的執(zhí)行次數(shù)是否不同。如果不同，則必須對(duì)最差效率、平均效率以及最優(yōu)效率作單獨(dú)研究對(duì)于算法基本操作的執(zhí)行次數(shù)，建立一個(gè)遞推關(guān)系以及相應(yīng)的初始條件解這個(gè)遞推式，或者至少確定它的解的增長(zhǎng)次數(shù)1.7算法性能的事前分析方法1.7.11.7.2問(wèn)題的規(guī)模與算法的策略算法時(shí)間效率的上限與下限1.7.31.7.4漸進(jìn)的上限——算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度的綜合討論1.7.5算法的空間效率分析方法從空間角度來(lái)評(píng)價(jià)算法——找出算法運(yùn)行所需的輔助存儲(chǔ)空間特征函數(shù)。105算法的空間效率分析算法空間存儲(chǔ)空間代碼空間：算法本身的存儲(chǔ)空間數(shù)據(jù)空間：輸入／輸出數(shù)據(jù)的存儲(chǔ)空間運(yùn)行空間算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間106計(jì)算多項(xiàng)式的值算法存儲(chǔ)空間分析的例子1-12函數(shù)結(jié)構(gòu)設(shè)計(jì)功能描述輸入輸出計(jì)算多項(xiàng)式的值evaluate系數(shù)floatcoef[]floatf(x)變量floatx規(guī)模intn函數(shù)名形參函數(shù)類型例107算法存儲(chǔ)空間分析的例子1-12頂部偽代碼描述計(jì)算函數(shù)值第一步細(xì)化先計(jì)算x的冪,存于數(shù)組中,再分別乘以相應(yīng)的系數(shù)第二步細(xì)化intA[N]放x的冪floatcoef[N]放系數(shù)A[0]=1，i=1當(dāng)i<nA[i]=x*A[i-1];

i++;f=0,i=0;當(dāng)i<nf=f+coef[i]*A[i];i++;法一108算法存儲(chǔ)空間分析的例子1-12算法一#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;intA[N],i;for(A[0]=1,i=1;i<=n;i++)A[i]=x*A[i-1];/*A[

]放x的冪*/for(f=0,i=0;i<=n;i++)f=f+coef[i]*A[i];return(f);}coef[]屬輸入輸出，為數(shù)據(jù)空間；A[N]為局部量，是輔助空間算法時(shí)間復(fù)雜度:O(n)空間復(fù)雜度：O(n)109算法存儲(chǔ)空間分析的例子1-12頂部偽代碼描述計(jì)算函數(shù)值第一步細(xì)化從f()最后一項(xiàng)系數(shù)開(kāi)始逐步乘x，反向處理第二步細(xì)化floatcoef[]放系數(shù)n為項(xiàng)數(shù)f=coef[n],i=n-1;當(dāng)

i>0

f=f*x+coef[i];i--；法二算法存儲(chǔ)空間分析的例子1-12110算法時(shí)間復(fù)雜度:O(n)空間復(fù)雜度：O(1)算法二#defineN100floatevaluate(floatcoef[],floatx,intn){floatf;inti;for(f=coef[n],i=n-1;i>=0;i--)f=f*x+coef[i];return(f);}111算法的空間復(fù)雜度定義

S(n)=O(g(n))

其中

n————問(wèn)題規(guī)模

g(n)————執(zhí)行算法所需的輔助空間算法空間復(fù)雜度S(n)空間復(fù)雜度含義O(n)表示每個(gè)輸入元素都分配到固定的儲(chǔ)存空間。O(1)代表算法需要固定的儲(chǔ)存空間，與輸入量無(wú)關(guān)若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。例112給出fibonacci數(shù)列前n項(xiàng)的遞歸與非遞歸的算法，試分析它們的算法復(fù)雜度。(費(fèi)氏數(shù)列——fibonacci數(shù)列)fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)遞歸的算法/*遞歸計(jì)算斐波那契數(shù)列的第n項(xiàng)*/longFib(longn){ if(n<=1)returnn;//遞歸邊界

elsereturnFib(n-1)+Fib(n-2);//遞歸條件}0,1,1,2,3,5,8,13,21,……算法分析的綜合例子1-13例Fibonacci函數(shù)的遞歸調(diào)用樹(shù)Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(2)Fib(1)Fib(1)Fib(1)Fib(0)Fib(0)Fib(1)Fib(0)Fib(1)nT(n)遞歸的運(yùn)算次數(shù)T(n-1)+T(n-2)+141251595311n…76543210114∴T(n)

Ω(2n/2)∴T(n)

O(2n)∴T(n)>2*T(n-2)又∵T(n-1)>T(n-2)∴T(n)<2*T(n-1)∵T(n-1)>T(n-2)T(n)=T(n-1)+T(n-2)+1<2*2*T(n-2)<2*2*2*T(n-3)<…<2n-1T(n-n+1)=2n-1T(1)=2n-1>2*2*T(n-4)>2*2*2*T(n-6)>…>2n/2T(n-n)=2n/2大O：漸進(jìn)上限Ω：漸進(jìn)下限算法分析的綜合例子1-13115Fibonacci數(shù)列通項(xiàng)公式fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)二階線性遞推數(shù)列的特征方程二階線性遞推數(shù)列的通項(xiàng)公式a=1；b=-1；c=-1二階線性遞推數(shù)列的一般形式求得數(shù)列第n項(xiàng)與n的關(guān)系Fibonacci數(shù)列通項(xiàng)公式116fibonacci數(shù)列定義

f0=0；f1=1；fn=fn-1+fn-2(n>=2)

∵T(n)=T(n-1)+T(n-2)+1117Fib函數(shù)遞歸算法時(shí)間復(fù)雜度分析結(jié)論T(n)

Ω(2n/2)=Ω(1.414n)T(n)

O(2n)大O：漸進(jìn)上限Ω：漸進(jìn)下限Θ

漸進(jìn)確界T(n)

Θ(1.618n)Fib函數(shù)遞歸算法時(shí)間復(fù)雜度分析曲線1181.1CONTENTS從編程說(shuō)起程序要處理的數(shù)據(jù)1.21.3數(shù)據(jù)結(jié)構(gòu)的引入1.4數(shù)據(jù)結(jié)構(gòu)的要素1.5如何設(shè)計(jì)算法如何評(píng)價(jià)算法的優(yōu)劣1.61.7算法性能的事前分析方法1.8算法性能的綜合考量算法性能的綜合考量120若待解決的問(wèn)題數(shù)據(jù)量極大，機(jī)器的存儲(chǔ)空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間時(shí)間復(fù)雜度空間復(fù)雜度邏輯復(fù)雜度若該程序使用次數(shù)較少，則力求算法簡(jiǎn)明易懂；對(duì)于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；算法評(píng)價(jià)角度相互制約時(shí)空轉(zhuǎn)換問(wèn)題數(shù)據(jù)數(shù)據(jù)處理功能測(cè)試：測(cè)試樣例設(shè)計(jì)數(shù)據(jù)引用：數(shù)據(jù)結(jié)構(gòu)描述模塊設(shè)計(jì)：函數(shù)結(jié)構(gòu)設(shè)計(jì)算法設(shè)計(jì)：自頂向下逐步細(xì)化程序設(shè)計(jì)：編碼算法分析：空間時(shí)間復(fù)雜度分析含義：數(shù)據(jù)元素的連接關(guān)系種類：集合、線性、非線性邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算含義：數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中種類：順序、鏈?zhǔn)?、索引、散列存?chǔ)原則：存數(shù)值存聯(lián)系；存得進(jìn)取得出含義：數(shù)據(jù)處理定義：基于數(shù)據(jù)的邏輯結(jié)構(gòu)實(shí)現(xiàn)：基于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)本章小結(jié)本章小結(jié)本章小結(jié)

數(shù)據(jù)結(jié)構(gòu)三要素是邏輯、存儲(chǔ)與運(yùn)算：

邏輯結(jié)構(gòu)說(shuō)的是問(wèn)題中的數(shù)據(jù)元素如何點(diǎn)點(diǎn)相關(guān)聯(lián)；

存儲(chǔ)結(jié)構(gòu)把數(shù)據(jù)值與邏輯關(guān)系存放到內(nèi)存的單元；

運(yùn)算是由算法描述數(shù)據(jù)處理的方案。

一種邏輯關(guān)系可以用多種方式來(lái)存儲(chǔ)，

“存數(shù)值且存聯(lián)系”，“存得進(jìn)并取得出”，

存儲(chǔ)兩規(guī)則，設(shè)計(jì)存的結(jié)構(gòu)時(shí)必遵循的法門無(wú)二般，

存儲(chǔ)結(jié)構(gòu)不同，則算法效率有快有慢。

算法效率從時(shí)間和空間兩個(gè)方面看，

復(fù)雜度用“大歐”的方法來(lái)估算，

用的是算法的漸進(jìn)上限，和運(yùn)算規(guī)模n相關(guān)。122結(jié)點(diǎn)邏輯關(guān)系為線性的結(jié)構(gòu)線性表Chapter

2DataStructuresandAlgorithmAnalysis主要內(nèi)容

線性表的邏輯結(jié)構(gòu)定義各種存儲(chǔ)結(jié)構(gòu)的描述方法

在線性表的兩類存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作學(xué)習(xí)目標(biāo)掌握線性表的兩類存儲(chǔ)結(jié)構(gòu)及基本操作掌握線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及適用場(chǎng)合2.1CONTENTS從邏輯結(jié)構(gòu)角度看線性表線性表的存儲(chǔ)結(jié)構(gòu)方法之一

——順序表線性表的存儲(chǔ)結(jié)構(gòu)方法之二

——鏈表線性表的應(yīng)用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結(jié)2.1CONTENTS從邏輯結(jié)構(gòu)角度看線性表線性表的存儲(chǔ)結(jié)構(gòu)方法之一

——順序表線性表的存儲(chǔ)結(jié)構(gòu)方法之二

——鏈表線性表的應(yīng)用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結(jié)2.1從邏輯結(jié)構(gòu)角度看線性表2.1.12.1.2實(shí)際問(wèn)題中的線性關(guān)系線性表的邏輯結(jié)構(gòu)2.1從邏輯結(jié)構(gòu)角度看線性表2.1.12.1.2實(shí)際問(wèn)題中的線性關(guān)系線性表的邏輯結(jié)構(gòu)實(shí)際問(wèn)題中的線性關(guān)系130排隊(duì)中的一對(duì)一關(guān)系實(shí)際問(wèn)題中的線性關(guān)系131密碼表jkhammotmoyznkvxuikyyulxksubotmyulzcgxkhamycharcode[27]="baefkilcjgdmqzhyoptxvrnwus";明碼ABCDEFGHIJKLMNOPQRSTUVWXYZ密碼BAEFKILCJGDMQZHYOPTXVRNWUSEBKTBPCAESAR截獲敵方情報(bào)一份字符串——各字符先后有特定順序凱撒實(shí)際問(wèn)題中的線性關(guān)系132客戶姓名電話身份證號(hào)地址張1138*****6101131980******李2152*****6101131981******王1139*****6101131990******張2139*****6101131972******李1188*****6101131976******………一個(gè)數(shù)據(jù)元素或一個(gè)結(jié)點(diǎn)電話號(hào)碼表結(jié)構(gòu)2.1從邏輯結(jié)構(gòu)角度看線性表2.1.12.1.2實(shí)際問(wèn)題中的線性關(guān)系線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)134一個(gè)線性表是n(n≥0)個(gè)同類型結(jié)點(diǎn)的有限序列。記作：(a1

a2…ai…an)其中：ai————表示一個(gè)結(jié)點(diǎn)（1≤i≤n）。

n——線性表長(zhǎng)度。n=0時(shí)為空表。定義線性表的邏輯結(jié)構(gòu)135a1a2a3a4an……開(kāi)始結(jié)點(diǎn)終端結(jié)點(diǎn)線性表結(jié)點(diǎn)之間具有先后的、線性的、一維的關(guān)系中間結(jié)點(diǎn)只有一個(gè)前趨和一個(gè)后繼結(jié)點(diǎn)線性表的主要操作136初始化

給線性表相關(guān)參數(shù)賦初值求長(zhǎng)度

求線性表的元素個(gè)數(shù)取元素

取給定位置的元素值定位

查找給定元素值的位置插入

在指定位置插入給定的值刪除

刪除指定位置的值或給定的值遍歷

從頭到尾掃描線性表，做指定的操作2.1CONTENTS從邏輯結(jié)構(gòu)角度看線性表線性表的存儲(chǔ)結(jié)構(gòu)方法之一

——順序表線性表的存儲(chǔ)結(jié)構(gòu)方法之二

——鏈表線性表的應(yīng)用舉例2.22.32.42.52.6順序表和鏈表的比較本章小結(jié)138線性表中的元素相依次放在一個(gè)連續(xù)的存儲(chǔ)空間中順序表2.2線性表的存儲(chǔ)結(jié)構(gòu)方法之一——順序表2.2.12.2.2順序表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)順序表的運(yùn)算2.2.3順序表運(yùn)算的討論2.2線性表的存儲(chǔ)結(jié)構(gòu)方法之一——順序表2.2.12.2.2順序表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)順序表的運(yùn)算2.2.3順序表運(yùn)算的討論順序表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)141012345a0a1a2a3a4a5存數(shù)值存聯(lián)系Ba1a2a0a3a4a5數(shù)值存儲(chǔ)了，聯(lián)系存儲(chǔ)了嗎？線性表結(jié)點(diǎn)邏輯特征：一一順序?qū)?yīng)物理地址相鄰體現(xiàn)邏輯關(guān)系相鄰用數(shù)組存儲(chǔ)線性表，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像，用這種方法存儲(chǔ)的線性表稱作順序表。142線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表定義

無(wú)論位于數(shù)組的什么位置，都能用相等的常量時(shí)間訪問(wèn)存儲(chǔ)區(qū)中的任何元素。隨機(jī)存取下標(biāo)01...k-1kk+1...n-1元素a1a2...ai-1aiai+1...an邏輯上相鄰對(duì)應(yīng)物理地址相鄰任一元素均可隨機(jī)存取順序表存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)143數(shù)組下標(biāo)a1

a2

an

01n-112n內(nèi)存元素序號(hào)LIST_SIZE-1備用空間last怎樣設(shè)計(jì)順序表的結(jié)構(gòu)，才能完整描述整個(gè)順序表信息？思考&討論考慮線性表所有可能的情形順序表存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)144數(shù)組下標(biāo)a1

a2

an

01n-112n內(nèi)存元素序號(hào)LIST_SIZE-1備用空間last怎樣設(shè)計(jì)順序表的結(jié)構(gòu)，才能完整描述整個(gè)順序表信息？思考&討論考慮線性表所有可能的情形順序表存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)145typedefintElemType;

//假定線性表元素的類型為整型#defineLIST_SIZE1024

//假定線性表的最大長(zhǎng)度為1024typedefstruct{ElemTypedata[LIST_SIZE];

intlast;//指向最后結(jié)點(diǎn)的位置}SequenList;sequential:[si‘kwin??l]a.連續(xù)的(序貫的)list:[list]n.目錄,名單,明細(xì)表數(shù)組下標(biāo)a1

a2

an

01n-112n內(nèi)存元素序號(hào)LIST_SIZE-1備用空間lastSequenList*LPtr；

//指向SequenList結(jié)構(gòu)的指針結(jié)構(gòu)描述

146例：typedefintElemType;【知識(shí)ABC】typedef————為類型取一個(gè)新名稱typedef是C語(yǔ)言的關(guān)鍵字，用于在原有數(shù)據(jù)類型（包括基本類型、構(gòu)造類型和指針等）的基礎(chǔ)上，由用戶自定義新的類型名稱。typedef已有類型名

新命名的類型別名;簡(jiǎn)化類型聲明提高程序可移植性關(guān)于結(jié)構(gòu)類型應(yīng)用的思考與討論typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;147這樣的結(jié)構(gòu)描述，系統(tǒng)會(huì)分配空間嗎？Q1148SequenListL；SequenList*L；二者有什么區(qū)別？系統(tǒng)怎樣分空間？結(jié)構(gòu)類型的定義——類型是存儲(chǔ)空間尺寸的描述結(jié)構(gòu)變量的定義——按類型尺寸大小分配存儲(chǔ)空間結(jié)構(gòu)指針——指向單元放的是結(jié)構(gòu)類型的數(shù)據(jù)，指針變量本身占一個(gè)int的空間Q2typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;149定義了結(jié)構(gòu)變量L后，順序表中的結(jié)點(diǎn)如何表示？SequenListL；L.data[0]=a1;X=L.last;

結(jié)構(gòu)成員引用方法1：結(jié)構(gòu)變量

結(jié)構(gòu)成員a1

a2

an

01n-1內(nèi)存lastQ3用指針p指向結(jié)構(gòu)空間后，其中的結(jié)點(diǎn)怎么用p表示？typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;150SequenListL；Sequenlist*p=&L；p->data[0]=a1;X=p->last;

結(jié)構(gòu)成員引用方法2：結(jié)構(gòu)指針

結(jié)構(gòu)成員a1

a2

an

01n-1內(nèi)存lastQ4

typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}ElemType;編號(hào)書(shū)名作者出版社價(jià)格151

當(dāng)結(jié)點(diǎn)內(nèi)容有多個(gè)數(shù)據(jù)項(xiàng)，而不是基本類型int時(shí)，怎么辦？typedefintElemType;typedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;a1

a2

an

01n-1內(nèi)存lastQ52.2線性表的存儲(chǔ)結(jié)構(gòu)方法之一——順序表2.2.12.2.2順序表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)順序表的運(yùn)算2.2.3順序表運(yùn)算的討論順序表的主要操作153初始化

給線性表相關(guān)參數(shù)賦初值求長(zhǎng)度

求線性表的元素個(gè)數(shù)取元素

取給定位置的元素值定位

查找給定元素值的位置插入

在指定位置插入給定的值刪除

刪除指定位置的值或給定的值遍歷

從頭到尾掃描線性表，做指定的操作順序表插入運(yùn)算——定義在線性表第i個(gè)（1

i

n+1）元素之前插入一個(gè)結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表

(a1，…ai-1，ai，…，an)變成長(zhǎng)度為n+1的線性表

(a1，…ai-1，x，ai，…，an)154定義需將第i至第n共（n-i+1)個(gè)元素后移插入的位置，可以是指定的下標(biāo)位置，也可以是指定的值之前，我們?cè)诖税辞耙环N要求設(shè)計(jì)算法。順序表插入運(yùn)算——定義1550a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]移動(dòng)元素的個(gè)數(shù)：last-k+10a11a2……k-1ai-1kXk+1ai…ai+1…an-1lastan…LIST_SIZE-1

插入前插入后數(shù)組下標(biāo)特地用k表示，以與元素標(biāo)號(hào)i區(qū)別順序表插入運(yùn)算——測(cè)試樣例設(shè)計(jì)156

一般情形邊界值異常情形插入的下標(biāo)位置k0≤k≤nk=0,n!(0≤k≤n)順序表未滿未滿已滿或未滿預(yù)期結(jié)果插入成功插入成功插入失敗

順序表插入運(yùn)算——函數(shù)結(jié)構(gòu)設(shè)計(jì)157功能描述輸入輸出順序表元素的插入Insert_SqList順序表地址(SequenList*)完成標(biāo)志(int)0：異常插入值(ElemType)1：正常插入位置(int)函數(shù)名形參函數(shù)類型順序表插入運(yùn)算——數(shù)據(jù)結(jié)構(gòu)描述158SequenList結(jié)構(gòu)ElemTypedata[LIST_SIZE]intlast順序表的地址：

SequenList*LPtr要插入的結(jié)點(diǎn)值x：ElemTypex插入的位置i：intiLPtrtypedefstruct{ElemTypedata[LIST_SIZE];intlast;}SequenList;0a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

data[LIST_SIZE]LPtr結(jié)構(gòu)描述

159順序表插入運(yùn)算——算法描述在順序表中第i個(gè)位置插入新元素x第一步細(xì)化異常情形處理，返回不成功處理標(biāo)志在順序表中移動(dòng)元素，空出下標(biāo)為k的位置插入新元素x修改元素最后位置指針?lè)祷爻晒μ幚順?biāo)志頂部偽代碼描述在順序表中第i個(gè)位置插入新元素x問(wèn)題順序表插入運(yùn)算——算法描述160第一步細(xì)化第二步細(xì)化異常情形處理返回不成功處理標(biāo)志若順序表溢出，則return0;若k是非法位置，則return0;在順序表中移動(dòng)元素，空出下標(biāo)為k的位置從順序表的最后一個(gè)元素起向后移動(dòng)(last–k+1)個(gè)元素插入新元素x將x放入表的k位置修改元素最后位置指針Last+1返回成功處理標(biāo)志return1在順序表中第i個(gè)位置插入新元素x問(wèn)題161第二步細(xì)化若k是非法位置，則return0;若順序表溢出，則return0;從順序表的最后一個(gè)元素起向后移動(dòng)(last–k+1)個(gè)元素將x放入表的k位置Last+1return1第三步細(xì)化if(LPtr->last>=LIST_SIZE－1)return0;if(k<0||k>(LPtr->last＋1))return0;j=LPtr->last;當(dāng)

j>=kLPtr->data[j+1]=LPtr->data[j];j--;LPtr->data[k]=x;LPtr->last=LPtr->last+1;return10a11a2……k-1ai-1kaik+1ai+1…an-1lastan……LIST_SIZE-1

順序表插入運(yùn)算——程序?qū)崿F(xiàn)162/*===========================================函數(shù)功能：順序表運(yùn)算——元素的插入函數(shù)輸入：順序表地址，插入值，插入位置函數(shù)輸出：完成標(biāo)志——0：異常1：正常=============================================*/intInsert_SqList(SeqList*LPtr,ElemTypex,intk){intj;if(LPtr->last>=LIST_SIZE-1)returnFALSE; //溢出

elseif(k<0||k>(LPtr->last+1))returnFALSE; //非法位置

else{for(j=LPtr->last;j>=k;j--) //從順序表的最后一個(gè)元素起

{LPtr->data[j+1]=LPtr->data[j];//向后移動(dòng)(last-k)個(gè)元素}LPtr->data[k]=x; //將x放入表的k位置

LPtr->last=LPtr->last+1; //修改最后結(jié)點(diǎn)指針last}returnTRUE;}順序表插入運(yùn)算——算法效率分析a1a2…aia1a2…xa1a2…ai+1…aiai+1…xaiai+1…an…anx…a1a2…aiai+1…an…a1a2…aiai+1…an…a1a2…aiai+1…an…an…O(1)O(n)O(?)最好情況最壞情況一般情況順序表插入運(yùn)算——算法效率分析164在第k個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)每一點(diǎn)插入概率Pk均等=1/(n+1)插入下標(biāo)位置k012...k...n-1n移動(dòng)次數(shù)nn-1n-2...n-k...10算法的平均時(shí)間復(fù)雜度為O(n)移動(dòng)元素的平均次數(shù)在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半元素順序表刪除運(yùn)算——定義165將線性表的第i(1≦i≦n)個(gè)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表：

(a1，…ai-1，ai，ai+1…，an)

變成長(zhǎng)度為n-1的線性表

(a1，…ai-1，ai+1，…，an)定義設(shè)第i個(gè)結(jié)點(diǎn)對(duì)應(yīng)下標(biāo)為k，則需將第k+1至last共last-k個(gè)元素前移。順序表刪除運(yùn)算——定義166刪除前刪除后0a11a2……k-1ai-1kaik+1ai+1k+2ai+2…an-1lastan…

data[LIST_SIZE]0a11a2……k-1ai-1kai+1k+1ai+2…an-2lastan-1…

移動(dòng)元素的個(gè)數(shù)：last-(k+1)+1=last-kLIST_SIZE-1LIST_SIZE-1順序表刪除運(yùn)算——測(cè)試樣例設(shè)計(jì)

一般情形邊界值異常情形刪除下標(biāo)位置k0≤k≤n-1k=0,n-1!(0≤k≤n-1)順序表非空空非空空非空空預(yù)期結(jié)果刪除成功刪除失敗刪除成功刪除失敗刪除失敗刪除失敗輸入：順序表的地址，要?jiǎng)h除的結(jié)點(diǎn)下標(biāo)位置k輸出：操作是否成功標(biāo)志順序表刪除運(yùn)算