基本概念和術(shù)語

一、基本概念和術(shù)語

數(shù)據(jù)(Data)

數(shù)據(jù)是信息的載體。它能夠被計算機識別、存儲和加工處理，是計算機程序加工的"原料”。

隨著計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的范疇包括：整數(shù)、實數(shù)、字符串、圖像和聲音等。

數(shù)據(jù)元素(DataElement)

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點、頂點、記錄。

一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(也可稱為字段、域、屬性)組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。

數(shù)據(jù)結(jié)構(gòu)(DataStructure)

數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相"關(guān)系，即數(shù)據(jù)的組織形式。

1.數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：

①數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicalStructure)；

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問

題抽象出來的數(shù)學(xué)模型。

②數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)(StorageStructure)；

數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)(亦稱為映象)，它依賴于計算機語言。對機器語言而言，存儲結(jié)構(gòu)是具

體的。一般，只在高級語言的層次上討論存儲結(jié)構(gòu)。

③數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。

數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算的集合。最常用的檢索、插入、刪除、更新、排序等運算

實際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。

所謂抽象的操作，是指我們只知道這些操作是"做什么"，而無須考慮"如何做"。只有確定了存儲結(jié)構(gòu)之后，才考慮如何具

體實現(xiàn)這些運算。

為了增加對數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識，下面舉例來說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念。

【例1.1】學(xué)生成績表，見下表。

學(xué)t成績表

學(xué)號姓名數(shù)學(xué)分析普通物理高等代數(shù)平均成績

880001J90859590

880002馬二80859085

880003張三95919995

88000470848680

880005王五91849289

注意：在表中指出數(shù)據(jù)元素?、數(shù)據(jù)項、開始結(jié)點和終端結(jié)點等概念

(1)邏輯結(jié)構(gòu)

表中的每一行是一個數(shù)據(jù)元索(或記錄、結(jié)點)，它由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項組成。

表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對表中任一個結(jié)點，與它相鄰且在它前面的結(jié)點(亦稱為H接前趨(ImmediatePredecessor))

最多只有一個；與表中任一結(jié)點相鄰且在其后的結(jié)點(亦稱為直接后繼(ImmediateSuccessor))也最多只仃一個。表中只有第

一個結(jié)點沒有直接前趨，故稱為開始結(jié)點；也只有最后一個結(jié)點沒有直接后繼。故稱之為終端結(jié)點。例如I,表中"馬二”所在結(jié)點

的直接前趨結(jié)點和直接后繼結(jié)點分別是"丁一"和"張三"所在的結(jié)點，上述結(jié)點間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)。

(2)存儲結(jié)構(gòu)

該表的存儲結(jié)構(gòu)是指用計算機語言如何表示結(jié)點之間的這種關(guān)系，即表中的結(jié)點是順序鄰接地存儲在一片連續(xù)的單元之中，

還是用指針將這些結(jié)點鏈接在一起？

(3)數(shù)據(jù)的運算

在上面的學(xué)生成績表中，可能要經(jīng)常查看某一學(xué)生的成績；當(dāng)學(xué)生退學(xué)時要刪除相應(yīng)的結(jié)點；進來新學(xué)生時要增加結(jié)點。究

竟如何進行查找、刪除、插入，這就是數(shù)據(jù)的運算問題。

搞清楚了上述三個問題，也就弄清了學(xué)生成績表這個數(shù)據(jù)結(jié)構(gòu)。

2.數(shù)據(jù)的邏輯結(jié)構(gòu)分類

在不產(chǎn)生混淆的前提下，常將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：

(1)線性結(jié)構(gòu)

線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前

趨和一個直接后繼。

線性表是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。

(2)非線性結(jié)構(gòu)

非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點可能有多個比接前趨和巴接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

3.數(shù)據(jù)的四種基本存儲方法

數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到：

（1）順序存儲方法

該方法把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得

到的存儲表示稱為順序存儲結(jié)構(gòu)（SequentialStorageStructure）,通常借助程序語言的數(shù)組描述。該方法主要應(yīng)用于線性的

數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。

（2）鏈接存儲方法

該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲表示稱為

鏈?zhǔn)酱鎯Y(jié)構(gòu)（LinkedStorageStructure），通常借助于程序語言的指針類型描述。

（3）索引存儲方法

該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引

項，則該索引表稱之為稠密索引（DenseIndex）o若一組結(jié)點在索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引（Spare

Index）o索引項的一般形式是：（關(guān)鍵字、地址）

關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引項的地址指示結(jié)點所在的存儲位置；稀疏索引中索引項的地址

指示一組結(jié)點的起始存儲位置。

（4）散列存儲方法

該方法的基本思想是：根據(jù)結(jié)點的關(guān)鍵字宜?接計嵬出該結(jié)點的存儲地址。

四種基本存儲方法，既可單獨使用，也可組合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲映像。

同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，

主要考慮運算方便及算法的時空要求。

4.數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系

數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面是一個整體。孤立地去理解一個方面，而不注意它們之間的聯(lián)系是

不可取的。

存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可缺少的一個方面：同邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識。

【例】線性表是一種邏輯結(jié)構(gòu)，若采用順序方法的存儲表示，可稱其為順序表；若采用鏈?zhǔn)酱鎯Ψ椒?，則可稱其為鏈表；若

采用散列存儲方法，則可稱為散列表。

數(shù)據(jù)的運算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個方面。在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之后，按定義的運算集合及其運算的性

質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。

【例】若對線性表上的插入、刪除運算限制在表的一端進行，則該線性表稱之為棧；若對插入限制在表的一端進行，而刪除

限制在表的另一端進行，則該線性表稱之為隊列。更進一步，若線性表采用順序表或鏈表作為存儲結(jié)構(gòu)，則對插入和刪除運算做

