1、編寫函數(shù)計算： 1-2+3-4+5-6+7+n(n很大）,例 子,數(shù)據(jù)結(jié)構(gòu),1,for(i=1;i=n;i+) s=s+flag*i； flag=-flag; ,while(j 0?i+;i-; j+; ,if (0= =n%2) return -n/2; else return -n/2+n;,F1F2F3,數(shù)據(jù)結(jié)構(gòu),2,有乘法 執(zhí)行效率低,乘法變?yōu)榧臃?執(zhí)行效率提高,沒有循環(huán)運算 算法簡潔 效率大幅提高 n很大更明顯,算法1算法2算法3,數(shù)據(jù)結(jié)構(gòu),3,數(shù)據(jù)的類型,算法,數(shù)據(jù)類型和算法之間的關(guān)聯(lián),程序設(shè)計時考慮的因素,數(shù)據(jù)結(jié)構(gòu),4,學(xué)習(xí)常用的算法；,訓(xùn)練復(fù)雜程序設(shè)計,課 程 目 的,抽象邏輯

2、結(jié)構(gòu) 選擇存儲結(jié)構(gòu) 設(shè)計算法,算法的時間分析和空間分析技術(shù),5,Objective,描述課程要求 說明課程目的 學(xué)習(xí)什么是數(shù)據(jù)結(jié)構(gòu) 學(xué)會用抽象數(shù)據(jù)類型表示數(shù)據(jù)結(jié)構(gòu) 學(xué)會時間復(fù)雜度和空間復(fù)雜度分析的技巧,數(shù)據(jù)結(jié)構(gòu)課程的重要性,前驅(qū)課程,程序設(shè)計能力 提高,專業(yè)基礎(chǔ)課,考研,第一章 概論,內(nèi)容,數(shù)據(jù)結(jié)構(gòu)討論的范疇 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語 抽象數(shù)據(jù)類型的表示與實現(xiàn) 算法與算法分析,數(shù)據(jù)結(jié)構(gòu)討論的范疇,數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計的關(guān)系 Niklaus Wirth： Algorithms + Data Structures = Programs 數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)描述 邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 算法：處理問題的策

3、略（對數(shù)據(jù)運算的描述) 程序：為計算機處理問題編制的一組指令集,解決問題的步驟,任務(wù),解,求解,輸入,輸出,抽象：過程抽象數(shù)據(jù)抽象,數(shù)據(jù)結(jié)構(gòu)：邏輯結(jié)構(gòu)物理結(jié)構(gòu),算法：解決問題的步驟,程序：計算機實現(xiàn)算法,數(shù)據(jù)的結(jié)構(gòu)類型,有什么類型的數(shù)據(jù)結(jié)構(gòu)？,數(shù)值,非數(shù)值,考生錄取信息系統(tǒng),考生信息表,姓名索引表,專業(yè)索引表,成績索引表,考生錄取信息系統(tǒng),計算機處理的對象：表 元素間的關(guān)系：線性關(guān)系 施加于對象上的操作 查詢、插入、刪除等 算法：如何進行各種查詢 模型：各種表格,棋盤格局,棋盤格局,計算機處理的對象：樹型結(jié)構(gòu) 元素間的關(guān)系： 層次關(guān)系，一對多的關(guān)系 施加于對象上的操作 查詢、插入、刪除等 算法

4、：博弈的規(guī)則和策略 模型：棋盤、棋子如何表示,快速送達(dá)疫苗,已知有臨近的五個村子發(fā)生了疫情，我們要用汽車快速地將疫苗送達(dá)到5個村子。目標(biāo)是尋找一條耗時最少的路線。,耗時矩陣,窮舉法,貪心算法,問題被抽象成了圖結(jié)構(gòu),快速送達(dá)疫苗,計算機處理的對象：圖 元素間的關(guān)系： 圖形或網(wǎng)狀關(guān)系，多對多的關(guān)系 施加于對象上的操作 查詢、插入、刪除等 算法：如何求距離、最短路徑等 模型：圖或者網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),集合結(jié)構(gòu)：,線性結(jié)構(gòu)：,數(shù)據(jù)結(jié)構(gòu),樹形結(jié)構(gòu)：,圖形結(jié)構(gòu)：,基本概念和術(shù)語,數(shù)據(jù)(Data)：信息的載體 描述客觀事物的數(shù)、字符等 計算機程序識別和處理的符號的集合。 數(shù)據(jù)類型 數(shù)值型數(shù)據(jù)： 整數(shù)、實數(shù)、字符

