基本概念和術(shù)語

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

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

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

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

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

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

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

數(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ù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問

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

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

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

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

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

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

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

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

體實(shí)現(xiàn)這些運(yùn)算。

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

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

學(xué)t成績(jī)表

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

880001J90859590

880002馬二80859085

880003張三95919995

88000470848680

880005王五91849289

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

趨和一個(gè)直接后繼。

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

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

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

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

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

（1）順序存儲(chǔ)方法

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

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

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

（2）鏈接存儲(chǔ)方法

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

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

（3）索引存儲(chǔ)方法

該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引

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

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

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

指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。

（4）散列存儲(chǔ)方法

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

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

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

主要考慮運(yùn)算方便及算法的時(shí)空要求。

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

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

不可取的。

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

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

采用散列存儲(chǔ)方法，則可稱為散列表。

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

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

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

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

了上述限制之后，可分別得到順序?；蜴湕?，順序隊(duì)列或鏈隊(duì)列。

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

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

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

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

乘、除和取模等操作。

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

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

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

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

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

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

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

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

一個(gè)ADT可描述為：

ADTADT-Name{

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

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

Operations:〃操作說明

Operation]:〃操作，它通常可用C或C++的函數(shù)原型來描述

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

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

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

Output:〃對(duì)返回?cái)?shù)據(jù)的說明

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

Operation2://操作

}//ADT

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

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

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

操作。

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

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

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

用程序。

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

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

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

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

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

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

1.計(jì)算機(jī)處理問題的分類

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

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

【例2.1】線性方程的求解

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

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

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

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

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

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

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

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

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

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

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

【例2.2】電話號(hào)碼查詢問題。

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

碼；否則指出該人沒有電話號(hào)碼。

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

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

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

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

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

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

姓名電話號(hào)碼

張二

姓氏地址張林

張?

李張潔

??李四

?

李中

電話號(hào)碼Tri句問題的索引存儲(chǔ)

【例2.3】田徑賽的時(shí)間安排問題。

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

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

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

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

頂點(diǎn)代表競(jìng)賽項(xiàng)目，在所有的兩個(gè)不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上條邊）。顯然同個(gè)選手選擇的兒個(gè)項(xiàng)目是不能在同時(shí)間

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

（2）競(jìng)賽項(xiàng)目的時(shí)間安排問題可以抽象為對(duì)無向圖進(jìn)行“著色”操作：即用盡可能少的顏色去給圖中每個(gè)頂點(diǎn)著色，使得任意兩個(gè)

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

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

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

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

姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3

T-跳高跳遠(yuǎn)100米

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

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

李四鉛球200米跳高

王五跳遠(yuǎn)200米—

參賽選手比賽項(xiàng)11表

三、算法的描述

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

1.算法

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

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

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

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

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

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

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

(1)輸入實(shí)例

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

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

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

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

2.算法的描述

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

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

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

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

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

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

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

voidError(char*message)

(〃輸出錯(cuò)誤信息

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

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

)

四、算法分析

1.評(píng)價(jià)算法好壞的標(biāo)準(zhǔn)

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

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

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

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

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

2.算法性能選擇

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

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

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

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

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

3.算法的時(shí)間性能分析

(1)算法耗費(fèi)的時(shí)間和語句頻度

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

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

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

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

費(fèi)就是該算法中所有語句的頻度之和。

【例3.3】求兩個(gè)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

)

)

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

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

分析：

語句(1)的循環(huán)控制變量i要增加到n,測(cè)試到i=n成立才會(huì)終止。故它的頻度是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的時(shí)間耗費(fèi)T(n)是矩陣階數(shù)n的函數(shù)。

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

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

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

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

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

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

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

a-MBN-??>

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

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

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

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

(3)漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能

主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。

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

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

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

地多。

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

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

度。

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

時(shí)間復(fù)雜度。

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

Temp=i;

i=j；

j=temp;

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

T(n)=O(l)o

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

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

r/列

