教學(xué)課件-數(shù)據(jù)結(jié)構(gòu)教程(胡元義)

第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)的概念1.2邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)1.3算法與算法分析

1.1數(shù)據(jù)結(jié)構(gòu)的概念

人們利用計(jì)算機(jī)的目的是解決實(shí)際問(wèn)題。在明確所要解決問(wèn)題的基礎(chǔ)上，經(jīng)過(guò)對(duì)問(wèn)題的深入分析和抽象，為其在計(jì)算機(jī)中建立一個(gè)模型，然后確定恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示該模型，再在此基礎(chǔ)上設(shè)計(jì)合適的算法，最后根據(jù)設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行相應(yīng)的程序設(shè)計(jì)來(lái)模擬和解決實(shí)際問(wèn)題，這就是計(jì)算機(jī)求解問(wèn)題的一般過(guò)程。因此，用計(jì)算機(jī)解決實(shí)際問(wèn)題的軟件開發(fā)一般分為下面幾個(gè)步驟：

(1)分析階段：分析實(shí)際問(wèn)題，從中抽象出一個(gè)數(shù)學(xué)模型。

(2)設(shè)計(jì)階段：設(shè)計(jì)出解決數(shù)學(xué)模型的算法。

(3)編程階段：用適當(dāng)?shù)木幊陶Z(yǔ)言編寫出可執(zhí)行的程序。

(4)測(cè)試階段：測(cè)試、修改直到得到問(wèn)題的解答。

數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開發(fā)過(guò)程中的設(shè)計(jì)階段，同時(shí)涉及分析階段和編程階段的若干基本問(wèn)題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容包括了如表1.1所示的數(shù)據(jù)表示和數(shù)據(jù)處理方面所對(duì)應(yīng)的3個(gè)層次。

數(shù)據(jù)結(jié)構(gòu)的核心內(nèi)容是分解與抽象。通過(guò)對(duì)問(wèn)題的抽象，舍棄數(shù)據(jù)元素(含義見后)的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過(guò)分解將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)的細(xì)節(jié)，就得到基本運(yùn)算的定義。上述兩個(gè)方面的結(jié)合使人們將問(wèn)題轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)，這是一個(gè)從具體(即具體問(wèn)題)到抽象(即數(shù)據(jù)結(jié)構(gòu))的過(guò)程。然后，通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮，進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，從而完成設(shè)計(jì)任務(wù)，這是一個(gè)從抽象(即數(shù)據(jù)結(jié)構(gòu))到具體(即具體實(shí)現(xiàn))的過(guò)程。熟練掌握這兩個(gè)過(guò)程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。1.1.1數(shù)據(jù)與數(shù)據(jù)元素

數(shù)據(jù)是人們利用文字符號(hào)、數(shù)學(xué)符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述。簡(jiǎn)而言之，數(shù)據(jù)是信息的載體，是對(duì)客觀事物的符號(hào)化表示。從計(jì)算機(jī)的角度看，數(shù)據(jù)是計(jì)算機(jī)程序?qū)λ枋隹陀^事物進(jìn)行加工處理的一種表示，凡是能夠被計(jì)算機(jī)識(shí)別、存取和加工處理的符號(hào)、字符、圖形、圖像、聲音、視頻信號(hào)等都可以稱為數(shù)據(jù)。我們?nèi)粘Ｉ婕暗降臄?shù)據(jù)主要分為兩類：一類是數(shù)值數(shù)據(jù)，包括整數(shù)、實(shí)數(shù)和復(fù)數(shù)等，它們主要用于工程和科學(xué)計(jì)算以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串以及文字、圖形、語(yǔ)音等，它們多用于控制、管理和數(shù)據(jù)處理等領(lǐng)域。

數(shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)“個(gè)體”，是數(shù)據(jù)的基本單位。在計(jì)算機(jī)中，數(shù)據(jù)元素通常被作為一個(gè)整體來(lái)進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄等。一個(gè)數(shù)據(jù)元素可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位，有時(shí)也稱為字段或域。例1.1一個(gè)學(xué)生信息(數(shù)據(jù))表如表1.2所示，請(qǐng)指出表中的數(shù)據(jù)、數(shù)據(jù)元素及數(shù)據(jù)項(xiàng)，并由此得出三者之間的關(guān)系。

【解】表1.2中是全部學(xué)生信息數(shù)據(jù)。表中的每一行即為記錄一個(gè)學(xué)生信息的數(shù)據(jù)元素，而該行中的每一項(xiàng)則為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際上反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可以由若干個(gè)數(shù)據(jù)元素構(gòu)成，而數(shù)據(jù)元素則又可以由若干數(shù)據(jù)項(xiàng)構(gòu)成。1.1.2數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素以及數(shù)據(jù)元素之間的相互關(guān)系，也即數(shù)據(jù)的組織形式，可以看做是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素集合。也即，可以把數(shù)據(jù)結(jié)構(gòu)看做是帶結(jié)構(gòu)的數(shù)據(jù)元素集合。進(jìn)一步說(shuō)，數(shù)據(jù)結(jié)構(gòu)描述按照一定邏輯關(guān)系組織起來(lái)的待處理數(shù)據(jù)元素的表示及相關(guān)操作，涉及數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算。因此，數(shù)據(jù)結(jié)構(gòu)包含以下三個(gè)方面的內(nèi)容：

(1)數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。

(2)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))。

(3)施加在數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上(主要指相鄰關(guān)系)來(lái)描述數(shù)據(jù)的，它與數(shù)據(jù)如何存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像表示，即在能夠反映數(shù)據(jù)邏輯關(guān)系的前提下數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方式。

數(shù)據(jù)的運(yùn)算是在數(shù)據(jù)上所施加的一系列操作，稱為抽象運(yùn)算，它只考慮這些操作的功能，而暫不考慮如何完成，只有在確定了存儲(chǔ)結(jié)構(gòu)后，才會(huì)具體實(shí)現(xiàn)這些操作。也即，抽象運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而實(shí)現(xiàn)則是建立在存儲(chǔ)結(jié)構(gòu)上的。最常用的運(yùn)算有：檢索、插入、刪除、更新以及排序等。 1.2邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

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

數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間邏輯關(guān)系的描述，它與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，可以劃分出以下四種基本邏輯結(jié)構(gòu)，如圖1-1所示。

(1)集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“屬于同一集合”的聯(lián)系之外，沒(méi)有其他關(guān)系。

(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)一”的關(guān)系。數(shù)據(jù)之間存在前后順序關(guān)系，除第一個(gè)元素和最后一個(gè)元素外，其余元素都有唯一一個(gè)前驅(qū)元素和唯一一個(gè)后繼元素。

(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著“一對(duì)多”的關(guān)系。數(shù)據(jù)之間存在層次關(guān)系，除了一個(gè)根結(jié)點(diǎn)(元素)外，其余元素(結(jié)點(diǎn))都有唯一一個(gè)前驅(qū)元素，并且可以有多個(gè)后繼元素。

(4)圖結(jié)構(gòu)(或稱網(wǎng)狀結(jié)構(gòu))：數(shù)據(jù)元素之間存在著“多對(duì)多”的關(guān)系。也即，每個(gè)元素都可以有多個(gè)前驅(qū)元素和多個(gè)后繼元素。圖1-1邏輯結(jié)構(gòu)的四種基本形態(tài)由于集合結(jié)構(gòu)具有簡(jiǎn)單性和松散性，因此通常只討論其他三種邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。若數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個(gè)線性序列簡(jiǎn)單地表示出來(lái)，則稱為線性結(jié)構(gòu)，否則稱為非線性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖結(jié)構(gòu)就屬于非線性結(jié)構(gòu)?，F(xiàn)實(shí)生活中的樓層編號(hào)就屬于線性結(jié)構(gòu)，而省、市、地區(qū)的劃分屬于樹形結(jié)構(gòu)，城市交通圖則屬于圖結(jié)構(gòu)。關(guān)于邏輯結(jié)構(gòu)需要注意以下幾點(diǎn)：

(1)邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無(wú)關(guān)。例如，給表1.2中的每個(gè)學(xué)生增加一個(gè)數(shù)據(jù)項(xiàng)“學(xué)號(hào)”，就得到另一個(gè)數(shù)據(jù)，但由于所有的數(shù)據(jù)元素仍是“一個(gè)接一個(gè)排列”，故新數(shù)據(jù)的邏輯結(jié)構(gòu)與原來(lái)數(shù)據(jù)的邏輯結(jié)構(gòu)相同，仍是一個(gè)線性結(jié)構(gòu)。

(2)邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)。例如，將表1.2中的學(xué)生按年齡由大到小的順序重新排列就得到另一個(gè)表格，但這個(gè)新表格中的所有數(shù)據(jù)元素“一個(gè)接一個(gè)排列”的性質(zhì)并沒(méi)有改變，其邏輯結(jié)構(gòu)與原表格相同，還是線性結(jié)構(gòu)。

