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

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

2、 　　(信息模型的核心)數(shù)據(jù)結(jié)構(gòu)：在程序設(shè)計(jì)領(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ù)是對事實(shí)、概念或指令的一種特殊表達(dá)形式，這種特殊的表達(dá)形式可以用人工的方式或者用自動化的裝置進(jìn)行通信、翻譯轉(zhuǎn)換或進(jìn)行加工處理?！?ISO) 例：生活中還有什么信息沒有被數(shù)字化？ 身份證，汽車牌號，電話號碼，條形代碼…… 例：《梁山好漢武藝之定量分析》 武力W=log2 X，（X為小嘍羅的數(shù)目），W∈[0,10]。 普通嘍羅的武力=

3、1；最高手的武力=10，即對付1024人。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于"記錄"。 一個數(shù)據(jù)元素由若干個數(shù)據(jù)項(xiàng)組成，相當(dāng)于"域"。 數(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)在計(jì)算機(jī)中的存儲

4、形式。 順序映象、非順序映象、索引存儲、哈希存儲 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系： 邏輯結(jié)構(gòu)：描述、理解問題，面向問題。 存儲結(jié)構(gòu)：便于機(jī)器運(yùn)算，面向機(jī)器。 程序設(shè)計(jì)中的基本問題：邏輯結(jié)構(gòu)如何轉(zhuǎn)換為存儲結(jié)構(gòu)。 2.2 有關(guān)數(shù)據(jù)類型的概念 　　數(shù)據(jù)類型：值的集合和定義在該值集上的一組操作的總稱。 　　 形式：類 　　抽象數(shù)據(jù)類型(ADT)：一個數(shù)學(xué)模型及該模型上的一組操作。 核心：是邏輯特性，而非具體表示、實(shí)現(xiàn)。 形式：模板類 課程任務(wù)： 學(xué)習(xí)ADT、實(shí)踐ADT。 如：

5、線性表類型、棧類型、隊(duì)列類型、數(shù)組類型、廣義表類型、樹類型、圖類型、查找表類型…… 第3節(jié) 算法的描述及分析 3.1 有關(guān)算法的概念 算法：特定問題求解步驟的一種描述。 1)有窮性　 2)確定性　 3)可行性 3.2 算法設(shè)計(jì)的要求 好算法： 　1)正確性　2)可讀性　3)健壯性　4)高效，低存儲 3.3 時間復(fù)雜度 事前估算：問題的規(guī)模，語言的效率，機(jī)器的速度 時間復(fù)雜度：在指定的規(guī)模下，基本操作重復(fù)執(zhí)行的次數(shù)。 n：問題的規(guī)模。 　f(n)：基本操作執(zhí)行的次數(shù)　 T(n)=O(f(n)) 漸進(jìn)時間復(fù)雜度(時間復(fù)雜度)

6、例：求兩個方陣的乘積 C＝A*B MATRIXMLT(float a[n][n],float b[n][n],float c[n][n]) { int i,j,k; for(i=0; i

7、 c[i][j]+ = a[i][k] * b[k][j]; // n*n*n } } 時間復(fù)雜度： 一般情況下，對循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，可以忽略循環(huán)體中步長加1、終值判斷、控制轉(zhuǎn)移等成分。 　 最好/最差/平均時間復(fù)雜度的示例： 例：在數(shù)組A[n]中查找值為k的元素。 for(i=0; i

8、< < 將指數(shù)時間算法改進(jìn)為多項(xiàng)式時間算法：偉大的成就。 3.5 空間復(fù)雜度 　　實(shí)現(xiàn)算法所需的輔助存儲空間的大小。 　　S(n)=O(f(n)) 按最壞情況分析。 3.6 算法舉例 例1：以下程序在數(shù)組中找出最大值和最小值 void maxmin(int A[], int n) { int max, min, i; max=min=A[0]; for(i=1; imax) max=A[i]; else if(A[i]

9、 min=%d\n", max, min); } 若數(shù)組為遞減排列，比較次數(shù)是多少？ if(A[i]>max)：n-1次 if(A[i]max)：n-1次 if(A[i]

10、;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,%d\n%",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ù) */

11、 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,%d\n%",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 power[MAX], f; int i; for(powe

12、r[0]=1,i=1;i<=n;i++) power[i]=x*power[i-1]; for(f=0,i=0;i<=n;i++) f+=coef[i]*power[i]; return(f); } 解法二：f(x)=a0+(a1+(a2+……+(an-1+anx)x)… x)x f(x)=a0+(a1+(a2+(a3+(a4+a5x)x)x)x)x float eval(float coef[],int n,float x) { int i; float f; for(f=coef[n],i=n-1;i>=0;i--) f=f*x+coef[i]; return(f); } 3.7 思考題 1、問：“s=s+i*j;”的執(zhí)行次數(shù)？時間復(fù)雜度？ for(i=1;i<=n;i++) if(5*i<=n) for(j=5*i;j<=n;j++) s=s+i*j; 2、問：“a[i][j]=x;”的執(zhí)行次數(shù)？時間復(fù)雜度？ for(i=0; i