n個元素的數(shù)組向左循環(huán)移動

i個位置有許多應(yīng)用會調(diào)用這個問題的算法，因此，要求有較高的時間性能和空間性能解法1：先將數(shù)組中的前

i

個元素存放在一個臨時數(shù)組中，再將余下的

n–i

個元素左移

i個位置，最后將前

i

個元素從臨時數(shù)組復(fù)制回原數(shù)組中后面的

i

個位置。共需要移動

i+(n–i)+i=i+n

次數(shù)組元素，但使用了

i

個額外的存儲單元【數(shù)組循環(huán)左移問題】將一個具有

n個元素的數(shù)組向左循環(huán)移動

i個位置有許多應(yīng)用會調(diào)用這個問題的算法，因此，要求有較高的時間性能和空間性能解法2：先設(shè)計一個函數(shù)將數(shù)組向左循環(huán)移動1個位置，然后再調(diào)用該算法

i次。只使用了1個額外的存儲單元，但共需要移動

i×n

次數(shù)組元素算法的作用【數(shù)組循環(huán)左移問題】將一個具有

n個元素的數(shù)組向左循環(huán)移動

i個位置有許多應(yīng)用會調(diào)用這個問題的算法，因此，要求有較高的時間性能和空間性能解法3：將這個問題看作是把數(shù)組AB轉(zhuǎn)換成數(shù)組BA（A代表數(shù)組的前

i個元素，B代表數(shù)組中余下的

n–i

個元素），先將A置逆得到A-1B，再將B置逆得到A-1B-1，最后將整個A-1B-1置逆得到(A-1B-1)-1=BAabcdefgcbagfeddefgabc共交換

次數(shù)組元素，只使用了1個用來交換的臨時單元算法的作用【排序問題】對整型數(shù)組r[n]進(jìn)行非降序排列。【算法】有很多排序算法可以解決這個問題，不同排序算法的運(yùn)行時間有很大差別，起泡排序和快速排序算法在不同數(shù)據(jù)規(guī)模的運(yùn)行時間如下表所示，隨著數(shù)據(jù)規(guī)模的增長，起泡排序和快速排序運(yùn)行時間的差別越來越大。算法的作用1-2-4本課程討論的主要內(nèi)容v第一章緒論數(shù)據(jù)模型數(shù)據(jù)模型數(shù)值問題：數(shù)學(xué)方程非數(shù)值問題：表、樹、圖等數(shù)據(jù)結(jié)構(gòu)問

題想法抽象模型基本思路算

法數(shù)據(jù)表示數(shù)據(jù)處理程

序程序語言編程環(huán)境例1-6

為百元買百雞問題抽象數(shù)據(jù)模型（《算經(jīng)》）【問題】雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何？x+y+z=1005×x+3×y+z/3=1000≤x≤200≤y≤330≤z≤100【想法——數(shù)據(jù)模型】設(shè)

x、y

和

z

分別表示公雞、母雞和小雞的個數(shù)，則有如下方程組成立：數(shù)據(jù)模型例1-7為學(xué)籍管理問題抽象數(shù)據(jù)模型如何實(shí)現(xiàn)增、刪、改、查等功能？各表項之間是什么關(guān)系？數(shù)據(jù)表示——存儲學(xué)籍表表結(jié)構(gòu)學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………199701021998032819971116……抽象數(shù)據(jù)模型例1-8為人機(jī)對弈問題抽象數(shù)據(jù)模型如何實(shí)現(xiàn)對弈？計算機(jī)的操作對象？各格局之間是什么關(guān)系？數(shù)據(jù)表示——存儲對弈樹樹結(jié)構(gòu)抽象數(shù)據(jù)模型例1-9為七巧板涂色問題抽象數(shù)據(jù)模型如何實(shí)現(xiàn)涂色？如何表示區(qū)域之間的鄰接關(guān)系？數(shù)據(jù)表示——存儲七巧板圖結(jié)構(gòu)BDAFECG抽象ABEDCFG數(shù)據(jù)模型討論什么（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)，其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系；（4）常用數(shù)據(jù)處理技術(shù)：查找技術(shù)、排序技術(shù)等。（2）數(shù)據(jù)的存儲結(jié)構(gòu)：如何將表、樹、圖等數(shù)據(jù)結(jié)構(gòu)存儲到計算機(jī)的存儲器中，其核心是如何有效地存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系；（3）算法：如何基于數(shù)據(jù)的某種存儲結(jié)構(gòu)實(shí)現(xiàn)插入、刪除、查找等基本操作，其核心是如何有效地處理數(shù)據(jù)；本課程主要討論非數(shù)值問題的數(shù)據(jù)組織和處理數(shù)據(jù)結(jié)構(gòu)和算法的作用對于許多實(shí)際的問題，寫出一個正確的算法還不夠，如果這個算法在規(guī)模較大的數(shù)據(jù)集上運(yùn)行，運(yùn)行效率就成為一個重要的問題對問題抽象出不同的數(shù)據(jù)模型問

