第1章緒論什么是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)算法和算法分析1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)值計(jì)算問(wèn)題的計(jì)算機(jī)解決例雞兔同籠問(wèn)題：雞和兔共n個(gè)頭，m個(gè)腳，求各有多少？數(shù)學(xué)模型，二元一次方程組求解x+y=n和2x+4y=mx=(4n-m)/2和y=n-x的自然數(shù)（包括0）程序輸入n和m計(jì)算x=(4n-m)/2和y=n-x判斷x和y是否滿足條件但是在實(shí)際中，很多是非數(shù)值計(jì)算問(wèn)題例1書(shū)目自動(dòng)檢索系統(tǒng)登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)索引表線性表例2人機(jī)對(duì)奕問(wèn)題樹(shù)……..……..…...…...…...…...例3多叉路口交通燈管理問(wèn)題CEDABABACADBABCBDDADBDCEAEBECED圖結(jié)論當(dāng)前計(jì)算機(jī)的應(yīng)用特點(diǎn)數(shù)據(jù)是各式各樣的數(shù)據(jù)之間的聯(lián)系也有多種情況不再僅僅是數(shù)值計(jì)算，大量的是非數(shù)值計(jì)算，通常要對(duì)數(shù)據(jù)進(jìn)行組織、管理和檢索等。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對(duì)象的特點(diǎn)，在計(jì)算機(jī)中的表示方式以及各個(gè)操作的具體實(shí)現(xiàn)手段。這些就是《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程研究的主要內(nèi)容為了解決這些問(wèn)題我們?cè)撛趺醋?!背景知識(shí)1968年開(kāi)始獨(dú)立開(kāi)設(shè)《數(shù)據(jù)結(jié)構(gòu)》課程1968年，唐.歐.克努特,《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》面向過(guò)程的程序設(shè)計(jì)思想程序＝算法＋數(shù)據(jù)結(jié)構(gòu)軟件=程序+文檔數(shù)據(jù)結(jié)構(gòu)沒(méi)有統(tǒng)一的定義數(shù)據(jù)結(jié)構(gòu)仍然在不斷發(fā)展中邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)算法算法的分析指數(shù)據(jù)元素之間抽象化的相互關(guān)系。獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的。

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式(映象)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示方法順序影象——順序存儲(chǔ)結(jié)構(gòu)非順序影象——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針(pointer)，用此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系?！稊?shù)據(jù)結(jié)構(gòu)》的研究?jī)?nèi)容是對(duì)信息的一種符號(hào)表示——人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。數(shù)據(jù)(Data)

在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)——包括數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)

(包括文字、表格、圖象、聲音等，都稱(chēng)為數(shù)據(jù))。數(shù)據(jù)元素(DataElement)：(也稱(chēng)結(jié)點(diǎn))是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位。但它還可以分割成若干個(gè)具有不同屬性的數(shù)據(jù)項(xiàng)(字段、域(field))，故不是組成數(shù)據(jù)的最小單位。數(shù)據(jù)項(xiàng)(dataitem)

是數(shù)據(jù)的不可分割的最小單位。1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。四類(lèi)基本結(jié)構(gòu)集合：數(shù)據(jù)元素除了同屬于一種類(lèi)型外，別無(wú)其它關(guān)系。線性結(jié)構(gòu)：一對(duì)一。樹(shù)型結(jié)構(gòu)：一對(duì)多。圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對(duì)多。數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組DataStructure=(D,S)其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集例4復(fù)數(shù)定義復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)，Complex=(C,R)其中C是兩個(gè)實(shí)數(shù)的集合{c1,c2}；R={P}，P是定義在集合C上的一種關(guān)系{<c1,c2>}，其中有序偶<c1,c2>表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部。邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示又稱(chēng)為存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)的表示和關(guān)系的表示順序映像順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系非順序映像鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面任何一個(gè)算法的設(shè)計(jì)取決與選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)算法的實(shí)現(xiàn)依賴(lài)于算法的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)集合上的一組操作的總稱(chēng)數(shù)據(jù)類(lèi)型分類(lèi)原子類(lèi)型：類(lèi)型的值是不可分解的結(jié)構(gòu)類(lèi)型：類(lèi)型的值是由若干成分按某種結(jié)構(gòu)組成，是可分解的。抽象數(shù)據(jù)類(lèi)型ADT一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作定義僅取決于它的一組邏輯特性，與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)抽象數(shù)據(jù)類(lèi)型的分類(lèi)原子類(lèi)型值是不可分解的固定聚合類(lèi)型值由確定數(shù)目的成分按某種結(jié)構(gòu)組成可變聚合類(lèi)型值得成分的數(shù)目不定ADT抽象數(shù)據(jù)類(lèi)型名