(3)邏輯結(jié)構(gòu)與所含數(shù)據(jù)元素的個(gè)數(shù)無(wú)關(guān)。例如，在表1.2中增加或刪除若干學(xué)生信息(數(shù)據(jù)元素)，所得到的表格仍為線性結(jié)構(gòu)。1.2.2存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示方法，也即數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像，包括數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素的表示以及數(shù)據(jù)元素之間關(guān)系的表示。數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中可以有以下四種基本存儲(chǔ)結(jié)構(gòu)：

(1)順序存儲(chǔ)結(jié)構(gòu)：借助于數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。通常順序存儲(chǔ)結(jié)構(gòu)是利用程序語(yǔ)言中的數(shù)組來(lái)描述的。

(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在數(shù)據(jù)元素上附加指針域，并借助指針來(lái)指示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常是利用程序語(yǔ)言中的指針類型來(lái)描述的。

(3)索引存儲(chǔ)結(jié)構(gòu)：在存儲(chǔ)所有數(shù)據(jù)元素信息的同時(shí)建立附加索引表。索引表中表項(xiàng)的一般形式是：(關(guān)鍵字，地址)。關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它唯一標(biāo)識(shí)該數(shù)據(jù)元素；地址則是指向該數(shù)據(jù)元素的指針。由關(guān)鍵字可以立即通過(guò)地址找到該數(shù)據(jù)元素。

(4)哈希(或散列)存儲(chǔ)結(jié)構(gòu)：此方法的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字通過(guò)哈希(或散列)函數(shù)直接計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)地址。順序存儲(chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)是節(jié)省存儲(chǔ)空間，即分配給數(shù)據(jù)的存儲(chǔ)單元全部用于存放數(shù)據(jù)元素的數(shù)據(jù)信息，數(shù)據(jù)元素之間的邏輯關(guān)系沒(méi)有占用額外的存儲(chǔ)空間。采用這種存儲(chǔ)結(jié)構(gòu)可以實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的隨機(jī)存取，即每個(gè)數(shù)據(jù)元素對(duì)應(yīng)有一個(gè)序號(hào)，并由該序號(hào)可以直接計(jì)算出數(shù)據(jù)元素的存儲(chǔ)地址(例如對(duì)于數(shù)組A其序號(hào)為數(shù)組元素的下標(biāo)，數(shù)組元素A[i]可以通過(guò)*(A+i)進(jìn)行存取)。但順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不便于修改，對(duì)數(shù)據(jù)元素進(jìn)行插入、刪除運(yùn)算時(shí)，可能要移動(dòng)一系列的數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)是便于修改，在進(jìn)行插入、刪除運(yùn)算時(shí)僅需修改相應(yīng)數(shù)據(jù)元素的指針值，而不必移動(dòng)數(shù)據(jù)元素。與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要缺點(diǎn)是存儲(chǔ)空間的利用率較低，因?yàn)槌擞糜跀?shù)據(jù)元素的存儲(chǔ)空間外還需要額外的存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。此外，由于邏輯上相鄰的數(shù)據(jù)元素在存儲(chǔ)空間中不一定相鄰。所以不能對(duì)數(shù)據(jù)元素進(jìn)行隨機(jī)存取。

線性結(jié)構(gòu)采用索引存儲(chǔ)方法后就可以對(duì)結(jié)點(diǎn)進(jìn)行隨機(jī)訪問(wèn)。在進(jìn)行插入、刪除運(yùn)算時(shí)，只需改動(dòng)存儲(chǔ)在索引表中數(shù)據(jù)元素的存儲(chǔ)地址，而不必移動(dòng)數(shù)據(jù)元素，所以仍保持較高的數(shù)據(jù)修改和運(yùn)算效率。索引存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)是增加了索引表，這也降低了存儲(chǔ)空間的利用率。哈希(或散列)存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是查找速度快，只要給出待查數(shù)據(jù)元素的關(guān)鍵字，就可以立即計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)地址。與前面三種存儲(chǔ)方法不同的是，哈希存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)而不存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。哈希存儲(chǔ)結(jié)構(gòu)一般只適合于對(duì)數(shù)據(jù)進(jìn)行快速查找和插入的場(chǎng)合。

圖1-2給出了表1.2在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的示意。圖1-2表1.2在不同的存儲(chǔ)結(jié)構(gòu)下的存儲(chǔ)示意 1.3算法與算法分析

1.3.1算法的定義和描述

算法是建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上對(duì)特定問(wèn)題求解步驟的一種描述，是若干條指令組成的有限序列。其中，每一條指令表示一個(gè)或多個(gè)操作。算法必須滿足以下性質(zhì)：

(1)有窮性：一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。

(2)確定性：算法的每一步必須有確切的含義而沒(méi)有二義性。對(duì)于相同的輸入，算法執(zhí)行的路徑是唯一的。

(3)可行性：算法所描述的操作都可以通過(guò)可實(shí)現(xiàn)的基本運(yùn)算在有限次執(zhí)行后得以完成。

(4)輸入：一個(gè)算法可以有零個(gè)或多個(gè)輸入。

(5)輸出：一個(gè)算法具有一個(gè)或多個(gè)輸出，且輸出與輸入之間存在某種特定的關(guān)系。算法的含義與程序十分相似但又有區(qū)別。一個(gè)程序不一定滿足有窮性，例如操作系統(tǒng)程序只要不停機(jī)執(zhí)行就永不停止，因此，操作系統(tǒng)不是一個(gè)算法。此外，程序中的語(yǔ)句最終都要轉(zhuǎn)化(編譯)成計(jì)算機(jī)可執(zhí)行的指令，而算法中的指令則無(wú)此限制，即一個(gè)算法可采用自然語(yǔ)言如英語(yǔ)、漢語(yǔ)描述，也可以采用圖形方式如流程圖、拓?fù)鋱D描述。算法給出了對(duì)一個(gè)問(wèn)題的求解，而程序僅是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來(lái)描述，則此時(shí)算法也就是一個(gè)程序。

對(duì)某個(gè)特定問(wèn)題的求解究竟采用何種數(shù)據(jù)結(jié)構(gòu)及選擇什么算法，需要看問(wèn)題的具體要求和現(xiàn)實(shí)環(huán)境的各種條件；數(shù)據(jù)結(jié)構(gòu)的選擇是否恰當(dāng)將直接影響到算法的效率，只有把數(shù)據(jù)結(jié)構(gòu)與算法有機(jī)地結(jié)合起來(lái)才能設(shè)計(jì)出高質(zhì)量的程序來(lái)。圖1-3求最大公約數(shù)的算法

例1.2

對(duì)兩個(gè)正整數(shù)m和n，給出求它們最大公因子的算法。

【解】算法設(shè)計(jì)如下：

(1)求余數(shù)：以n除m，余數(shù)為r，且0≤?r＜n。

(2)判斷余數(shù)r是否等于零：如果r為零，則輸出n的當(dāng)前值(即為最大公因子)，算法結(jié)束；否則執(zhí)行(3)。

(3)將n值傳給m、將r值傳給n，轉(zhuǎn)(1)。上述算法給出了三個(gè)計(jì)算步驟，而且每一步驟意義明確并切實(shí)可行。雖然出現(xiàn)了循環(huán)，但m和n都是已給定的有限整數(shù)，并且每次m除以n后得到的余數(shù)r即使不為零也總有r<min(m，n)，這就保證循環(huán)執(zhí)行有限次后必然終止，即滿足算法的所有特征，所以是一個(gè)正確的算法。1.3.2算法分析和復(fù)雜度計(jì)算

算法設(shè)計(jì)主要是考慮可解算法的設(shè)計(jì)，而算法分析則是研究和比較各種算法的性能與優(yōu)劣。算法的時(shí)間復(fù)雜度和空間復(fù)雜度是算法分析的兩個(gè)主要方面，其目的主要是考察算法的時(shí)間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。

(1)時(shí)間復(fù)雜度：一個(gè)程序的時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。