題想法抽象模型基本思路算

法數(shù)據(jù)表示數(shù)據(jù)處理程

序程序語言編程環(huán)境對不同求解方法的抽象描述不同的算法效率不同對數(shù)據(jù)模型的不同表示（存儲）1-3數(shù)據(jù)結(jié)構(gòu)的基本概念v第一章緒論數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)？什么是數(shù)據(jù)元素？什么是結(jié)構(gòu)？關(guān)系指的是什么？學(xué)什么？數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型如何描述與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)？1-3-1數(shù)據(jù)結(jié)構(gòu)v第一章緒論理解數(shù)據(jù)數(shù)據(jù)：所有能輸入到計算機(jī)中并能被程序識別和處理的符號集合數(shù)據(jù)數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等數(shù)據(jù)是程序的處理對象，嚴(yán)格來說，計算機(jī)=數(shù)據(jù)處理機(jī)學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………200601022006032820051116……數(shù)據(jù)是程序的處理對象理解數(shù)據(jù)數(shù)據(jù)：所有能輸入到計算機(jī)中并能被程序識別和處理的符號集合數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在程序中作為一個整體進(jìn)行考慮和處理數(shù)據(jù)項：構(gòu)成數(shù)據(jù)元素的最小單位學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………199701021998032819971116……數(shù)據(jù)元素數(shù)據(jù)項通常情況下，數(shù)據(jù)元素具有相同個數(shù)和類型的數(shù)據(jù)項理解數(shù)據(jù)元素一般來說，能獨(dú)立、完整地描述問題世界的一切實(shí)體都是數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時的著眼點(diǎn)學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………199701021998032819971116……學(xué)籍管理問題，數(shù)據(jù)元素是什么？表項抽象理解數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系人機(jī)對弈問題，數(shù)據(jù)元素是什么？格局抽象理解數(shù)據(jù)元素數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時的著眼點(diǎn)一般來說，能獨(dú)立、完整地描述問題世界的一切實(shí)體都是數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系七巧板涂色問題，數(shù)據(jù)元素是什么？區(qū)域DAFECGB抽象ABEDCFG理解數(shù)據(jù)元素數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時的著眼點(diǎn)一般來說，能獨(dú)立、完整地描述問題世界的一切實(shí)體都是數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合按照視點(diǎn)的不同，分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的整體是否基于內(nèi)存關(guān)聯(lián)方式或鄰接關(guān)系取決于實(shí)際問題理解邏輯結(jié)構(gòu)如何理解邏輯關(guān)系？數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的整體數(shù)據(jù)的邏輯結(jié)構(gòu)在形式上可定義為一個二元組：

Data_Structure=(D,R)其中D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的集合Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={(A,B),(A,E),(A,F),(B,C),(B,D),

(C,D),(D,E),(D,G),(E,F),(E,G)}ABEDCFG理解邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：（2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對一的線性關(guān)系（3）樹結(jié)構(gòu)：數(shù)據(jù)元素之間是一對多的層次關(guān)系（4）圖結(jié)構(gòu)：數(shù)據(jù)元素之間是多對多的任意關(guān)系（1）集合：數(shù)據(jù)元素之間沒有關(guān)系線性關(guān)系：線性結(jié)構(gòu)非線性關(guān)系：樹結(jié)構(gòu)和圖結(jié)構(gòu)

理解邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)的存儲（物理）結(jié)構(gòu)：數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機(jī)中的表示存儲結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，具體實(shí)現(xiàn)時依賴于計算機(jī)語言計算機(jī)語言如何進(jìn)行內(nèi)存分配？在變量定義時進(jìn)行內(nèi)存分配內(nèi)存數(shù)據(jù)元素邏輯關(guān)系算

法想