{

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

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

基本操作:〈基本操作的定義〉

}ADT

抽象數(shù)據(jù)類(lèi)型名抽象數(shù)據(jù)類(lèi)型可用(D,S,P)三元組表示，其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。用偽碼(不真正執(zhí)行的符號(hào))描述基本操作的定義格式為：

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

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

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)只為操作提供輸入值；

引用參數(shù)以&打頭，除了可以提供輸入值外，還將返回操作結(jié)果。

描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。說(shuō)明操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類(lèi)型的描述方法：例6抽象數(shù)據(jù)類(lèi)型三元組的定義ADTTriplet{ 數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3∈Elemset} 數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>} 基本操作： InitTriplet(&T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組T…… DestroyTriplet(&T) 操作結(jié)果：三元組T被銷(xiāo)毀 Get(T,i,&e) 初始條件：三元組T已存在，1≤i≤3 操作結(jié)果：用e返回T的第i元的值 。。。。。。。。。。。}ADTTriplet多形數(shù)據(jù)類(lèi)型多形數(shù)據(jù)類(lèi)型是指其值的成分不確定的數(shù)據(jù)類(lèi)型例如：e1,e2,e3可以是整型、字符、字符串，也可以是構(gòu)造的復(fù)雜類(lèi)型要求：元素之間的關(guān)系相同，基本操作相同具有相同的數(shù)據(jù)抽象1.3抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型可以通過(guò)固有數(shù)據(jù)類(lèi)型來(lái)表示和實(shí)現(xiàn)用已存在的數(shù)據(jù)類(lèi)型來(lái)說(shuō)明新的結(jié)構(gòu)用已實(shí)現(xiàn)的操作來(lái)組合新的操作采用類(lèi)C語(yǔ)言作為描述工具本教材采用類(lèi)C語(yǔ)言和偽碼描述類(lèi)C語(yǔ)言簡(jiǎn)要說(shuō)明采用類(lèi)C語(yǔ)言作為描述工具介于偽碼和C語(yǔ)言之間的語(yǔ)言有時(shí)用偽碼表示只含抽象操作的抽象算法預(yù)定義常量和類(lèi)型數(shù)據(jù)結(jié)構(gòu)的表示基本操作的算法用以下格式函數(shù)描述函數(shù)類(lèi)型函數(shù)名（函數(shù)參數(shù)表）{//算法說(shuō)明語(yǔ)句序列}函數(shù)名賦值語(yǔ)句簡(jiǎn)單賦值傳來(lái)賦值成組賦值交換賦值條件賦值條件語(yǔ)句ifswitch循環(huán)語(yǔ)句forwhiledo-while結(jié)束語(yǔ)句函數(shù)結(jié)束語(yǔ)句：returncase結(jié)束語(yǔ)句：break異常結(jié)束語(yǔ)句：exit輸入和輸出語(yǔ)句輸入語(yǔ)句：scanf輸出語(yǔ)句：printf通常省略格式串注釋單行注釋//基本函數(shù)求最大值 max求最小值 min求絕對(duì)值 abs求不足整數(shù)值 floor求進(jìn)位整數(shù)值 ceil判定文件結(jié)束 eof判定行結(jié)束 eoln邏輯運(yùn)算約定短路！例7抽象數(shù)據(jù)類(lèi)型Triplet的表示和實(shí)現(xiàn)//-----采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)-----typedefElemType*Triplet;//由InitTriplet分配3個(gè)元素存儲(chǔ)空間//-----基本操作的函數(shù)原型說(shuō)明-----StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3); //操作結(jié)果:構(gòu)造了三元組T，元素………………//-----基本操作的實(shí)現(xiàn)-----StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){ //構(gòu)造三元組T，依次置T的3個(gè)元素的初值為v1，v2和v3。 T=(ElemType*)malloc(3*sizeof(ElemType));//分配三個(gè)單元的存儲(chǔ)空間 if(!T)exit(OVERFLOW); //分配存儲(chǔ)空間失敗 T[0]=v1,T[1]=V2,T[2]=V3; returnOK;}//InitTriplet…………1.4算法和算法分析算法算法設(shè)計(jì)的要求算法效率的度量算法的存儲(chǔ)空間需求1.4.1算法算法：對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，

其中每一條指令表示一個(gè)或多個(gè)操作算法應(yīng)具有的5個(gè)重要特性有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成確定性：算法中每一條指令必須有確切的含義，無(wú)二義性。并且，在任何條件下，算法同時(shí)只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出?？尚行运惴枋龅乃胁僮鞫急仨氉銐蚧荆际强梢酝ㄟ^(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。輸入一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。它們可以使用輸入語(yǔ)句由外部提供，也可以使用賦值語(yǔ)句在算法內(nèi)給定。輸出一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。算法與程序的區(qū)別算法的含義與程序十分相似，但二者有區(qū)別一個(gè)程序不一定滿足有窮性（如一個(gè)操作系統(tǒng)在用戶未使用前一直處于“等待”的循環(huán)中,直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無(wú)休止地運(yùn)行，直到系統(tǒng)停工。）；程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。算法若用計(jì)算機(jī)語(yǔ)言來(lái)書(shū)寫(xiě)，則它就可以是程序。一個(gè)算法可以用自然語(yǔ)言、數(shù)學(xué)語(yǔ)言或約定的符號(hào)來(lái)描述，也可以用流程圖、計(jì)算機(jī)高級(jí)程序語(yǔ)言（如C語(yǔ)言）或偽代碼等來(lái)描述。1.4.2算法設(shè)計(jì)的要求算法設(shè)計(jì)的目標(biāo)正確性程序不含語(yǔ)法錯(cuò)誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果?？勺x性在算法是正確的前提下，算法的可讀性是擺在第一位的，這在當(dāng)今大型軟件需要多人合作完成的環(huán)境下是至關(guān)重要的，另一方面，晦澀難讀的程序易于隱藏錯(cuò)誤而難以調(diào)試。健壯性當(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)行處理。效率與低存儲(chǔ)量需求效率指的是算法執(zhí)行的時(shí)間（時(shí)間復(fù)雜性）；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間（空間復(fù)雜性）。一般這兩者與問(wèn)題的規(guī)模有關(guān)1.4.3算法效率的度量事后統(tǒng)計(jì)的方法必須編寫(xiě)好可運(yùn)行程序依賴(lài)計(jì)算機(jī)的硬件和軟件環(huán)境在算法中的某些部位插裝時(shí)間函數(shù)time

(), 測(cè)定算法完成某一功能所花費(fèi)時(shí)間

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(”%d%d\n“,n,runTime)；事前分析估算的方法高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行時(shí)所需要消耗的時(shí)間取決于：依據(jù)算法選用何種策略問(wèn)題的規(guī)模書(shū)寫(xiě)程序的語(yǔ)言編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量機(jī)器執(zhí)行指令的速度可見(jiàn)選擇絕對(duì)的時(shí)間單位衡量算法的效率不可取一個(gè)特定算法的效率只依賴(lài)于問(wèn)題的規(guī)模是問(wèn)題規(guī)模的函數(shù)漸進(jìn)時(shí)間復(fù)雜度例：NxN矩陣相乘算法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] }可見(jiàn)除了循環(huán)控制外，c[i][j]+=a[i,k]*b[k][j]是基本操作整個(gè)算法的執(zhí)行時(shí)間與該基本操作執(zhí)行次數(shù)的n3成正比。記為：T(n)=O(n3)算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法時(shí)間復(fù)雜度記作：