(2)空間復(fù)雜度：一個(gè)程序的空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。在復(fù)雜度計(jì)算中，實(shí)際上是把求解問(wèn)題的關(guān)鍵操作，如加法、減法和比較運(yùn)算指定為基本操作，然后把算法執(zhí)行基本操作的次數(shù)作為算法的時(shí)間復(fù)雜度，而算法執(zhí)行期間占用存儲(chǔ)單元的數(shù)量作為算法的空間復(fù)雜度。

在此，涉及到頻度的概念，即語(yǔ)句(指令)的頻度是指它在算法中被重復(fù)執(zhí)行的次數(shù)。一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句(指令)的頻度之和(記作T(n))，它是該算法所求解問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)。當(dāng)問(wèn)題規(guī)模n趨向無(wú)窮大時(shí)，T(n)的數(shù)量級(jí)稱為時(shí)間復(fù)雜度，記作：

T(n)＝O(f(n))上述式子中“O”的文字含義是T(n)的數(shù)量級(jí)，其嚴(yán)格的數(shù)學(xué)定義是：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則存在正常數(shù)C和n0，使得當(dāng)n≥n0時(shí)都滿足：

0≤T(n)≤C·f(n)算法的時(shí)間復(fù)雜度采用這種數(shù)量級(jí)的形式表示后，將給分析算法的時(shí)間復(fù)雜度帶來(lái)很大的方便。即對(duì)一個(gè)算法，只需分析影響該算法時(shí)間復(fù)雜度的主要部分即可，而無(wú)需對(duì)該算法的每一個(gè)語(yǔ)句都進(jìn)行詳細(xì)的分析。

(1)執(zhí)行一條讀寫語(yǔ)句或賦值語(yǔ)句所用的時(shí)間為O(1)。

(2)依次執(zhí)行一系列語(yǔ)句所用的時(shí)間采用求和準(zhǔn)則。

(3)條件語(yǔ)句if的耗時(shí)主要是當(dāng)條件為真時(shí)執(zhí)行語(yǔ)句體所用的時(shí)間，而檢測(cè)條件是否為真還需耗費(fèi)O(1)。

(4)對(duì)while、do…while和for這樣的循環(huán)語(yǔ)句，其運(yùn)行時(shí)間為每次執(zhí)行循環(huán)體及檢測(cè)是否繼續(xù)循環(huán)的時(shí)間，故常用乘法準(zhǔn)則。例1.3

試求下面程序段的時(shí)間復(fù)雜度。

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

C[i][j]=0;

for(k=0;k<n;k++)

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

}

【解】我們給程序中的語(yǔ)句進(jìn)行編號(hào)，并在其右側(cè)列出該語(yǔ)句的頻度：

(1)

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

(2)

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

{

(3)

C[i][j]=0 n2

(4)

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

(5)

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

n3

}第2章線性表2.1線性表及其邏輯結(jié)構(gòu)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 2.1線性表及其邏輯結(jié)構(gòu)

2.1.1線性表的定義

線性表是一種線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間是線性關(guān)系，數(shù)據(jù)元素“一個(gè)接一個(gè)的排列”；并且，在一個(gè)線性表中所有數(shù)據(jù)元素的類型都是相同的。簡(jiǎn)單地說(shuō)，一個(gè)線性表是n個(gè)元素的有限序列，其特點(diǎn)是在數(shù)據(jù)元素的非空集合中：

(1)存在唯一一個(gè)稱為“第一個(gè)”的元素。

(2)存在唯一一個(gè)稱為“最后一個(gè)”的元素。

(3)除第一個(gè)元素之外，序列中的每一個(gè)元素只有一個(gè)直接前驅(qū)。

(4)除最后一個(gè)元素之外，序列中的每一個(gè)元素只有一個(gè)直接后繼。

因此，我們可以給出線性表的定義如下：

線性表是具有相同數(shù)據(jù)類型的n(n≥0)個(gè)數(shù)據(jù)元素的有限序列，通常記為

(2-1)其中，n為表長(zhǎng)，n=0時(shí)稱為空表。式(2-1)表示相鄰元素之間存在著順序關(guān)系：ai-1稱為ai的直接前驅(qū)，ai+1稱為ai的直接后繼。也就是說(shuō)：對(duì)于ai，當(dāng)i=2,…,n時(shí)，有且僅有一個(gè)直接前驅(qū)ai-1；當(dāng)i=1,2,…,n-1時(shí)，有且僅有一個(gè)直接后繼ai+1；而a1是表中的第一個(gè)元素，它沒(méi)有前驅(qū)；an是表中的最后一個(gè)元素，它沒(méi)有后繼。正是由于存在數(shù)據(jù)元素相鄰的這種線性關(guān)系，因此線性表結(jié)構(gòu)是線性的。由式(2-1)還可得知：對(duì)非空線性表，每個(gè)數(shù)據(jù)元素在表中都有一個(gè)確定的位置，即數(shù)據(jù)元素ai在表中的位置僅取決于元素ai本身的序號(hào)i。

從邏輯關(guān)系上看，線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間存在著“一對(duì)一”的邏輯關(guān)系。通常把具有這種特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。反之，任何一個(gè)線性結(jié)構(gòu)(其數(shù)據(jù)元素必須是同一類型)都可以用線性表的形式表示出來(lái)，只需按照數(shù)據(jù)元素的邏輯關(guān)系把它們順序排列就可以了。由線性表的定義可以看出，線性表具有如下特征：

(1)均勻性：線性表中的所有數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型，無(wú)論該類型為簡(jiǎn)單類型還是結(jié)構(gòu)類型。也即，線性表中每個(gè)數(shù)據(jù)元素的長(zhǎng)度、大小和類型都相同。

(2)有序性：線性表中各數(shù)據(jù)元素是有序的，且各數(shù)據(jù)元素之間的次序是不能改變的。為了反映這種有序性，對(duì)線性表中的每一個(gè)數(shù)據(jù)元素用序號(hào)標(biāo)識(shí)，并且所有序號(hào)均為整數(shù)。2.1.2線性表的基本操作

數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層面上，而運(yùn)算的具體實(shí)現(xiàn)則建立在存儲(chǔ)結(jié)構(gòu)上。因此，下面定義的線性表基本運(yùn)算是作為邏輯結(jié)構(gòu)的一部分，并且每一個(gè)操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲(chǔ)結(jié)構(gòu)之后才能完成。

歸納起來(lái)，對(duì)線性表實(shí)施的基本操作有如下幾種：

(1)置線性表為空：L=Init_List()。操作結(jié)果生成一個(gè)空的線性表L。

(2)求線性表的長(zhǎng)度：Length_List(L)。求得線性表中數(shù)據(jù)元素的個(gè)數(shù)。

(3)取表中第i個(gè)元素：Get_List(L,i)。當(dāng)1≤i≤Length_List(L)時(shí)，操作結(jié)果是返回線性表L中的第i個(gè)數(shù)據(jù)元素ai的值或ai的地址。

(4)按給定值x查找：Locate_List(L,x)。若線性表L中存在值為x的數(shù)據(jù)元素，則返回首次出現(xiàn)在L中其值為x的數(shù)據(jù)元素的序號(hào)或地址，即查找成功；否則返回0值。

(5)插入操作：Insert_List(L,i,x)。當(dāng)1≤i≤n+1(n為插入前表L的長(zhǎng)度)時(shí)，在線性表L的第i個(gè)位置上插入一個(gè)值為x的新數(shù)據(jù)元素，這樣使序號(hào)為i、i+1、…、n的數(shù)據(jù)元素變?yōu)樾蛱?hào)為i+1、i+2、…、n+1的數(shù)據(jù)元素。插入后新表長(zhǎng)=原表長(zhǎng)+1。

(6)刪除操作：Delete_List(L,i)。當(dāng)1≤i≤n(n為刪除前表L的長(zhǎng)度)時(shí)，在線性表L中刪除序號(hào)為i的數(shù)據(jù)元素，刪除后使序號(hào)為i+1、i+2、…、n的數(shù)據(jù)元素變?yōu)樾蛱?hào)為i、i+1、...、n-1的數(shù)據(jù)元素。刪除后新表長(zhǎng)=原表長(zhǎng)-1。

2.2線性表的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

2.2.1線性表的順序存儲(chǔ)——順序表

線性表的順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元按順序依次存放線性表中的每一個(gè)元素(數(shù)據(jù)元素)，這種存儲(chǔ)方式存儲(chǔ)的線性表稱為順序表。在這種順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰，也即無(wú)需增加額外存儲(chǔ)空間來(lái)表示線性表中元素之間的邏輯關(guān)系。