法數(shù)據(jù)表示數(shù)據(jù)處理理解存儲結(jié)構(gòu)通常有兩種存儲結(jié)構(gòu)：（1）順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置表示redgreenblue……起始地址例：(red,green,blue)下標(biāo)理解存儲結(jié)構(gòu)（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示020002080300redgreenblue02000300∧………起始地址地址通常有兩種存儲結(jié)構(gòu)：（1）順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置表示例：(red,green,blue)理解存儲結(jié)構(gòu)下標(biāo)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是用戶視圖，面向問題數(shù)據(jù)的存儲結(jié)構(gòu)是實(shí)現(xiàn)視圖，面向計算機(jī)

問

題想法抽象模型基本思路算

法數(shù)據(jù)表示數(shù)據(jù)處理程

序程序語言編程環(huán)境邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以采用多種存儲結(jié)構(gòu)來實(shí)現(xiàn)，采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的數(shù)據(jù)本身的構(gòu)成方式數(shù)據(jù)在內(nèi)存的存儲表示1-3-2抽象數(shù)據(jù)類型v第一章緒論理解數(shù)據(jù)類型什么是數(shù)據(jù)類型呢？數(shù)據(jù)類型：一組值的集合以及定義于這個值集上的一組操作inta,b;floatx,y;x=1234567.123;x=x%y;a=10000000000000;a=a%b;數(shù)據(jù)類型是數(shù)據(jù)的一種屬性，包含三層含義：分配存儲空間—存儲格式，值的集合—取值范圍，運(yùn)算集合—進(jìn)行運(yùn)算。理解抽象水果地圖抽象：抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)1+1=22+3=5x+y=z抽象的好處是什么？算術(shù)運(yùn)算代數(shù)運(yùn)算在一個更高的層次上思考問題抽象數(shù)據(jù)類型把什么抽象掉了呢？抽象數(shù)據(jù)類型：一個數(shù)據(jù)模型以及定義在該模型上的一組操作

抽象數(shù)據(jù)類型問

題想法抽象模型基本思路邏輯結(jié)構(gòu)數(shù)據(jù)模型=數(shù)據(jù)的邏輯結(jié)構(gòu)強(qiáng)調(diào)有哪些數(shù)據(jù)元素，數(shù)據(jù)元素之間滿足什么邏輯關(guān)系，基于數(shù)據(jù)模型有哪些基本操作抽象數(shù)據(jù)類型不考慮數(shù)據(jù)項，把具體的數(shù)據(jù)類型抽象掉了學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………199701021998032819971116……抽象抽象數(shù)據(jù)類型只考慮數(shù)據(jù)的邏輯結(jié)構(gòu)和基本操作抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型把什么抽象掉了呢？抽象數(shù)據(jù)類型：一個數(shù)據(jù)模型以及定義在該模型上的一組操作

如何實(shí)現(xiàn)抽象數(shù)據(jù)類型（abstract

data

type，簡稱ADT）呢？實(shí)現(xiàn)層（C、…）●自定義數(shù)據(jù)類型●自定義函數(shù)實(shí)現(xiàn)層（C++、Java、…）●成員變量●成員函數(shù)類抽象層●數(shù)據(jù)模型（邏輯結(jié)構(gòu)）●操作集合（a）定義——ADT定義設(shè)計層●數(shù)據(jù)表示（存儲結(jié)構(gòu)）●算法（b）設(shè)計——數(shù)據(jù)結(jié)構(gòu)設(shè)計（c）實(shí)現(xiàn)——程序語言實(shí)現(xiàn)抽象數(shù)據(jù)類型如何定義抽象數(shù)據(jù)類型呢？ADT

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

數(shù)據(jù)元素之間邏輯關(guān)系的定義

輸入：執(zhí)行此操作所需要的輸入功能：該操作將完成的功能輸出：執(zhí)行該操作后產(chǎn)生的輸出

……

……endADT

DataModelOperation操作1操作2操作n操作接口（函數(shù)原型）抽象數(shù)據(jù)類型1-4算法的基本概念v第一章緒論見識算法圖靈獎與算法Hoare在26歲發(fā)明了聞名于世的快速排序算法；Ronald、Shamir和Adleman發(fā)明了國際上最具影響力的公鑰密碼算法RSA；Knuth編著的《程序設(shè)計的藝術(shù)》奠定了數(shù)據(jù)結(jié)構(gòu)與算法領(lǐng)域的主要內(nèi)容；Floyd發(fā)明了求解多源點(diǎn)最短路徑的Floyd算法以及堆結(jié)構(gòu)；Karp在網(wǎng)絡(luò)流和組合優(yōu)化問題領(lǐng)域都發(fā)明了許多高效算法；

