數(shù)據(jù)結(jié)構(gòu)C語言版 第1章 緒論

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