由于順序表中每個(gè)元素具有相同的類型，即其長(zhǎng)度相同，則順序表中第i個(gè)元素ai的存儲(chǔ)地址為L(zhǎng)oc(ai)?=?Loc(a1)+(i-1)×L1≤i≤n其中：Loc(a1)為順序表的起始地址(即第一個(gè)元素的地址)；L為每個(gè)元素所占存儲(chǔ)空間的大小。由此可知，只要知道順序表的起始地址和每個(gè)元素所占存儲(chǔ)空間的大小，就可以求出任意一個(gè)元素的存儲(chǔ)地址，即順序表中的任意一個(gè)元素都可以隨機(jī)存取(隨機(jī)存取的特點(diǎn)是存取每一個(gè)元素所花費(fèi)的時(shí)間相同)。

在程序設(shè)計(jì)語(yǔ)言中，一維數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組連續(xù)的存儲(chǔ)區(qū)域，并且每個(gè)數(shù)組元素的類型相同，故用一維數(shù)組來(lái)存儲(chǔ)順序表非常合適。在C語(yǔ)言中，一維數(shù)組的數(shù)組元素下標(biāo)是從0開始的，這樣順序表中序號(hào)為i的元素ai存儲(chǔ)在一維數(shù)組中時(shí)其下標(biāo)為i-1。為了避免這種不一致性，我們約定：順序表中的元素存放于一維數(shù)組時(shí)是從下標(biāo)為1的位置開始的。這樣，元素的序號(hào)即為其下標(biāo)。此外，考慮到順序表的運(yùn)算有插入、刪除等操作，即表長(zhǎng)是可變的，因此，數(shù)組的容量需要設(shè)計(jì)得足夠大。我們用data[MAXSIZE]來(lái)存儲(chǔ)順序表，而MAXSIZE是根據(jù)實(shí)際問(wèn)題所定義的一個(gè)足夠大的整數(shù)。此時(shí)順序表中的數(shù)據(jù)由data[1]開始依次存放。由于當(dāng)前順序表中的實(shí)際元素個(gè)數(shù)可能還未達(dá)到MAXSIZE-1值，因此需要用一個(gè)len變量來(lái)記錄當(dāng)前順序表中最后一個(gè)元素在數(shù)組中的位置(即下標(biāo))；即len起著一個(gè)指針的作用，它始終指向順序表中的最后一個(gè)元素且表空時(shí)len=0。從結(jié)構(gòu)上考慮，我們將data和len組合在一個(gè)結(jié)構(gòu)體里來(lái)作為順序表的類型：

typedefstruct

{

datatypedata[MAXSIZE];//存儲(chǔ)順序表中的元素

intlen;//順序表的表長(zhǎng)

}SeqList;//順序表類型

其中，datatype為順序表中元素的類型，在具體實(shí)現(xiàn)中可為int、float、char類型或其他結(jié)構(gòu)類型。我們約定，data數(shù)組存放順序表的元素是從下標(biāo)1開始的；也即，順序表中的元素可存放在data數(shù)組中下標(biāo)為1～MAXSIZE-1的任何一個(gè)位置。這樣，第i個(gè)元素的實(shí)際存放位置就是i；len為順序表的表長(zhǎng)。有了順序表類型，則可以定義如下順序表和指向順序表的指針變量：

SeqListList,*L;

在此，List是一個(gè)結(jié)構(gòu)體變量，它內(nèi)部含有一個(gè)可存儲(chǔ)順序表的data數(shù)組；L是指向List這類結(jié)構(gòu)體變量的指針變量，如“L=&List;”；或者動(dòng)態(tài)生成一個(gè)順序表存儲(chǔ)空間并由L指向該空間，如“L=(SeqList*)malloc(sizeof(SeqList));”。在這種定義下，List.data[i]或L->data[i]均表示順序表中第i個(gè)元素的值；而List.len或L->len均表示順序表的表長(zhǎng)。兩種表示示意如圖2-1所示。圖2-1線性表順序存儲(chǔ)的不同表示2.2.2順序表上基本運(yùn)算的實(shí)現(xiàn)

1.順序表的初始化

順序表的初始化就是構(gòu)造一個(gè)空表，將L設(shè)為指針變量，然后動(dòng)態(tài)分配順序表的存儲(chǔ)空間，并設(shè)表長(zhǎng)len=0。

算法如下：

SeqList*Init_SeqList()

{

SeqList*L;

L=(SeqList*)malloc(sizeof(SeqList));

L->len=0;

returnL;

}

2.建立順序表

依次輸入順序表的長(zhǎng)度n和n個(gè)順序表元素即可建立順序表。算法如下：

voidCreatList(SeqList**L)

{

inti,n;

printf("InputlengthofList:");

scanf("%d",&n);

printf("InputelementsofList:\n");

for(i=1;i<=n;i++)

scanf("%d",&(*L)->data[i]);

(*L)->len=n;

}注意，形參**L是為了保證在函數(shù)CreatList中生成的順序表返回到主調(diào)函數(shù)空間時(shí)仍能夠找到它，這樣當(dāng)CreatList函數(shù)調(diào)用結(jié)束時(shí)，仍可在主調(diào)函數(shù)中訪問(wèn)該順序表。主調(diào)函數(shù)必需設(shè)置一個(gè)SeqList型指針變量(如SeqList*p)，然后使用語(yǔ)句“p=Init_SeqList();”和語(yǔ)句“CreatList(&p);”即可完成順序表的建立。插入時(shí)可能出現(xiàn)下述非法情況：

(1)當(dāng)L->len=MAXSIZE-1，順序表已放滿元素。

(2)當(dāng)i＜1或i≥MAXSIZE時(shí)，i已超出數(shù)組范圍。

(3)當(dāng)L->len+1＜i＜MAXSIZE時(shí)，i雖沒(méi)有超出數(shù)組范圍，但i指示的位置使得順序表元素不再連續(xù)存放。

(2)、(3)可以用i＜1或i＞L->len+1表示。算法如下：

voidInsert_SeqList(SeqList*L,inti,datatypex)

{

intj;

if(L->len==MAXSIZE-1) //表滿

printf(“TheListisfull!\n”);

else

if(i<1||i>L->len+1) //插入位置非法

printf(“Thepositionisinvalid!\n”);

else

{

for(j=L->len;j>=i;j--)

//將an～ai順序后移一個(gè)元素位置

L->data[j+1]=L->data[j];

L->data[i]=x;

//插入x到第i個(gè)位置

L->len++;

//表長(zhǎng)增1

}

}順序表進(jìn)行插入運(yùn)算的時(shí)間消耗主要在表中元素的移動(dòng)上。對(duì)n個(gè)元素的順序表來(lái)說(shuō)：

(1)可插入的位置從1～n+1共有n+1個(gè)位置。

(2)在第i個(gè)位置上插入新元素時(shí)需要移動(dòng)的元素個(gè)數(shù)為：n-(i-1)?=?n-i?+?1(如圖2-2所示)。圖2-2插入新元素時(shí)需要移動(dòng)的元素示意圖也即，在順序表上做插入操作需要移動(dòng)表中一半的元素，顯然時(shí)間復(fù)雜度為O(n)。刪除時(shí)可能會(huì)出現(xiàn)下述非法情況：

(1)當(dāng)L->len=0時(shí)，順序表為空而無(wú)法刪除。

(2)當(dāng)i＜1或i＞L->Len時(shí)，i位置上沒(méi)有元素，即刪除位置非法。算法如下：

voidDelete_SeqList(SeqList*L,datatypei)

{

intj;

if(L->len==0) //表為空

printf("TheListisempt!\n");

else

if(i<1||i>L->len) //刪除位置非法

printf("Thepositionisinvalid!\n");

else

{

for(j=i+1;j<=L->len;j++) //將ai+1～an順序前移一個(gè)位置實(shí)現(xiàn)對(duì)ai的刪除

L->data[j-1]=L->data[j];

L->len--; //表長(zhǎng)減1

}

}與插入運(yùn)算相同，刪除運(yùn)算的時(shí)間消耗主要在表中元素的移動(dòng)上。對(duì)有n個(gè)元素的順序表來(lái)說(shuō)：

(1)可刪除的位置從1～n共有n個(gè)。

(2)刪除第i個(gè)元素時(shí)需要移動(dòng)的元素的個(gè)數(shù)為：n-i(如圖2-3所示)。圖2-3刪除ai時(shí)要移動(dòng)的元素示意圖也即，在順序表上做刪除運(yùn)算大約需要移動(dòng)表中一半的元素，顯然算法的時(shí)間復(fù)雜度為O(n)。

5.查找運(yùn)算