Hopcroft和他的學(xué)生Tarjan在數(shù)據(jù)結(jié)構(gòu)和算法方面有眾多創(chuàng)造性貢獻(xiàn)；姚期智（Chi-ChihYao）發(fā)明了偽隨機(jī)數(shù)的生成算法以及加密/解密算法；Sutherland發(fā)明的圖形圖像算法改善了屏幕刷新的文件顯示；Dijkstra發(fā)明了單源點(diǎn)的最短路徑算法Dijkstra算法；Wilkinson在數(shù)值線性代數(shù)方面發(fā)現(xiàn)很多有意義的算法；Blum發(fā)現(xiàn)了著名的算法設(shè)計技術(shù)——分支限界法……算法是計算機(jī)科學(xué)的基石三大學(xué)報文章概覽見識算法算法及算法的特性學(xué)什么？算法的描述方法1-4-1算法及算法的特性v第一章緒論算法的起源算法的中文名稱出自《周髀算經(jīng)》（西周~秦漢）張倉《九章算術(shù)》創(chuàng)立的機(jī)械化算法體系今有三分之一，五分之二。問合之得幾何？答曰：十五分之十一。又有三分之二，七分之四，九分之五。問合之得幾何？答曰：得一、六十三分之五十。又有二分之一，三分之二，四分之三，五分之四。問合之得幾何？答曰：得二、六十分之四十三。合分（分?jǐn)?shù)相加）術(shù)（算法）曰：母（分母）互乘子（分子），并以為實(shí)（被除數(shù)），母相乘為法（除數(shù)），實(shí)如（除以）法而一。不滿法者，以法命之，其母同者，直相從（加）之。歐幾里得《幾何原本》創(chuàng)立的邏輯演繹體系世界數(shù)學(xué)的兩大體系算法的英文名稱來自于波斯數(shù)學(xué)家阿勒·霍瓦里松《代數(shù)對話錄》

（公元825年）Algorithm在Webster'sNewWorldDictionary（1957版）中尚未出現(xiàn)Algorithm——算法；Logarithm——對數(shù)；Algorism——算術(shù)歐幾里得算法被人們認(rèn)為是史上第一個算法算法的起源張倉《九章算術(shù)》創(chuàng)立的機(jī)械化算法體系歐幾里得《幾何原本》創(chuàng)立的邏輯演繹體系世界數(shù)學(xué)的兩大體系算法的定義輸入操作步驟：

1.………2.………3.………算法

:是對特定問題求解步驟的一種描述，是指令的有限序列算法不是問題的答案，而是解決問題的操作步驟1.柿子切塊，雞蛋加適量鹽攪拌2.鍋里放油3.把雞蛋倒進(jìn)去炒熟4.加入蔥花5.把柿子放進(jìn)去放少許鹽和味精6.翻炒幾下出鍋裝盤木須柿子的做法：輸出算法的操作步驟應(yīng)該滿足什么要求？（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成每一條指令都不是無限循環(huán)！有窮不是數(shù)學(xué)意義上的概念！算法的特性輸入操作步驟：

1.………2.………3.………輸出（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成（2）確定性：每一條指令必須有確切的含義，相同的輸入得到相同的輸出上下文無關(guān)算法的操作步驟應(yīng)該滿足什么要求？算法的特性輸入操作步驟：

1.………2.………3.………輸出（3）可行性：操作步驟可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)（1）有窮性：總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成（2）確定性：每一條指令必須有確切的含義，相同的輸入得到相同的輸出機(jī)器可執(zhí)行算法的操作步驟應(yīng)該滿足什么要求？算法的特性輸入操作步驟：

1.………2.………3.………輸出步驟1：找出

m的所有質(zhì)因子步驟2：找出

n的所有質(zhì)因子步驟3：從第1步和第2步得到的質(zhì)因子中找出所有公因子步驟4：將找到的所有公因子相乘，結(jié)果即為

m和

