《數(shù)據(jù)結構C語言版 第1章 緒論》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構C語言版 第1章 緒論（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第1章 緒論 程序=算法+數(shù)據(jù)結構 Nicklaus Wirth（1934-）Pascal之父，1984年圖靈獎得主。他的學生Philipe Kahn和Anders Hejlsberg(Delphi之父)靠Turbo Pascal起家，創(chuàng)辦了Borland公司。第1節(jié) 什么是數(shù)據(jù)結構？許多軟件存在共性：學生信息管理、圖書信息管理、人事檔案管理數(shù)學模型：用符號、表達式組成的數(shù)學結構，其表達的內(nèi)容與所研究對象的行為、特性基本一致。信息模型：信息處理領域中的數(shù)學模型。(信息模型的核心)數(shù)據(jù)結構：在程序設計領域，研究操作對象及其之間的關系和操作。忽略數(shù)據(jù)的具體含義，研究信息模型的結構特性、處理方法。第

2、2節(jié) 概念、術語2.1 有關數(shù)據(jù)結構的概念 數(shù)據(jù)：對客觀事物的符號表示?！皵?shù)據(jù)是對事實、概念或指令的一種特殊表達形式，這種特殊的表達形式可以用人工的方式或者用自動化的裝置進行通信、翻譯轉換或進行加工處理?！?ISO) 例：生活中還有什么信息沒有被數(shù)字化？ 身份證，汽車牌號，電話號碼，條形代碼 例：梁山好漢武藝之定量分析武力W=log2 X，（X為小嘍羅的數(shù)目），W0,10。普通嘍羅的武力=1；最高手的武力=10，即對付1024人。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當于記錄。 一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成，相當于域。 數(shù)據(jù)對象：性質相同的數(shù)據(jù)元素的集合。 數(shù)據(jù)結構：相互之間存在特定關系的數(shù)據(jù)集合。

3、 四種結構形式：集合、線性、樹形、圖(網(wǎng))狀 邏輯結構：關系S描述的是數(shù)據(jù)元素之間的邏輯關系。 形式定義：(D，S，P) D：數(shù)據(jù)元素的集合(數(shù)據(jù)對象) S：D上關系的有限集 P：D上的基本操作集存儲結構：數(shù)據(jù)結構在計算機中的存儲形式。 順序映象、非順序映象、索引存儲、哈希存儲邏輯結構與存儲結構的關系： 邏輯結構：描述、理解問題，面向問題。 存儲結構：便于機器運算，面向機器。程序設計中的基本問題：邏輯結構如何轉換為存儲結構。2.2 有關數(shù)據(jù)類型的概念數(shù)據(jù)類型：值的集合和定義在該值集上的一組操作的總稱。 形式：類抽象數(shù)據(jù)類型(ADT)：一個數(shù)學模型及該模型上的一組操作。 核心：是邏輯特性，而非具

4、體表示、實現(xiàn)。 形式：模板類課程任務：學習ADT、實踐ADT。如：線性表類型、棧類型、隊列類型、數(shù)組類型、廣義表類型、樹類型、圖類型、查找表類型第3節(jié) 算法的描述及分析3.1 有關算法的概念 算法：特定問題求解步驟的一種描述。 1)有窮性 2)確定性 3)可行性3.2 算法設計的要求好算法：1)正確性2)可讀性3)健壯性4)高效，低存儲3.3 時間復雜度 事前估算：問題的規(guī)模，語言的效率，機器的速度 時間復雜度：在指定的規(guī)模下，基本操作重復執(zhí)行的次數(shù)。 n：問題的規(guī)模。f(n)：基本操作執(zhí)行的次數(shù) T(n)=O(f(n) 漸進時間復雜度(時間復雜度)例：求兩個方陣的乘積 CA*BMATRIXM

5、LT(float ann,float bnn,float cnn) int i,j,k; for(i=0; in; i+) / n+1 for(j=0; jn; j+) / n(n+1) cij=0; / n*n for(k=0; kn; k+) / n*n*(n+1) cij+ = aik * bkj; / n*n*n 時間復雜度： 一般情況下，對循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，可以忽略循環(huán)體中步長加1、終值判斷、控制轉移等成分。 最好/最差/平均時間復雜度的示例：例：在數(shù)組An中查找值為k的元素。 for(i=0; in-1; i+) if(Ai=k) return i; 3.4

6、常見時間復雜度 按數(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; imax) max=Ai; else if(Aimax)：n-1次 if(Aimax)：n-1次 if(Aimin): 0次例2：n元買n支筆，鉛筆0.5元/支,圓珠筆2元/支,鋼筆3元/支,求算法輸出各種組合方案。解法一：窮舉法void

7、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+) /*

8、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=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; in; i+) for(j=0; j=i; j+) aij=x; 1-6