第1章 緒論 程序=算法+數(shù)據(jù)結(jié)構(gòu) Nicklaus Wirth（1934-）Pascal之父，1984年圖靈獎(jiǎng)得主。他的學(xué)生Philipe Kahn和Anders Hejlsberg(Delphi之父)靠Turbo Pascal起家，創(chuàng)辦了Borland公司。第1節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)？許多軟件存在共性：學(xué)生信息管理、圖書(shū)信息管理、人事檔案管理數(shù)學(xué)模型：用符號(hào)、表達(dá)式組成的數(shù)學(xué)結(jié)構(gòu)，其表達(dá)的內(nèi)容與所研究對(duì)象的行為、特性基本一致。信息模型：信息處理領(lǐng)域中的數(shù)學(xué)模型。(信息模型的核心)數(shù)據(jù)結(jié)構(gòu)：在程序設(shè)計(jì)領(lǐng)域，研究操作對(duì)象及其之間的關(guān)系和操作。忽略數(shù)據(jù)的具體含義，研究信息模型的結(jié)構(gòu)特性、處理方法。第2節(jié) 概念、術(shù)語(yǔ)2.1 有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念 數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示。“數(shù)據(jù)是對(duì)事實(shí)、概念或指令的一種特殊表達(dá)形式，這種特殊的表達(dá)形式可以用人工的方式或者用自動(dòng)化的裝置進(jìn)行通信、翻譯轉(zhuǎn)換或進(jìn)行加工處理?！?ISO) 例：生活中還有什么信息沒(méi)有被數(shù)字化？ 身份證，汽車(chē)牌號(hào)，電話(huà)號(hào)碼，條形代碼 例：梁山好漢武藝之定量分析武力W=log2 X，（X為小嘍羅的數(shù)目），W0,10。普通嘍羅的武力=1；最高手的武力=10，即對(duì)付1024人。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于"記錄"。 一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成，相當(dāng)于"域"。 數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)：相互之間存在特定關(guān)系的數(shù)據(jù)集合。 四種結(jié)構(gòu)形式：集合、線性、樹(shù)形、圖(網(wǎng))狀 邏輯結(jié)構(gòu)：關(guān)系S描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。 形式定義：(D，S，P) D：數(shù)據(jù)元素的集合(數(shù)據(jù)對(duì)象) S：D上關(guān)系的有限集 P：D上的基本操作集存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。 順序映象、非順序映象、索引存儲(chǔ)、哈希存儲(chǔ)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系： 邏輯結(jié)構(gòu)：描述、理解問(wèn)題，面向問(wèn)題。 存儲(chǔ)結(jié)構(gòu)：便于機(jī)器運(yùn)算，面向機(jī)器。程序設(shè)計(jì)中的基本問(wèn)題：邏輯結(jié)構(gòu)如何轉(zhuǎn)換為存儲(chǔ)結(jié)構(gòu)。2.2 有關(guān)數(shù)據(jù)類(lèi)型的概念數(shù)據(jù)類(lèi)型：值的集合和定義在該值集上的一組操作的總稱(chēng)。 形式：類(lèi)抽象數(shù)據(jù)類(lèi)型(ADT)：一個(gè)數(shù)學(xué)模型及該模型上的一組操作。 核心：是邏輯特性，而非具體表示、實(shí)現(xiàn)。 形式：模板類(lèi)課程任務(wù)：學(xué)習(xí)ADT、實(shí)踐ADT。如：線性表類(lèi)型、棧類(lèi)型、隊(duì)列類(lèi)型、數(shù)組類(lèi)型、廣義表類(lèi)型、樹(shù)類(lèi)型、圖類(lèi)型、查找表類(lèi)型第3節(jié) 算法的描述及分析3.1 有關(guān)算法的概念 算法：特定問(wèn)題求解步驟的一種描述。 1)有窮性 2)確定性 3)可行性3.2 算法設(shè)計(jì)的要求好算法：1)正確性2)可讀性3)健壯性4)高效，低存儲(chǔ)3.3 時(shí)間復(fù)雜度 事前估算：?jiǎn)栴}的規(guī)模，語(yǔ)言的效率，機(jī)器的速度 時(shí)間復(fù)雜度：在指定的規(guī)模下，基本操作重復(fù)執(zhí)行的次數(shù)。 n：?jiǎn)栴}的規(guī)模。f(n)：基本操作執(zhí)行的次數(shù) T(n)=O(f(n) 漸進(jìn)時(shí)間復(fù)雜度(時(shí)間復(fù)雜度)例：求兩個(gè)方陣的乘積 CA*BMATRIXMLT(float ann,float bnn,float cnn) int i,j,k; for(i=0; i<n; i+) / n+1 for(j=0; j<n; j+) / n(n+1) cij=0; / n*n for(k=0; k<n; k+) / n*n*(n+1) cij+ = aik * bkj; / n*n*n 時(shí)間復(fù)雜度： 一般情況下，對(duì)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，可以忽略循環(huán)體中步長(zhǎng)加1、終值判斷、控制轉(zhuǎn)移等成分。 最好/最差/平均時(shí)間復(fù)雜度的示例：例：在數(shù)組An中查找值為k的元素。 for(i=0; i<n-1; i+) if(Ai=k) return i; 3.4 常見(jiàn)時(shí)間復(fù)雜度 按數(shù)量級(jí)遞增排序： < < < < < < < < 將指數(shù)時(shí)間算法改進(jìn)為多項(xiàng)式時(shí)間算法：偉大的成就。3.5 空間復(fù)雜度實(shí)現(xiàn)算法所需的輔助存儲(chǔ)空間的大小。S(n)=O(f(n) 按最壞情況分析。3.6 算法舉例例1：以下程序在數(shù)組中找出最大值和最小值void maxmin(int A, int n) int max, min, i; max=min=A0; for(i=1; i<n; i+) if(Ai>max) max=Ai; else if(Ai<min) min=Ai; printf("max=%d, min=%dn", max, min);若數(shù)組為遞減排列，比較次數(shù)是多少？ if(Ai>max)：n-1次 if(Ai<min): n-1次若數(shù)組為遞增排列，比較次數(shù)是多少？ if(Ai>max)：n-1次 if(Ai<min): 0次例2：n元買(mǎi)n支筆，鉛筆0.5元/支,圓珠筆2元/支,鋼筆3元/支,求算法輸出各種組合方案。解法一：窮舉法void scheme(int n) int i,j,k,count; float money; for(i=0;i<=n;i+) for(j=0;j<=n;j+) for(k=0;k<=n;k+) count=i+j+k; money=3*i+2*j+0.5*k; if(count=n && money=n) printf("%d,%d,%dn%",i,j,k); 解法二：經(jīng)分析鋼筆最多n/3支，圓珠筆最多n/2支。void scheme(int n) int i,j; float money; for(i=0;i<=n/3;i+) /* i是鋼筆的個(gè)數(shù) */ for(j=0;j<=(n-3*i)/2;j+) /* j是圓珠筆的個(gè)數(shù) */ money=3*i+2*j+0.5*(n-i-j); if(money=n) printf("%d,%d,%dn%",i,j,n-i-j); 例3：計(jì)算f(x)=a0+a1x+a2x2+.+anxn解法一：先將x的冪存于power，再分別乘以相應(yīng)系數(shù)。float eval(float coef,int n,float x) float powerMAX, f; int i; for(power0=1,i=1;i<=n;i+) poweri=x*poweri-1; for(f=0,i=0;i<=n;i+) f+=coefi*poweri; return(f);解法二：f(x)=a0+(a1+(a2+(an-1+anx)x) x)xf(x)=a0+(a1+(a2+(a3+(a4+a5x)x)x)x)xfloat eval(float coef,int n,float x) int i; float f; for(f=coefn,i=n-1;i>=0;i-) f=f*x+coefi; return(f);3.7 思考題1、問(wèn)：“s=s+i*j;”的執(zhí)行次數(shù)？時(shí)間復(fù)雜度？for(i=1;i<=n;i+) if(5*i<=n)for(j=5*i;j<=n;j+) s=s+i*j;2、問(wèn)：“aij=x;”的執(zhí)行次數(shù)？時(shí)間復(fù)雜度？for(i=0; i<n; i+) for(j=0; j<=i; j+) aij=x; 1-6