數(shù)據(jù)結(jié)構 第一章概論

數(shù)據(jù)結(jié)構

---------------------------------------------數(shù)據(jù)結(jié)構第一章概論第一章緒論1.1數(shù)據(jù)結(jié)構研究什么？

將現(xiàn)實世界中的數(shù)據(jù)描述及關系表示出來，并存儲到計算機內(nèi)，供用戶程序操作?，F(xiàn)實世界中的數(shù)據(jù)描述及關系：

4種：離散型，線性結(jié)構，層次結(jié)構，網(wǎng)狀結(jié)構。離散數(shù)學：研究離散型。數(shù)據(jù)結(jié)構：研究線性結(jié)構，層次結(jié)構和網(wǎng)狀結(jié)構。線性結(jié)構：線性表表示。層次結(jié)構：樹形結(jié)構表示。網(wǎng)狀結(jié)構：圖結(jié)構表示。數(shù)據(jù)結(jié)構研究：數(shù)據(jù)邏輯結(jié)構，存儲結(jié)構及施加其上的運算。

數(shù)據(jù)結(jié)構第一章概論例1L=(20,-5,66,15,44)是一個線性表例2一張登記表DL

序號姓名性別年齡

1李剛男25記錄12王霞女29記錄23劉大海男40記錄34李愛林男44記錄4其中：姓名、性別、年齡是數(shù)據(jù)項(item)、數(shù)據(jù)域(field)；

(姓名，性別，年齡)是記錄(record),C語言將"記錄"(record)定義為”結(jié)構”(struct)；登記表也是一個線性表。

數(shù)據(jù)結(jié)構第一章概論例3家族中父子關系是一種層次結(jié)構--樹

T

張一張三張二一張三一張三小張三大

張二張四

層次結(jié)構：部門之間的隸屬關系：學校->系->科->班領導和被領導之間領導關系：主席->部長->司長->處長->科長數(shù)據(jù)結(jié)構第一章概論例4無向圖G

ABDCEFG其中：A、B、C等是頂點(vertex),

圖中任意兩個頂點之間都可能有關系。網(wǎng)絡結(jié)構：電網(wǎng)，電信網(wǎng)，計算機通信網(wǎng)等。數(shù)據(jù)結(jié)構第一章概論

1.基本數(shù)據(jù)結(jié)構的定義、特性、運算與算法

1.1線性結(jié)構：線性表；棧,隊列,雙隊列；數(shù)組,串。

1.2非線性結(jié)構：樹,二叉樹；圖,網(wǎng)絡。

2.數(shù)據(jù)結(jié)構的存儲結(jié)構與實現(xiàn)選擇存儲結(jié)構,設計算法

3.查找算法：順序,折半,分塊,哈希,二叉排序樹等

4.排序算法：內(nèi)部排序,外部排序

5.文件

6.基本應用與綜合應用

要求具備的知識：

c語言及程序設計，具有一定的程序設計能力。

本課程的內(nèi)容和任務數(shù)據(jù)結(jié)構第一章概論1.2基本概念和術語1.數(shù)據(jù)（data)----

所有能輸入到計算機中并被計算機程序加工、處理的符號的總稱。如：整數(shù)、實數(shù)、字符、聲音、圖象、圖形等。2.數(shù)據(jù)元素(dataelement)---

數(shù)據(jù)的基本單位。（元素、記錄、結(jié)點、頂點）在計算機程序中通常作為一個整體進行考慮和處理。3.數(shù)據(jù)項(dataitem)----

是數(shù)據(jù)的不可分割的最小單位。如：姓名、年齡等一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。如:(姓名、年齡)數(shù)據(jù)結(jié)構第一章概論4.數(shù)據(jù)對象(dataobject)——

由性質(zhì)相同(類型相同)的數(shù)據(jù)元素組成的集合。

數(shù)據(jù)對象是數(shù)據(jù)的一個子集。例1由4個整數(shù)組成的數(shù)據(jù)對象

D1={20,-30,88,45}

例2由正整數(shù)組成的數(shù)據(jù)對象

D2={1,2,3,...}

