數(shù)據(jù)結(jié)構(gòu)（第2版）（C語言實(shí)現(xiàn)）緒論

數(shù)據(jù)結(jié)構(gòu)（第2版）（C語言實(shí)現(xiàn)）目錄導(dǎo)航1.11.21.31.41.51.6數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)算法的特性和算法的描述算法分析關(guān)于數(shù)據(jù)結(jié)構(gòu)的地位三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素（記錄）>數(shù)據(jù)項(xiàng)例：教職工基本情況表>教職工個(gè)人記錄>工號(hào)、姓名、性別……基本概念和術(shù)語能被計(jì)算機(jī)識(shí)別并能輸入計(jì)算機(jī)中并能被處理的符號(hào)集合。數(shù)值型數(shù)據(jù)非數(shù)值型數(shù)據(jù)（多媒體信息，如圖片、音頻、視頻）其中，數(shù)據(jù)元素中的數(shù)據(jù)項(xiàng)是有獨(dú)立含義的數(shù)據(jù)最小單位，也稱數(shù)據(jù)域。是組成數(shù)據(jù)的有一定意義的基本單位，也稱數(shù)據(jù)記錄或結(jié)點(diǎn)1.數(shù)據(jù)（Data)2、數(shù)據(jù)元素

（dataelement）1.1數(shù)據(jù)結(jié)構(gòu)的基本概念整數(shù)數(shù)據(jù)對象N={0,1,2,…}1.1數(shù)據(jù)結(jié)構(gòu)的基本概念學(xué)生數(shù)據(jù)對象學(xué)生記錄的集合3、數(shù)據(jù)對象(DataObject)：是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。4、數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。1.1數(shù)據(jù)結(jié)構(gòu)的基本概念5．?dāng)?shù)據(jù)類型

數(shù)據(jù)類型（DataType）是用來刻畫一組性質(zhì)相同的數(shù)據(jù)及其上的操作的總稱。按照取值的不同，數(shù)據(jù)類型還可以分為兩類：原子類型和結(jié)構(gòu)類型。原子類型是不可以再分解的基本類型，包括整型、實(shí)型、字符型等。結(jié)構(gòu)類型是由若干個(gè)類型組合而成，是可以再分解的。typedefstruct{intno;charname[20];intage;floatscore;}STUDENT;STUDENTstu,*p;抽象數(shù)據(jù)類型(ADTs:AbstractDataTypes)更高層次的數(shù)據(jù)抽象。由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的操作。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（數(shù)據(jù)對象，數(shù)據(jù)對象之間的關(guān)系，在數(shù)據(jù)對象上的操作）ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

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

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式1.2數(shù)據(jù)結(jié)構(gòu)的基本概念例如，線性表的抽象數(shù)據(jù)類型描述如下：ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}基本操作：InitList(&L)初始條件：表L不存在。操作結(jié)果：構(gòu)造一個(gè)空的線性表。ClearList(&L)初始條件：表L已存在。操作結(jié)果：表L被置為空。ListLength(L)初始條件：表L已存在。操作結(jié)果：返回線性表L的元素個(gè)數(shù)?！瓆ADTList1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)1.3.1數(shù)據(jù)的邏輯結(jié)構(gòu)（1）集合。

（2）線性結(jié)構(gòu)。

（3）樹形結(jié)構(gòu)。

（4）圖結(jié)構(gòu)。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)1.3.2存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)，指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)形式。順序存儲(chǔ)是把數(shù)據(jù)元素存放在一塊地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。鏈?zhǔn)酱鎯?chǔ)是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，數(shù)據(jù)元素的存儲(chǔ)關(guān)系并不能反映其邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址。1.4算法的特性和算法的描述1.5.1數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切。兩者既有聯(lián)系又有區(qū)別。數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系可用一個(gè)公式描述：程序=算法+數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)，算法總是要依賴于某種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)與算法的區(qū)別在于：數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上解決實(shí)際問題。算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是這些思想的邏輯基礎(chǔ)。1.4算法的特性和算法的描述1.4.1什么是算法

算法(algorithm)是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為有限的操作序列。操作序列包括了一組操作，每一個(gè)操作都完成特定的功能。例如，求n個(gè)數(shù)中最大者的問題，其算法描述如下：

1．定義一個(gè)變量max和一個(gè)數(shù)組a[]，分別用來存放最大數(shù)和數(shù)組的元素，并假定第一個(gè)數(shù)最大，賦給max，即：

max=a[0];1.5算法2．依次把數(shù)組a中其余的n-1個(gè)數(shù)與max進(jìn)行比較，遇到較大的數(shù)時(shí)，將其賦給max。

for(i=1;i<n;i++)if(max<a[i])max=a[i];