n的最大公約數(shù)【想法】將這兩個自然數(shù)分別進(jìn)行質(zhì)因數(shù)分解，然后找出所有公因子并將這些公因子相乘。例如，48=2×2×2×2×3，36=2×2×3×3，公因子有2、2、3，因此，48和36的最大公約數(shù)為2×2×3=12。例1-12設(shè)計算法求兩個自然數(shù)的最大公約數(shù)。【算法】設(shè)兩個自然數(shù)是m和n，算法如下：滿足算法的特性嗎？如何找出所有質(zhì)因子？如何找出所有公因子？質(zhì)因數(shù)分解尚未找到多項式時間算法不滿足確定性、有窮性！算法的特性好算法的特性（1）正確性：算法能滿足具體問題的需求，即對于任何合法的輸入，算法都會得出正確的結(jié)果。一個算法滿足什么特性才能稱之為好算法呢？（4）抽象分級：用合適的抽象分級組織表達(dá)算法的思想，

啟發(fā)式規(guī)則7±2。（2）健壯性：算法對非法輸入的抵抗能力，即對于錯誤的輸入，算法應(yīng)能識別并做出處理，而不是產(chǎn)生錯誤動作或陷入癱瘓。（3）可理解性：算法容易理解和實(shí)現(xiàn)。（5）高效性：具有較短的執(zhí)行時間并占用較少的輔助空間。米勒原則：人類的短期記憶能力一般限于一次記憶

5～9

個對象1-4-2算法的描述方法v第一章緒論歐幾里得算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））m

n

r35252510105【想法——基本思路】設(shè)兩個自然數(shù)為m和

n，歐幾里得算法的基本思想是將

m和

n輾轉(zhuǎn)相除直到余數(shù)為01050自然語言描述算法【算法——自然語言描述】設(shè)兩個自然數(shù)為m和

n，歐幾里得算法如下：步驟1：將m除以n得到余數(shù)r；步驟2：若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟3；步驟3：將n的值放在m中，將r的值放在n中，重新執(zhí)行步驟1；優(yōu)點(diǎn)：容易理解；缺點(diǎn)：冗長、二義性使用方法：粗線條描述算法思想；注意事項：避免寫成自然段輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））流程圖描述算法優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次【算法——流程圖描述】設(shè)兩個自然數(shù)為m和

n，算法為開始結(jié)束r=m%nr=0m=nn=r輸出nY輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））程序語言描述算法【算法——程序語言描述】設(shè)兩個自然數(shù)為m和

n，算法為優(yōu)點(diǎn)：能由計算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））偽代碼描述算法什么是偽代碼呢？偽代碼：介于自然語言和程序設(shè)計語言之間的方法，它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計。偽代碼有標(biāo)準(zhǔn)嗎？偽代碼不是一種實(shí)際的編程語言，但在表達(dá)能力上類似于編程語言，同時極小化了描述算法的不必要的技術(shù)細(xì)節(jié)偽代碼被稱為“算法語言”或“第一語言”【算法——偽代碼描述】設(shè)兩個自然數(shù)為m和

n，算法為優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，

容易理解，容易實(shí)現(xiàn)使用方法：7±2偽代碼描述算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））米勒原則：人類的短期記憶能力一般限于一次記憶

5～9

個對象輸入：兩個自然數(shù)m和n輸出：m和n的最大公約數(shù)1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}只描述子函數(shù)；省略主函數(shù)和頭函數(shù)偽代碼描述算法輾轉(zhuǎn)相除求兩個自然數(shù)的最大公約數(shù)（古希臘（公元前300年））【算法——偽代碼描述】設(shè)兩個自然數(shù)為m和

n，算法為輸入：兩個自然數(shù)m和n輸出：m和n的最大公約數(shù)1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;1-5算法分析v第一章緒論算法分析算法設(shè)計：面對一個問題，如何設(shè)計一個高效的算法算法分析：對已設(shè)計的算法，如何評價或判斷其優(yōu)劣檢驗評估指導(dǎo)改進(jìn)如何評價算法？易讀性健壯（容錯）性可維護(hù)性可擴(kuò)展性……效率（速度）——算法的核心和靈魂算法分析算法的時間復(fù)雜度學(xué)什么？算法的空間復(fù)雜度算法分析實(shí)例1-5-1算法的時間復(fù)雜度v第一章緒論度量算法效率如何度量算法的效率呢？缺點(diǎn)：（1）編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時間和精力

（2）所得實(shí)驗結(jié)果依賴于計算機(jī)的軟硬件等環(huán)境因素

