《數(shù)據(jù)結(jié)構(gòu)》全套教學(xué)課件

第1章緒論總體要求：理解什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)理解數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)和邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系理解什么是數(shù)據(jù)類型、抽象數(shù)據(jù)類型理解算法的定義、算法的特性、算法的時間代價和算法的空間代價熟悉用C語言描述算法的方法，能夠使用C語言編寫程序核心技能點：具有抽象數(shù)據(jù)的能力具有C語言編程的能力具有算法的時間代價和算法的空間代價靜態(tài)分析能力1全套可編輯PPT課件

第1章緒論2擴展技能點：抽象數(shù)據(jù)類型的應(yīng)用能力算法的時間代價和算法的空間代價方法應(yīng)用實際的能力相關(guān)知識點：C語言的基本語句C語言函數(shù)的編寫格式及功能C語言標識符的命名規(guī)則C語言類型定義數(shù)學(xué)極限的知識第1章緒論3學(xué)習(xí)重點：熟練掌握算法的定義、算法的特性、算法的時間代價和算法的空間代價分析掌握數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)和邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系熟悉用C語言描述算法的方法第1章緒論41.1數(shù)據(jù)結(jié)構(gòu)的概念及分類1.1.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)大致可分為兩類：一類是數(shù)值性數(shù)據(jù)，包括整數(shù)、浮點數(shù)、復(fù)數(shù)、雙精度數(shù)等，主要用于工程和科學(xué)計算，以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串，以及文字、圖形、圖像、語音等的數(shù)據(jù)。從傳統(tǒng)的觀點來看，在解決應(yīng)用問題時，總把數(shù)據(jù)按其性質(zhì)歸類到一些稱之為數(shù)據(jù)對象(DataObject)的集合中。在數(shù)據(jù)對象中所有數(shù)據(jù)成員，即數(shù)據(jù)元素，都具有相同的性質(zhì)，它們是數(shù)據(jù)的子集。例如，整數(shù)數(shù)據(jù)對象可以是集合N={0,1,2,3,…}。英文字母數(shù)據(jù)對象可以是集合LETTER={A,B,…,Z}。第1章緒論5

綜合考慮數(shù)據(jù)對象及其所有數(shù)據(jù)成員之間的關(guān)系，就可得到數(shù)據(jù)結(jié)構(gòu)的定義：據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：

Data

Structure={D，R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第1章緒論61.1.2數(shù)據(jù)結(jié)構(gòu)的分類依據(jù)數(shù)據(jù)成員之間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)也稱為線性表，在這種結(jié)構(gòu)中所有數(shù)據(jù)成員(也稱為數(shù)據(jù)元素)都按某種次序排列在一個序列中，如圖1.2所示。對于線性結(jié)構(gòu)中每一數(shù)據(jù)元素，除第一個元素外，其它每一個元素都有一個且僅有一個直接前驅(qū)，第一個數(shù)據(jù)元素沒有直接前驅(qū)；除最后一個元素外，其他每一個元素都有一個且僅有一個直接后繼。第1章緒論7圖1.2線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系第1章緒論8

在非線性結(jié)構(gòu)中各個數(shù)據(jù)成員不再保持在一個線性序列中，每個數(shù)據(jù)成員可能與零個或多個其他數(shù)據(jù)成員發(fā)生聯(lián)系。根據(jù)關(guān)系的不同，可分為層次結(jié)構(gòu)和群結(jié)構(gòu)。層次結(jié)構(gòu)是按層次劃分的數(shù)據(jù)元素的集合，指定層次上的元素，可以有零個或多個處于下一個層次上的、直接的所屬下層元素。在第7章將重點討論樹形結(jié)構(gòu)，它是典型的層次結(jié)構(gòu)。樹中的元素叫做結(jié)點。樹可以為空，也可以不為空。若樹不為空，它有一個叫做根的結(jié)點，其他結(jié)點都是從它派生出來的。除根以外，每一個結(jié)點都有一個處于該結(jié)點直接上層的結(jié)點。樹的結(jié)構(gòu)如圖1.3所示。第1章緒論9圖1.3樹形結(jié)構(gòu)圖1．4群聚集(a)圖結(jié)構(gòu)(b)網(wǎng)絡(luò)結(jié)構(gòu)

群結(jié)構(gòu)中所有元素之間無順序關(guān)系。集合就是一種群結(jié)構(gòu)，在本教材中不討論。在集合中沒有重復(fù)的元素。另一種群結(jié)構(gòu)就是圖結(jié)構(gòu)，如圖1．4(a)所示。它是由圖的頂點集合和連接頂點的邊集合組成。還有一種圖的特殊形式，即網(wǎng)絡(luò)結(jié)構(gòu)。它給每條邊賦予一個權(quán)值，這個權(quán)值指明了在遍歷圖時經(jīng)過此邊時的耗費。例如，在圖1．4(b)中，頂點代表城市，賦予邊的權(quán)值表示兩個城市之間的距離。第1章緒論101.2抽象數(shù)據(jù)類型1.2.1數(shù)據(jù)類型在程序設(shè)計語言中介紹過各種數(shù)據(jù)類型。以C語言為例，有5種基本的數(shù)據(jù)類型：字符型、整型、浮點型、雙精度型和無值，分別用保留字char，int，float，double和void標識。這些數(shù)據(jù)類型不但規(guī)定了使用該類型時的取值范圍，而且還規(guī)定了該類型可以用的一組操作。例如，與整型相關(guān)的操作有+，-，*，／，與浮點型相關(guān)的操作也有+，-，*，／。然而整型的“／”操作與浮點型的“／”操作雖然形式一樣，卻是兩個不同的操作。如整型運算3／2的運算結(jié)果為1，浮點型運算3／2的運算結(jié)果為1.5。因為操作“／”用于幾個數(shù)據(jù)類型，故稱它是一種重載操作。事實上，數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)，以及允許執(zhí)行操作的一種描述。第1章緒論1.2.2數(shù)據(jù)抽象與抽象數(shù)據(jù)類型一、抽象數(shù)據(jù)類型定義（ADT）作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實世界。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。定義：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式。定義它的人同樣不必要關(guān)心它如何存儲。11第1章緒論抽象數(shù)據(jù)類型表示法：

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

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

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

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名例：線性表的表示名稱線性表

數(shù)據(jù)對象D={ai|ai(-ElemSet,i=0,1,2,...,n-1,n>=0}任意數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R1={<ai-1,ai>|ai-1,ai(-D,i=1,...,n-1}除第一個和最后一個外，每個元素有唯一的直接前趨和唯一的直接后繼?；静僮鱈istInsert(&L,i,e)L為線性表，i為位置，e為數(shù)據(jù)元素。ListDelete(&L,i,e)...12第1章緒論1.2.3用于描述數(shù)據(jù)結(jié)構(gòu)的語言

數(shù)據(jù)結(jié)構(gòu)的描述可以有多種方式，如語言方式、圖形方式和表格方式。從面向?qū)ο笥^點方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計語言有Delphi、Java、C++等。從面向過程觀點方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計語言有標準Pascal、標準C、基本BASIC語言等。從另一個角度來看，很多算法是面向過程的。對于熟悉面向過程開發(fā)方法的讀者，可方便地從傳統(tǒng)的面向過程方法過渡到用面向?qū)ο蠓椒ㄩ_發(fā)程序。因此，本書采用C語言來描述各種數(shù)據(jù)結(jié)構(gòu)。13第1章緒論

