數(shù)據(jù)結(jié)構(gòu) 課件 (袁輝) 第1-6章 緒論 -數(shù)組

第1章緒論總體要求：理解什么是數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(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ù)類型理解算法的定義、算法的特性、算法的時(shí)間代價(jià)和算法的空間代價(jià)熟悉用C語言描述算法的方法，能夠使用C語言編寫程序核心技能點(diǎn)：具有抽象數(shù)據(jù)的能力具有C語言編程的能力具有算法的時(shí)間代價(jià)和算法的空間代價(jià)靜態(tài)分析能力1第1章緒論2擴(kuò)展技能點(diǎn)：抽象數(shù)據(jù)類型的應(yīng)用能力算法的時(shí)間代價(jià)和算法的空間代價(jià)方法應(yīng)用實(shí)際的能力相關(guān)知識(shí)點(diǎn)：C語言的基本語句C語言函數(shù)的編寫格式及功能C語言標(biāo)識(shí)符的命名規(guī)則C語言類型定義數(shù)學(xué)極限的知識(shí)第1章緒論3學(xué)習(xí)重點(diǎn)：熟練掌握算法的定義、算法的特性、算法的時(shí)間代價(jià)和算法的空間代價(jià)分析掌握數(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ù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)大致可分為兩類：一類是數(shù)值性數(shù)據(jù)，包括整數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)、雙精度數(shù)等，主要用于工程和科學(xué)計(jì)算，以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串，以及文字、圖形、圖像、語音等的數(shù)據(jù)。從傳統(tǒng)的觀點(diǎn)來看，在解決應(yīng)用問題時(shí)，總把數(shù)據(jù)按其性質(zhì)歸類到一些稱之為數(shù)據(jù)對(duì)象(DataObject)的集合中。在數(shù)據(jù)對(duì)象中所有數(shù)據(jù)成員，即數(shù)據(jù)元素，都具有相同的性質(zhì)，它們是數(shù)據(jù)的子集。例如，整數(shù)數(shù)據(jù)對(duì)象可以是集合N={0,1,2,3,…}。英文字母數(shù)據(jù)對(duì)象可以是集合LETTER={A,B,…,Z}。第1章緒論5

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

Data

Structure={D，R}

其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(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ù)元素)都按某種次序排列在一個(gè)序列中，如圖1.2所示。對(duì)于線性結(jié)構(gòu)中每一數(shù)據(jù)元素，除第一個(gè)元素外，其它每一個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)，第一個(gè)數(shù)據(jù)元素沒有直接前驅(qū)；除最后一個(gè)元素外，其他每一個(gè)元素都有一個(gè)且僅有一個(gè)直接后繼。第1章緒論7圖1.2線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系第1章緒論8

