1、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)、算法,學(xué)習(xí)目的：了解抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn);掌握算法的特征和算法分析的方法。,重點(diǎn)難點(diǎn)：算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念與分析。,2014-2-20,1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn),1.4 算法和算法分析,教學(xué)內(nèi)容,2014-2-20,1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)(P9),抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。 本書采用類C語言，是C語言的一個(gè)核心子集。,2014-2-20,類C介紹,1. 預(yù)定義常量和類型 /函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #defi

2、ne ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;,2014-2-20,2. 數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義typedef 描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。 typedef int Status;,3.基本操作的算法使用函數(shù)描述 函數(shù)類型 函數(shù)名（參數(shù)表） /算法說明 語句序列 /函數(shù)名,2014-2-20,4. 賦值語句 a=1; a=b=c=1; a=b10?c:d;,5. 選擇語句 if（表達(dá)式

3、） 語句； if（表達(dá)式） 語句； else 語句; switch(表達(dá)式) case 值1：語句序列1；break; case 值n：語句序列n；break; default:語句序列n+1; ,2014-2-20,6. 循環(huán)語句 for, while, do-while,7.結(jié)束語句 函數(shù)結(jié)束：return 表達(dá)式； return； case結(jié)束： break； 異常結(jié)束： exit(異常代碼)；,8. 輸入輸出語句 scanf(格式串,變量）; printf(格式串,表達(dá)式);,2014-2-20,9. 注釋 / , /* */,10.基本函數(shù) max, min, abs, eof, e

4、oln,11. 邏輯運(yùn)算約定 char name20; int age; ; struct student stu1;,13. 指針 int *p; /定義了一個(gè)指向整型變量的指針變量p *p / 表示p指向的對(duì)象,struct student int num; char name20; int age; stu1, stu2; stu1.num=1111;,2014-2-20,typedef struct float realpart； float imagpart； complex；,/存儲(chǔ)結(jié)構(gòu)的定義,/基本操作的函數(shù)原型說明,void Assign( complex i=n; +i)fo

5、r (j=1; j=n; +j) ci,j = 0;for (k=1; k=n; +k)ci,j += ai,k*bk,j;乘法運(yùn)算是矩陣相乘問題的基本操作，整個(gè)算法 的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)n3成正比。,2012-8-20,一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作： T（n）=O（f(n)） 它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。,2012-8-20,算法的時(shí)間復(fù)雜度計(jì)算,語句頻度：語句重復(fù)執(zhí)行的次數(shù) 例1： +x;s=0; 例2： for(i=1;

6、i=n;+i) +x;s+=x; 例3： for(j=1;j=n;+j) for(k=1;k=n;+=k) +x;s+=x;,含基本操作“x增1”的語句的頻度分別為1, n, n2 則這3個(gè)程序段的時(shí)間復(fù)雜度分別為O(1),O(n),O(n2),分別稱為常量階、線性階、平方階。 我們總是考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長（最壞情況下估算算法執(zhí)行時(shí)間的一個(gè)上界） 一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。與待處理數(shù)據(jù)的初態(tài)無關(guān)。,2012-8-20,例4 for( i=1; in; i+) y=y+1;

7、for( j=0; j=2n; j+) x+; ,頻度,n-1,(n-1)(2n+1),T(n)=n-1+(n-1)(2n+1)=O(n2),2012-8-20,例5 i=1; while ( i=n ) i=i*2;,頻度,1,?,設(shè)為x，則有：2x=n,即x=log2n,所以i=i*2的頻度為log2n T(n)=O(log2n),2012-8-20,例6 兩個(gè) n n 的矩陣相乘。 void Mult_matrix( int c, int a, int b， int n)/ a、b 和 c 均為 n 階方陣，且 c 是 a 和 b 的乘積for (i=1; i=n; +i)for (j=

8、1; j=n; +j) ci,j = 0;for (k=1; k=n; +k)ci,j += ai,k*bk,j;/ Mult_matrix 算法的時(shí)間復(fù)雜度為T(n)=O (n3),2012-8-20,一個(gè)算法的時(shí)間復(fù)雜度還可以具體分為最好、最差（最壞）、平均三種情況討論。 最好情況下最容易求出，但沒有多大實(shí)際意義 最差情況下也容易求出，而且這是估計(jì)該算法執(zhí)行時(shí)間的一個(gè)上界 平均情況下最難計(jì)算：在很多情況下地輸入數(shù)據(jù)集出現(xiàn)的概率難以確定。 一般，算法的時(shí)間復(fù)雜度如無特別說明，則指最壞情況下的時(shí)間復(fù)雜度。,2012-8-20,4、算法的存儲(chǔ)空間需求,算法的空間復(fù)雜度定義為: S(n) = O(

9、f(n) 表示隨著問題規(guī)模 n 的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與 f(n) 的增長率相同。 算法的存儲(chǔ)量包括: 1)輸入數(shù)據(jù)所占空間 2)程序本身所占空間 3)輔助變量所占空間,2012-8-20,若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。 若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。,2012-8-20,課堂總結(jié)主要內(nèi)容：了解抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn);掌握算法的特征和算法分析的方法。重點(diǎn)難點(diǎn)：算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念與分析。,2012-8-20,作業(yè)：,指出下列程序段的時(shí)間復(fù)雜度（寫出主要語句的頻度） 1. int sum1( int n ) int p=1 , sum = 0 , i; for( i=1; i=n; i+) p*= i ; sum+= p ; retur