1.3算法定義什么是算法(Algorithm)?通常人們將算法定義為一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列。一個算法應(yīng)當具有以下特性：

⑴有輸入。一個算法必須有0個或多個輸入，它們是算法開始運算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。

⑵有輸出。一個算法應(yīng)有一個或多個輸出，輸出的量是算法計算的結(jié)果。

⑶確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動作都應(yīng)嚴格地、清晰地規(guī)定。

⑷有窮性。一個算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。

⑸有效性。算法中每一條運算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運算就能完成。14第1章緒論1.4算法性能分析與度量1.4.1算法的性能標準判斷一個算法的優(yōu)劣，主要有以下幾個標準：

⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標準。要求算法的編寫者對問題的要求有正確的理解，并能正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)算法。

⑵可使用性。要求算法能夠很方便地使用。此特性亦稱用戶友好性。為便于用戶使用，要求該算法具有良好的界面，完備的用戶文檔。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出都通過參數(shù)表顯式地傳遞，少用公用變量或全局變量，每個算法只完成一個功能。

⑶可讀性。算法應(yīng)當是可讀的。這是理解、測試和修改算法的需要。為了達到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名和函數(shù)名的命名必須有實際含義，讓人見名知義。在算法中必須加入注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用和算法中各程序段完成的功能等。15第1章緒論1.4算法性能分析與度量1.4.1算法的性能標準⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標準。要求算法的編寫者對問題的要求有正確的理解，并能正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)算法。

⑵可使用性。要求算法能夠很方便地使用。此特性亦稱用戶友好性。為便于用戶使用，要求該算法具有良好的界面，完備的用戶文檔。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出都通過參數(shù)表顯式地傳遞，少用公用變量或全局變量，每個算法只完成一個功能。

⑶可讀性。算法應(yīng)當是可讀的。這是理解、測試和修改算法的需要。為了達到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名和函數(shù)名的命名必須有實際含義，讓人見名知義。在算法中必須加入注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用和算法中各程序段完成的功能等。16第1章緒論⑷效率。算法的效率主要指算法執(zhí)行時計算機資源的消耗，包括存儲和運行時間的開銷，前者叫做算法的空間代價，后者叫做算法的時間代價。算法的效率與多種因素有關(guān)。例如，所用的計算機系統(tǒng)、可用的存儲容量和算法的復(fù)雜性等。下面將重點地討論算法的效率，其他判斷標準在以后的章節(jié)中再加以討論。

⑸健壯性。要求在算法中加入對輸參數(shù)、打開文件、讀文件記錄，以及子程序調(diào)用狀態(tài)進行自動檢錯和報錯并通過與用戶對話來糾錯的功能。這也叫做容錯性或例外處理。一個完整的算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。但在算法初寫時可以暫不管它，集中精力考慮如何實現(xiàn)必要的功能，待到算法成熟時再追加它。17第1章緒論1.4.2算法的后期測試算法效率的度量分為事前估計和后期測試。后期測試主要通過在算法中的某些部位插裝時間函數(shù)(如clock())來測定算法完成某一規(guī)定功能所需的時間。下面程序給出測試的示例。

程序清單程序演示

但是，一個算法運行與環(huán)境有關(guān)，同樣的算法在速度不同的計算機運行，執(zhí)行速度相差非常大；此外，一個算法用不同的編譯器編譯出的目標代碼也不一樣長，完成同樣的功能所需時間也不同。對于一個存儲需求極大的算法，如果可用的存儲空間不夠，在運行時將不得不頻繁地進行內(nèi)外存交換，需要的運行時間就很多。因此，算法的運行時間依賴于所用的計算機系統(tǒng)、編譯器、可用存儲空間大小等?？梢詫λ惴ǖ倪\行時間進行測量，以評估算法的正確性和可使用性，但在不同的機型、不同的編譯器版本和不同的硬軟件配置情況下，想通過測量結(jié)果來判斷算法的優(yōu)劣是不行的。18第1章緒論1.4.3算法的事前估計算法復(fù)雜性的度量屬于事前估計。它可分為空間復(fù)雜度度量和時間復(fù)雜度度量。空間復(fù)雜度(SpaceComplexity)是指當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占用的存儲空間也以某種單位由1增加到S(n)，則稱此算法的空間復(fù)雜度為S(n)；時間復(fù)雜度(TimeComplexity)是指當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所耗費的時間也以某種單位由1增加到T(n)，則稱此算法的時間復(fù)雜度為T(n)。

1.空間復(fù)雜度度量⑴固定部分。這部分空間的大小與輸入輸出個數(shù)多少和數(shù)值大小無關(guān)。主要包括存放程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成員等)變量所占的空間等。這部分屬于靜態(tài)空間，只要做簡單的統(tǒng)計就可估算。⑵可變部分。這部分空間主要包括與問題規(guī)模(即實例特性)有關(guān)的成分變量所占空間、遞歸工作棧所用空間，以及在算法運行過程中動態(tài)使用的空間。19第1章緒論2.時間復(fù)雜度度量算法的運行時間涉及加、減、乘、除、轉(zhuǎn)移、存和取等基本運算。要想準確地計算總運算時間是不可行的，因此，度量算法的運行時間，主要從程序結(jié)構(gòu)著手，統(tǒng)計算法的程序步數(shù)。簡單地說，程序步是指在語法上或語義上有意義的一段指令序列，而且這段指令序列的執(zhí)行時間與實例特性無關(guān)。

程序步的統(tǒng)計

程序步統(tǒng)計程序清單程序演示1.4.4漸進的時間復(fù)雜度算法的時間效率是通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量的。程序在計算機上運行所消耗的時間與下列因素有關(guān)：⑴書寫算法的程序設(shè)計語言；⑵編譯產(chǎn)生的機器語言代碼質(zhì)量；⑶機器執(zhí)行指令的速度；