最后，max中的數(shù)就是n個(gè)數(shù)中的最大者。1.4算法的特性和算法的描述1.4.2算法的五大特性算法具有以下5個(gè)特性。（1）有窮性。有窮性指的是算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成。（2）確定性。算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。算法在一定條件下，只有一條執(zhí)行路徑，也就是相同的輸入只能有一個(gè)唯一的輸出結(jié)果。（3）可行性。算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。（4）輸入。算法具有零個(gè)或多個(gè)輸入。（5）輸出。算法至少有一個(gè)或多個(gè)輸出。輸出的形式可以是打印輸出也可以是返回一個(gè)或多個(gè)值。1.4.3算法的描述算法的描述方式有多種：自然語言、偽代碼（或稱為類語言）、程序流程圖及程序設(shè)計(jì)語言（如C語言）。例如，求兩個(gè)正整數(shù)m和n的最大公約數(shù)的算法可用以下幾種方式描述。1.4算法的特性和算法的描述1.4算法的特性和算法的描述1．自然語言描述法我們利用自然語言描述m是否為質(zhì)數(shù)的算法如下：（1）輸入正整數(shù)m和n；（2）求m除以n的余數(shù)，將余數(shù)送入中間變量r，并將n的值賦給m，r的值賦給n；（3）判斷r是否為零。如果為零，則m即為所求最大公約數(shù)，輸出最大公約數(shù)，算法結(jié)束；否則，執(zhí)行步驟（2）。1.5算法2．程序流程圖法

求兩個(gè)正整數(shù)m和n的最大公約數(shù)的程序流程圖描述如下：1.5算法voiddcf()/*求最大公約數(shù)*/{ scanf(m,n); /*輸入兩個(gè)正整數(shù)*/ do{ r=m%n; /*r表示兩個(gè)數(shù)的余數(shù)*/ m=n; n=r; }while(r); printf(m); /*輸出最大公約數(shù)*/}

3．類語言法1.4算法的特性和算法的描述

voiddcf()/*求最大公約數(shù)*/{ intm,n,r; printf(“請輸入兩個(gè)正整數(shù)m和n：\n”); scanf(“%d,%d”,&m,&n);printf(“dcf（%d，%d）=”,m,n); r=m; do{ /*使用輾轉(zhuǎn)相除法法求解最大公約數(shù)*/ r=m%n; /*r存放兩個(gè)數(shù)的余數(shù)*/ m=n; n=r; }while(r); printf(“%d\n”,n); /*輸出最大公約數(shù)*/}

4．程序設(shè)計(jì)語言法1.5.1算法設(shè)計(jì)的四個(gè)目標(biāo)一個(gè)好的算法應(yīng)該具備以下目標(biāo)：

1．算法的正確性算法的正確性（correctness）是指算法至少應(yīng)該包括對于輸入、輸出和加工處理無歧義性的描述，能正確反映問題的需求，且能夠得到問題的正確答案。1.5算法分析

通常算法的正確性應(yīng)包括以下4個(gè)層次：a.算法對應(yīng)的程序沒有語法錯(cuò)誤；b.對于幾組輸入數(shù)據(jù)能得到滿足規(guī)格要求的結(jié)果；c.對于精心選擇的典型的、苛刻的帶有刁難性的幾組輸入數(shù)據(jù)能得到滿足規(guī)格要求的結(jié)果；d.對于一切合法的輸入都能得產(chǎn)生滿足要求的結(jié)果。1.5算法分析2．可讀性算法主要是為了人們方便閱讀和交流，其次才是計(jì)算機(jī)執(zhí)行。可讀性（readability）好有助于人們對算法的理解，晦澀難懂的程序往往隱含錯(cuò)誤不易被發(fā)現(xiàn)，難以調(diào)試和修改。1.5算法分析3．健壯性（robustness）當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出反應(yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生異?；蚰涿畹妮敵鼋Y(jié)果。例如，求一元二次方程根ax2+bx+c=0的算法，需要考慮多種情況，先判斷b2-4ac的正負(fù)，如果為正數(shù)，則該方程有兩個(gè)不同的實(shí)根；如果為負(fù)，表明該方程無實(shí)根；如果為零，表明該方程只有一個(gè)實(shí)根；如果a=0，則該方程又變成了一元一次方程，此時(shí)若b=0，還要處理除數(shù)為零的情況。如果輸入的a、b、c不是數(shù)值型，還要提示用戶輸入錯(cuò)誤。1.5算法分析4．高效率和低存儲(chǔ)量效率指的是算法的執(zhí)行時(shí)間。對于同一個(gè)問題如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長的效率低。存儲(chǔ)量需求指算法在執(zhí)行過程中需要的最大存儲(chǔ)空間。效率與低存儲(chǔ)量需求都與問題的規(guī)模有關(guān)，求100個(gè)人的平均分與求1000個(gè)人的平均分所花的執(zhí)行時(shí)間和運(yùn)行空間顯然有一定差別。設(shè)計(jì)算法時(shí)應(yīng)盡量選擇高效率和低存儲(chǔ)量需求的算法。1.5算法分析1.5.2算法效率評價(jià)算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上的運(yùn)行時(shí)所耗費(fèi)的時(shí)間來度量，而度量一個(gè)算法在計(jì)算機(jī)上的執(zhí)行時(shí)間通常有兩種方法：

1．事后統(tǒng)計(jì)方法這種方法有兩個(gè)缺陷：一是必須依據(jù)算法事先編制好程序，這通常需要花費(fèi)大量的時(shí)間與精力；二是時(shí)間的長短依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素，有時(shí)會(huì)掩蓋算法本身的優(yōu)劣。因此，人們常常采用事前分析估算的方法評價(jià)算法的好壞。1.5算法分析2．事前分析估算方法這主要在計(jì)算機(jī)程序編制前，對算法依據(jù)數(shù)學(xué)中的統(tǒng)計(jì)方法進(jìn)行估算。這主要是因?yàn)樗惴ǖ某绦蛟谟?jì)算機(jī)上的運(yùn)行時(shí)間取決于以下因素：