事后統(tǒng)計（定量分析）：將算法實(shí)現(xiàn)，測算其時間和空間開銷事前分析（定性分析）：對算法所消耗資源的一種估算方法時間空間對估算方法有什么要求呢？能夠刻畫效率；與語言環(huán)境無關(guān)；具有一般性……時間復(fù)雜度算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間指令系統(tǒng)、編譯的代碼質(zhì)量單位時間每條語句執(zhí)行次數(shù)之和=for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語句的執(zhí)行次數(shù)問題規(guī)模：輸入量的大小基本語句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令注意到，幾乎所有算法，對于規(guī)模更大的輸入需要運(yùn)行更長的時間運(yùn)行算法所需要的時間

T

是問題規(guī)模

n

的函數(shù)，記作

T(n)如何表示算法的運(yùn)行時間函數(shù)呢？算法的運(yùn)行時間=基本語句的執(zhí)行次數(shù)如何計算算法中基本語句的執(zhí)行次數(shù)呢？時間復(fù)雜度：當(dāng)問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)在漸近意義下的階——關(guān)注的是增長趨勢問題規(guī)模可以是多個變量

多元函數(shù)時間復(fù)雜度大O記號定義1-1若存在兩個正的常數(shù)

c和

n0，對于任意

n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)T(n)和f(n)具有相同的增長趨勢，T(n)的增長至多趨同于函數(shù)f(n)的增長定理1-1：若T(n)=amnm+am-1nm-1+

+a1n+a0是一個m次多項式，則T(n)=O(nm)關(guān)注增長率——忽略所有低次冪和最高次冪的系數(shù)大O記號時間復(fù)雜度是一種估算技術(shù)（信封背面的技術(shù)）Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)常見的時間復(fù)雜度：多項式時間，易解問題指數(shù)時間，難解問題時間復(fù)雜度是在不同數(shù)量級的層面上比較算法大O記號估算的局限冰雹猜想（HailstoneSequence，角谷猜想，3n+1問題）1.輸入一個正整數(shù)n；2.如果n

等于1，結(jié)束算法；3.如果n

是奇數(shù)，則n

變?yōu)?n+1，否則n

變?yōu)閚/2；4.重新執(zhí)行步驟2；所有測試的正整數(shù)都可以終止，但是至今沒有人證明對所有的正整數(shù)該過程都能夠終止，而且至今沒有人能夠分析這個簡單算法的時間復(fù)雜度例如：n=9，有{9,

28,

14,

7,

22,

11,

34,

17,

52,

26,

13,

40,

20,

10,

5,

16,

8,

4,

2,

1}例如：n=27，經(jīng)過77步變換到達(dá)頂峰值9232，又經(jīng)過32步變換到達(dá)谷底值11-5-2算法的空間復(fù)雜度v第一章緒論空間分析算法在運(yùn)行過程中需要哪些存儲空間？（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)intCommonFactor(intm,intn){}voidBubbleSort(intr[],intn){ }voidEquation(doublea,doubleb,doublec,double*p,double*q){}（2）算法本身占用的空間與算法相關(guān)，大小固定intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)空間分析算法在運(yùn)行過程中需要哪些存儲空間？（3）執(zhí)行算法需要的輔助空間與算法相關(guān)，體現(xiàn)效率除算法本身和輸入輸出數(shù)據(jù)所占用的空間外，算法臨時開辟的存儲空間空間復(fù)雜度：算法在執(zhí)行過程中需要的輔助空間數(shù)量空間復(fù)雜度也是問題規(guī)模的函數(shù)，通常記作：S(n)=O(f(n))（2）算法本身占用的空間與算法相關(guān)，大小固定（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)空間分析算法在運(yùn)行過程中需要哪些存儲空間？空間復(fù)雜度voidBubbleSort(intr[],intn){ intj,temp,bound,exchange=n; while(exchange!=0){

bound=exchange;exchange=0;for(j=1;j<bound;j++)if(r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}}}voidMerge(intr[],ints,intm,intt){intr1[n];inti=s,j=m+1,k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m)r1[k++]=r[i++];while(j<=t)r1[k++]=r[j++];for(i=s;i<t;i++)r[i]=r1[i];}O(1)O(n)就地（原地）算法：空間復(fù)雜度為O(1)，輔助空間是常數(shù)1-5-3算法分析實(shí)例v第一章緒論非遞歸算法例1++x;例2for(i=1;i<=n;++i)++x;O(1)常數(shù)階O(n)線性階例3for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;O(n2)平方階例4for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}O(n3)立方階例5for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;分析的策略是從內(nèi)部（或最深層部分）向外展開例6for(i=1;i<=n;i=2*i) ++x;O(log2n)對數(shù)階分析的策略是設(shè)其執(zhí)行次數(shù)為T(n)，則有2T(n)≤n，即T(n)≤log2nO(n2)T(n)=O(log2n)=O(logn)非遞歸算法遞歸算法分析的策略是根據(jù)遞歸過程建立遞推關(guān)系式并求解（求和表達(dá)式）例7分析遞推式