⑷問題的規(guī)模，即算法的時間效率與算法處理的數(shù)據(jù)個數(shù)n的關(guān)系。在這四個因素中，前三個都與具體的機器有關(guān)。我們分析算法的效率應(yīng)拋開具體的機器，僅考慮算法本身的因素，因此，算法的時間效率只與問題的規(guī)模有關(guān)，算法的時間效率是問題規(guī)模的函數(shù)。算法的時間效率也稱作算法的時間復(fù)雜度。20第1章緒論算法的時間效率分析通常采用O(f(n))表示法(O(f(n))讀作大O的f(n))。定義：T(n)=O(f(n))當且僅當存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。由于上述定義中對所有的n(n≥n0)，只要n比較大一般均成立，而我們考慮的算法的時間效率也主要是在數(shù)據(jù)個數(shù)n相當大時的情況。所以，我們具體分析一個算法的時間效率T(n)時，一般不考慮n為一個較小的數(shù)時了T(n)≤f(n)不成立的情況。令函數(shù)T(n)為算法的時間復(fù)雜度，其中n為算法處理的數(shù)據(jù)個數(shù)。則T(n)=O(f(n))表示算法的時間復(fù)雜度隨數(shù)據(jù)個數(shù)n的增長率和函數(shù)f(n)的增長率相同，或者說兩者具有相同的數(shù)量級。當算法的時間復(fù)雜度T(n)和數(shù)據(jù)個數(shù)n無關(guān)系時，T(n)≤c*l，所以此時算法的時間復(fù)雜度T(n)=O(1)；當算法的時間復(fù)雜度了T(n)和數(shù)據(jù)個數(shù)n為線性關(guān)系時，T(n)≤c*n，所以此時算法的時間復(fù)雜度T(n)=O(n)；當算法的時間復(fù)雜度T(n)和數(shù)據(jù)個數(shù)n為平方關(guān)系時，T(n)≤c*n2，所以此時算法的時間復(fù)雜度T(n)=O(n2)；依此類推，還有，O(n3)、O(1bn)、O(2n)，等等。因此，分析一個算法中基本語句的執(zhí)行次數(shù)就可求出算法的時間復(fù)雜度。21第1章緒論例1.1設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運算程序段的時間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;/*基本語句1*/for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];/*基本語句2*/}解：設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有

f(n)=n2+n3

因程序段的時間復(fù)雜度T(n)=O(f(n))=n2+n3≤c*n3=O(n3)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(n3)。22第1章緒論例1.2設(shè)n為如下程序段處理的數(shù)據(jù)個數(shù)，求如下程序段的時間復(fù)雜度。

for(i=1;i<=n;i=2*i)printf(“i=％d\n”,i);／*基本語句*／解：設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有2f(n)≤n，即有f(n)≤lbn

因程序段的時間復(fù)雜度T(n)=f(n)≤lbn≤c*1bn=O(1bn)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(1bn)。在很多情況中，算法中數(shù)據(jù)元素的取值情況不同算法的時間復(fù)雜度也會不同。此時算法的時間復(fù)雜度應(yīng)是數(shù)據(jù)元素最壞情況下取值的時間復(fù)雜度或數(shù)據(jù)元素等概率取值情況下的平均(或稱期望)時間復(fù)雜度。23第1章緒論24解：這個算法的時間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。當某次排序過程中沒有任何兩個數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時算法將因標記flag=0不滿足循環(huán)條件而結(jié)束。但是，在最壞情況下，每次排序過程中都至少有兩個數(shù)組元素交換位置，因此，應(yīng)按最壞情況計算該算法的時間復(fù)雜度。設(shè)基本語句的執(zhí)行次數(shù)為f(n)，最壞情況下有f(n)≈n+4*n2/2因算法的時間復(fù)雜度T(n)=f(n)≈n+n2≤c*n2=O(n2)，其中。為常數(shù)，所以該算法的時間復(fù)雜度為O(n2)。例1.3下邊的算法是用冒泡排序法對數(shù)組a中的n個整數(shù)類型的數(shù)據(jù)元素(a[0]～a[n-1])從小到大排序的算法，求該算法的時間復(fù)雜度。VoidBubbleSort(inta[],intn){inti,j,flag=l;inttemp;for(i=1;i<n&&flag==l;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1]a[j+1]=temp;}}}}第1章緒論25例1.4下邊算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第i個位置的數(shù)組元素，要求當刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復(fù)雜度。其中，數(shù)組下標從0至n-1。intDelete(inta[],int*n,inti){intj;if(i<0||i>*n)return0;

/*刪除位置錯誤，失敗返回*/for(j=i+1;j<*n;j++)a[j-1]=a[j];／*移位填補*/(*n)--;／*數(shù)組元素個數(shù)減l*/return1;／*刪除成功返回*/}解：這個算法的時間復(fù)雜度隨刪除數(shù)據(jù)的位置不同而不同。當刪除最后一個位置的數(shù)組元素時有i=n-1，j=i+1=n,此時因不需移位填補而循環(huán)次數(shù)為0；當刪除倒數(shù)第2個位置的數(shù)組元素時有i=n-2，j=i+1=n-1，此時因只需移位填補一次而循環(huán)次數(shù)為1依此類推，當刪除第一個位置的數(shù)組元素時有i=0，j=i+1=1，此時因需移位填補n-1次而循環(huán)次數(shù)為n-1。此時算法的時間復(fù)雜度應(yīng)是刪除數(shù)據(jù)的位置等概率取值情況下的平均時間復(fù)雜度。第1章緒論

假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的(一般情況下均可作等概率假設(shè))，設(shè)pi為刪除第i個位置上數(shù)據(jù)元素的概率，則有pi=1／n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有:

因該算法的時間復(fù)雜度T(n)=E≤(n+1)／2≤c*n=O(n)，其中c為常數(shù)，所以該算法的時間復(fù)雜度為O(n)。26第1章緒論27常見的時間復(fù)雜度有以下幾種情形：O（1）常數(shù)時間O（lbn）對數(shù)時間O（n）線性時間O（nlbn）線性對數(shù)時間O（n2）平方時間O（n3）立方時間O（2n）指數(shù)時間上述的時間復(fù)雜度的優(yōu)劣次序如下（n≥16）O（1）<O（lbn）<O（n）<O（nlbn）<O（n2）<O（n3）<O（2n）變化曲線如圖1.5所示圖1.5常見的時間復(fù)雜度曲線第1章緒論1.4.5漸進的空間復(fù)雜度當實例特性n充分大時，需要的存儲空間體積將如何隨之變化，也可以像分析時間復(fù)雜度一樣，用大O表示法來表示。設(shè)S(n)是算法的漸進空間復(fù)雜度，在最壞情況下它可以表示為實例特性n的某個函數(shù)f(n)的數(shù)量級，記為：

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

這里所說的不是程序指令、常數(shù)、指針等所需要的存儲空間，也不是輸入數(shù)據(jù)所占用的存儲空間。而是為解決問題所需要的輔助存儲空間。例如，在排序算法中為移動數(shù)據(jù)所需的臨時工作單元，在遞歸算法中所需的遞歸工作棧等。通常，只有完成同一功能的幾個算法之間才具有可比性。例如，同樣是排序算法，待排序數(shù)據(jù)都是n個，作為輸入和存放這些數(shù)據(jù)的數(shù)組或鏈表結(jié)點也同樣都是n個，因此這些輸入數(shù)據(jù)所占用的存儲空間不用進行比較，可比較的只有那些輔助的或附加的存儲空間?？梢允褂么驩表示法來標記這些空間，用以比較各算法的優(yōu)劣。28第1章緒論29本章小結(jié)