了上述限制之后，可分別得到順序棧或鏈棧，順序隊列或鏈隊列。

數(shù)據(jù)類型（DataType）

所謂數(shù)據(jù)類型是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)

據(jù)結(jié)構(gòu)。

【例1.2】C語言的〃整數(shù)類型〃就定義了一個整數(shù)可取值的范圍（其最大值INT-MAX依賴于具體機器）以及對整數(shù)可施加的加I、減、

乘、除和取模等操作。

按〃值〃是否可分解，可將數(shù)據(jù)類型劃分為兩類：

①原子類型：其值不可分解。通常是由語言直接提供。

【例】C語言的整型、字符型等標(biāo)準(zhǔn)類型及指針等簡單的導(dǎo)出類型；

②結(jié)構(gòu)類型：其值可分解為若干個成分（或稱為分壯）。是用戶借助于語言提供的描述機制自己定義的，它通常是由標(biāo)準(zhǔn)類型派

生的，故它也是一種導(dǎo)出類型。

【例】C的數(shù)組、結(jié)構(gòu)等類型。

抽象數(shù)據(jù)類型（AbstractType簡稱ADT）

ADT是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作?？梢钥醋魇菙?shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。

一個ADT可描述為：

ADTADT-Name{

Data:〃數(shù)據(jù)說明

〃數(shù)據(jù)元素之間邏輯關(guān)系的描述

Operations:〃操作說明

Operation]:〃操作，它通?？捎肅或C++的函數(shù)原型來描述

Input:〃對輸入數(shù)據(jù)的說明

Preconditions:〃執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)〃可看作初始條件

Process:〃對數(shù)據(jù)執(zhí)行的操作

Output:〃對返回數(shù)據(jù)的說明

Postconditions:〃執(zhí)行本操作后系統(tǒng)的狀態(tài)〃〃系統(tǒng)”可看作某個數(shù)據(jù)結(jié)構(gòu)

Operation2://操作

}//ADT

抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立于具體實現(xiàn)。它的優(yōu)點是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通

過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了信息隱藏。在C++中，我們可以用類（包括模板類）的說明來表示

ADT,用類的實現(xiàn)來實現(xiàn)ADT【參閱[10]]。因此，C++中實現(xiàn)的類相當(dāng)于是數(shù)據(jù)的存儲結(jié)構(gòu)及其在存儲結(jié)構(gòu)上實現(xiàn)的對數(shù)據(jù)的

操作。

ADT和類的概念實際上反映了程序或軟件設(shè)計的兩層抽象：ADT相當(dāng)于是在概念公（或稱為抽象層）上描述問題，而類相當(dāng)于

是在實現(xiàn)層上描述問題。此外，C++中的類只是一個由用戶定義的普通類型，可用它來定義變量（稱為對象或類的實例）。因此，

在C++中，最終是通過操作對象來解決實際問題的，所以我們可將該層次看作是應(yīng)用層。例如，main程序就可看作是用戶的應(yīng)

用程序。

由于C語言中沒有提供"類”這一數(shù)據(jù)類型，因此無法實現(xiàn)ADT,故我們不采用ADT的形式來描述數(shù)據(jù)結(jié)構(gòu)，以節(jié)省篇幅。大

家只要記住，它實際上等價于我們定義的數(shù)據(jù)的邏輯結(jié)構(gòu)以及在邏輯結(jié)構(gòu)上定義的抽象操作。

二、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

數(shù)據(jù)結(jié)構(gòu)是計算機軟件和計算機應(yīng)用專業(yè)的核心課程之一，在眾多的計算機系統(tǒng)軟件和應(yīng)用軟件中都要用到各種數(shù)據(jù)結(jié)

構(gòu)。因此，僅掌握幾種計算機語言是難以應(yīng)付眾多復(fù)雜的課題的。要想有效地使用計算機，還必須學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。

選擇合適數(shù)據(jù)結(jié)構(gòu)解決應(yīng)用問題

1.計算機處理問題的分類

（1）數(shù)值計算問題

在計算機發(fā)展初期，人們使用計算機主要是處理數(shù)值計算問題。

【例2.1】線性方程的求解

該類問題涉及的運算對象是簡單的整型、實型或布爾型數(shù)據(jù)。程序設(shè)計者的主要精力集中于程序設(shè)計的技巧，無須重視數(shù)據(jù)

結(jié)構(gòu)。

（2）非數(shù)值性問題

隨著計算機應(yīng)用領(lǐng)域的擴大和軟、硬件的發(fā)展，”非數(shù)值性問題”越來越顯得重要。據(jù)統(tǒng)計，當(dāng)今處理非數(shù)值性問題占用了90%

以上的機器時間，這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決

此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。

2.非數(shù)值問題求解

著名的瑞士計算機科學(xué)家沃思（N.Wirth）教授曾提出：算法+數(shù)據(jù)結(jié)構(gòu)=程序

數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)算法：是對數(shù)據(jù)運算的描述

程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實際問

題的數(shù)據(jù)結(jié)構(gòu)。

【例2.2】電話號碼查詢問題。

編一個查詢某個城市或單位的私人電話號碼的程序。要求對任意給出的一個姓名，若該人有電話號碼，則迅速找到其電話號

碼；否則指出該人沒有電話號碼。

要解此問題首先構(gòu)造一張電話號碼登記表。表中每個結(jié)點存放兩個數(shù)據(jù)項：姓名和電話號碼。

要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲方式。最簡單的方式是將表中結(jié)點順序地存儲在計算機中?查找時從頭開

始依次查對姓名，直到找出正確的姓名或是找遍整個表均沒有找到為止。這種查找算法對于一個不大的單位或許是可行的，但對

一個有成千上萬私人電話的城市就不實用了。若這張表是按姓氏排列的，則可另造一張姓氏索引表，采用如下圖所示的存儲結(jié)構(gòu)。