例3由26個字母組成的數(shù)據(jù)對象

D3={A,B,C,...,Z}

其中：D1，D3是有窮集，D2是無窮集。5.抽象數(shù)據(jù)對象

ElemSet={某種同類型的數(shù)據(jù)元素}數(shù)據(jù)結(jié)構第一章概論6.數(shù)據(jù)結(jié)構(datastructure)----

數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。內(nèi)容包括：數(shù)據(jù)邏輯結(jié)構、數(shù)據(jù)存儲結(jié)構和數(shù)據(jù)運算。

數(shù)據(jù)邏輯結(jié)構：數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)存儲結(jié)構：數(shù)據(jù)元素及其關系在存儲器中的存儲表示。數(shù)據(jù)運算：定義在數(shù)據(jù)邏輯結(jié)構上的操作。如：查詢，插入，刪除和修改，排序等。數(shù)據(jù)邏輯結(jié)構有兩大類：

線性結(jié)構：特征：若結(jié)構是非空集，則僅有一個開始結(jié)點和一個終止結(jié)點；其他結(jié)點都只有一個前趨結(jié)點和一個后繼結(jié)點。

非線性結(jié)構：特征：一個結(jié)點有多個前趨結(jié)點和后繼結(jié)點。

數(shù)據(jù)存儲結(jié)構有4種：順序存儲結(jié)構，鏈接存儲結(jié)構，索引存儲結(jié)構和散列存儲結(jié)構。

數(shù)據(jù)結(jié)構第一章概論數(shù)據(jù)邏輯結(jié)構和存儲結(jié)構與運算三者之間有緊密的關系：如：給定一種數(shù)據(jù)的邏輯結(jié)構，可采取順序存儲結(jié)構或鏈接存儲結(jié)構進行存儲；按定義的運算和運算性質(zhì)的不同，施加于同一數(shù)據(jù)結(jié)構上，則會導致有不同的種類的數(shù)據(jù)結(jié)構產(chǎn)生。如：限制在線性表的一端做插入和刪除操作，稱該線性表為棧；若限制在線性表的一端插入，另一端刪除操作，稱該線性表為隊。其棧和隊都有順序存儲結(jié)構或鏈接存儲結(jié)構，則它們存儲結(jié)構稱為：順序棧，鏈式棧，順序隊，鏈式隊。數(shù)據(jù)結(jié)構第一章概論1.線性表

2.棧線性結(jié)構3.隊列,雙隊列

4.數(shù)組數(shù)據(jù)結(jié)構5.字符串

非線性1.樹,二叉樹結(jié)構2.圖

數(shù)據(jù)邏輯結(jié)構分類數(shù)據(jù)結(jié)構第一章概論數(shù)據(jù)順序存儲結(jié)構和鏈式存儲結(jié)構（物理結(jié)構，存儲表示,物理表示）

數(shù)據(jù)結(jié)構在計算機存儲器中的映象(mapping)。(1)順序存儲結(jié)構(向量,一維數(shù)組)

例.chara[5]={'A','B','C','D'}；

ABCDE01234a是一維數(shù)組(2)非順序存儲結(jié)構(鏈接表：指針類型和結(jié)構類型定義）例.單鏈表

datanext┌─┬┐┌─┬┐┌─┬┐┌─┬─┐Head─→│A│┼→│B│┼→│C│┼→│D│^│└─┴┘└─┴┘└─┴┘└─┴─┘4個結(jié)點的單鏈表數(shù)據(jù)結(jié)構第一章概論7.數(shù)據(jù)類型（datatype)---

是一個值的集合和定義在這個值上的一組操作的總稱。用數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構。