本章介紹的主要內(nèi)容是應(yīng)用于整個數(shù)據(jù)結(jié)構(gòu)課程的基本概念和性能分析方法。學(xué)習(xí)本章內(nèi)容，將為后續(xù)章節(jié)的學(xué)習(xí)打下良好的基礎(chǔ)。1.基本概念和術(shù)語⑴數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。⑵數(shù)據(jù)對象(DataObject)具有相同屬性的數(shù)據(jù)元素集合。在數(shù)據(jù)對象中所有數(shù)據(jù)成員，即數(shù)據(jù)元素，都具有相同的性質(zhì)，它們是數(shù)據(jù)的子集。⑶數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：DataStructure={D，R)其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第1章緒論30⑷數(shù)據(jù)邏輯結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。是指從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)。它屬于用戶的視圖，是面向問題的。⑸數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)應(yīng)該如何在計算機中存放，是數(shù)據(jù)邏輯結(jié)構(gòu)的物理存儲方式，是屬于具體實現(xiàn)的視圖，是面向計算機的。⑹數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)，以及允許執(zhí)行操作的一種描述。⑺抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。例如，線性表數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。⑻算法(Algorithm)通常人們將算法定義為一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列。一個算法應(yīng)當具有以下特性：①有輸入。②有輸出。③確定性。④有窮性。⑤有效性。第1章緒論31

2.算法的分析⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標準。⑵算法的效率主要指算法執(zhí)行時計算機資源的消耗，包括存儲和運行時間的開銷，前者叫做算法的空間代價，后者叫做算法的時間代價。⑶算法效率的度量分為事前估計和后期測試。算法復(fù)雜性的度量屬于事前估計。它可分為空間復(fù)雜度度量和時間復(fù)雜度度量?？臻g復(fù)雜度(SpaceComplexity)是指當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占用的存儲空間也以某種單位由1增加到S(n)，則稱此算法的空間復(fù)雜度為S(n)；時間復(fù)雜度(TimeComplexity)是指當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所耗費的時間也以某種單位由1增加到T(n)，則稱此算法的時間復(fù)雜度為T(n)。后期測試主要通過在算法中的某些部位插裝時間函數(shù)(如clock())來測定算法完成某一規(guī)定功能所需的時間。

第1章緒論32

⑷算法的時間效率分析通常采用O(f(n))表示法(O(f(n))讀作大O的f(n))。定義：T(n)=O(f(n))當且僅當存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。⑸算法的時間復(fù)雜度是衡量一個算法好壞的重要指標。一般來說，具有多項式時間復(fù)雜度的算法是可接受、可實際使用的算法；具有指數(shù)時間復(fù)雜度的算法是只有當n足夠小時才可使用的算法。常見的時間復(fù)雜度有以下幾種情形：O（1）常數(shù)時間、O（lbn）對數(shù)時間、O（n）線性時間、O（nlbn）線性對數(shù)時間、O（n2）平方時間、O（n3）立方時間、O（2n）指數(shù)時間。上述的時間復(fù)雜度的優(yōu)劣次序如下（n≥16）O（1）<O（lbn）<O（n）<O（nlbn）<O（n2）<O（n3）<O（2n）第1章緒論33

習(xí)題一、填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的

以及它們之間的

和運算等的學(xué)科。2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是

的有限集合，R是D上的

有限集合。3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的

、數(shù)據(jù)的

和數(shù)據(jù)的

這三個方面的內(nèi)容。4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是

和

。5.線性結(jié)構(gòu)中元素之間存在

關(guān)系，樹形結(jié)構(gòu)中元素之間存在

關(guān)系，圖形結(jié)構(gòu)中元素之間存在

關(guān)系。6.在線性結(jié)構(gòu)中，第一個結(jié)點

前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點

后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。7.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有

結(jié)點，其余每個結(jié)點有且只有

個前驅(qū)結(jié)點；葉子結(jié)點沒有

結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以

。8.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以

。9.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是

。10.數(shù)據(jù)的運算最常用的有5種，它們分別是

。11.一個算法的效率可分為

效率和

效率。第1章緒論二、單項選擇題1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：（）A）一對多關(guān)系B）多對多關(guān)系C）多對一關(guān)系D）一對一關(guān)系2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的

結(jié)構(gòu)；（）A)存儲B)物理C)邏輯D)物理和存儲3.算法分析的目的是：（）A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進D)分析算法的易懂性和文檔性4.算法分析的兩個主要方面是：（）A)空間復(fù)雜性和時間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5.算法指的是：（）A)計算方法B)排序方法C)解決問題的有限運算序列D)調(diào)度方法6.算法必須具備輸入、輸出和

等5個特性。（）A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性34第1章緒論三、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？2.簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。四、分析下面各程序段的時間復(fù)雜度

1.for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;2.s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;3.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;35第2章線性表總體要求：熟悉線性表的定義熟悉線性表的抽象數(shù)據(jù)類型描述中各種操作的含義熟練掌握順序存儲線性表的建立、插入、刪除和定位算法熟練掌握鏈式存儲線性表的建立、插入、刪除和定位算法核心技能點：線性表各種存儲結(jié)構(gòu)應(yīng)用于實際問題的能力擴展技能點：線性表各種存儲結(jié)構(gòu)和算法C語言環(huán)境下的實現(xiàn)36第2章線性表相關(guān)知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言指針的知識C語言函數(shù)的知識C語言類型定義學(xué)習(xí)重點：熟悉線性表的定義熟悉線性表的抽象數(shù)據(jù)類型描述中各種操作的含義掌握線性表各種存儲結(jié)構(gòu)下算法的實現(xiàn)37第2章線性表2.1線性表實例及概念在計算機應(yīng)用中，線性表是一種常見的數(shù)據(jù)類型。諸如在文件、內(nèi)存、數(shù)據(jù)庫等管理系統(tǒng)中經(jīng)常需要對屬于線性表的數(shù)據(jù)類型進行處理。例如，表2.1表示的是一個有關(guān)學(xué)生情況的信息文件，文件中每個記錄對應(yīng)于一個學(xué)生的情況，它由學(xué)號、姓名、性別、年齡及籍貫等信息組成。

表2.1學(xué)生情況信息文件38第2章線性表

在這個實例中我們可以看到，文件中的記錄一個接著一個，它們之間存在著一種前后關(guān)系。為了研究這種數(shù)據(jù)結(jié)構(gòu)中元素間的關(guān)系，我們可以忽略記錄中的具體內(nèi)容，而只將它看作結(jié)構(gòu)中的一個元素。從數(shù)據(jù)結(jié)構(gòu)的視點來看，可以將上例中的整個信息文件看作為一個線性表，而文件中的每一個記錄可看作為線性表中的一個數(shù)據(jù)元素。一般，一個線性表是由n個元素組成的有限序列，可記作：L=（a0,a1,…an-1）其中，每個ai都是線性表L的數(shù)據(jù)元素。數(shù)據(jù)元素可以是各種各樣的。例如，它可以是一個數(shù)，一個符號或一個記錄等，但同一線性表中的元素必須屬于同一種數(shù)據(jù)對象。39第2章線性表