在非線性結(jié)構(gòu)中各個(gè)數(shù)據(jù)成員不再保持在一個(gè)線性序列中，每個(gè)數(shù)據(jù)成員可能與零個(gè)或多個(gè)其他數(shù)據(jù)成員發(fā)生聯(lián)系。根據(jù)關(guān)系的不同，可分為層次結(jié)構(gòu)和群結(jié)構(gòu)。層次結(jié)構(gòu)是按層次劃分的數(shù)據(jù)元素的集合，指定層次上的元素，可以有零個(gè)或多個(gè)處于下一個(gè)層次上的、直接的所屬下層元素。在第7章將重點(diǎn)討論樹形結(jié)構(gòu)，它是典型的層次結(jié)構(gòu)。樹中的元素叫做結(jié)點(diǎn)。樹可以為空，也可以不為空。若樹不為空，它有一個(gè)叫做根的結(jié)點(diǎn)，其他結(jié)點(diǎn)都是從它派生出來的。除根以外，每一個(gè)結(jié)點(diǎn)都有一個(gè)處于該結(jié)點(diǎn)直接上層的結(jié)點(diǎn)。樹的結(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)所示。它是由圖的頂點(diǎn)集合和連接頂點(diǎn)的邊集合組成。還有一種圖的特殊形式，即網(wǎng)絡(luò)結(jié)構(gòu)。它給每條邊賦予一個(gè)權(quán)值，這個(gè)權(quán)值指明了在遍歷圖時(shí)經(jīng)過此邊時(shí)的耗費(fèi)。例如，在圖1．4(b)中，頂點(diǎn)代表城市，賦予邊的權(quán)值表示兩個(gè)城市之間的距離。第1章緒論101.2抽象數(shù)據(jù)類型1.2.1數(shù)據(jù)類型在程序設(shè)計(jì)語言中介紹過各種數(shù)據(jù)類型。以C語言為例，有5種基本的數(shù)據(jù)類型：字符型、整型、浮點(diǎn)型、雙精度型和無值，分別用保留字char，int，float，double和void標(biāo)識(shí)。這些數(shù)據(jù)類型不但規(guī)定了使用該類型時(shí)的取值范圍，而且還規(guī)定了該類型可以用的一組操作。例如，與整型相關(guān)的操作有+，-，*，／，與浮點(diǎn)型相關(guān)的操作也有+，-，*，／。然而整型的“／”操作與浮點(diǎn)型的“／”操作雖然形式一樣，卻是兩個(gè)不同的操作。如整型運(yùn)算3／2的運(yùn)算結(jié)果為1，浮點(diǎn)型運(yùn)算3／2的運(yùn)算結(jié)果為1.5。因?yàn)椴僮鳌埃庇糜趲讉€(gè)數(shù)據(jù)類型，故稱它是一種重載操作。事實(shí)上，數(shù)據(jù)類型是對(duì)數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)，以及允許執(zhí)行操作的一種描述。第1章緒論1.2.2數(shù)據(jù)抽象與抽象數(shù)據(jù)類型一、抽象數(shù)據(jù)類型定義（ADT）作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實(shí)世界。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。定義：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲(chǔ)方式。定義它的人同樣不必要關(guān)心它如何存儲(chǔ)。11第1章緒論抽象數(shù)據(jù)類型表示法：

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

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

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

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

數(shù)據(jù)對(duì)象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}除第一個(gè)和最后一個(gè)外，每個(gè)元素有唯一的直接前趨和唯一的直接后繼?；静僮鱈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ū)ο笥^點(diǎn)方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計(jì)語言有Delphi、Java、C++等。從面向過程觀點(diǎn)方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計(jì)語言有標(biāo)準(zhǔn)Pascal、標(biāo)準(zhǔn)C、基本BASIC語言等。從另一個(gè)角度來看，很多算法是面向過程的。對(duì)于熟悉面向過程開發(fā)方法的讀者，可方便地從傳統(tǒng)的面向過程方法過渡到用面向?qū)ο蠓椒ㄩ_發(fā)程序。因此，本書采用C語言來描述各種數(shù)據(jù)結(jié)構(gòu)。13第1章緒論

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

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

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

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

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

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

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

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

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

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

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

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

程序清單程序演示

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

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

程序步的統(tǒng)計(jì)

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

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

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

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

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

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

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

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

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

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

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

第1章緒論32