查找運(yùn)算是指在順序表中查找與給定值x相等的元素。在順序表中完成該運(yùn)算最簡(jiǎn)單的方法是：從第一個(gè)元素a1起依次和x比較，直到找到一個(gè)與x相等的元素時(shí)則返回該元素的存儲(chǔ)位置(即下標(biāo))；如果查遍整個(gè)表都沒(méi)找到與x相等的元素則返回0值。算法一如下：

intLocation_SeqList(SeqList*L,datatypex)

{

inti=1; //從第一個(gè)元素開始查找

while(i<L->len&&L->data[i]!=x) //順序表未查完且當(dāng)前元素不是要找的元素

i++;

if(L->data[i]==x)

returni; //找到則返回其位置值

else

return0; //未找到則返回0值

}該算法還可以改進(jìn)為如下算法二：

intLocation_SeqList1(SeqList*L,datatypex)

{

i=L->len;

L->data[0]=x;

while(L->data[i]!=x)

i--;

returni;

}算法一：算法二：因此，查找算法的時(shí)間復(fù)雜度為O(n)。

例2.1

已知線性表A長(zhǎng)度為n，試寫出將該線性表逆置的算法。

【解】實(shí)現(xiàn)對(duì)線性表元素逆置的示意如圖2-4所示。因此，對(duì)n個(gè)元素進(jìn)行逆置的for語(yǔ)句只能循環(huán)n/2次。

實(shí)現(xiàn)逆置的算法如下：

voidCoverts(SeqList*A)

{

inti,n;

intx;

n=A->len; //n為線性表*A的長(zhǎng)度

for(i=1;i<n/2;i++) //實(shí)現(xiàn)逆置

{

x=A->data[i];

A->data[i]=A->data[n-i+1];

A->data[n-i+1]=x;

}

}圖2-4實(shí)現(xiàn)線性表元素逆置示意

例2.2

有順序表A和B，其表中元素均按由小到大的順序排列。編寫一個(gè)算法將它們合并成一個(gè)順序表C，并且要求表C中的元素也按由小到大的順序排列。

【解】算法實(shí)現(xiàn)如下：

voidMerge(SeqList*A,SeqList*B,SeqList**C)

{//形參**C是為了保證在返回到主調(diào)函數(shù)時(shí)仍能夠找到所生成的順序表C

inti=1,j=1,k=1;

if(A->len+B->len>=MAXSIZE)

printf("Error!\n");

else

{*C=(SeqList*)malloc(sizeof(SeqList));

while(i<=A->len&&j<=B->len)

if(A->data[i]<B->data[j])

(*C)->data[k++]=A->data[i++];

else

(*C)->data[k++]=B->data[j++];

while(i<=A->len) //當(dāng)表A未復(fù)制完

(*C)->data[k++]=A->data[i++];

while(j<=B->len) //當(dāng)表B未復(fù)制完

(*C)->data[k++]=B->data[j++];

(*C)->len=k-1; //存儲(chǔ)表長(zhǎng)

}

}

算法的時(shí)間復(fù)雜度是O(m+n)，其中m是A的表長(zhǎng)，n是B的表長(zhǎng)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)

2.3.1單鏈表由于線性表中的每個(gè)元素至多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素，即元素之間是“一對(duì)一”的邏輯關(guān)系。為了在元素之間建立起這種線性關(guān)系，采用鏈表存儲(chǔ)最簡(jiǎn)單也最常用的方法是：在每個(gè)元素中除了含有數(shù)據(jù)信息外，還要有一個(gè)指針用來(lái)指向它的直接后繼元素，即通過(guò)指針建立起元素之間的線性關(guān)系，我們稱這種元素為結(jié)點(diǎn)，結(jié)點(diǎn)中存放數(shù)據(jù)信息的部分稱為數(shù)據(jù)域，存放指向后繼結(jié)點(diǎn)指針的部分稱為指針域(如圖2-5所示)。因此，線性表中的n個(gè)元素通過(guò)各自結(jié)點(diǎn)的指針域“鏈”在一起而被稱之為鏈表，因?yàn)槊總€(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，所以稱其為單鏈表。圖2-5單鏈表結(jié)點(diǎn)結(jié)構(gòu)鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的，單鏈表結(jié)點(diǎn)的定義如下：

typedefstructnode

{

datatypedata; //data為結(jié)點(diǎn)的數(shù)據(jù)信息

structnode*next; //next為指向后繼結(jié)點(diǎn)的指針

}LNode; //單鏈表結(jié)點(diǎn)類型

圖2-6是線性表(a1,a2,a3,a4,a5,a6)對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。當(dāng)然必須將第一個(gè)結(jié)點(diǎn)的地址200放入到一個(gè)指針變量如H中，最后一個(gè)結(jié)點(diǎn)由于沒(méi)有后繼，其指針域必須置空(NULL)以表明鏈表到此結(jié)束。我們通過(guò)指針H就可以由第一個(gè)結(jié)點(diǎn)的地址開始“順藤摸瓜”的找到每一個(gè)結(jié)點(diǎn)?？梢钥闯?，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有以下特點(diǎn)：

(1)邏輯關(guān)系相鄰的元素在物理位置上可以不相鄰。

(2)表中的元素只能順序訪問(wèn)而不能隨機(jī)訪問(wèn)。

(3)表的大小可以動(dòng)態(tài)變化。

(4)插入、刪除等操作只需修改指針(地址)而無(wú)需移動(dòng)元素。

作為線性表的一種存儲(chǔ)結(jié)構(gòu)，我們關(guān)心的是結(jié)點(diǎn)之間的邏輯關(guān)系，而對(duì)每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)地址并不感興趣。所以通常將單鏈表形象地畫為圖2-7的形式而不再用圖2-6的形式來(lái)表示。

通常我們用“頭指針”來(lái)標(biāo)識(shí)一個(gè)單鏈表，如單鏈表L、單鏈表H等均是指單鏈表中的第一個(gè)結(jié)點(diǎn)的地址存放在指針變量L或H中。當(dāng)頭指針為“NULL”時(shí)，則表示單鏈表為空(如圖2-7所示)。圖2-7不帶頭結(jié)點(diǎn)的單鏈表示意圖通常需要3個(gè)指針變量來(lái)完成一個(gè)單鏈表的建立。例如，我們用指針變量head指向單鏈表的第一個(gè)結(jié)點(diǎn)(表頭結(jié)點(diǎn))；指針變量q則指向單鏈表的鏈尾結(jié)點(diǎn)；指針變量p則指向新產(chǎn)生的鏈表結(jié)點(diǎn)。并且，新產(chǎn)生的鏈表結(jié)點(diǎn)*p總是插入到鏈尾結(jié)點(diǎn)*q的后面而成為新的鏈尾結(jié)點(diǎn)。因此，插入結(jié)束時(shí)要使指針變量q指向這個(gè)新的鏈尾結(jié)點(diǎn)(即q始終指向鏈尾結(jié)點(diǎn))。單鏈表建立的過(guò)程如下：

(1)表頭結(jié)點(diǎn)的建立

p=(structnode*)malloc(sizeof(structnode)); //動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)空間

scanf(“%d”,p->data);//給結(jié)點(diǎn)中的數(shù)據(jù)成員輸入數(shù)據(jù)

p->next=NULL; //置鏈尾結(jié)點(diǎn)標(biāo)志

head=p; //第一個(gè)產(chǎn)生的鏈表結(jié)點(diǎn)即為頭結(jié)點(diǎn)

q=p; //第一個(gè)產(chǎn)生的鏈表結(jié)點(diǎn)同時(shí)也是鏈尾結(jié)點(diǎn)

(2)其他鏈表結(jié)點(diǎn)的建立

p=(structnode*)malloc(sizeof(structnode)); //動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)空間

scanf(“%d”,p->data);//給結(jié)點(diǎn)中的數(shù)據(jù)成員輸入數(shù)據(jù)

p->next=NULL; //置鏈尾結(jié)點(diǎn)標(biāo)志

q->next=p;//將這個(gè)新結(jié)點(diǎn)鏈接到原鏈尾結(jié)點(diǎn)的后面

