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

理論課教材：

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏吳偉民編著數(shù)據(jù)結(jié)構(gòu)1.0學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要意義和要求

1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4算法和算法的度量第一章緒論學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要意義和要求數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)學(xué)科的兩大支柱

數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的基礎(chǔ)

程序=算法+數(shù)據(jù)結(jié)構(gòu)要求：意義：（1）掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲(chǔ)結(jié)構(gòu)（2）提高閱讀和編寫算法的能力（3）能針對(duì)給定問(wèn)題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計(jì)和分析算法1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇程序

=算法

+數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)：為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法：處理問(wèn)題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例1書目自動(dòng)檢索系統(tǒng)例2人機(jī)對(duì)奕問(wèn)題例3多叉路口交通燈管理問(wèn)題例1書目自動(dòng)檢索系統(tǒng)書目文件按書名按作者名按分類號(hào)索引表線性表例2人機(jī)對(duì)奕問(wèn)題樹……..……..…...…...…...…...例3多叉路口交通燈管理問(wèn)題圖CEDABABACADBABCBDDADBDCEAEBECED數(shù)據(jù)結(jié)構(gòu)定義

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體”的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。數(shù)據(jù)（data)—所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合，是計(jì)算機(jī)操作的對(duì)象的總稱。數(shù)據(jù)元素（dataelement）—是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record）數(shù)據(jù)項(xiàng)（dataitem）—有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)。數(shù)據(jù)對(duì)象（dataobject)—是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。1.2基本概念和術(shù)語(yǔ)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)(datastructure)—是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)

其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。數(shù)據(jù)元素的映象方法：例用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關(guān)系的映象方法：（表示x,y的方法）順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系鏈?zhǔn)接诚?/p>

以附加信息(指針)表示后繼關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映象換句話說(shuō)

按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系線性表樹圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針

1345

元素1

1400

1346

元素4∧…….……..…….

1400

元素2

1536…….……..…….

1536

元素3

1346

鏈?zhǔn)酱鎯?chǔ)h1536元素21400元素11346元素3∧元素41345h元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖1.2基本概念和術(shù)語(yǔ)在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所屬的數(shù)據(jù)類型。例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef

自己定義數(shù)據(jù)類型typedefstruct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;數(shù)據(jù)類型：是一個(gè)值的集合和定義在此集合上的一組操作的總稱。1.2基本概念和術(shù)語(yǔ)不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。抽象數(shù)據(jù)類型

(AbstractDataType簡(jiǎn)稱ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象。一個(gè)抽象的數(shù)據(jù)類型的模塊通常應(yīng)包含定義、表示和實(shí)現(xiàn)三部分。抽象數(shù)據(jù)類型定義格式ADT

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

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D是數(shù)據(jù)對(duì)象；

S是D上的關(guān)系集；

P是對(duì)D的基本操作集。

賦值參數(shù)只為操作提供輸入值。引用參數(shù)以&打頭，除可提供輸入值外，還可返回操作結(jié)果。其中基本操作的定義格式為:

基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之?；静僮骼?，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象： //D

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系： //S

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作： //P

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。本書采用的C語(yǔ)言核心子集(1)預(yù)定義常量類型://函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是//函數(shù)的結(jié)果狀態(tài)代碼typedefintStatus(2)數(shù)據(jù)元素類型約定為ElemType(3)基本操作的算法都用以下形式的函數(shù)描述

函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{ //算法說(shuō)明 語(yǔ)句序列

}函數(shù)名(4)賦值語(yǔ)句(5)選擇語(yǔ)句

if和switch(6)循環(huán)語(yǔ)句

for,while,do-while(7)結(jié)束語(yǔ)句

return,break,exit(8)輸入輸出語(yǔ)句

scanf,printf(9)注釋

單行注釋//(10)基本函數(shù)

max,min,abs,eof…(11)邏輯運(yùn)算

&&,||,!//-----基本操作的函數(shù)原型說(shuō)明void

Assign(complex&Z,floatrealval,floatimagval)；

//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參

//數(shù)realval

和imagval

的值floatGetReal(cpmplexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

GetImag(complexZ)；

//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//用sum返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}typedefstruct{floatrealpart；

floatimagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義例如，對(duì)以上定義的復(fù)數(shù)。1.4算法和算法的度量算法（algorithm）—解決某一特定問(wèn)題的具體步驟的描述，是指令的有限序列一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性

對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。2．確定性

算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。并且在任何條件下，算法都只有一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。3．可行性

算法中的所有操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次來(lái)實(shí)現(xiàn)。4．有輸入一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。5．有輸出一個(gè)算法有零個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。算法特性算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)

可讀性(readability)

健壯性(robustness)

效率與低存儲(chǔ)量算法設(shè)計(jì)的要求1．正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；算法設(shè)計(jì)的要求2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3．健壯性

當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4．高效率與低存儲(chǔ)量需求

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間，兩者都與問(wèn)題的規(guī)模有關(guān)。算法設(shè)計(jì)的要求算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)度量

1.事后統(tǒng)計(jì)——利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分

缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序

所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

算法效率的度量2.事前分析估計(jì)——一個(gè)高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：

依據(jù)的算法選用何種策略

問(wèn)題的規(guī)模

程序語(yǔ)言

編譯程序產(chǎn)生機(jī)器代碼質(zhì)量

機(jī)器執(zhí)行指令速度算法效率的度量

同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———所以使用絕對(duì)時(shí)間單位衡量算法效率不合適

假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。

一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。算法效率的度量注意：T(n)是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)，而O(f(n))是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。f(n)是n趨向無(wú)窮大時(shí)與T(n)為同階無(wú)窮大。算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

=

原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。如何估算算法的時(shí)間復(fù)雜度voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)例一兩個(gè)矩陣相乘voidselect_sort(int&a[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列?；静僮?

比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:

O(n2)j=i;//

選擇第i個(gè)最小元素for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){}//select_sortif(j!=i)