k13.10]變量計(jì)數(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+

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

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

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

【例3.11】變量計(jì)數(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

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

(4)算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實(shí)例的初始狀態(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)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān)：

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

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

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

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

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

更長(zhǎng)。

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

0(n),

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

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

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

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

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

五、線性表的邏輯定義

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

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

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

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

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

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

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

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

均成績(jī)等數(shù)據(jù)項(xiàng)組成。

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

對(duì)于非空的線性表：

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

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

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

常見的線性表的基本運(yùn)算

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

2.ListLength(L)求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。

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

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

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

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

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

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

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

注意：

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

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

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

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

五、順序表

1.順序表的定義

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

⑵順序表(SequentialList)用順序存儲(chǔ)方法存儲(chǔ)的線性表簡(jiǎn)稱為順序表(SequentialList)o

2.結(jié)點(diǎn)藥的存儲(chǔ)地址

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

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

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

注意：

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

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

3.順序表類型定義

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

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

typedefstruct{

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

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

}SeqUst；

6儲(chǔ)位班下標(biāo)

b0

b*c

b*(i-l)c

b*(rr-l)cn-1

b+ncn

b*(ListSizel)cl.istSize-1

M序表示愈舊

注意：

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

類型來定義順序表類型。

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

義過大而浪費(fèi)存儲(chǔ)空間。

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

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

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

4.順序表的特點(diǎn)

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

亦相鄰。

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

1.表的初始化

voidInitList(SeqList*L)

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

L->length=0；

2.求表長(zhǎng)

intListLength(SeqList*L)

{〃求表長(zhǎng)只需返回L->length

returnL->length;

3.取表中第i個(gè)結(jié)點(diǎn)

DataTypeGetNode(L,i)

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

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

Error("positionerror")；

returnL->data[i-l]；

)

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

【參見參考書】

5,插入

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

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

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

注意：

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

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

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

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

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

入表的末尾。具體過程見【動(dòng)畫演示】

(3)具體算法描述

voidInsertList(SeqList*L,DataTypex,inti)

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

intj;

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

ErrorC'positionerror");法位置，退出運(yùn)行

if(L->length>=ListSize)

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

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

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

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

L->Length++;〃表長(zhǎng)加

(4)算法分析

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

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

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

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

③移動(dòng)結(jié)點(diǎn)的平均次數(shù)Eis(n)

&3Axp0T+D

u1

其中：

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

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

均等的，則

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

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

即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)。

6.刪除

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

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

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

注意：

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

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

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

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

缺。其刪除過程【參見動(dòng)畫演示】

(3)具體算法描述

voidDeleteList(SeqList*L,inti)

{〃從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)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é)點(diǎn)前移

L->length—;〃表長(zhǎng)減小

)

(4)算法分析

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

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

②移動(dòng)結(jié)點(diǎn)的平均次數(shù)EDE(n)

4-1

其中：

刪除表中第i個(gè)位置結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i

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

則

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

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

M

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

七、單鏈表

1、鏈接存儲(chǔ)方法

鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表(LinkedList).

鏈表的具體存儲(chǔ)表示為：

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

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

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

注意：

鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。

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

Idata|next|

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

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

注意：

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

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

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

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

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

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

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

終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即NULL。

4、單鏈表的一般圖示法

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

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

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

單鏈表的一般圖示法

5、單鏈表類型描述

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

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

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

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

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

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

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

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

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

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

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

11

1指針變量1結(jié)點(diǎn)變量

11

11

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

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

1

1T

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

1型結(jié)點(diǎn)的地址1

11

111

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

1J__11

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

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

〃函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中

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

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

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

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

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

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

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

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

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

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

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

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

注意：

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

從而引起程序的錯(cuò)誤。

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

八、單鏈表的運(yùn)算

1、建立單鏈表

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

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

(1)頭插法建表

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

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

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

具體方法【參見動(dòng)畫演示】

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

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

LinkListCreatListF(void)

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

charch;

LinkListhead;〃頭指針

ListNode*s;//工作指針

head=NULL;〃鏈表開始為空

ch=getcharO;〃讀入第個(gè)字符

while(ch!=，\n){

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

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

s->next=head;

head=s;

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

)

returnhead;

)

(2)尾插法建表

①算法思路

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

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

head―a|.|?,

、、③1

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

具體方法【參見動(dòng)畫演示】

注意：

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

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

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

LinkListCreatListR(void)

{〃返回單鏈表的頭指針

charch;

LinkListhead;〃頭指針

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

head=NULL;〃鏈表開始為空

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

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

while(ch!='\n'){

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

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

if(head!=NULL)

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

else

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

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

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

"/endwhile

if(r!=NULL)

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

returnhead;

)

注意：

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

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

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

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

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

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

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

①頭結(jié)點(diǎn)及作用

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

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

進(jìn)行特殊處理；

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

了。

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

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

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

(a)非空表

FbH~~Fl

附中?&示期影

(b)空表

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

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

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

LinkListCreatListRl(void)

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

charch;

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

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

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

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

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

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

r->next=s;

r=s;

)

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

returnhead;

)

注意：

上述算法里，動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，這對(duì)申請(qǐng)空間極少的程序而言不會(huì)出問題。但在實(shí)用程序里，尤其是對(duì)

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

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

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

2.單鏈表的查找運(yùn)算

(1)按序號(hào)查找

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

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

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

②查找的思想方法

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

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

注意：

頭結(jié)點(diǎn)可看做是第0個(gè)結(jié)點(diǎn)。

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

ListNode*GetNode(LinkListhead,inti)

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

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

intj;

ListNode*p;

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

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

p=p->next;

j++；

)

if(i==j)

returnp;〃找到了第i個(gè)結(jié)點(diǎn)

elsereturnNULL;〃當(dāng)i〈0或i〉0時(shí)，找不到第i個(gè)結(jié)點(diǎn)

)

④算法分析

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

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

力(+D=+="2=/國(guó)

IJ-I

(2)按值查找

①思想方法

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

點(diǎn)的存儲(chǔ)位置；否則返回NULL。

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

ListNode*LocateNode(LinkListhead,DataTypekey)

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

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