5、串 非數(shù)值型數(shù)據(jù)： 文字、表、圖像、圖形、聲音、視頻等,基本概念和術(shù)語,數(shù)據(jù)元素(Data Element)： 數(shù)據(jù)的基本單位，完整地描述一個對象 棋盤中的一個格局（狀態(tài)），一個考生記錄，一個頂點等； 數(shù)據(jù)項(Data Item)： 組成數(shù)據(jù)元素的有特定意義的最小單位 考生信息中的學(xué)號、姓名。 數(shù)據(jù)元素是數(shù)據(jù)項的集合。 數(shù)據(jù)對象(Data Object)： 具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。 整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, 學(xué)生數(shù)據(jù)對象,基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。,基本概念和術(shù)語,元素集合：D=a1, a

6、2, a3, a4, a5, a6 關(guān)系集合： R=, R1= , R2=, R3= , (D,R1) (D,R2) (D,R3),基本概念和術(shù)語,形式定義：數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structures （D，R） D(Data)是數(shù)據(jù)元素的集合 R(Relation)是D上關(guān)系的集合。,基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。 數(shù)據(jù)的邏輯結(jié)構(gòu)： 集合結(jié)構(gòu)：同屬于一個集合，別無其它關(guān)系 線性結(jié)構(gòu)：一對一的關(guān)系 樹形結(jié)構(gòu)：一對多的關(guān)系， 圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對多的關(guān)系,基本概念和術(shù)語,邏輯結(jié)構(gòu)（定義中的關(guān)系）： 數(shù)據(jù)元素之間的邏輯關(guān)系 存儲結(jié)構(gòu)(物理結(jié)構(gòu))： 數(shù)據(jù)結(jié)構(gòu)在計算機中

7、的表示 邏輯結(jié)構(gòu)在存儲器中的映像,邏輯結(jié)構(gòu)中的關(guān)系的表示,順序存儲（順序映像） 借助元素的存儲位置表示數(shù)據(jù)元素之間的關(guān)系 鏈?zhǔn)酱鎯Γǚ琼樞蛴诚瘢?借助指示元素存儲地址的指針（Pointer）表示數(shù)據(jù)元素之間的邏輯關(guān)系。,抽象數(shù)據(jù)類型（ADT）,抽象數(shù)據(jù)類型: ADT（Abstract Data Type） 一個數(shù)學(xué)模型及定義在該模型上的一組操作,抽象數(shù)據(jù)類型,查找 登錄 刪除 修改,符 號 表,抽象數(shù)據(jù)類型表示方法,三元組（D，R，P） D：數(shù)據(jù)對象，具有相同特性的數(shù)據(jù)元素的集合 R：D上的關(guān)系的集合 P：對D的基本操作集 定義格式 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象定義 可用偽代碼描

8、述 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系定義 可用偽代碼描述 基本操作：基本操作定義 ADT 抽象數(shù)據(jù)類型名,偽代碼是一種用于描述算法的語言，介于高級程序設(shè)計語言和自然語言之間。,抽象數(shù)據(jù)類型例子,元素集合：D=a1, a2, a3, a4, a5, a6 R2=, P1=加法、減法 P2=乘法、除法 (D,R2) (D,R2,P1) (D,R2,P2),基本操作的定義格式,基本操作名（參數(shù)表） 初始條件： 操作結(jié)果： Add(int a, b) 初始條件：已知a和b 操作結(jié)果：返回a與b的和,抽象數(shù)據(jù)類型（ADT）,ADT的描述方法： 類C語言：偽代碼和C語言組合 偽代碼：描述算法的語言，介于高級程序設(shè)計語言

9、和自然語言之間。 交換賦值用：A B,算法與算法分析,算法： 對特定問題求解步驟的一種描述 指令的有限序列 每一條指令表示一個或多個操作 算法特性： 有窮性：執(zhí)行有限步，每步有限的時間 確定性：相同輸入有相同輸出，無二義性 可行性：所有操作可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的 輸入：具有零個或多個輸入 輸出：具有一個或多個輸出,算法設(shè)計的原則,算法設(shè)計的目標(biāo)： 正確性：滿足預(yù)先規(guī)定的功能和性能要求 可讀性：清晰簡潔、層次分明、 易讀易懂，注釋； 健壯性：當(dāng)輸入不合法的數(shù)據(jù)時，算法應(yīng)能進行適當(dāng)處理，不至于引起嚴(yán)重后果； 高效性：有效使用存儲空間和有較高的時間效率。 與問題的規(guī)模有關(guān)： 時