q=p; //使指針q指向這個(gè)新的鏈尾結(jié)點(diǎn)由于指針變量head總是指向單鏈表的表頭結(jié)點(diǎn)(第一個(gè)鏈表結(jié)點(diǎn))，因此表頭結(jié)點(diǎn)的建立過(guò)程與其他鏈表結(jié)點(diǎn)的建立是有區(qū)別的。另外，新產(chǎn)生的鏈表結(jié)點(diǎn)*p同時(shí)又是鏈尾結(jié)點(diǎn)，故除了給結(jié)點(diǎn)*p的數(shù)據(jù)成員賦值之外，還應(yīng)使*p的指針成員p->next為空(NULL)來(lái)表示新的鏈尾。表頭結(jié)點(diǎn)的建立如圖2-8(a)所示，在圖2-8(a)中我們用“^”表示空指針值。圖2-8鏈表的建立對(duì)于其他鏈表結(jié)點(diǎn)的建立，則多了一個(gè)將新產(chǎn)生的鏈表結(jié)點(diǎn)*p鏈接到原鏈尾結(jié)點(diǎn)*q后面的操作。由于指針變量q總是指向單鏈表的鏈尾結(jié)點(diǎn)，因此待新鏈表結(jié)點(diǎn)*p產(chǎn)生之后，原鏈尾結(jié)點(diǎn)*q的指針q->next應(yīng)指向這個(gè)新鏈表結(jié)點(diǎn)*p，這樣才能使新鏈表結(jié)點(diǎn)*p鏈到原鏈尾結(jié)點(diǎn)*q之后而成為新的鏈尾結(jié)點(diǎn)，這一操作過(guò)程是由語(yǔ)句“q->next=p;”完成的。最后還應(yīng)使指針變量q指向這個(gè)新的鏈尾結(jié)點(diǎn)*p，即通過(guò)語(yǔ)句“q=p;”來(lái)使q指向新的鏈尾結(jié)點(diǎn)，這樣使得指針q始終指向鏈尾結(jié)點(diǎn)。其他鏈表結(jié)點(diǎn)的建立如圖2-8(b)所示。在線性表的鏈?zhǔn)酱鎯?chǔ)中，為了便于單鏈表的建立并且使插入和刪除操作的實(shí)現(xiàn)在各種情況下統(tǒng)一，通常在單鏈表的第一個(gè)結(jié)點(diǎn)之前添加了一個(gè)頭結(jié)點(diǎn)；該頭結(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，即通過(guò)頭指針指向的頭結(jié)點(diǎn)，可以訪問(wèn)到單鏈表中的所有數(shù)據(jù)結(jié)點(diǎn)(如圖2-9所示)。在線性表的鏈?zhǔn)酱鎯?chǔ)中，為了便于單鏈表的建立并且使插入和刪除操作的實(shí)現(xiàn)在各種情況下統(tǒng)一，通常在單鏈表的第一個(gè)結(jié)點(diǎn)之前添加了一個(gè)頭結(jié)點(diǎn)；該頭結(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，即通過(guò)頭指針指向的頭結(jié)點(diǎn)，可以訪問(wèn)到單鏈表中的所有數(shù)據(jù)結(jié)點(diǎn)(如圖2-9所示)。圖2-9帶頭結(jié)點(diǎn)的單鏈表2.3.2單鏈表上基本運(yùn)算的實(shí)現(xiàn)

1.建立單鏈表

1)在鏈表頭部插入結(jié)點(diǎn)的方式建立單鏈表(頭插法)

鏈表與順序表不同，它是一個(gè)動(dòng)態(tài)生成的過(guò)程，鏈表中每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不是預(yù)先分配的，而是在程序運(yùn)行中動(dòng)態(tài)生成的。在C語(yǔ)言中，動(dòng)態(tài)生成的結(jié)點(diǎn)其存儲(chǔ)空間都取自于“堆”(堆是一種可以任意申請(qǐng)和釋放的存儲(chǔ)結(jié)構(gòu)，本書不予介紹)，而堆不屬于某一個(gè)函數(shù)，故在被調(diào)函數(shù)中生成的單鏈表在被調(diào)函數(shù)運(yùn)行結(jié)束后仍然存在，只不過(guò)必須將單鏈表的頭指針傳回給主調(diào)函數(shù)方可在主調(diào)函數(shù)中訪問(wèn)到這個(gè)單鏈表：一種方法是使用指向指針的指針如**head來(lái)完成；另一種方法則是通過(guò)能夠返回指針值的被調(diào)函數(shù)來(lái)完成。此外，為了保證以后插入、刪除操作變得簡(jiǎn)單，所生成的單鏈表還應(yīng)有頭結(jié)點(diǎn)。單鏈表建立是從空表開始的，每讀入一個(gè)數(shù)據(jù)則申請(qǐng)一個(gè)結(jié)點(diǎn)，然后插在頭結(jié)點(diǎn)之后，圖2-10給出了存儲(chǔ)線性表('A','B','C','D')的單鏈表建立過(guò)程，因?yàn)槭窃趩捂湵眍^部插入，故生成結(jié)點(diǎn)的順序與線性表中元素的順序正好相反。另外，對(duì)本章算法中出現(xiàn)的結(jié)點(diǎn)，其類型為datatype的數(shù)據(jù)域data均默認(rèn)為char類型。圖2-10在頭部插入建立單鏈表算法如下：

voidCreateLinkList(LNode**head)

{//將主調(diào)函數(shù)中指向待生成單鏈表的指針地址(如&p)傳給**head

charx;

LNode*p;

*head=(LNode*)malloc(sizeof(LNode)); //在主調(diào)函數(shù)空間生成鏈表頭結(jié)點(diǎn)

(*head)->next=NULL; //*head為鏈表頭指針

printf("Inputanycharstring:\n");

scanf("%c",&x); //結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閏har型，讀入結(jié)點(diǎn)數(shù)據(jù)

while(x!='\n') //生成鏈表的其他結(jié)點(diǎn)

{

p=(LNode*)malloc(sizeof(LNode)); //申請(qǐng)一個(gè)結(jié)點(diǎn)空間

p->data=x;

p->next=(*head)->next; //將頭結(jié)點(diǎn)的next值賦給新結(jié)點(diǎn)*p的next

(*head)->next=p; //頭結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)*p實(shí)現(xiàn)在表頭插入

scanf("%c",&x); //繼續(xù)生成下一個(gè)新結(jié)點(diǎn)

}

}另一種生成單鏈表的方法是在算法所在的函數(shù)空間中直接生成，然后將單鏈表的頭指針?lè)祷亟o主調(diào)函數(shù)：

LNode*CreateLinkList()

{

LNode*head,*p; //head為單鏈表頭指針，p為生成單鏈表的暫存指針

charx;

head=(LNode*)malloc(sizeof(LNode));//生成鏈表頭結(jié)點(diǎn)

head->next=NULL; //head為鏈表頭指針

printf("Inputanycharstring:\n");

scanf("%c",&x); //結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閏har型，讀入結(jié)點(diǎn)數(shù)據(jù)

while(x!='\n') //生成鏈表的其他結(jié)點(diǎn)

{

p=(LNode*)malloc(sizeof(LNode)); //申請(qǐng)一個(gè)結(jié)點(diǎn)空間

p->data=x;

p->next=head->next; //將頭結(jié)點(diǎn)的next值域賦給新結(jié)點(diǎn)的*p的next

head->next=p; //頭結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)的*p實(shí)現(xiàn)在表頭插入

scanf("%c",&x); //繼續(xù)生成下一個(gè)新結(jié)點(diǎn)

}

returnhead; //返回單鏈表表頭指針

}

2)在鏈表的尾部插入結(jié)點(diǎn)的方式建立單鏈表(尾接法)

在頭部插入結(jié)點(diǎn)的方式生成單鏈表較為簡(jiǎn)單，但生成結(jié)點(diǎn)的順序與線性表中的元素順序正好相反。若希望兩者的次序一致則可采用尾插法來(lái)生成單鏈表。由于每次都是將新結(jié)點(diǎn)插入到鏈表的尾部，因此必須再增加一個(gè)指針q來(lái)始終指向單鏈表的尾結(jié)點(diǎn)，以方便新結(jié)點(diǎn)的插入。圖2-11給出了在鏈尾插入結(jié)點(diǎn)生成單鏈表的過(guò)程示意。圖2-11在尾部插入建立單鏈表示意圖算法如下：

LNode*CreateLinkList()

{

LNode*head,*p,*q;

charx;

head=(LNode*)malloc(sizeof(LNode)); //生成頭結(jié)點(diǎn)

head->next=NULL;

p=head;

q=p; //指針q始終指向鏈尾結(jié)點(diǎn)

printf("Inputanycharstring:\n");

scanf("%c",&x);

while(x!='\n') //生成鏈表的其他結(jié)點(diǎn)

{

p=(LNode*)malloc(sizeof(LNode));

p->data=x;

p->next=NULL;

q->next=p; //在鏈尾插入

q=p;

scanf("%c",&x);

}

returnhead; //返回單鏈表表頭指針

}