(1)原子類型(如：int,char,float等)(2)結(jié)構類型(如：數(shù)組,結(jié)構,聯(lián)合體等）8.抽象數(shù)據(jù)類型(AbstractDataType)----

與計算機的實現(xiàn)無關的數(shù)據(jù)類型。形式定義：

ADT抽象數(shù)據(jù)類型名

{1.數(shù)據(jù)對象；

2.數(shù)據(jù)關系:一個或多個關系；

3.一組基本操作/運算

}ADT抽象數(shù)據(jù)類型名注意：常用DataType表示抽象元素類型。數(shù)據(jù)結(jié)構第一章概論1.3算法和算法分析

數(shù)據(jù)的運算是通過算法描述的。1.算法----求解一個特定任務的指令的有限序列。例.求a[0..n-1]中n個數(shù)的平均值(假定n>0)。

floataverage(floata[],intn){inti；floats=0.0；//累加器賦初值

for(i=0；i<n；i++)s=s+a[i]；//a[i]累加到s中

s=s/n；//計算平均值

printf(“ave=%f”,s)；//輸出

return(s)；//返回

}其中：a,n為輸入量；s為輸出量。數(shù)據(jù)結(jié)構第一章概論2.算法的5個特征(1)有窮性：在有限步(或有限時間)之后算法終止。例.{i=0；s=0；

while(i<10)s++；

i++；

}(2)確定性：無二義性。例.{x=5；y=10；

z=x+++y；

printf(“%d,%d,%d”,x,y,z)；

}x+++y解釋為：x+(++y)？

(x++)+y？數(shù)據(jù)結(jié)構第一章概論

(3)可行性：可以在計算機上實現(xiàn)。

for(i=1,s=0；i<10；++i)s++；？？？

(4)輸入：有0或多個輸入量。

(5)輸出：至少有一個輸出量。3.算法設計要求

(1)正確性

a.無語法錯誤；

b.對n組輸入產(chǎn)生正確結(jié)果；

c.對特殊輸入產(chǎn)生正確結(jié)果；

d.對所有輸入產(chǎn)生正確結(jié)果。

(2)可讀性：“算法主要是為了人的閱讀與交流”。

(3)健壯性：有出錯處理的提示。

(4)高效與低存儲量數(shù)據(jù)結(jié)構第一章概論下列描述不符合算法的什么特征和要求？

例1voidsuanfa1(){inti,s=0；

for(i=0；i>=0；i++)//死循環(huán)

s++；//不能終止

}

例2floatsuanfa2(){intx,y；

scanf(“%d”,&x)；

y=sqrt(x)；//當x<0時,出錯

return(y)；

}數(shù)據(jù)結(jié)構第一章概論4.算法的時間復雜度衡量算法性能：

a.算法正確性；

b.執(zhí)行算法所消耗的時間；

c.執(zhí)行算法所消耗的空間（主要考慮輔存空間）；

d.算法易讀易理解，易于編碼，易于調(diào)試等。

主要討論算法執(zhí)行時間。算法所消耗的時間：算法中每條語句執(zhí)行時間之和。每條語句執(zhí)行時間=語句的執(zhí)行次數(shù)×一次執(zhí)行該語句的時間。語句的頻度：設n為求解的問題的規(guī)模,基本操作(或語句)執(zhí)行次數(shù)總和稱為語句頻度,記作f(n)。問題的規(guī)模n：指線性表的長度，多項式的項數(shù)，矩陣的階數(shù)，樹的結(jié)點數(shù)，圖中的頂點或邊數(shù)等。

注：一次執(zhí)行語句的時間是很難精確算出的：它與機器的執(zhí)行速度，編譯程序編譯質(zhì)量及運行環(huán)境等因素有關。算法所消耗的時間粗略地用算法中語句執(zhí)行的最大次數(shù)來度量。數(shù)據(jù)結(jié)構第一章概論

//求兩個n階方陣的乘積：C=A*B#definen100intMultiply(inta[n][n],intb[n][n],intc[n][n]){intj,i,k；語句的頻度f(n)(1)for(i=0；i<n；i++)n+1(2)for(j=0；j<n；j++){n(n+1)(3)c[i][j]=0；n2(4)for(k=0；k<n；k++)n2(n+1)(5)c[i][j]=c[i][j]+a[i][k]*b[k][j]；n3}}算法所消耗的時間就是所有語句頻度之和T(n):T(n)=2n3+3n2+2n+1T(n)是矩陣的階數(shù)n的函數(shù)。當n→∞，2n3+3n2+2n+1與n3

同階，即同一數(shù)量級。記為：

T(n)=O(f(n))=O(n3)即與f(n)中最高的階相同。數(shù)據(jù)結(jié)構第一章概論

例1{ints；語句的頻度f(n)scanf(“%d”,&s)；1s++；1printf(“%d”,s)；1}

其中：語句頻度為：f(n)=f(1)=3與問題規(guī)模n無關的常數(shù)。時間復雜度為：T(n)=O(f(n))=O(3)=O(1）

O(1)稱成為常量階/常量數(shù)量級只要算法的執(zhí)行時間不隨問題規(guī)模n增大而增長，即使算法中有上千條語句，其執(zhí)行的時間只不過是一個較大的常數(shù)，算法的時間復雜度仍然是常數(shù)階O(1)。數(shù)據(jù)結(jié)構第一章概論例2分析下面的算法voidsum(inta[],intn)f(n）

{ints=0,i；//1次

for(i=0；i<n；i++)//n次

s=s+a[i]；//n次

printf(“%d”,s)；//1次

}其中：語句頻度為：f(n)=1+n+n+1

時間復雜度為：T(n)=O(f(n))=O(2n+2)=O(n）

O(n)稱成為線性階/線性數(shù)量級一般情況下，對步進循環(huán)，只考慮循環(huán)體中的語句執(zhí)行的次數(shù)，可忽略步長加1，終值判斷，控制轉(zhuǎn)移等成分。數(shù)據(jù)結(jié)構第一章概論例3分析下面的算法1.voidsum(intm,intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=m；i++)//m次

4.{for(j=1；j<=n；j++)//m*n次

5.s++；//m*n次

6.printf(“%d”,s)；//m次

7.}8.}

其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1

當m=n時,f(n)=2n2+2n+1T(n)=O(f(n))=O(2n2+2n+1)=O(n2)平方階。

對嵌套層次的循環(huán)結(jié)構，時間的復雜度T(n)由最內(nèi)層循環(huán)體語句的頻度f(n)決定。數(shù)據(jù)結(jié)構第一章概論例4分析下面的算法1.voidsum(intn)2.{inti,j,s=0；//1次

3.for(i=1；i<=n；i++)//n次

4.{for(j=1；j<=i；j++)//?次

5.s++；//?次

6.printf(“%d”,s)；//n次

7.}8.}數(shù)據(jù)結(jié)構第一章概論

其中：第4行的次數(shù)為1+2+...+n=n(1+n)/2

第5行的次數(shù)為1+2+...+n=n(1+n)/2f(n)=1+n+n(n+1)+n=n2+3n+1T(n)=O(f(n))=O(n2）平方階例5有算法：在數(shù)組a[0..n-1]中查找k值：

(1)i=n-1;(2)while(i>=0&&(a[i]!=k))(3)i--;(4)returni;(3)語句的頻度不僅問題規(guī)模n有關，而且與a數(shù)組各元素和k的取值有關。若a中沒有要找的k值，(3)語句的頻度為f(n)=n;若a中最前一個元素是要找的k，則(3)語句的頻度為常數(shù)0。在這種情況下，采用最壞的時間復雜度作為算法的時間復雜度：T(n)=0(n)

數(shù)據(jù)結(jié)構第一章概論常用時間復雜度遞增依次為：常數(shù)階O(1),

對數(shù)階O(log2n),

線性階O(n),

線性對數(shù)階O(nlog2n),

平方階O(n2),

立方階O(n3)…K方階O(nk)，指數(shù)階O(2n)。

O(1)算法效率最高，O(2n)算法效率最低。5.算法的空間復雜度執(zhí)行算法所需存儲空間的大小。也是問題規(guī)模n的函數(shù)。

6.算法的復雜度包括：算法時間復雜度和算法空間復雜度。低高數(shù)據(jù)結(jié)構第一章概論例6冒泡排序的C語言算法

//對數(shù)組a中n個數(shù)按遞增次序作冒泡排序

1.Voidbubble1(inta[],intn)2.{inti,j,temp；

3.for(i=0；i<=n-2；i++)//？次

4.for(j=0；j<=n-2-i；j++)