10、間復(fù)雜度 空間復(fù)雜度,算法效率的衡量方法及其準(zhǔn)則,衡量算法效率的方法主要有兩大類： 事后統(tǒng)計： 利用計算機的時鐘進行算法執(zhí)行時間的統(tǒng)計 在算法中的插裝時間函數(shù)time ( )測定算法完成某一功能所花費時間。 缺陷： 必須把算法轉(zhuǎn)變成為程序執(zhí)行， 依賴于硬件和軟件環(huán)境，掩蓋算法本身的優(yōu)劣；,算法效率的衡量方法及其準(zhǔn)則,衡量算法效率的方法主要有兩大類： 事前分析估算： 需要考慮用程序運行的時間主要取決的因素 算法選用的策略； 問題的規(guī)模； 使用語言：級別越高，效率越低； 編譯程序所產(chǎn)生的機器代碼的質(zhì)量； 機器執(zhí)行指令的速度；,后三條與算法設(shè)計無關(guān),算法效率的衡量方法及其準(zhǔn)則,一個特定算法的“運行工

11、作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量 n 來表示），或者說：它是問題規(guī)模的函數(shù)。,時間復(fù)雜度,隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率T(n)和函數(shù)f(n)的增長率相同，則可記作為： T(n)=O(f(n) 稱T(n)為算法的（漸近）時間復(fù)雜度,算法 程序的控制結(jié)構(gòu)（順序，分支，循環(huán)） 原操作（必須的操作）構(gòu)成,估計算法的時間復(fù)雜度,算法的執(zhí)行時間 原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時間 執(zhí)行時間 和 原操作執(zhí)行次數(shù)之和成正比 估算： 從算法中選取一種對于算法最基本的原操作 以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運行時間的衡量準(zhǔn)則 語句頻率：重復(fù)執(zhí)行的次數(shù),或者說算法

12、中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),估計算法的時間復(fù)雜度,+x; s=0;,時間復(fù)雜度,for(j=1;j=n;+j) +x;s+=x;,語句的頻度為1時間復(fù)雜度O(1) 常量階,語句的頻度為n時間復(fù)雜度為O(n)線性階,時間復(fù)雜度,for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,語句頻度為nn，時間復(fù)雜度為O(n2)。 平方階,時間復(fù)雜度,for(j=1;j=n;+j) for(k=1;k=j;+k) +x;s+=x; 語句頻度：,為近似于n2，時間復(fù)雜度為O(n2)。,時間復(fù)雜度只考慮量級就可以了。,時間復(fù)雜度,s=0; for(j=1

13、;j=n;j*=2) for(k=1;k=n;+k) s+; 語句頻度為：,時間復(fù)雜度為：O(nlog2n),時間復(fù)雜度,例：矩陣加法：n n for( i = 0; i n; i+) for( j = 0; j n; j+) cij = aij + bij; ,語句的頻度：重復(fù)執(zhí)行的次數(shù)：n*n; T( n ) = O ( n 2) 即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級；,常見的時間復(fù)雜度,c log2n n nlog2n n2 n3 2n 3n n!,算法的空間復(fù)雜度,算法的空間復(fù)雜度： 算法在執(zhí)行時所占用的存儲空間 算法的空間復(fù)雜度表示： S(n)=O(g(n) 表示隨著

14、問題規(guī)模 n 的增大，算法運行所需存儲量的增長率與函數(shù)g(n)的增長率相同。,算法的空間復(fù)雜度,算法的存儲量 程序本身所占的存儲空間； 輸入數(shù)據(jù)所占的空間 （變量） 輔助變量所占空間 （系統(tǒng)堆棧） 固定部分vs.可變部分,空間復(fù)雜度度量,固定部分程序指令代碼的空間，常數(shù)、簡單變量 可變部分 與實例特性有關(guān)的成分變量所占空間 引用變量所占空間 遞歸棧所用空間 通過malloc等命令動態(tài)使用的空間,算法的空間復(fù)雜度,輸入數(shù)據(jù)所占空間只取決于問題本身和算法無關(guān) 只需分析輔助變量所占的額外空間即可。 所需額外空間相對于輸入數(shù)據(jù)量來說只是一個常數(shù) 算法為“原地工作”記 O(1)； 算法所需的存儲量與特定的輸入有關(guān) 需要分析時間復(fù)雜度,作業(yè),第一章 一 、二題,選做題,我們要做一個城市公交車站點查詢系統(tǒng)。為簡單起見，假設(shè)各