《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 第1章 緒論》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 第1章 緒論（6頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第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ù)學(xué)模型：用符號(hào)、表達(dá)式組成的數(shù)學(xué)結(jié)構(gòu)，其表達(dá)的內(nèi)容與所研究對(duì)象的行為、特性基本一致。
信息模型：信息處理領(lǐng)域中的數(shù)學(xué)模型。
2、
(信息模型的核心)數(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)
例：生活中還有什么信息沒有被數(shù)字化？
身份證，汽車牌號(hào)，電話號(hào)碼，條形代碼……
例：《梁山好漢武藝之定量分析》
武力W=log2 X，（X為小嘍羅的數(shù)目），W∈[0,10]。
普通嘍羅的武力=
3、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)形式：集合、線性、樹形、圖(網(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ǔ)
4、形式。
順序映象、非順序映象、索引存儲(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ù)類型的概念
數(shù)據(jù)類型：值的集合和定義在該值集上的一組操作的總稱。
形式：類
抽象數(shù)據(jù)類型(ADT)：一個(gè)數(shù)學(xué)模型及該模型上的一組操作。
核心：是邏輯特性，而非具體表示、實(shí)現(xiàn)。
形式：模板類
課程任務(wù)：
學(xué)習(xí)ADT、實(shí)踐ADT。
如：
5、線性表類型、棧類型、隊(duì)列類型、數(shù)組類型、廣義表類型、樹類型、圖類型、查找表類型……
第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ù)雜度)
6、例：求兩個(gè)方陣的乘積 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
}
}
時(shí)間復(fù)雜度：
一般情況下，對(duì)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，可以忽略循環(huán)體中步長(zhǎng)加1、終值判斷、控制轉(zhuǎn)移等成分。
最好/最差/平均時(shí)間復(fù)雜度的示例：
例：在數(shù)組A[n]中查找值為k的元素。
for(i=0; i
8、< <
將指數(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=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是鋼筆的個(gè)數(shù) */
11、 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,%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、問(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)：“a[i][j]=x;”的執(zhí)行次數(shù)？時(shí)間復(fù)雜度？
for(i=0; i
數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 第1章 緒論