的時間復(fù)雜度假定

n=2k各種情況基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關(guān)？例8在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素

intFind(intA[],intn,intk)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }如果算法的時間代價與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況最好情況：1次，O(1)最壞情況：n

次，O(n)平均情況：n/2次，O(n)基本語句？最好情況：不能代表算法的效率，當(dāng)出現(xiàn)概率較大時分析最壞情況：最壞能壞到什么程度，實(shí)時系統(tǒng)需要分析平均情況：已知輸入數(shù)據(jù)分布情況，通常假設(shè)等概率分布如果算法的時間代價與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況各種情況如何定義平均？2-1引言v第二章線性表學(xué)籍管理問題學(xué)號姓名性別出生日期籍貫15041001王軍男吉林省圖們市15041002李明男吉林省吉林市15041003湯曉影女吉林省長春市………200201022003032820031116……抽象學(xué)籍管理問題，數(shù)據(jù)元素是什么？元素之間的關(guān)系？完成什么功能？二維表線性結(jié)構(gòu)Page01工資管理問題工資管理問題，數(shù)據(jù)元素是什么？元素之間的關(guān)系？完成什么功能？職工號000826000235000973…姓名王一梅李明鄭浩…性別女男男…基本工資348038602850…崗位津貼190024001600…業(yè)績津貼138016001050…抽象所有二維表抽象的數(shù)據(jù)模型都是線性結(jié)構(gòu)嗎？研究如何存儲線性結(jié)構(gòu)，并實(shí)現(xiàn)增、刪、改、查等基本操作。二維表線性結(jié)構(gòu)約瑟夫環(huán)問題【問題】約瑟夫環(huán)問題由古羅馬史學(xué)家約瑟夫（Josephus）提出，他參加并記錄了公元66—70年猶太人反抗羅馬的起義。在城市淪陷之后，他和40名死硬的將士在附近的一個洞穴中避難。這些起義者表決說“要投降毋寧死”。于是，約瑟夫建議每個人輪流殺死他旁邊的人，而這個順序是由抽簽決定的。約瑟夫有預(yù)謀地抓到了最后一簽，并且，作為洞穴中的兩個幸存者之一，他說服了他原先的犧牲品一起投降了羅馬。【想法——數(shù)據(jù)模型】設(shè)

n(n>0)個人圍成一個環(huán)，n個人的編號分別為1，2，…，n，從第1個人開始報數(shù)，報到

m時停止報數(shù)，報

m的人出環(huán)，再從他的下一個人起重新報數(shù)，報到

m時停止報數(shù)，報m的人出環(huán)，……，如此下去，直到所有人全部出環(huán)為止。對于任意給定

n和

m，求

n個人出環(huán)的次序。如何存儲這種環(huán)狀線性結(jié)構(gòu)，并求解約瑟夫環(huán)的出環(huán)次序呢？12354出環(huán)的順序是：31524例如，n=5,m=3，則約瑟夫環(huán)問題隨處可見的線性結(jié)構(gòu)關(guān)于線性結(jié)構(gòu)什么是線性結(jié)構(gòu)？在邏輯上有什么特點(diǎn)？如何存儲線性結(jié)構(gòu)？在不同的存儲結(jié)構(gòu)上，如何實(shí)現(xiàn)插入、刪除、查找等基本操作？在不同的存儲結(jié)構(gòu)上，基本操作的時空性能如何？2-2線性表的邏輯結(jié)構(gòu)v第二章線性表線性表的定義線性表的邏輯特征線性表的抽象數(shù)據(jù)類型定義學(xué)什么？2-2-1線性表的定義v第二章線性表線性表的定義線性表（表）：n（n≥0）個具有相同類型的數(shù)據(jù)元素的有限序列（a1,a2,…,ai,…,an）線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)空表：長度等于零的線性表ai（1≤i≤n）稱為數(shù)據(jù)元素下角標(biāo)