線性表的結(jié)構(gòu)是通過數(shù)據(jù)元素之間的相鄰關(guān)系來體現(xiàn)的。在線性表L中，元素ai-1與ai相鄰并位于ai之前，稱為ai的直接前驅(qū)，而ai+1與ai相鄰并位于ai之后，稱為ai的直接后繼。元素a0稱為L的最先元素，除最先元素外，L中的其他元素都有且僅有一個直接前驅(qū)；元素an-1稱為L的最后元素，除最后元素外，L中的其他元素都有且僅有一個直接后繼。元素ai是第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。線性表中的元素個數(shù)n稱為線性表的長度，長度為0的線性表稱為空表。為了對線性表及其有關(guān)操作的實現(xiàn)方法有比較直觀的了解，我們先要考慮線性表的存儲方式，其次是有關(guān)的操作。在以下幾節(jié)中我們將圍繞上述這些問題展開討論。40第2章線性表

2.2線性表的存儲方式在編制程序之前，我們總是要考慮一下在該程序中涉及到哪些數(shù)據(jù)，這些數(shù)據(jù)應(yīng)該以何種方式存儲到計算機中等問題。如果是使用某種程序設(shè)計語言來編程，則要考慮在該程序中應(yīng)定義哪些變量，這些變量的類型是什么或應(yīng)如何定義等等。那么，對于線性表應(yīng)采取什么存儲方式呢?線性表一般有順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)兩種存儲方式。按順序存儲結(jié)構(gòu)建立起來的線性表稱為順序表，按鏈式存儲結(jié)構(gòu)建立起來的線性表稱為線性鏈表。41第2章線性表

2.2.1線性表的順序存儲結(jié)構(gòu)在計算機內(nèi)可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一片連續(xù)的存儲區(qū)域，也就是用一組地址連續(xù)的存儲單元來依次存儲線性表的各個元素。線性表(a0，a1，a2，…，ai，…，an-1)的順序存儲結(jié)構(gòu)如圖2.1所示,這種存儲方式的特點是用存儲單元物理位置的相鄰來表示相鄰元素間的邏輯關(guān)系。42圖2.1線性表的順序存儲結(jié)構(gòu)示意圖第2章線性表43

假設(shè)線性表的每個元素需占用s個存儲單元，并以第一個存儲單元的地址作為數(shù)據(jù)元素的存儲位置，則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+s

一般來說，線性表中第i個元素ai的存儲地址為LOC(ai)=LOC(a0)+i*s式中，LOC(a0)為線性表的第一個元素a0的存儲地址，通常稱為線性表的開始地址或基地址。在線性表的順序存儲結(jié)構(gòu)中，應(yīng)該包括存儲數(shù)據(jù)元素的一個一維數(shù)組，取名為list，其長度可取一個適當?shù)淖畲笾礛axSize，另外還應(yīng)包括一個表示元素個數(shù)的整型變量，取其名為size，如圖2.2所示。第2章線性表44

使用C語言，我們可以定義以下的記錄(結(jié)構(gòu))類型來表示順序表，其類型名用SeqList表示。

MaxSize線性表可能達到的最大長度；typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;

在定義了順序表的類型SeqList之后，我們就可以定義屬于這種類型的線性表，例如：SeqListLa，Lb；此后，可在程序中引用線性表La，Lb的相應(yīng)成分，例如La.list[0]表示線性表的第一個元素，La.size表示線性表的當前長度等等。圖2-2線性表的類型定義示意圖第2章線性表452.2.2線性表的鏈式存儲結(jié)構(gòu)以上我們研究了線性表的順序存儲結(jié)構(gòu)，它的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，因此順序表中任一元素的存儲位置都可以用一個簡單直觀的公式來表示。然而，從另一方面看，這種存儲結(jié)構(gòu)也有許多不足之處：首先，我們難以確定適當?shù)拇鎯臻g的大小，如果指定得太小，則難以擴充；如果指定得太大，則存儲空間不能得到充分的利用。其次，在做插入或刪除時需移動大量元素。本節(jié)我們還將討論另一種存儲結(jié)構(gòu)——鏈式存儲結(jié)構(gòu)。由于它不要求邏輯關(guān)系上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)存在的缺點。第2章線性表46

線性表的鏈式存儲結(jié)構(gòu)也有很多種類。按鏈的類別來分類，可以分為單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表等；按結(jié)點的分配方式來分類，可以分為動態(tài)鏈表和靜態(tài)鏈表。下面分別進行介紹。1．單鏈表單鏈表存儲結(jié)構(gòu)是用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素。為了表示數(shù)據(jù)元素間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息外，還需存儲一個直接后繼的信息。圖2.3表示線性表（A,B,C,D）采用單鏈表存儲結(jié)構(gòu)時在內(nèi)存中的存儲狀態(tài)。圖2-3單鏈表存儲狀態(tài)示例第2章線性表47

在線性表的鏈式存儲結(jié)構(gòu)中，數(shù)據(jù)元素ai的存儲映像，稱為結(jié)點。單鏈表的結(jié)點包括兩個域：存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域。n個結(jié)點ai(0≤i≤n-1)的存儲映像鏈結(jié)成一個鏈表，即為線性表的鏈式存儲結(jié)構(gòu)。線性表鏈式存儲結(jié)構(gòu)的特點是：數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的。由于此鏈表的每個結(jié)點中只包含一個指針域故稱為單鏈表。對單鏈表的存取必須從頭指針開始進行，頭指針指向鏈表中的第一個結(jié)點。同時由于最后一個數(shù)據(jù)元素沒有直接后繼，因此線性表中最后一個結(jié)點的指針域為“空”(NULL)。第2章線性表48

由于一個線性鏈表的鏈頭指針可以確定整個的線性鏈表，因此我們往往用這個鏈頭指針來表示它所指向的線性鏈表。有時，為了適應(yīng)算法的需要，需在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針，此時，單鏈表的頭指針指向頭結(jié)點。帶頭結(jié)點的單鏈表邏輯結(jié)構(gòu)表示如圖2.4所示。（提示：為了方便表示，本書以后的鏈表都用邏輯結(jié)構(gòu)表示）圖2-4帶頭結(jié)點的單鏈表第2章線性表49

為了表示線性表的鏈式存儲結(jié)構(gòu)，首先要定義存放數(shù)據(jù)元素的結(jié)點類型，其次是指向這種結(jié)點的指針類型，然后我們就可以定義一個屬于這種類型的指針型變量并使其指向頭結(jié)點來表示一個線性表。假設(shè)結(jié)點類型名為SLNode，結(jié)點指針類型名為SLlink，結(jié)點類型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類型為DataType，我們就可以用以下的類型及變量定義來表示線性表。