那么查找過程是先在索引表中查對姓氏，然后根據(jù)索引表中的地址到電話號碼登記表中核查姓名，這樣查找登記表時就無需查找

其它姓氏的名字了。因此，在這種新的結(jié)構(gòu)上產(chǎn)生的查找算法就更為有效。

姓名電話號碼

張二

姓氏地址張林

張?

李張潔

??李四

?

李中

電話號碼Tri句問題的索引存儲

【例2.3】田徑賽的時間安排問題。

假設(shè)某校的田徑選拔賽共設(shè)六個項目的比賽，即跳高、跳遠、標(biāo)槍、鉛球、100米和200米短跑，規(guī)定每個選手至多參加三個

項目的比賽?，F(xiàn)有五名選手報名比賽，選手所選擇的項目如參賽選手比賽項目表所示?，F(xiàn)在要求設(shè)計?個競賽日程安排衣，使得

在盡可以短的時間內(nèi)安排完比賽。

（1）為了能較好地解決這個問題，首先應(yīng)該選擇?個合適的數(shù)據(jù)結(jié)構(gòu)來表示它。2表示該問題的數(shù)據(jù)結(jié)構(gòu)模型圖如右下圖（圖中

頂點代表競賽項目，在所有的兩個不能同時進行比賽的項目之間連上條邊）。顯然同個選手選擇的兒個項目是不能在同時間

內(nèi)比賽的，因此該選手選擇的項目中應(yīng)該兩兩有邊相連。

（2）競賽項目的時間安排問題可以抽象為對無向圖進行“著色”操作：即用盡可能少的顏色去給圖中每個頂點著色，使得任意兩個

有邊連接的相鄰頂點著上不同的顏色。每種顏色表示個比賽時間，著上同?種顏色的頂點是可以安排在同?時間內(nèi)競賽的項

目。由此可得：只要安排4個不同的時間競賽即可。時間1內(nèi)可以比賽跳高（A）和標(biāo)槍（C）,時間2內(nèi)可以比賽跳遠（B）和

鉛球（D）,時間3和時間4內(nèi)分別比賽100米（E）和200米（F）。

解決問題的一個關(guān)鍵步驟是，選取合適的數(shù)據(jù)結(jié)構(gòu)表示該問題，然后才能寫出有效的算法。

姓名項目1項目2項目3

T-跳高跳遠100米

馬二標(biāo)槍鉛球—

g標(biāo)槍100米200米

李四鉛球200米跳高

王五跳遠200米—

參賽選手比賽項11表

三、算法的描述

數(shù)據(jù)的運算通過算法(Algorithm)描述，討論算法是數(shù)據(jù)結(jié)構(gòu)課程的重要內(nèi)容之-o

1.算法

非形式地說，算法是任意個良定義的計算過程。它以?個或多個值作為輸入，并產(chǎn)生個或多個值作為輸出。

(1)?個算法可以被認(rèn)為是用來解決個計算問題的工具。

(2)?個算法是?系列將輸入轉(zhuǎn)換為輸出的計算步驟。

【例3.1]有這樣個排序問題：將?個數(shù)字序列排序為非降序。該問題的形式定義由滿足下述關(guān)系的輸入輸出序列構(gòu)成：

輸入：數(shù)字序列(aba2?..,an).

輸出：輸出序列的一個枚舉⑶㈤,…，a；〉使得ai&z'V...芻3'

對于一個輸入實例(31,41,59,26,41,58)，排序算法應(yīng)返回輸出序列(26,31,41,41,58,59).

(1)輸入實例

輸入實例：?個問題的輸入實例是滿足問題陳述中所給出的限制、為計算該問題的解所需要的所有輸入構(gòu)成的。

(2)正確的算法和不正確的算法

若?個算法對于每個輸入實例均能終止并給出正確的結(jié)果，則稱該算法是正確的。正確的算法解決了給定的計算問題.

?個不正確的算法是指對某些輸入實例不終止，或者雖然終止但給出的結(jié)果不是所渴望得到的答案，?般只考慮正確的算法。

2.算法的描述

?個算法可以用自然語言、計算機程序語言或其它語言來說明，惟?的要求是該說明必須精確地描述計算過程。

?般而言，描述算法最合適的語言是介于自然語言和程序語言之間的偽語言。它的控制結(jié)構(gòu)往往類似于Pascal、C等程序語言，

但其中可使用任何表達能力強的方法使算法表達更加清晰和簡潔，而不至于陷入具體的程序語言的某些細節(jié)。

從易于上機驗證算法和提高實際程序設(shè)計能力考慮，采用C語言描述算法。

【例3.2]定義一個輸出錯誤信息后退出程序運行的錯誤處理函數(shù)，該函數(shù)將在后續(xù)的許多程序中用來簡化處理代碼。

#include<stdlib.h>//其中有exit的說明

ttinclude<stdio.h>//其中有標(biāo)準(zhǔn)錯誤stderr的說明

voidError(char*message)

(〃輸出錯誤信息

fprintf(stderr,“Error:%s\n”,message);

exit(l);〃終止程序，返回給操作系統(tǒng)

)

四、算法分析

1.評價算法好壞的標(biāo)準(zhǔn)

求解同一計算問題可能有許多不同的算法，究竟如何來評價這些算法的好壞以便從中選出較好的算法呢？

選用的算法首先應(yīng)該是"正確"的。此外，主要考慮如R三點：

①執(zhí)行算法所耗費的時間；

②執(zhí)行算法所耗費的存儲空間，其中主要考慮輔助存儲空間；

③算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。

2.算法性能選擇

一個占存儲空間小、運行時間短、其它性能也好的算法是很難做到的。原因是上述要求有時相互抵觸：要節(jié)約算法的執(zhí)行時