2.求表長(zhǎng)

算法如下：

intLength_LinkList(LNode*head)

{

LNode*p=head; //p指向單鏈表頭結(jié)點(diǎn)

inti=0; //i為結(jié)點(diǎn)計(jì)數(shù)器

while(p->next!=NULL)

{

p=p->next;

i++;

}

returni; //返回表長(zhǎng)值i

}

求表長(zhǎng)算法的時(shí)間復(fù)雜度為O(n)。

3.查找

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

從鏈表的第一個(gè)結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)是第i個(gè)結(jié)點(diǎn)則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找。如果整個(gè)表都無(wú)序號(hào)為i的結(jié)點(diǎn)(即i大于鏈表中結(jié)點(diǎn)的個(gè)數(shù))則返回空指針值。算法如下：

LNode*Get_LinkList(LNode*head,inti)

{ //在單鏈表head中查找第i個(gè)結(jié)點(diǎn)

LNode*p=head; //由第一個(gè)結(jié)點(diǎn)開始查找

intj=0;

while(p!=NULL&&j<i) //當(dāng)未查到鏈尾且j小于i時(shí)繼續(xù)查找

{

p=p->next;

j++;

}

returnp; //找到則返回指向i結(jié)點(diǎn)的指針值，找不到則p已為空返回空值

}

2)按值查找

從鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找，若當(dāng)前結(jié)點(diǎn)值等于x則返回指向該結(jié)點(diǎn)的指針值，否則繼續(xù)向后查找。如果整個(gè)表都找不到值等于x的結(jié)點(diǎn)，則返回空值。

算法如下：

LNode*Locate_LinkList(LNode*head,charx)

{ //在單鏈表中查找結(jié)點(diǎn)值為x的結(jié)點(diǎn)

LNode*p=head->next;//由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找

while(p!=NULL&&p->data!=x) //當(dāng)未查到鏈尾且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找

p=p->next;

returnp; //找到則返回指向值為x的結(jié)點(diǎn)的指針值，找不到則p已為空返回空值

}

查找算法的時(shí)間復(fù)雜度均為O(n)。

4.插入

因?yàn)殒湵碇械母鹘Y(jié)點(diǎn)是通過(guò)指針鏈接起來(lái)的，所以我們可以通過(guò)改變鏈表結(jié)點(diǎn)中指針的指向來(lái)實(shí)現(xiàn)鏈表結(jié)點(diǎn)的插入與刪除。我們知道，數(shù)組進(jìn)行插入或刪除操作時(shí)需要移動(dòng)大量的數(shù)組元素，但是鏈表的插入或刪除操作由于僅需修改有關(guān)指針的指向而變得非常容易。

在鏈表結(jié)點(diǎn)*p(即指針p所指結(jié)點(diǎn))之后插入鏈表結(jié)點(diǎn)*q的示意如圖2-12所示。圖2-12在結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*q插入操作如下：

①q->next=p->next;

②p->next=q;

在涉及改變指針值的操作中一定要注意指針值的改變次序，否則容易出錯(cuò)。假如上面插入操作的順序改為

①p->next=q;

②q->next=p->next;此時(shí)，①將使鏈表結(jié)點(diǎn)*p的指針p->next指向鏈表結(jié)點(diǎn)*q，②將*p的指針p->next值(指向*q)賦給了結(jié)點(diǎn)*q的指針q->next，這使得結(jié)點(diǎn)*q的指針q->next指向結(jié)點(diǎn)*q自身；這種操作的結(jié)果將導(dǎo)致鏈表由此斷為兩截，而后面的一截鏈表就“丟失”了。因此，在插入鏈表結(jié)點(diǎn)*q時(shí)，應(yīng)將鏈表結(jié)點(diǎn)*p的指針p->next值(指向后繼結(jié)點(diǎn))先賦給結(jié)點(diǎn)*q的指針q->next(即語(yǔ)句“q->next=p->next;”)，以防止鏈表的斷開，然后再使結(jié)點(diǎn)*p的指針p->next改為指向結(jié)點(diǎn)*q(即語(yǔ)句“p->next=q;”)。算法如下：

voidInsert_LinkList(LNode*head,inti,batatybex)

{ //在單鏈表head的第i個(gè)位置上插入值為x的元素

LNode*p,*q;

p=Get_LinkList(head,i-1); //查找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL)

printf("Error!\n"); //第i-1個(gè)位置不存在而無(wú)法插入

else

{

q=(LNode*)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間

q->data=x;

q->next=p->next; //完成插入操作①

p->next=q; //完成插入操作②

}

}

該算法的時(shí)間花費(fèi)在尋找第i-1個(gè)結(jié)點(diǎn)上，故算法時(shí)間復(fù)雜度為O(n)。

5.刪除

要?jiǎng)h除一個(gè)鏈表結(jié)點(diǎn)必須知道它的前驅(qū)鏈表結(jié)點(diǎn)，只有使指針變量p指向這個(gè)前驅(qū)鏈表結(jié)點(diǎn)時(shí)，我們才可以通過(guò)下面的語(yǔ)句實(shí)現(xiàn)所要?jiǎng)h除的操作(如圖2-13所示)：

p->next=p->next->next;

也即通過(guò)改變鏈表結(jié)點(diǎn)*p中指針p->nxet的指向，使它由指向待刪結(jié)點(diǎn)改為指向待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)，由此達(dá)到從鏈表中刪去待刪結(jié)點(diǎn)的目的。圖2-13刪除鏈表結(jié)點(diǎn)示意圖多數(shù)情況下，在刪除待刪結(jié)點(diǎn)*q前都要先找到這個(gè)待刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，這就需要借助一個(gè)指針變量(如p)來(lái)定位于這個(gè)前驅(qū)結(jié)點(diǎn)，然后才能通過(guò)下面的語(yǔ)句進(jìn)行刪除結(jié)點(diǎn)*q的操作(如圖2-14所示)。

q=p->next;; //q指向第i個(gè)結(jié)點(diǎn)

p->next=q->next; //從鏈表中刪除第i個(gè)結(jié)點(diǎn)圖2-14刪除一般鏈表結(jié)點(diǎn)示意圖算法如下：

voidDel_LinkList(LNode*head,inti)

{ //刪除單鏈表head上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)

LNode*p,*q;

p=Get_LinkList(head,i-1); //查找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL)

printf(“第i-1個(gè)結(jié)點(diǎn)不存在!\n”); //待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)不存在，故無(wú)待刪結(jié)點(diǎn)

else

if(p->next==NULL)

printf("第i個(gè)結(jié)點(diǎn)不存在!\n"); //待刪結(jié)點(diǎn)不存在

else

{

q=p->next;; //q指向第i個(gè)結(jié)點(diǎn)

p->next=q->next; //從鏈表中刪除第i個(gè)結(jié)點(diǎn)

free(q); //系統(tǒng)回收第i個(gè)結(jié)點(diǎn)的存儲(chǔ)空間

}

}

刪除算法的時(shí)間復(fù)雜度為O(n)。2.3.3循環(huán)鏈表

所謂循環(huán)鏈表就是將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針值由空改為指向單鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。這樣，從鏈表中的任一結(jié)點(diǎn)位置出發(fā)都可以找到鏈表的其他結(jié)點(diǎn)(如圖2-15所示)。在循環(huán)鏈表上的操作基本上與單鏈表相同，只是將原來(lái)判斷指針是否為NULL改為判斷是否為頭指針，而再無(wú)其他變化。圖2-15帶頭結(jié)點(diǎn)的循環(huán)鏈表示意圖例如，在帶頭結(jié)點(diǎn)的循環(huán)鏈表中查找值等于x的結(jié)點(diǎn)，其實(shí)現(xiàn)算法如下：

LNode*Locate_CycLink(LNode*head,datatypex)

{

LNode*p=head->next; //由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開始查找

while(p!=head&&p->data!=x)//當(dāng)未查完循環(huán)鏈表且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找

p=p->next;

if(p!=head)

returnp; //找到值等于x的結(jié)點(diǎn)*p，返回其指針值p

else

returnNULL; //當(dāng)p又查到頭結(jié)點(diǎn)時(shí)則無(wú)等于x值的結(jié)點(diǎn)，故返回NULL值

}由于鏈表的操作通常是在表頭或表尾進(jìn)行，因此也可改變循環(huán)鏈表的標(biāo)識(shí)方法，即不用頭指針而用一個(gè)指向尾結(jié)點(diǎn)的指針R來(lái)標(biāo)識(shí)循環(huán)鏈表。這種標(biāo)識(shí)的好處是可以直接找到鏈尾結(jié)點(diǎn)，而找到頭結(jié)點(diǎn)也非常容易，R->next即為指向頭結(jié)點(diǎn)的指針。