typedefstructNode{DataTypedata;structNode*next;}SLNode,*SLlink;

在定義了單鏈表的結(jié)點類型SLNode及結(jié)點指針類型SLlink之后，就可定義一個SLlink型的變量來表示屬于這種類型的線性表，例如：SLlinkhead；在相關(guān)的程序中，先使head指向某一個單鏈表的頭結(jié)點或第一個結(jié)點，然后就可對這個用head所表示的單鏈表進行各種操作。第2章線性表50

2．靜態(tài)鏈表上述這種存儲結(jié)構(gòu)的特點是動態(tài)地生成結(jié)點，通過存放在結(jié)點中的指針域?qū)⒔Y(jié)點中的數(shù)據(jù)元素鏈接起來。但在有的高級語言中沒有指針類型，也不能動態(tài)地生成結(jié)點。在這種場合下，我們可以借用一個一維數(shù)組來存儲線性鏈表。這種數(shù)組的類型及變量定義如下：

MaxSize為鏈表可能的最大長度；

Typedefstruct{DataTypedata;intnext;}node;nodeslspace[MaxSize]；在上述定義中，變量slspace是一個結(jié)構(gòu)型的數(shù)組，用于存放鏈表中的結(jié)點。該數(shù)組中每一個元素表示線性鏈表中的一個結(jié)點。這種結(jié)點由data與next兩個域組成，data部分存放數(shù)據(jù)元素，而next部分存放指示下一個結(jié)點在數(shù)組中位置的整型指示器。使用這種存儲方式所存儲的線性鏈表稱為靜態(tài)鏈表。第2章線性表513．雙向循環(huán)鏈表對于單鏈表來說，在其每個結(jié)點中設(shè)置一個指針，指針指向該結(jié)點的后繼結(jié)點，因此鏈表中最后一個結(jié)點的指針域必定為空。單鏈表存儲結(jié)構(gòu)的這種特點決定了對它的訪問方式。我們只能從單鏈表的鏈頭開始對單鏈表中的數(shù)據(jù)元素進行訪問而不能從其中的任一結(jié)點開始，其次我們只能由前向后地對單鏈表進行訪問，而不能由后向前地進行訪問。這對某些應(yīng)用來說是不方便的，為此我們要對單鏈表的存儲結(jié)構(gòu)進行一些改造。首先我們使鏈表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表就形成一個環(huán)，這樣形成的鏈表稱為循環(huán)鏈表。對于循環(huán)鏈表，可以從鏈表中的任一點出發(fā)找到鏈表中所有的其他結(jié)點。循環(huán)鏈表的結(jié)構(gòu)形式如圖2.5所示。第2章線性表52圖2-5循環(huán)鏈表結(jié)構(gòu)示意圖(a)非空表(b)空表第2章線性表53

在對循環(huán)鏈表進行處理時所要注意的是：算法中判別當前指針p是否達到鏈尾的條件不是判別p是否等于NULL，而是要判別p是否等于頭指針。其他方面與單鏈表基本一致。其次，我們在鏈表的結(jié)點中增加了一個指向前驅(qū)結(jié)點的指針域，這樣形成的鏈表稱為雙向鏈表。對于雙向鏈表，既可以對數(shù)據(jù)元素由前向后地進行訪問，又可以由后向前地進行訪問。雙向鏈表的結(jié)點及結(jié)點指針類型可定義如下：

typedefstructNode{DataTypedata;structNode*prior;structNode*next;}DLNode,*DLlink;第2章線性表54

如果線性鏈表的存儲結(jié)構(gòu)中同時采用上述兩種鏈接方式，則就形成雙向循環(huán)鏈表。在圖2.6中所表示的是線性表d1=(A，B，C)的雙向循環(huán)鏈表的存儲結(jié)構(gòu)圖。圖2-6雙向循環(huán)鏈表的示意圖第2章線性表552.3線性表的有關(guān)操作在確定了線性表的存儲結(jié)構(gòu)后，應(yīng)考慮對線性表所施行的操作。從邏輯上講可以對線性表施行數(shù)據(jù)元素的插入、刪除等各種操作，但這些操作實現(xiàn)過程及執(zhí)行效率又完全取決于數(shù)據(jù)的存儲結(jié)構(gòu)。下面我們按順序表、單鏈表以及雙向循環(huán)鏈表幾種存儲方式來介紹有關(guān)算法的實現(xiàn)過程。2.3.1順序表的操作實現(xiàn)順序表是以順序存儲方式存儲的線性表。如前所述，順序存儲方式的特點是用一片連續(xù)的存儲區(qū)域依次存儲線性表的各個元素。在這種存儲方式下，線性表的某些操作容易實現(xiàn)。下面著重討論在順序存儲結(jié)構(gòu)方式下，線性表的查找(求位序)、插入及刪除等操作的實現(xiàn)。第2章線性表561.查找(求位序)函數(shù)線性表的查找函數(shù)是指在指定的線性表L中查找指定的元素x。若L中存在其值與x相等的數(shù)據(jù)元素，則函數(shù)值為該數(shù)據(jù)元素在線性表中的位序，否則為-1。從上述所說明的查找函數(shù)的含義中我們可以看到，對查找的函數(shù)應(yīng)該設(shè)置兩個參數(shù)，即在參數(shù)中指定被查找的線性表及所查找的元素。假設(shè)被查找的線性表SeqlistL在本函數(shù)之外已說明，而所查找的元素為DataTypex，查找函數(shù)取名為ListLocate，則該函數(shù)可表示為:intListLocate(SeqlistL,DataTypex)；第2章線性表57

功能是:在線性表L中查找數(shù)據(jù)元素x。若L中存在與x相等的數(shù)據(jù)元素，則返回該數(shù)據(jù)元素在線性表中的序號，否則返回-1。處理過程:從第一個元素起，依次將L中的元素與x進行比較，直至某一個元素與x比較相等，則返回該元素的序號，或與n個元素全比較都不相等，則返回-1。程序如下：

intListLocate(SeqlistL,DataTypex){inti=0;while(i<L.size&&L.list[i]!=x)i++;if(i<L.size)return(i);elsereturn(-1);}

在上述程序中，while循環(huán)的條件是必須同時滿足(i<=L.size&&L.data[i]!=x)。其中，第一個條件表示還沒有比較完，第二個條件表示還沒有查到。只有在這兩個條件同時滿足時才能繼續(xù)往下查找。第2章線性表58