⑷算法的時(shí)間效率分析通常采用O(f(n))表示法(O(f(n))讀作大O的f(n))。定義：T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對(duì)所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。⑸算法的時(shí)間復(fù)雜度是衡量一個(gè)算法好壞的重要指標(biāo)。一般來說，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可接受、可實(shí)際使用的算法；具有指數(shù)時(shí)間復(fù)雜度的算法是只有當(dāng)n足夠小時(shí)才可使用的算法。常見的時(shí)間復(fù)雜度有以下幾種情形：O（1）常數(shù)時(shí)間、O（lbn）對(duì)數(shù)時(shí)間、O（n）線性時(shí)間、O（nlbn）線性對(duì)數(shù)時(shí)間、O（n2）平方時(shí)間、O（n3）立方時(shí)間、O（2n）指數(shù)時(shí)間。上述的時(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ù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的

以及它們之間的

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

的有限集合，R是D上的

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

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

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

這三個(gè)方面的內(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)中，第一個(gè)結(jié)點(diǎn)

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

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

結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有

個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有

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

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

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

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

。11.一個(gè)算法的效率可分為

效率和

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

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

等5個(gè)特性。（）A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性34第1章緒論三、簡答題1.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？2.簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。四、分析下面各程序段的時(shí)間復(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ù)類型描述中各種操作的含義熟練掌握順序存儲(chǔ)線性表的建立、插入、刪除和定位算法熟練掌握鏈?zhǔn)酱鎯?chǔ)線性表的建立、插入、刪除和定位算法核心技能點(diǎn)：線性表各種存儲(chǔ)結(jié)構(gòu)應(yīng)用于實(shí)際問題的能力擴(kuò)展技能點(diǎn)：線性表各種存儲(chǔ)結(jié)構(gòu)和算法C語言環(huán)境下的實(shí)現(xiàn)36第2章線性表相關(guān)知識(shí)點(diǎn)：C語言數(shù)組的知識(shí)C語言結(jié)構(gòu)體的知識(shí)C語言指針的知識(shí)C語言函數(shù)的知識(shí)C語言類型定義學(xué)習(xí)重點(diǎn)：熟悉線性表的定義熟悉線性表的抽象數(shù)據(jù)類型描述中各種操作的含義掌握線性表各種存儲(chǔ)結(jié)構(gòu)下算法的實(shí)現(xiàn)37第2章線性表2.1線性表實(shí)例及概念在計(jì)算機(jī)應(yīng)用中，線性表是一種常見的數(shù)據(jù)類型。諸如在文件、內(nèi)存、數(shù)據(jù)庫等管理系統(tǒng)中經(jīng)常需要對(duì)屬于線性表的數(shù)據(jù)類型進(jìn)行處理。例如，表2.1表示的是一個(gè)有關(guān)學(xué)生情況的信息文件，文件中每個(gè)記錄對(duì)應(yīng)于一個(gè)學(xué)生的情況，它由學(xué)號(hào)、姓名、性別、年齡及籍貫等信息組成。

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

在這個(gè)實(shí)例中我們可以看到，文件中的記錄一個(gè)接著一個(gè)，它們之間存在著一種前后關(guān)系。為了研究這種數(shù)據(jù)結(jié)構(gòu)中元素間的關(guān)系，我們可以忽略記錄中的具體內(nèi)容，而只將它看作結(jié)構(gòu)中的一個(gè)元素。從數(shù)據(jù)結(jié)構(gòu)的視點(diǎn)來看，可以將上例中的整個(gè)信息文件看作為一個(gè)線性表，而文件中的每一個(gè)記錄可看作為線性表中的一個(gè)數(shù)據(jù)元素。一般，一個(gè)線性表是由n個(gè)元素組成的有限序列，可記作：L=（a0,a1,…an-1）其中，每個(gè)ai都是線性表L的數(shù)據(jù)元素。數(shù)據(jù)元素可以是各種各樣的。例如，它可以是一個(gè)數(shù)，一個(gè)符號(hào)或一個(gè)記錄等，但同一線性表中的元素必須屬于同一種數(shù)據(jù)對(duì)象。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中的其他元素都有且僅有一個(gè)直接前驅(qū)；元素an-1稱為L的最后元素，除最后元素外，L中的其他元素都有且僅有一個(gè)直接后繼。元素ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。線性表中的元素個(gè)數(shù)n稱為線性表的長度，長度為0的線性表稱為空表。為了對(duì)線性表及其有關(guān)操作的實(shí)現(xiàn)方法有比較直觀的了解，我們先要考慮線性表的存儲(chǔ)方式，其次是有關(guān)的操作。在以下幾節(jié)中我們將圍繞上述這些問題展開討論。40第2章線性表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

功能是:在線性表L中查找數(shù)據(jù)元素x。若L中存在與x相等的數(shù)據(jù)元素，則返回該數(shù)據(jù)元素在線性表中的序號(hào)，否則返回-1。處理過程:從第一個(gè)元素起，依次將L中的元素與x進(jìn)行比較，直至某一個(gè)元素與x比較相等，則返回該元素的序號(hào)，或與n個(gè)元素全比較都不相等，則返回-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)的條件是必須同時(shí)滿足(i<=L.size&&L.data[i]!=x)。其中，第一個(gè)條件表示還沒有比較完，第二個(gè)條件表示還沒有查到。只有在這兩個(gè)條件同時(shí)滿足時(shí)才能繼續(xù)往下查找。第2章線性表58

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

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

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