間往往要以犧牲更多的空間為代價；而為了節(jié)省空間可能要耗費更多的計算時間。因此我們只能根據(jù)具體情況有所側(cè)電：

①若該程序使用次數(shù)較少，則力求算法簡明易懂；

②對于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法；

③若待解決的問題數(shù)據(jù)量極大，機器的存儲空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。

3.算法的時間性能分析

(1)算法耗費的時間和語句頻度

一個算法所耗費的時間=算法中每條語句的執(zhí)行時間之和

每條語句的執(zhí)行時間=語句的執(zhí)行次數(shù)(即頻度(FrequencyCount))/語句執(zhí)行一次所需時間

算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時間取決于機器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。

若要獨立于機器的軟、硬件系統(tǒng)來分析算法的時間耗費，則設(shè)每條語句執(zhí)行一次所需的時間均是單位時間，-個算法的時間耗

費就是該算法中所有語句的頻度之和。

【例3.3】求兩個n階方陣的乘積C=A、B,其算法如卜.：

#definen100//n可根據(jù)需要定義，這里假定為

voidMatrixMultiply(intA[a],intB[n][n],intC[n][n])

{〃右邊列為各語句的頻度

inti,j,k；

⑴for(i=0;i<n;i++)//n+1

(

⑵for(j=0;j<n;j++)//n(n+1)

(

⑶C[i][j]=O;//n2

(4)for(k=0;k<n;k++)//n2(n+1)

⑸C[i][j]=C[i][j]+A[i][k]*B[k][j];//n3

)

)

該算法中所有語句的頻度之和(即算法的時間耗費)為：

T(n)=2n3+3n2+2n+l(1.1)

分析：

語句(1)的循環(huán)控制變量i要增加到n,測試到i=n成立才會終止。故它的頻度是n+1。但是它的循環(huán)體卻只能執(zhí)行n次。語句(2)

作為語句(1)循環(huán)體內(nèi)的語句應(yīng)該執(zhí)行n次，但語句(2)本身要執(zhí)行n+1次，所以語句(2)的頻度是n(n+l)。同理可得語句(3),(4)和(5)

23

的頻度分別是，，n(n+l)?no

算法MatrixMuhiply的時間耗費T(n)是矩陣階數(shù)n的函數(shù)。

(2)問題規(guī)模和算法的時間復(fù)雜度

算法求解問題的輸入楠稱為問題的規(guī)模(Size),一般用一個整數(shù)表示。

【例3.4］矩陣乘積問題的規(guī)模是矩陣的階數(shù)。

【例3.5］一個圖論問題的規(guī)模則是圖中的頂點數(shù)或邊數(shù)。

一個算法的時間復(fù)雜度(TimeComplexity,也稱時間復(fù)雜性)T(n)是該算法的時間耗費，是該算法所求解問題規(guī)模n的函數(shù)。當(dāng)

問題的規(guī)模n趨向無窮大時，時間復(fù)雜度T(n)的數(shù)最?級(階)稱為算法的漸進時間復(fù)雜度。

【例3.6］算法MatrixMultidy的時間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無窮大時，顯然有

a-MBN-??>

這表明，當(dāng)n充分大時，T(n)和「之比是一個不等于零的常數(shù)。即T(n)和「是同階的，或者說T(n)和/的數(shù)量級相同。記作丁(0=0(1?)

是算法MatrixMultiply的漸近時間復(fù)雜度。

數(shù)學(xué)符號“O”的嚴(yán)格的數(shù)學(xué)定義：

若T(n)和fi：n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0,使得當(dāng)*n0時都滿足gT(n)WC-f(n)。

(3)漸進時間復(fù)雜度評價算法時間性能

主要用算法時間復(fù)雜度的數(shù)量級(即算法的漸近時間復(fù)雜度)評價一個算法的時間性能。

【例3.7］有兩個算法A1和A?求解同一問題，時間復(fù)雜度分別是T|(n)=100n2,T,(n)=5n\

(1)當(dāng)輸入量n<20時，有T|(n)>T,(n),后者花費的時間較少。

(2)隨著問題規(guī)模n的增大，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時，算法A1比算法A?要有效

地多。

它們的漸近時間復(fù)雜度0(/)和0而)從宏觀上評價了這兩個算法在時間方面的質(zhì)量。在算法分析時，往往對算法的時間復(fù)雜度和漸

近時間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n))簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻

度。

