1、數(shù)據(jù)結(jié)構(gòu)和算法（2學(xué)時(shí)）,數(shù)據(jù)結(jié)構(gòu)和算法的基本概念 流程圖和NS圖 1) 讓同學(xué)們知道程序設(shè)計(jì)實(shí)際上應(yīng)該是數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)： 首先確定數(shù)據(jù)的表示方式(結(jié)構(gòu)），然后確定處理步驟（算法）； 數(shù)據(jù)的結(jié)構(gòu)決定了程序的結(jié)構(gòu)，算法是離不開數(shù)據(jù)結(jié)構(gòu)的；同時(shí)，通過(guò)對(duì)不同算法效率分析，讓大家知道算法設(shè)計(jì)的重要意義。 2）學(xué)會(huì)用流程圖和NS圖來(lái)描述算法。,數(shù)據(jù)結(jié)構(gòu)及算法（2學(xué)時(shí)）,數(shù)據(jù)結(jié)構(gòu)及算法基本概念 流程圖和NS圖,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念 1. 數(shù)據(jù)表示決定程序結(jié)構(gòu),編寫程序設(shè)計(jì)來(lái)求解實(shí)際問(wèn)題時(shí)，首先必然要將“問(wèn)題域?qū)ο笞優(yōu)榍蠼庥驅(qū)ο蟆薄?數(shù)據(jù)的表示方式確定了您程序的結(jié)構(gòu)和處理步驟，例如：,編寫一個(gè)

2、從一組數(shù)中找出最大數(shù)的程序。,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,1.數(shù)據(jù)表示決定程序結(jié)構(gòu),先以3個(gè)數(shù)為例：,有的同學(xué)想，高級(jí)語(yǔ)言中提供了關(guān)系運(yùn)算和邏輯運(yùn)算（如并且、或者運(yùn)算），能否這樣做：,3個(gè)數(shù)我們用a、b、c表示，最大數(shù)為max: if(a=b,這樣做行嗎？,隨著數(shù)的增加，不僅程序規(guī)模太大！而且對(duì)有些應(yīng)用來(lái)說(shuō)，沒(méi)法確定處理步驟（例如排序）。,或者： max=a; if(b=max) max=b;,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,要解決這個(gè)問(wèn)題，我們首先要考慮：不只要表示單個(gè)的數(shù)，而且要表示數(shù)之間的關(guān)系。從邏輯上看，我們可以描述如下：。,1.數(shù)據(jù)表示決定程序結(jié)構(gòu),ai,1 i n;,在這種描述下，

3、a1是第1個(gè)元素，an是最后一個(gè)元素，除第一和最后元素外， ai的前一個(gè)元素為ai-1，后一個(gè)元素為ai+1。在該結(jié)構(gòu)下處理步驟描述如下：,假設(shè)第1個(gè)數(shù)為最大數(shù)max； i的初始值為2，重復(fù)以下步驟N-1次： 如ai大于max，則max=ai,i=i+1;,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,再看一個(gè)例子：確定某門課程各個(gè)分?jǐn)?shù)的人數(shù)。,1.數(shù)據(jù)表示決定程序結(jié)構(gòu),牢記 ：數(shù)據(jù)的表示方式確定了您程序的結(jié)構(gòu)和處理步驟！,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念 2. 數(shù)據(jù)結(jié)構(gòu)的簡(jiǎn)單定義：,數(shù)據(jù)間是存在一定關(guān)系的。在解決實(shí)際問(wèn)題時(shí)，不光要考慮單個(gè)數(shù)據(jù)本身，還需要考慮數(shù)據(jù)間的關(guān)系。,為了表示現(xiàn)實(shí)世界中各種復(fù)雜的關(guān)系，計(jì)算

4、機(jī)科學(xué)家們抽象出了四種最基本的關(guān)系，現(xiàn)實(shí)世界中各種復(fù)雜的關(guān)系可由他們或他們之間的組合來(lái)表示。,數(shù)據(jù)結(jié)構(gòu)是指有關(guān)系的數(shù)據(jù)的集合。,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念 2. 常見(jiàn)的處理對(duì)象之間的關(guān)系,處理對(duì)象之間的關(guān)系通?？梢杂孟旅娴倪壿嫿Y(jié)構(gòu)進(jìn)行描述：,一. 數(shù)據(jù)結(jié)構(gòu)基本概念,例如：人機(jī)對(duì)弈。,在人機(jī)對(duì)弈問(wèn)題中，計(jì)算機(jī)處理的對(duì)象主要是棋的“格局”，根據(jù)可能的格局選擇走法。如下圖：,格局之間是有關(guān)系的，但其關(guān)系通常不是線性的，因?yàn)閺囊粋€(gè)格局可以派生出許多格局，如下圖：,一. 數(shù)據(jù)結(jié)構(gòu)基本概念,又例如：交通查詢系統(tǒng)。,下面是某地區(qū)交通示意圖。我們要開發(fā)一個(gè)交通查詢系統(tǒng)，能回答從甲地到乙地如何費(fèi)用最省、如何中

5、轉(zhuǎn)車次最少等問(wèn)題。,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,它是指解決某一類特定類型問(wèn)題的一系列步驟。,3.1算法的基本概念,3. 算法,例如：求2個(gè)整數(shù)的最大公約數(shù)。,我們拿變量M、N來(lái)表示這兩正整數(shù)。采用著名的歐幾里德輾轉(zhuǎn)相除法來(lái)解決該問(wèn)題，步驟如下： 1）M除以N，得到余數(shù)R; 2）判斷 R0，正確則 N 即為“最大公約數(shù)”，否則下一步； 3) 將 N 賦值給 M，將 R 賦值給 N，重做第一步。,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,3.2算法的5個(gè)特性,3. 算法,能行性；確定性；有0或多個(gè)輸出；有1或多個(gè)輸出；有窮性。,一. 數(shù)據(jù)結(jié)構(gòu)及算法基本概念,3. 算法,一個(gè)算法的好壞，正確是基本前提，同時(shí)主