i表示該元素在線性表中的位置或序號線性表的邏輯特征1.數(shù)據(jù)元素個數(shù)的有限性a1ai-1aiana22.數(shù)據(jù)元素類型的相同性3.數(shù)據(jù)元素類型的抽象性4.相鄰數(shù)據(jù)元素的序偶性，且a1無前驅(qū)，an無后繼序偶：兩個具有固定次序的元素組成的序列，記作(a，b)，且稱a是b

的前驅(qū)，b是a

的后繼L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))不確定、任意2-2-2線性表的抽象數(shù)據(jù)類型定義v第二章線性表線性表的抽象數(shù)據(jù)類型定義ADTListDataModelOperationendADT線性表中的數(shù)據(jù)元素具有相同類型，相鄰元素具有前驅(qū)和后繼關(guān)系InitList：表的初始化，建一個空表CreateList：建立具有n個元素的線性表DestroyList：銷毀表，釋放表所占用的存儲空間Length：求表的長度Get：在表中取序號為i

的數(shù)據(jù)元素Locate：在線性表中查找值等于x

的元素Insert：在表的第i

個位置處插入一個新元素xDelete：刪除表中的第i

個元素Empty：判斷表是否為空InitList

輸入：無功能：表的初始化，建一個空表輸出：無CreateList

輸入：n個數(shù)據(jù)元素

功能：建立一個線性表

輸出：具有n個元素的線性表DestroyList輸入：無功能：銷毀表，釋放表所占用的存儲空間輸出：無Locate輸入：數(shù)據(jù)元素x

功能：在線性表中查找值等于x

的元素輸出：查找成功返回x

在表中的序號，否則返回0線性表的抽象數(shù)據(jù)類型定義（a1,a2,…,ai,…,an）Get輸入：元素的序號i

功能：在表中取序號為i

的數(shù)據(jù)元素輸出：若i合法，返回序號為i的元素值Length

輸入：無功能：求表的長度輸出：表中數(shù)據(jù)元素的個數(shù)Insert輸入：插入位置i，待插x功能：在表的第i

個位置處插入一個新元素x輸出：若插入成功，表中增加一個新元素；否則給出失敗信息Delete

輸入：刪除位置i功能：刪除表中的第i

個元素輸出：若刪除成功，表中減少一個元素；否則給出失敗信息Empty輸入：無功能：判斷表是否為空輸出：若是空表，返回1，否則返回0線性表的抽象數(shù)據(jù)類型定義（a1,a2,…,ai,…,an）（1）線性表的基本操作根據(jù)實(shí)際應(yīng)用而定（2）復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)（3）對不同的應(yīng)用，操作的接口可能不同2-3線性表的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)v第二章線性表順序表的存儲結(jié)構(gòu)順序表的實(shí)現(xiàn)學(xué)什么？順序表的類定義、構(gòu)造函數(shù)、析構(gòu)函數(shù)順序表的判空、取長度操作：Empty、Length順序表的查找操作：Get、Locate順序表的插入、刪除操作：Insert、Delete2-3-1順序表的存儲結(jié)構(gòu)v第二章線性表順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)某些內(nèi)存單元可能是空嗎？例：（34,23,67,43）342367434存儲要點(diǎn)用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素用什么屬性來描述順序表？342367434存儲空間的起始位置順序表的容量（最大長度）順序表的當(dāng)前長度例：（34,23,67,43）Page03順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

長度數(shù)組的長度MaxSize線性表的長度lengthMaxSize≥length（a1,

…,ai-1

,ai,…,an）Page04順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)存取訪問0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

長度（a1,

…,ai-1

,ai,…,an）如何求得任意元素的存儲地址？cLoc(ai)Loc(a1)Loc(ai)=Loc(a1)+(i-1)×cPage07存取時間是O(1)隨機(jī)存取2-3-2順序表的實(shí)現(xiàn)v第二章線性表順序表的實(shí)現(xiàn)——類定義InitList：表的初始化，建一個空表CreateList：建立具有n個元素的線性表DestroyList：銷毀表，釋放表所占用的存儲空間Length：求表的長度Get：在表中取序號為i

的數(shù)據(jù)元素Locate：在線性表中查找值等于x

的元素In