【例3.8］算法MatrixMultiply的時間復(fù)雜度一般為T(n尸0(r)，f(n尸一是該算法中語句(5)的頻度。下面再舉例說明如何求算法的

時間復(fù)雜度。

【例3.9］交換i和j的內(nèi)容。

Temp=i;

i=j；

j=temp;

以上三條單個語句的頻度均為1,該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作

T(n)=O(l)o

如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類

算法的時間復(fù)雜度是0(1)。

r/列

k13.10]變量計數(shù)之一。

(z1X

x7x=0;y=0;

z2

\(for(k-l;k<=n;k++)

(z3)\

xzx++;

z4\

\rz)for(i=l;i<=n;i++)

75X

x(ZJfor(j=l;j<=n;j++)

(767\+

xy+

一般情況下，對步進循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長加1、終值判別、控制轉(zhuǎn)移等成分。因此,

以上程序段中頻度最大的語句是(6),其頻度為f(n)=n2,所以該程序段的時間復(fù)雜度為T(n)=0(n2)。

當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。

【例3.11】變量計數(shù)之二。

(1)x=l;

(2)for(i=l;i<=n;i++)

(3)for(j=l;j<=i;j++)

(4)for(k=l;k<=j;k++)

(5)x++;

該程序段中頻度最大的語句是(5),內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒仃直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，

而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：

M/dMZJTM

則該程序段的時間復(fù)雜度為T(n)=O(n3/6+低次項)=0(1?).

(4)算法的時間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關(guān)。

【例3.12］在數(shù)值A(chǔ)［0..n-l］中查找給定值K的算法大致如下：

(1)i=n-l;

(2)while(i>=0&&(A［i］!=k))

(3)i—;

(4)returni;

此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及K的取值有關(guān)：

①若A中沒有與K相等的元素，則語句(3)的頻度fi：n)=n：

②若A的最后一個元素等于K,則語句(3)的頻度*n)是常數(shù)0。

(5)最壞時間復(fù)雜度和平均時間復(fù)雜度

最壞情況下的時間復(fù)雜度稱最壞時間復(fù)雜度。一般不特別說明，討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度。

這樣做的原因是：最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何

更長。

【例3.19】查找算法【例18】在最壞情況下的時間復(fù)雜度為T(n尸0(n),它表示對于任何輸入實例，該算法的運行時間不可能大于

0(n),

平均時間復(fù)雜度是指所有可能的輸入實例均以等概率出現(xiàn)的情況下，算法的期望運行時間。

常見的時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)0(1)、對數(shù)階OQoga)、線形階0(n)、線形對數(shù)階WnlogM、平方階0(哈立方

階0(r)....k次方階0(小)、指數(shù)階0(2%顯然，時間復(fù)雜度為指數(shù)階0(2。的算法效率極低，當(dāng)n值稍大時就無法應(yīng)用。

類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度(SpaceComplexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n

的函數(shù)。漸近空間復(fù)雜度也常常簡稱為空間復(fù)雜度。算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

五、線性表的邏輯定義

線性結(jié)構(gòu)是最簡單且最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是一種典型的線性結(jié)構(gòu)。

線性表(LinearList)是由n(n20)個數(shù)據(jù)元素(結(jié)點)a”aC,…，a1,組成的有限序列。

①數(shù)據(jù)元素的個數(shù)n定義為表的長度(n=0時稱為空表)。

②將非空的線性表(n>0)記作：(a”ai,???,a?)

③數(shù)據(jù)元素a,(IWiWn)只是個抽象符號，其具體含義在不同情況下可以不同。

［例I］英文字母表(A,B,Z)是線性表，表中每個字母是一個數(shù)據(jù)元素(結(jié)點)

【例2】?副撲克牌的點數(shù)(2,3,…，10,J,Q,K,A)也是一個線性表，其中數(shù)據(jù)元素是每張牌的點數(shù)

【例3】學(xué)生成績表(見概論中表1.1)中，每個學(xué)生及其成績是一個數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號、姓名、各科成績及平

均成績等數(shù)據(jù)項組成。

線性表的邏輯結(jié)構(gòu)特征

對于非空的線性表：

①有且僅有一?個開始結(jié)點a”沒有直接前趨，有且僅有一個宜接后繼山；

②有且僅有一個終結(jié)結(jié)點a.，沒有直接后繼，有且僅有一個直接前趨a?H：

③其余的內(nèi)部結(jié)點a,(2WiWn-l)都有且僅有一個直接前趨a,7和一個a,一。

常見的線性表的基本運算

1.InitList(L)構(gòu)造一個空的線性表L,即表的初始化。

2.ListLength(L)求線性表L中的結(jié)點個數(shù)，即求表長。

3.GetNode(L,i)取線性表L中的第i個結(jié)點，這里要求IWiWListLength(L)

4.LocateNode(L,x)在L中查找值為x的結(jié)點，并返回該結(jié)點在L中的位置。若L中有多個結(jié)點的值和x相同，則返回首

次找到的結(jié)點位置；若L中沒有結(jié)點的值為x,則返回一個特殊值表示查找失敗。

5.InsertList(L,x,i)在線性表L的第i個位置上插入一個值為x的新結(jié)點，使得原編號為i,i+1,…，n的結(jié)點變?yōu)榫?/p>

號為i+1,i+2,…，n+1的結(jié)點。這里IWiWn+l,而n是原表L的長度。插入后，表L的長度加1。

6.DeleteList(L,i)刪除線性表L的第i個結(jié)點，使得原編號為i+1,i+2,…，n的結(jié)點變成編號為i,i+1,…，nT的

結(jié)點。這里lWiWn,而n是原表L的長度。刪除后表L的長度減1。

注意：

以上所提及的運算是邏輯結(jié)構(gòu)上定義的運算。只要給出這些運算的功能是“做什么〃，至于〃如何做”等實現(xiàn)細節(jié)，只有待確

定了存儲結(jié)構(gòu)之后才考慮。

組合基本運算，實現(xiàn)復(fù)雜運算

對于實際問題中涉及的其它更為復(fù)雜的運算，可以用基本運算的組合來實現(xiàn)。具體請【參見參考書目】

五、順序表

1.順序表的定義

(1)順序存儲方法：即把線性表的結(jié)點按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。

⑵順序表(SequentialList)用順序存儲方法存儲的線性表簡稱為順序表(SequentialList)o

2.結(jié)點藥的存儲地址

不失一般性，設(shè)線性表中所有結(jié)點的類型相同，則每個結(jié)點所占用存儲空間大小亦相同。假設(shè)表中每個結(jié)點占用c個存儲單

元，其中第一個單元的存儲地址則是該結(jié)點的存儲地址，并設(shè)表中開始結(jié)點街的存儲地址(簡稱為基地址)是LOC(ai),那么結(jié)

點擊的存儲地址LOC⑷可通過下式計算：LOC(af)=LOC(a,)+(i-1)*cl<i<n

注意：

在順序表中，每個結(jié)點a的存儲地址是該結(jié)點在表中的位置i的線性函數(shù)。只要知道基地址和每個結(jié)點的大小，就可在相同時

間內(nèi)求出任一結(jié)點的存儲地址。是一種隨機存取結(jié)構(gòu)。

3.順序表類型定義

defineListSize100〃表空間的大小可根據(jù)實際需要而定，這里假設(shè)為

typedefintDataType;〃DataType的類型可根據(jù)實際情況而定，這里假設(shè)為int

typedefstruct{

DataTypedata[ListSize]；〃向最data用于存放表結(jié)點

intlength；〃當(dāng)前的表長度

}SeqUst；

6儲位班下標(biāo)

b0

b*c

b*(i-l)c

b*(rr-l)cn-1

b+ncn

b*(ListSizel)cl.istSize-1

M序表示愈舊

注意：

①用向量這種順序存儲的數(shù)組類型存儲線性表的元素外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，因此用結(jié)構(gòu)

類型來定義順序表類型。

②存放線性表結(jié)點的向量空間的大小ListSize應(yīng)仔細選值，使其既能滿足表結(jié)點的數(shù)目動態(tài)增加的需求，又不致于預(yù)先定

義過大而浪費存儲空間。

③由于C語言中向量的卜.標(biāo)從0開始，所以若L是SeqList類型的順序表，則線性表的開始結(jié)點即和終端結(jié)點分別存儲

在L.data[0]和L.Data]L.length-1]中。

④若L是SeqList類型的指針變量，則a1和a。分別存儲在L?>data[0]和L->data[L?AengthJ]中。

4.順序表的特點

順序表是用向好實現(xiàn)的線性表，向量的卜.標(biāo)可以看作結(jié)點的相對地址。因此順序表的的特點是邏輯上相鄰的結(jié)點其物理位濘.

亦相鄰。

六、順序表上實現(xiàn)的基本運算

1.表的初始化

voidInitList(SeqList*L)

{//順序表的初始化即將表的氏度置為

L->length=0；

2.求表長

intListLength(SeqList*L)

{〃求表長只需返回L->length

returnL->length;

3.取表中第i個結(jié)點

DataTypeGetNode(L,i)

{〃*\\*/取表中第i個結(jié)點只需返回和L->data[iT]即可

if(i<lI|i>L->(length-1))

Error("positionerror")；

returnL->data[i-l]；

)

4.查找值為x的結(jié)點

【參見參考書】

5,插入

(1)插入運算的邏輯描述

線性表的插入運算是指在表的第i(l<i<n+l)個位置上，插入一個新結(jié)點x,使長度為n的線性表：(a1，…，知…aQ

變成長度為n+1的線性表:(aP...?知,x,a,,...an)

注意：

①由于向量空間大小在聲明時確定，當(dāng)L->length2ListSize時，表空間一滿，不可再做插入操作

②當(dāng)插入位置i的值為i>n或iVl時為止.法位置，不可做正常插入操作

(2)順序表插入操作過程

在順序表中，結(jié)點的物理順序必須和結(jié)點的邏輯順序保持一致，因此必須將表中位置為n,n-1,…，i上的結(jié)點，依次后移

到位置n+1,n,i+1上，空出第i個位置，然后在該位置上插入新結(jié)點X。僅當(dāng)插入位置i=n+l時，才無須移動結(jié)點，直接將x插

入表的末尾。具體過程見【動畫演示】

(3)具體算法描述

voidInsertList(SeqList*L,DataTypex,inti)

{〃將新結(jié)點x插入L所指的順序表的第i個結(jié)點ai的位置上

intj;

if(i<l||i>L->length+l)

ErrorC'positionerror");法位置，退出運行

if(L->length>=ListSize)

Error("overflow");〃表空間溢出，退出運行

for(j=L->length-l;j>=i-l;j-)

L->data[j+l]=L->data[j];〃結(jié)點后移

L->data[i-l]=x;〃插入x

L->Length++;〃表長加

(4)算法分析

①問題的規(guī)模表的長度L->length(設(shè)值為n)是問題的規(guī)模。

②移動結(jié)點的次數(shù)由表長n和插入位置i決定

算法的時間主?；ㄙM在for循環(huán)中的結(jié)點后移語句上。該語句的執(zhí)行次數(shù)是n-i+1。當(dāng)1=什1：移動結(jié)點次數(shù)為0,即算法在

最好時間復(fù)雜度是0(1)當(dāng)i=l：移動結(jié)點次數(shù)為n,即算法在最壞情況下時間復(fù)雜度是0(n)

③移動結(jié)點的平均次數(shù)Eis(n)

&3Axp0T+D

u1

其中：

在表中第i個位置插入一個結(jié)點的移動次數(shù)為n-i+l

Pi表示在表中第i個位置上插入一個結(jié)點的概率。不失一般性，假設(shè)在表中任何合法位置(IWiVn+I)上的插入結(jié)點的機會是

均等的，則

Pl=P2=--=Pn+l=l/(n+l)

因此，在等概率插入的情況卜.，

即在順序表上進行插入運算，平均要移動一半結(jié)點。

6.刪除

(1)刪除運算的邏輯描述

線性表的刪除運算是指將表的第i(IWWn)個結(jié)點刪去，使長度為n的線性表(a1，…，叼ai+1,an)

變成長度為n-1的線性表(aPa^,ai+Pan)

注意：

當(dāng)要刪除元素的位置i不在表長范圍(即i<l或i>L->length)時，為II：.法位置，不能做正常的刪除操作

(2)順序表刪除操作過程

在順序表上實現(xiàn)刪除運算必須移動結(jié)點，才能反映出結(jié)點間的邏輯關(guān)系的變化。若i=n,則只要簡單地刪除終端結(jié)點，無須

移動結(jié)點；若1W運nJ,則必須將表中位置i+1,i+2,n的結(jié)點，依次前移到位置i,i+1,…，n-l±,以填補刪除操作造成的空

缺。其刪除過程【參見動畫演示】

(3)具體算法描述

voidDeleteList(SeqList*L,inti)

{〃從L所指的順序表中刪除第i個結(jié)點ai

intj;

if(i<l||i>L->length)

Error("positionerror");〃非法位置

for(j=i;j<=L->length-l;j++)

L->data[jT]=L->data[j];〃結(jié)點前移

L->length—;〃表長減小

)

(4)算法分析

①結(jié)點的移動次數(shù)由表長n和位置i決定：i=n時，結(jié)點的移動次數(shù)為0,即為0(1);i=l時，結(jié)點的移動次數(shù)為n?l,算法時

間復(fù)雜度分別是0(n)

②移動結(jié)點的平均次數(shù)EDE(n)

4-1

其中：

刪除表中第i個位置結(jié)點的移動次數(shù)為n-i

Pi表示刪除表中第i個位置上結(jié)點的概率。不失般性，假設(shè)在表中任何合法位置(iWKn)上的刪除結(jié)點的機會是均等的，

則

Pl=p2=??=Pn=l/n

因此，在等概率插入的情況下，

M

順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是0(n)。

七、單鏈表

1、鏈接存儲方法

鏈接方式存儲的線性表簡稱為鏈表(LinkedList).

鏈表的具體存儲表示為：

①用一組任意的存儲單元來存放線性表的結(jié)點(這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的)

②鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存

儲指示其后繼結(jié)點的地址(或位置)信息(稱為指針(pointer)或鏈(link))

注意：

鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街?，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。

2、鏈表的結(jié)點結(jié)構(gòu)

Idata|next|

data域一存放結(jié)點值的數(shù)據(jù)域

next域一存放結(jié)點的宜接后繼的地址(位置)的指針域(鏈域)

注意：

①鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。

②每個結(jié)點只有一個鏈域的鏈表稱為單鏈表(SingleLinkedList)o

【例】線性表(bat,cat,eat,fat,hat,jat,lat,mat)的單鏈表示如示意圖

3、頭指針head和終端結(jié)點指針域的表示

單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。

注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。

【例】頭指針名是head的鏈表可稱為表head。

終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即NULL。

4、單鏈表的一般圖示法

由于我們常常只注重結(jié)點間的邏輯順序，不關(guān)心每個結(jié)點的實際位置，可以用箭頭來表示鏈域中的指針，線性表(bat,cat,

fat>hat,jat,lat,mat)的單鏈表就可以表示為下圖形式。

head—"but|爪cat||A???—mat|,

單鏈表的一般圖示法

5、單鏈表類型描述

typedefcharDataType;〃假設(shè)結(jié)點的數(shù)據(jù)域類型為字符

typedefstructnode{〃結(jié)點類型定義

DataTypedata;〃結(jié)點的數(shù)據(jù)域

structnode*next;〃結(jié)點的指針域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

①LinkList和ListNode*是不同名字的同一個指針類型(命名的不同是為了概念上更明確)

②LinkList類型的指針變量head表示它是單鏈表的頭指針

③ListNode*類型的指針變量p表示它是指向某一結(jié)點的指針

6、指針變量和結(jié)點變量

指針變量P(其值是結(jié)點地址)和

結(jié)點變揖*1%其值是結(jié)點內(nèi)容)之關(guān)系

11

1指針變量1結(jié)點變量

11

11

1定義1在變量說明部分顯式1在程序執(zhí)行時，通過標(biāo)準(zhǔn)

1定義1函數(shù)maHoc生成

1

1T

1取值1非空時，存放某類1實際存放結(jié)點各域內(nèi)容

1型結(jié)點的地址1

11

111

1操作方式1通過指針變量名訪問1通過指針生成、訪問和釋放1

1J__11

①生成結(jié)點變量的標(biāo)準(zhǔn)函數(shù)

p=(ListNode*)malloc(sizeof(ListNode))：

〃函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間，并將其首地址放入指針變量p中

②釋放結(jié)點變量空間的標(biāo)準(zhǔn)函數(shù)

free(p)；〃釋放p所指的結(jié)點變量空間

③結(jié)點分量的訪問

利用結(jié)點變量的名字*P訪問結(jié)點分量

方法一：(*p).data和(*p).next

方法二：p->data和p->next

④指針變量p和結(jié)點變量*P的關(guān)系

指針變量p的值一結(jié)點地址

結(jié)點變量*P的值——結(jié)點內(nèi)容

(*p).data的值一^p指針?biāo)附Y(jié)點的data域的值

(*p).next的值---*p后繼結(jié)點的地址

*((*p).next)---*p后繼結(jié)點

注意：

①若指針變量p的值為空(NULL),則它不指向任何結(jié)點。此時，若通過*p來訪問結(jié)點就意味著訪問一個不存在的變量,

從而引起程序的錯誤。

②有關(guān)指針類型的意義和說明方式的詳細解釋，【參考C語言的有關(guān)資料】0

八、單鏈表的運算

1、建立單鏈表

假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符'\n'為輸入條件結(jié)束標(biāo)志符。動態(tài)地

建立單鏈表的常用方法有如下兩種：

(1)頭插法建表

①算法思路從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當(dāng)前鏈

表的表頭匕直到讀入結(jié)束標(biāo)志為止。

將結(jié)點*S插到單鏈表head的頭1：

具體方法【參見動畫演示】

注意：該方法生成的鏈表的結(jié)點次序與輸入順序相反。

②具體算法實現(xiàn)

LinkListCreatListF(void)

{//返回單鏈表的頭指針

charch;

LinkListhead;〃頭指針

ListNode*s;//工作指針

head=NULL;〃鏈表開始為空

ch=getcharO;〃讀入第個字符

while(ch!=，\n){

s=(ListNode*)malloc(sizeof(ListNode));〃生成新結(jié)點

s->data=ch;〃將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中

s->next=head;

head=s;

ch=getchar();〃讀入下一字符

)

returnhead;

)

(2)尾插法建表

①算法思路

從一個空表開始,重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當(dāng)前鏈表的表尾上，直

到讀入結(jié)束標(biāo)志為止。

head―a|.|?,

、、③1

將新結(jié)點*S插到單鏈表head的尾上

具體方法【參見動畫演示】

注意：

1.采用尾插法建表，生成的鏈表中結(jié)點的次序和輸入順序?致

2.必須增加?個尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點

②具體算法實現(xiàn)

LinkListCreatListR(void)

{〃返回單鏈表的頭指針

charch;

LinkListhead;〃頭指針

ListNode*s,*r;〃工作指針

head=NULL;〃鏈表開始為空

r=NULL;〃尾指針初值為空

ch=getchar();〃讀入第個字符

while(ch!='\n'){

s=(ListNode*)malloc(sizeof(ListNode));〃生成新結(jié)點

s->data=ch;〃將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中

if(head!=NULL)

head=s;〃新結(jié)點插入空表

else

r->next=s;〃將新結(jié)點插到*r之后

r=s;〃尾指針指向新表尾

ch=getchar();〃讀入卜.一字符

"/endwhile

if(r!=NULL)

r->next=NULL;〃對于非空表，將尾結(jié)點指針域置空head=s;

returnhead;

)

注意：

1.開始結(jié)點插入的特殊處理

由于開始結(jié)點的位置是存放在頭指針(指針變量)中,而其余結(jié)點的位置是在其前趨結(jié)點的指針域中，插入開始結(jié)點時要將頭指

針指向開始結(jié)點。

2.空表和非空表的不同處理

若讀入的第一個字符就是結(jié)束標(biāo)志符,則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在;否則鏈表head非空，最后一個尾結(jié)點

*r是終端結(jié)點,應(yīng)將其指針域置空。

(3)尾插法建帶頭結(jié)點的單鏈表

①頭結(jié)點及作用

頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點。它具有兩個優(yōu)點：

L由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致，無須

進行特殊處理；

2.無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針(空表中頭結(jié)點的指針域空)，因此空表和非空表的處理也就統(tǒng)一

了。

②帶頭結(jié)點的單鏈表

head頭結(jié)點開始結(jié)點終端結(jié)點

ai|4^1ai[~4~????—>1a,-,|A|

(a)非空表

FbH~~Fl

附中?&示期影

(b)空表

帶頭結(jié)點的單鏈表

注意：頭結(jié)點數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應(yīng)用中可用于存放表長等附加信息。

③尾插法建帶頭結(jié)點鏈表算法

LinkListCreatListRl(void)

{〃用尾插法建立帶頭結(jié)點的單鏈表

charch;

LinkListhead=(ListNode*)malloc(sizeof(ListNode));〃生成頭結(jié)點

ListNode*s,*r;〃工作指針

r=head;//尾指針初值也指向頭結(jié)點

while((ch=getchar())!="\n'){

s=(ListNode*)malloc(sizeof(ListNode));〃生成新結(jié)點

s->data=ch;〃將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中

r->next=s;

r=s;

)

r->next=NULL;〃終端結(jié)點的指針域置空，或空表的頭結(jié)點指針域置空

returnhead;

)

注意：

上述算法里，動態(tài)申請新結(jié)點空間時未加錯誤處理，這對申請空間極少的程序而言不會出問題。但在實用程序里，尤其是對

空間需求較大的程序，凡是涉及動態(tài)申請空間，一定要加入借誤處理以防系統(tǒng)無空間可供分配。

(4)算法時間復(fù)雜度

以上三個算法的時間復(fù)雜度均為0(n)。

2.單鏈表的查找運算

(1)按序號查找

①鏈表不是隨機存取結(jié)構(gòu)

在鏈表中，即使知道被訪問結(jié)點的序號i,也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈

域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。

②查找的思想方法

計數(shù)器j置為0后，掃描指針p指針從鏈表的頭結(jié)點開始順著鏈掃描。當(dāng)p掃描下一個結(jié)點時，計數(shù)器j相應(yīng)地加1。當(dāng)j=i時，指

針p所指的結(jié)點就是要找的第i個結(jié)點。而當(dāng)p指針指為null且#i時，則表示找不到第i個結(jié)點。

注意：

頭結(jié)點可看做是第0個結(jié)點。

③具體算法實現(xiàn)

ListNode*GetNode(LinkListhead,inti)

{〃在帶頭結(jié)點的單鏈表head中查找第i個結(jié)點，若找到(WiWn),

〃則返回該結(jié)點的存儲位置，否則返回NULL。

intj;

ListNode*p;

p=head;j=0;〃從頭結(jié)點開始掃描

while(p-〉next&&j〈i){〃順指針向后掃描,直到p-〉next為NULL或i=j為止

p=p->next;

j++；

)

if(i==j)

returnp;〃找到了第i個結(jié)點

elsereturnNULL;〃當(dāng)i〈0或i〉0時，找不到第i個結(jié)點

)

④算法分析

算法中，while語句的終止條件是搜索到表尾或者滿足j2i,其頻度最多為i,它和被尋找的位置有關(guān)。在等概率假設(shè)下，平

均時間復(fù)雜度為：

力(+D=+="2=/國

IJ-I

(2)按值查找

①思想方法

從開始結(jié)點出發(fā)，順著鏈逐個將結(jié)點的值和給定值key作比較，若有結(jié)點的值與key相等，則返回首次找到的其值為key的結(jié)

點的存儲位置；否則返回NULL。

②具體算法實現(xiàn)

ListNode*LocateNode(LinkListhead,DataTypekey)

{〃在帶頭結(jié)點的單鏈發(fā)head中查找其值為key的結(jié)點

ListNode*p=head->next;〃從開始結(jié)點比較“我非空，p初始值指向開始結(jié)