T(n)=O(f(n))

它表示隨著問(wèn)題規(guī)模的增大，算法執(zhí)行的時(shí)間增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。語(yǔ)句的頻度語(yǔ)句的頻度是該語(yǔ)句重復(fù)執(zhí)行的次數(shù){++x;s=0}for(i=1;i<=n;++i){++x;s+=x;}for(j=1;j<=n;++j)

for(k=1;k<=n;++k){++x;s+=x}++x的頻度分別是1、n1和n2。三個(gè)程序的時(shí)間復(fù)雜度分別為O(1)、O(n1)和O(n2)。稱(chēng)為常量階、線性階和平方階其它可能的時(shí)間復(fù)雜度：對(duì)數(shù)階：O(logn)指數(shù)階：O(2n)其它：O(nlogn)、O(n!)等等時(shí)間復(fù)雜度的分析一般情況下，一個(gè)算法只選擇一種基本運(yùn)算討論時(shí)間復(fù)雜度，根據(jù)需要也可能綜合幾個(gè)基本算法討論時(shí)間復(fù)雜度特別的討論有時(shí)算法中基本運(yùn)算的重復(fù)執(zhí)行次數(shù)隨著問(wèn)題的輸入集不同而不同例如起泡排序中a[j]a[j+1]語(yǔ)句當(dāng)a中初始序列為自小至大有序，基本操作的執(zhí)行次數(shù)為0；當(dāng)a中初始序列為自大至小有序，基本操作的執(zhí)行次數(shù)