2．插入操作如圖2.7所示，線性表的插入操作是指在線性表的第i-1個數(shù)據(jù)元素與第i個數(shù)據(jù)元素之間插入一個新的元素。由于我們所采用的是順序的存儲結(jié)構(gòu)，插入后元素間的邏輯關(guān)系會發(fā)生變化，為了仍然保持邏輯上相鄰的數(shù)據(jù)元素在存儲位置上也相鄰，則必須將第i號到第n-1號元素向后移動一個位置，除非插入位置是i=n。插入后線性表的長度應(yīng)該由原來的n變?yōu)閚+1。圖2.7順序表插入操作示意圖

(a)插入前(b)插入后第2章線性表59

從上述所說明的插入操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中指定所插入的線性表、插入位置及插入的元素。假設(shè)所插入的線性表SeqList*L在本操作之外已說明，而插入位置及插入的元素分別為inti及DataTypex，插入操作取名為ListInsert，則該操作可表示為：

intListInsert(SeqList*L,inti,DataTypex)；功能為：在線性表*L中的第i號元素之前插入數(shù)據(jù)元素x，其中，0≤i≤L->size操作的處理過程為：⑴檢查插入位置i是否合法；⑵將第i號到第L->size-1號元素向后移動一個位置；⑶在位置i處存入元素x。第2章線性表60程序如下：intListInsert(SeqList*L,inti,DataTypex){intj;if(L->size>=MaxSize-1){printf("順序表已滿無法插入!\n"); return0;}elseif(i<0||i>L->size+1){printf("參數(shù)i不合法!\n");return0;}Else{for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*為插入做準備*/L->list[i]=x;/*插入*/L->size++;/*元素個數(shù)加1*/return1;}}在上述程序中我們要注意的是元素后移時應(yīng)該從最后一個元素開始移動，所以for語句采用了j--形式。第2章線性表61

3．刪除操作如圖2.8所示，線性表的刪除操作是指在線性表中刪除其中的第i個數(shù)據(jù)元素。由于我們所采用的是順序的存儲結(jié)構(gòu)，刪除后元素間的邏輯關(guān)系會發(fā)生變化，為了仍然保持邏輯上相鄰的數(shù)據(jù)元素在存儲位置上也相鄰，則必須將第i+1號到第n-1號元素向前移動一個位置，除非刪除的是最后一個元素。刪除后線性表的長度應(yīng)該由原來的n變?yōu)閚-1。圖2-8順序表刪除操作示意圖(a)刪除前；(b)刪除后第2章線性表62

從上述所說明的刪除操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中要指定一個線性表及刪除元素的序號。假設(shè)作為操作對象的線性表SeqList*L在本操作之外已說明，而刪除元素的序號用i表示，刪除元素DataType*x，刪除操作取名為ListDelete，則該操作可表示為：

intListDelete(SeqList*L,inti,DataType*x)；功能為：在順序表*L中刪除第i號元素，其中，

0≤i≤L->size-1

處理過程為：⑴檢查刪除位置i是否合法；⑵將第i+1號到第L->size-1號元素向前移動一個位置；⑶數(shù)據(jù)元素個數(shù)減1。第2章線性表63程序如下：intListDelete(SeqList*L,inti,DataType*x) {intj;if(L->size==0){printf("順序表已空無數(shù)據(jù)元素可刪!\n");return0;}elseif(i<0||i>L->size-1){printf("參數(shù)i不合法");return0;}else{*x=L->list[i];/*保存刪除的元素到參數(shù)x中*/for(j=i+1;j<L->size;j++)L->list[j-1]=L->list[j];/*依次前移*/L->size--;/*數(shù)據(jù)元素個數(shù)減1*/return1;}}第2章線性表64

從上述插入及刪除算法可見，當在順序結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要消耗在移動元素上(換句話說，移動元素的操作為預(yù)估算法時間復(fù)雜度的基本操作)，而移動元素的個數(shù)取決于插入或刪除元素的位置。以插入算法為例，當插入位置i為n時，移動次數(shù)為0次；當插入位置i為0時，移動次數(shù)為n次，平均次數(shù)為n/2，可表示成線性階O(n)。第2章線性表65

4.逆置操作線性表的逆置操作是指對指定的線性表進行逆置，即反向排列該線性表中的所有數(shù)據(jù)元素，逆置后線性表的長度仍保持不變。對該操作應(yīng)通過設(shè)置一個參數(shù)來指定一個線性表。假設(shè)參數(shù)為SeqList*L逆置操作取名為Listinver，則該操作可表示為：

ListInver(SeqList*L)；功能為：對順序表L中的所有元素進行逆置。處理過程為：是將整個元素的序列分為前后兩部分，然后將這兩部分中所有對應(yīng)的元素進行交換。第2章線性表66程序如下：Listinver(SeqList*L){inti,m,n;DataTypetemp;n=L->size;m=n/2;for(i=0;i<m;i++){temp=L->list[i];L->list[i]=L->list[n-i-1];L->list[n-i-1]=temp;}}從上述逆置過程可以看到，交換的次數(shù)是L->size/2，與元素的個數(shù)有關(guān)。第2章線性表672.3.2單鏈表的操作實現(xiàn)線性鏈表即以鏈式存儲方式存儲的線性表。如前所述，鏈式存儲方式的特點是用一組任意的存儲單元來存儲線性表的各個元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由指針來表示的。在這種存儲方式下，線性表的操作可通過對指針的訪問或改變指針來實現(xiàn)。在下面的討論中，線性鏈表主要是指單鏈表，主要討論在帶表頭單鏈表存儲結(jié)構(gòu)方式下，線性表的取元素操作及插入、刪除等操作的實現(xiàn)。第2章線性表68

1.取元素操作取元素操作是指在指定的線性表L中取其第i個數(shù)據(jù)元素。若0≤i≤ListLength(L)-1，則函數(shù)值為1，否則為0。對該操作我們一般應(yīng)設(shè)置三個參數(shù)，即在參數(shù)中指定線性表、所取元素的序號及帶回值的變量。在線性鏈表的存儲結(jié)構(gòu)下，線性表可以用指向鏈頭的指針型變量來表示。假設(shè)指定的線性表SLlinkhead在本操作之外已說明，而元素序號為inti，取元素操作取名為SLinkGet，則該操作可表示為：

intSLinkGet(SLlinkhead,inti,DataType*x)；功能為：取帶頭結(jié)點的單鏈表head中的第i個數(shù)據(jù)元素。若0≤i≤ListLength(L)-1，則返回1，表中的第i個數(shù)據(jù)元素由x帶回，否則返回0。操作的處理過程為：⑴初始化，使指針p指向第一個元素的結(jié)點；⑵是指針逐個后移直至指針指向第i個元素結(jié)點或指針為空；⑶若第i個元素結(jié)點存在則由x帶回該元素返回1，否則返回0。第2章線性表69程序如下：intSLinkGet(SLlinkhead,inti,DataType*x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類似，只是不刪除數(shù)據(jù)元素ai結(jié)點*/{SLNode*p;intj;p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next; j++; }if(j!=i){printf("取元素位置參數(shù)錯！");return0;}*x=p->data;return1;}第2章線性表70