a．算法采用的策略、方法；

b．編譯產(chǎn)生的代碼質(zhì)量；

c．問題的規(guī)模；

d．書寫的程序語言，對于同一個(gè)算法，語言級(jí)別越高，執(zhí)行效率越低；

e．機(jī)器執(zhí)行指令的速度。1.5算法分析

例如，斐波那契數(shù)列的算法和語句的的頻度如下。每一條語句的頻度

f0=0;1f1=1;1printf(“%d,%d”,f0,f1);1for(i=2;i<=n;i++)n{ fn=f0+f1;n-1 printf(“,%d”,fn);n-1 f0=f1;n-1 f1=fn;n-1}每一條語句的右端是對應(yīng)語句的頻度（frequencycount），即語句的執(zhí)行次數(shù)。上面算法總的執(zhí)行次數(shù)為T(n)=1+1+1+n+4(n-1)=5n-1。1.5算法分析1.5.3算法的時(shí)間復(fù)雜度在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T（n）隨n的變化情況并確定T（n）的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：

T（n）=O(f（n）)

它表示隨問題規(guī)模n的增大，算法的執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度（asymptotictimecomplexity），簡稱為時(shí)間復(fù)雜度。

1.5算法分析

一般情況下，隨n的增大，T（n）的增長較慢的算法為最優(yōu)的算法。例如，在下列三段程序段中，給出原操作x=x+1的時(shí)間復(fù)雜度分析。（1）x=x+1；（2）for（i=1；i<=n；i++）

x=x+1；（3）for（i=1；i<=n；i++）

for（j=1；j<=n；j++）

x=x+1；

1.5算法分析

常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：

O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)。一些常見函數(shù)的增長率如圖1.10所示。1.5算法分析例1.1分析以下程序段的時(shí)間復(fù)雜度。for(i=2;i<=n;i++) for(j=2;j<=i-1;j++){ x++;//基本操作 a[i][j]=x;//基本操作}

該程序段中的基本操作是第二層for循環(huán)中的語句，即x++和a[i][j]=x，其語句頻度為(n-1)(n-2)/2。因此，其時(shí)間復(fù)雜度為O(n2)。例1.2分析以下算法的時(shí)間復(fù)雜度。voidFun(){inti=1;while(i<=n){i=i*2;//基本操作}}

該函數(shù)fun()的基本運(yùn)算是i=i*2，設(shè)執(zhí)行時(shí)間為T(n)，則2T(n)≤n，則有T(n)≤log2n=O(log2n)。因此，時(shí)間復(fù)雜度為O(log2n)。例1.3分析以下算法的時(shí)間復(fù)雜度。voidFunc(){ i=s=0; while(s<n){ i++;//基本操作s+=i;//基本操作 }}【例1.4】分析以下代碼的時(shí)間復(fù)雜度。intMaxSubSum(inta[],intn){inti,j,k,sum1,maxsum=0;for(i=0;i<n;i++){for(j=i;j<n;j++){sum1=0;for(k=i;k<=j;k++)sum1+=a[k];if(sum1>maxsum)maxsum=sum1;}}returnmaxsum;}【例1.5】一個(gè)算法所需時(shí)間由以下遞歸方程表示，分析算法的時(shí)間復(fù)雜度。

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=22T(n-2)+2+1=22(2T(n-3)+1)+2+1=……=2k-1(2T(n-k)+1)+2k-2+…+2+1=…=2n-2(2T(1)+1)+2n-2+…+2+1=2n-1+…+2+1=2n-1因此，該算法的時(shí)間復(fù)雜度為O(2n)。1.5.4算法的空間復(fù)雜度空間復(fù)雜度（spacecomplexity）作為為算法所需存儲(chǔ)空間的量度，記作：

S(n)=O(f(n))

其中，n為問題的規(guī)模，f(n)為語句關(guān)于n的所占存儲(chǔ)空間的函數(shù)。

1.5算法分析例1.5以下是一個(gè)簡單插入排序算法，分析算法的空間復(fù)雜度。for(i=0;i<n;i++){t=a[i+1];j=i;while(j>=0&&t<a[j]){a[j+1]=a[j];j--;}a[j+1]=t;}該算法借助了變量t，與問題規(guī)模n的大小無關(guān)，空間復(fù)雜度為O(1)。例1.6以下算法是求n個(gè)數(shù)中的最大者，分析算法的空間復(fù)雜度。intFindMax(inta[],intn){intm;if(n<=1)returna[0];else{m=Find