例如對(duì)兩個(gè)循環(huán)鏈表H1和H2做鏈接操作，即將H2的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)鏈接到H1的尾結(jié)點(diǎn)之后，并將H2的尾結(jié)點(diǎn)中的next指針指向H1的頭結(jié)點(diǎn)。如果采用頭指針標(biāo)識(shí)方法，則需要遍歷整個(gè)H1鏈表直到尾結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(n)；而采用尾指針R1、R2來(lái)分別標(biāo)識(shí)H1和H2這兩個(gè)循環(huán)鏈表，則時(shí)間復(fù)雜度為O(1)。具體操作如下：①P=R1->next; //保存R1的頭結(jié)點(diǎn)指針

②R1->next=R2->next->next; //使R1鏈尾結(jié)點(diǎn)的next指針指向R2的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

free(R2->next); //系統(tǒng)回收R2頭結(jié)點(diǎn)的存儲(chǔ)空間

③R2-next->p; //R2原尾結(jié)點(diǎn)的next指針指向R1的頭結(jié)點(diǎn)而形成循環(huán)鏈表

這一過(guò)程如圖2-16所示。圖2-16兩個(gè)用尾指針標(biāo)識(shí)的循環(huán)鏈表鏈接成一個(gè)循環(huán)鏈表示意圖2.3.4雙向鏈表

相對(duì)于單鏈表來(lái)說(shuō)，循環(huán)鏈表雖然有其優(yōu)點(diǎn)但仍有不足。因?yàn)閺难h(huán)鏈表中的某個(gè)結(jié)點(diǎn)出發(fā)只能順著指針?lè)较蛳蚝髮ふ移渌Y(jié)點(diǎn)，而無(wú)法直接到達(dá)該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。要想到達(dá)它的前驅(qū)結(jié)點(diǎn)，則只能循環(huán)遍歷整個(gè)鏈表。需要?jiǎng)h除鏈表中某一結(jié)點(diǎn)時(shí)也存在著同樣的問(wèn)題，僅僅知道待刪除結(jié)點(diǎn)的地址是不夠的，還必須知道待刪除結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的地址，而要找到這個(gè)直接前驅(qū)結(jié)點(diǎn)則又要對(duì)鏈表進(jìn)行循環(huán)遍歷。為了克服循環(huán)鏈表這種單向性的缺點(diǎn)，可以采用雙向鏈表結(jié)構(gòu)來(lái)滿足那些經(jīng)常需要沿兩個(gè)方向移動(dòng)的鏈表。

顧名思義，所謂雙向鏈表就是指鏈表的每一個(gè)結(jié)點(diǎn)中除了數(shù)據(jù)域之外，還設(shè)置了兩個(gè)指針域：一個(gè)用來(lái)指向該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)；另一個(gè)用來(lái)指向該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如圖2-17所示。圖2-17雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)雙向鏈表的結(jié)點(diǎn)定義如下：

typedefstructdlnode

{

datatypedata; //data為結(jié)點(diǎn)的數(shù)據(jù)信息

structdlnode*prior,*next; //prior和next分別為指向直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針

}DLNode; //雙向鏈表結(jié)點(diǎn)類型雙向鏈表也用頭指針來(lái)標(biāo)識(shí)，通常也是采用帶頭結(jié)點(diǎn)的循環(huán)鏈表結(jié)構(gòu)。圖2-18是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表示意。也即，在雙向鏈表中可以通過(guò)某結(jié)點(diǎn)的指針p直接得到指向它的后繼結(jié)點(diǎn)指針p->next，也可直接得到指向它的前驅(qū)結(jié)點(diǎn)指針p->prior。這樣，在查找前驅(qū)結(jié)點(diǎn)的操作中就無(wú)需再循環(huán)遍歷鏈表了。圖2-18帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表示意圖設(shè)p是指向雙向循環(huán)鏈表中某一結(jié)點(diǎn)的指針，則p->prior->next表示的是*p結(jié)點(diǎn)的前驅(qū)指針prior所指前驅(qū)結(jié)點(diǎn)的后繼指針(該前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)即為*p結(jié)點(diǎn))，即與p相等。類似地，p->next->prior也與p相等，因此有以下等式成立：

p＝p->prior->next＝p->next->prior

設(shè)p指向雙向循環(huán)鏈表中的某一結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，則插入可分為兩種情況：一種是在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*s；另一種是在*p結(jié)點(diǎn)之前插入結(jié)點(diǎn)*s。

1.在結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*s

在結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*s要注意如下兩點(diǎn)：

(1)首先修改待插結(jié)點(diǎn)*s的前驅(qū)指針和后繼指針，以避免“斷鏈”現(xiàn)象出現(xiàn)。

(2)接下來(lái)先修改*p的后繼結(jié)點(diǎn)之前驅(qū)指針，然后再修改*p的后繼指針。

在結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*s的示意如圖2-19所示，其操作過(guò)程如下：

①s->prior=p;

②s->next=p->next;

③p->next->prior=s;

④p->next=s;圖2-19在結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*s的操作次序示意圖

2.在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s

在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s要注意如下兩點(diǎn)：

(1)首先修改待插結(jié)點(diǎn)*s的前驅(qū)指針和后繼指針，以避免“斷鏈”現(xiàn)象出現(xiàn)。

(2)接下來(lái)先修改*p的前驅(qū)結(jié)點(diǎn)的后繼指針，然后再修改*p的前驅(qū)指針。

在結(jié)點(diǎn)*p之前插入*s的示意如圖2-20所示，其操作過(guò)程如下：

①s->prior=p->prior;

②

s->next=p;

③p->prior->next=s;

④p->prior=s;圖2-20在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s的操作次序示意圖注意：兩種插入方法中指針操作的順序不是唯一的但也不是任意的，操作次序不當(dāng)就不能實(shí)現(xiàn)正確地插入，還有可能使一部分鏈表“丟失”。

設(shè)指針p指向雙向鏈表中某結(jié)點(diǎn)，則刪除結(jié)點(diǎn)*p的示意圖如圖2-21所示，其操作過(guò)程如下：

①p->prior->next=p->next;

②p->next->prior=p->prior;

③free(p);圖2-21雙向鏈表中刪除結(jié)點(diǎn)*p操作次序示意圖建立帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表算法如下：

DLNode*CreateDlinkList()//建立帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表

{

DLNode*head,*s;

charx;

head=(DLNode*)malloc(sizeof(DLNode)); //先生成僅含頭結(jié)點(diǎn)的空雙向循環(huán)鏈表

head->prior=head;

head->next=head;

printf("Inputanycharstring:\n");

scanf("%c",&x); //讀入結(jié)點(diǎn)數(shù)據(jù)

while(x!='\n') //采用頭插法生成雙向循環(huán)鏈表

{

s=(DLNode*)malloc(sizeof(DLNode)); //生成待插入結(jié)點(diǎn)的存儲(chǔ)空間

s->data=x; //將讀入的數(shù)據(jù)賦給待插入結(jié)點(diǎn)*s

s->prior=head; //新插入的結(jié)點(diǎn)*s其前驅(qū)結(jié)點(diǎn)為頭結(jié)點(diǎn)*head

s->next=head->next; //插入后*s的后繼結(jié)點(diǎn)為頭結(jié)點(diǎn)*head原來(lái)的后繼結(jié)點(diǎn)

head->next->prior=s; //頭結(jié)點(diǎn)的原后繼結(jié)點(diǎn)其前驅(qū)結(jié)點(diǎn)為*s

head->next=s; //頭結(jié)點(diǎn)此時(shí)新的后繼結(jié)點(diǎn)為*s

scanf("%c",&x); //繼續(xù)讀入下一個(gè)結(jié)點(diǎn)數(shù)據(jù)

}

returnhead; //返回頭指針

}2.3.5靜態(tài)鏈表

有些高級(jí)語(yǔ)言沒(méi)有“指針”數(shù)據(jù)類型，要想發(fā)揮鏈表結(jié)構(gòu)的長(zhǎng)處，可用一個(gè)一維數(shù)組空間來(lái)模擬鏈表結(jié)構(gòu)，即稱之為靜態(tài)鏈表。

靜態(tài)鏈表的構(gòu)造方法是用一維數(shù)組的一個(gè)數(shù)組元素來(lái)表示結(jié)點(diǎn)，結(jié)點(diǎn)中的數(shù)據(jù)域(data)仍