2.插入操作線性鏈表插入操作是指對某一個線性鏈表，在序號為i的結(jié)點之前插入一個指定元素值的新結(jié)點。假設(shè)在序號為i-1，i兩個結(jié)點之間插入一個數(shù)據(jù)元素值為x的新結(jié)點，已知p為該鏈表中指向ai-1結(jié)點的指針，如圖2.9所示。圖2.9帶頭結(jié)點的線性鏈表插入操作第2章線性表71

為插入數(shù)據(jù)元素x，首先要生成一個數(shù)據(jù)域為x的結(jié)點，然后插入在單鏈表中。根據(jù)插入操作的邏輯定義，需要修改ai-1結(jié)點的指針域，使其指向結(jié)點x，而結(jié)點x中的指針域應(yīng)指向ai結(jié)點，從而實現(xiàn)三個元素ai-1，ai和x之間邏輯關(guān)系的變化。假設(shè)p為指向結(jié)點ai-1的指針，q為指向結(jié)點x的指針，則上述指針修改可用語句描述為：

q->next=p->next；p->next=q； 從上述說明的插入操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中指定所插入的線性鏈表、插入位置及插入的元素。假設(shè)所插入的線性鏈表SLlinkhead在本操作之外已說明，而插入位置及插入的元素分別為inti,DataTypex，插入操作取名為SLinkInsert，則該操作可表示為：

intSLinkInsert(SLNode*head,inti,DataTypex)；功能為：在帶頭結(jié)點的單鏈表head中的第i號結(jié)點之前插入數(shù)據(jù)元素值為x的新結(jié)點。操作的處理過程為：⑴尋找第i-1個結(jié)點，使指針p指向該結(jié)點；⑵若由于i不合理而找不到相應(yīng)的結(jié)點，則輸出信息，否則，生成一個新結(jié)點q,并將q插入到結(jié)點p之后。第2章線性表72程序如下：intSLinkInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;/*p指向頭結(jié)點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&j<i-1)/*指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);q->data=x;q->next=p->next;/*給指針q->next賦值*/p->next=q;/*給指針p->next重新賦值*/return1;}第2章線性表73

3.刪除操作線性鏈表的刪除操作是指刪除線性鏈表中的第i號結(jié)點。如圖2.10所示，p為指向結(jié)點ai-1的指針。為在單鏈表中實現(xiàn)元素之間邏輯關(guān)系的變化，僅需修改結(jié)點p中的指針域即可，指針修改可用語句描述為：

s=p->next;/*指針s指向數(shù)據(jù)元素ai結(jié)點*/*x=s->data;/*把指針s所指結(jié)點的數(shù)據(jù)元素域值賦予x*/p->next=p->next->next;圖2.10帶頭結(jié)點的線性鏈表刪除操作第2章線性表74

從上述說明的刪除操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中要指定一個線性鏈表及刪除元素的結(jié)點序號。假設(shè)作為操作對象的線性鏈表SLNodehead在本操作之外已說明，而刪除元素的序號用inti表示，刪除操作取名為SLinkDelete,由DataType*x帶回刪除元素，則該操作可表示為：

intSLinkDelete(SLNode*head,intiDataType*x)；功能為：在帶頭結(jié)點的單鏈表head中刪除第i個結(jié)點并返回該結(jié)點中的元素值。處理過程為：⑴尋找第i號結(jié)點，使指針p指向該結(jié)點的前驅(qū)結(jié)點；⑵若由于i不合理而找不到相應(yīng)的結(jié)點，則輸出信息，返回0。否則，改變p的指針域，使得第i號結(jié)點從鏈表中被刪除，釋放該結(jié)點并返回1。第2章線性表75程序如下：intSLinkDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;/*p指向頭結(jié)點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)/*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}s=p->next; /*指針s指向數(shù)據(jù)元素ai結(jié)點*/*x=s->data; /*把指針s所指結(jié)點的數(shù)據(jù)元素域值賦予x*/p->next=p->next->next;/*把數(shù)據(jù)元素ai結(jié)點從單鏈表中刪除指*/free(s); /*釋放指針s所指結(jié)點的內(nèi)存空間*/return1;}第2章線性表76

4.逆置操作單鏈表的逆置操作是指對一個用帶頭結(jié)點的鏈表表示的線性表進行逆置。當線性表采用順序存儲結(jié)構(gòu)表示時，可借助數(shù)據(jù)元素的交換來完成逆置操作。而當采用單鏈表存儲結(jié)構(gòu)時，則以修改指針來完成逆置操作。單鏈表逆置前后的狀態(tài)如圖2.11所示。圖2.11單鏈表逆置操作示意圖第2章線性表77

在該操作中所涉及的參數(shù)是指定單鏈表的鏈頭指針SLNode*head。假設(shè)本操作取名為SLinkinver，則逆置操作可表示為：

SLinkinver(SLNode*head)；功能是a0與an-1互換，a1與an-2互換…依次類推。該操作在處理過程中，如果把逆置后的鏈表看成是一個新的鏈表，則處理過程如下：⑴建立一個新的鏈表作為逆置后的鏈表(使用原帶頭結(jié)點)，其初始狀態(tài)為空表；⑵依次從原鏈表中取下一個結(jié)點，并將該結(jié)點從鏈頭插入到新的鏈表中；

⑶重復(fù)過程⑵，直至原鏈表中的結(jié)點全部取完。第2章線性表78程序如下：SLinkinver(SLNode*head){SLNode*p,*s;p=head->next;head->next=NULL;while(p!=NULL){s=p;p=p->next;s->next=head->next;head->next=s;}}第2章線性表79

5．建鏈表操作線性鏈表的建表操作是指由一個一維數(shù)組a中的n個元素的值，建立一個長度為n的線性鏈表，其操作的含義如圖2.12所示。圖2.12建表操作示意圖第2章線性表80

在該操作中所涉及的參數(shù)是鏈表的長度n，存放n個元素的一維數(shù)組a中，表示所生成線性鏈表的鏈頭指針為head。假設(shè)這些參數(shù)均在本操作之外已說明，本操作取名為CrtLink，則建表操作表示為：

CrtLink(SLNode*head,intn,DataTypea[])；功能是建立一個由head指向的長度為n的單鏈表(帶頭結(jié)點)，并使其n個數(shù)據(jù)元素的值依次等于一維數(shù)組a中的n個元素的值。該操作的處理過程為：⑴建立一個空表；⑵生成一個結(jié)點，按從后到前上的次序從數(shù)組a中取出元素作為結(jié)點中的元素值，然后從鏈頭插入該結(jié)點；⑶重復(fù)執(zhí)行過程⑵，直至生成n個結(jié)點。第2章線性表81程序如下：CrtLink(SLNode*head,intn,DataTypea[]){SLNode*p;inti;head=(SLNode*)malloc(sizeof(SLNode));head.next=NULL;for(i=n-1;i>=0;i--){p=(SLNode*)malloc(