intListInsert(SeqList*L,inti,DataTypex)；功能為：在線性表*L中的第i號(hào)元素之前插入數(shù)據(jù)元素x，其中，0≤i≤L->size操作的處理過程為：⑴檢查插入位置i是否合法；⑵將第i號(hào)到第L->size-1號(hào)元素向后移動(dòng)一個(gè)位置；⑶在位置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];/*為插入做準(zhǔn)備*/L->list[i]=x;/*插入*/L->size++;/*元素個(gè)數(shù)加1*/return1;}}在上述程序中我們要注意的是元素后移時(shí)應(yīng)該從最后一個(gè)元素開始移動(dòng)，所以for語句采用了j--形式。第2章線性表61

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

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

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

0≤i≤L->size-1

處理過程為：⑴檢查刪除位置i是否合法；⑵將第i+1號(hào)到第L->size-1號(hào)元素向前移動(dòng)一個(gè)位置；⑶數(shù)據(jù)元素個(gè)數(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ù)元素個(gè)數(shù)減1*/return1;}}第2章線性表64

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

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

ListInver(SeqList*L)；功能為：對(duì)順序表L中的所有元素進(jìn)行逆置。處理過程為：是將整個(gè)元素的序列分為前后兩部分，然后將這兩部分中所有對(duì)應(yīng)的元素進(jìn)行交換。第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，與元素的個(gè)數(shù)有關(guān)。第2章線性表672.3.2單鏈表的操作實(shí)現(xiàn)線性鏈表即以鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)的線性表。如前所述，鏈?zhǔn)酱鎯?chǔ)方式的特點(diǎn)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表的各個(gè)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由指針來表示的。在這種存儲(chǔ)方式下，線性表的操作可通過對(duì)指針的訪問或改變指針來實(shí)現(xiàn)。在下面的討論中，線性鏈表主要是指單鏈表，主要討論在帶表頭單鏈表存儲(chǔ)結(jié)構(gòu)方式下，線性表的取元素操作及插入、刪除等操作的實(shí)現(xiàn)。第2章線性表68

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

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

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

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

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

intSLinkInsert(SLNode*head,inti,DataTypex)；功能為：在帶頭結(jié)點(diǎn)的單鏈表head中的第i號(hào)結(jié)點(diǎn)之前插入數(shù)據(jù)元素值為x的新結(jié)點(diǎn)。操作的處理過程為：⑴尋找第i-1個(gè)結(jié)點(diǎn)，使指針p指向該結(jié)點(diǎn)；⑵若由于i不合理而找不到相應(yīng)的結(jié)點(diǎn)，則輸出信息，否則，生成一個(gè)新結(jié)點(diǎn)q,并將q插入到結(jié)點(diǎn)p之后。第2章線性表72程序如下：intSLinkInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;/*p指向頭結(jié)點(diǎn)*/j=-1;/*j初始為-1*/while(p->next!=NULL&&j<i-1)/*指針p指向數(shù)據(jù)元素ai-1結(jié)點(diǎn)*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯(cuò)！");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號(hào)結(jié)點(diǎn)。如圖2.10所示，p為指向結(jié)點(diǎn)ai-1的指針。為在單鏈表中實(shí)現(xiàn)元素之間邏輯關(guān)系的變化，僅需修改結(jié)點(diǎn)p中的指針域即可，指針修改可用語句描述為：

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

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

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

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

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

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

⑶重復(fù)過程⑵，直至原鏈表中的結(jié)點(diǎn)全部取完。第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．建鏈表操作線性鏈表的建表操作是指由一個(gè)一維數(shù)組a中的n個(gè)元素的值，建立一個(gè)長度為n的線性鏈表，其操作的含義如圖2.12所示。圖2.12建表操作示意圖第2章線性表80

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

CrtLink(SLNode*head,intn,DataTypea[])；功能是建立一個(gè)由head指向的長度為n的單鏈表(帶頭結(jié)點(diǎn))，并使其n個(gè)數(shù)據(jù)元素的值依次等于一維數(shù)組a中的n個(gè)元素的值。該操作的處理過程為：⑴建立一個(gè)空表；⑵生成一個(gè)結(jié)點(diǎn)，按從后到前上的次序從數(shù)組a中取出元素作為結(jié)點(diǎn)中的元素值，然后從鏈頭插入該結(jié)點(diǎn)；⑶重復(fù)執(zhí)行過程⑵，直至生成n個(gè)結(jié)點(diǎn)。第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(sizeof(SLNode)