6、要要考慮其所花的時(shí)間和所占的空間，即時(shí)間復(fù)雜度和空間復(fù)雜度。,3.3算法效率,在上面求最大公約數(shù)的例子中，大家考慮還有哪些方法，時(shí)間復(fù)雜度如何？,霍爾排序與插入排序運(yùn)行時(shí)間演示比較。,貨郎擔(dān)問(wèn)題簡(jiǎn)介。,空間復(fù)雜度的問(wèn)題，大家考慮一下如何將數(shù)組倒排。,向量旋轉(zhuǎn)問(wèn)題算法比較。,二.流程圖和NS圖,二. 線性表及幾個(gè)簡(jiǎn)單算法 1. 冒泡排序,1.2 過(guò)程演示（5，4，2，3，1由小到大排序）,在剩余的4個(gè)數(shù)中進(jìn)行第2趟,二. 線性表及幾個(gè)簡(jiǎn)單算法 1. 冒泡排序,1.2 過(guò)程演示（5，4，2，3，1由小到大排序）,在這種方法中，第i趟是將從1到的n-i+1依次比較，結(jié)果是將這n-i+1個(gè)中最大“沉入

7、”在n-i+1的位置上；,我們還可以從后面向前面比較（向上“冒泡”），如：,二. 線性表及幾個(gè)簡(jiǎn)單算法 1. 冒泡排序,1.3 “冒泡”過(guò)程演示（小的向前“冒”）,其余各趟略,實(shí)際上，我們可以改進(jìn)上面算法：一旦發(fā)現(xiàn)在某趟中，沒(méi)有發(fā)生交換，則表明已經(jīng)排序好。,二. 線性表及幾個(gè)簡(jiǎn)單算法 1. 冒泡排序,1.4 算法分析,最好情況下比較n-1此，且不需移動(dòng)位置；最壞情況下（逆序），比較和移動(dòng)n(n-1)/2次；,2. 選擇排序,第1步， 從n個(gè)數(shù)中選擇最?。ù螅┑臄?shù)作為第1 個(gè)數(shù)；,第i (1in)從n-i+1個(gè)數(shù)中選擇最?。ù螅┑臄?shù)作為第i 個(gè)數(shù)；當(dāng)i從1變化到n-1后，排序完成。,第2步， 從

8、n-1個(gè)數(shù)中選擇最?。ù螅┑臄?shù)作為第2個(gè)數(shù)；,二. 線性表及幾個(gè)簡(jiǎn)單算法,2. 選擇排序,2.1 過(guò)程演示（5，4，2，3，1由小到大排序）,在剩余的4個(gè)數(shù)中進(jìn)行第2趟,實(shí)際上，我們可以改進(jìn)上面算法：不需要每次比較都交換，只需要找到最小數(shù)的位置后，才交換。,二. 線性表及幾個(gè)簡(jiǎn)單算法,2. 選擇排序,2.2 算法分析,根據(jù)本算法的思想，該主要運(yùn)算是比較2個(gè)數(shù)的大小，每趟比較完成后需要將2個(gè)數(shù)互換。請(qǐng)考慮該算法比較的次數(shù)和互換的次數(shù)。,比較次數(shù)：(n-1)+(n-2)+1=n(n-1)/2=O(n2)； 互換次數(shù)：最小為0，最大為n-1;運(yùn)算3(n-1)次；,所以本算法的優(yōu)化思想一種是考慮如何減

9、少比較次數(shù)。由于第一次比較的次數(shù)不可能減少，那么前面比較的結(jié)果能否用于后面的比較呢？答案是肯定的，請(qǐng)大家考慮一下8個(gè)隊(duì)比賽決出前3名至少需要多少場(chǎng)比賽？,二. 線性表及幾個(gè)簡(jiǎn)單算法,2. 選擇排序,2.3 算法優(yōu)化(參考）,下面我們來(lái)將9，38，26，17，8，85排序。,這實(shí)際上是在一些書中叫做錦標(biāo)賽排序的算法，它除第1此比較需n-1次外，其它每次比較都只需要log2n+1次；所以其時(shí)間復(fù)雜度為O(n log2n),二. 線性表及幾個(gè)簡(jiǎn)單算法,3. 順序查找,3.1 基本思路,從第1個(gè)數(shù)開始，依次與 ai (1in)比較，如相等，則成功結(jié)束；否則表示查找失敗。,二. 線性表及幾個(gè)簡(jiǎn)單算法,4. 折半查找,4.1 基本思路,針對(duì)已排好順序的表進(jìn)行查找。使用2個(gè)值low和high來(lái)表示要查找值所在的區(qū)間low,hight,另外定義區(qū)間的中間位置mid=low+hight/2;low的初始值分別為1和n； 1. 首先將查找值與中間位置值進(jìn)行比較，若相等則成功，轉(zhuǎn)結(jié)束； 2. 否則如其大于中間值，則將 low=mid+1,hight不變; mid=low+hight/2轉(zhuǎn)步驟1； 3. 如其小于中間值，則將 hight=mid-1,low不變; mid=low+hight/2,轉(zhuǎn)步驟1； 4.