數(shù)據(jù)結(jié)構(gòu)(C語言版)

第1章概論本章主要介紹以下內(nèi)容：數(shù)據(jù)結(jié)構(gòu)中涉及的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容算法的概念、描述方法以及評價標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第1頁。本章目錄1.1什么是數(shù)據(jù)結(jié)構(gòu)11.2算法和算法分析25.5哈夫曼樹5

1.3本章小結(jié)3結(jié)束數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第2頁。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.1.1基本概念及術(shù)語1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)1.1.4抽象數(shù)據(jù)類型返回到本節(jié)目錄返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第3頁。1.1.1

基本概念及術(shù)語在系統(tǒng)的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識之前，先了解一些相關(guān)概念和術(shù)語。1．?dāng)?shù)據(jù)（Data）指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。例如，整數(shù)、實(shí)數(shù)、字符、圖像、聲音等都是數(shù)據(jù)。2．?dāng)?shù)據(jù)元素（DataElement）數(shù)據(jù)元素（也稱為結(jié)點(diǎn)）是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)處理中不可分割的最小單位。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第4頁。3．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。這些數(shù)據(jù)元素不是孤立存在的，而是有著某種關(guān)系，這種關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)一般包括以下三個方面內(nèi)容：（1）數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。（3）數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)施加的操作。返回到本節(jié)目錄1.1.1

基本概念及術(shù)語數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)定義：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映像方式把它存放在計算機(jī)存儲器中，并在這些數(shù)據(jù)上定義了一個運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。簡言之，數(shù)據(jù)結(jié)構(gòu)={邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+運(yùn)算集合

}。4．?dāng)?shù)據(jù)類型(DataType)數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。如在高級語言中，整型類型的取值范圍為：-32768～+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。返回到本節(jié)目錄1.1.1

基本概念及術(shù)語數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第6頁。5．?dāng)?shù)據(jù)類型(DataType)高級語言中的數(shù)據(jù)類型分為兩大類：（1）原子類型其值是不可分解的。如C語言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型）。（2）結(jié)構(gòu)類型其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的。如C語言中的的構(gòu)造類型（結(jié)構(gòu)體、共用體、枚舉等類型）。返回到本節(jié)目錄1.1.1

基本概念及術(shù)語數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第7頁。1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)1．定義數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述?？梢杂靡粋€二元組表示，其形式化描述為： Data_Structure=（D，R）其中D是數(shù)據(jù)元素的有限集合，R是D上關(guān)系的有限集合。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計算機(jī)的。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第8頁。2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)的分類根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系的不同特性，分為下列四類基本結(jié)構(gòu)，如圖1-1所示。（a）集合結(jié)構(gòu)

（b）線性結(jié)構(gòu)

（c）樹型結(jié)構(gòu)

（d）圖形結(jié)構(gòu)圖1-1數(shù)據(jù)結(jié)構(gòu)的四種基本邏輯結(jié)構(gòu)返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第9頁。（1）集合結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系，這是一種最簡單的數(shù)據(jù)結(jié)構(gòu)。（2）線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著“一對一”的關(guān)系?！纠?.1】學(xué)籍檔案管理假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如表1-1所示的學(xué)生信息。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第10頁。特點(diǎn)：表中的每一行是一個數(shù)據(jù)元素（或記錄、結(jié)點(diǎn)），它由學(xué)號、姓名、性別及出生年月等數(shù)據(jù)項(xiàng)組成。表中數(shù)據(jù)元素之間是一種先后關(guān)系，對于表中任一結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)（稱為直接前驅(qū)）最多只有一個；與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)（稱為直接后繼）也最多只有一個。我們將這種關(guān)系稱為“線性結(jié)構(gòu)”。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第11頁。（3）樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著“一對多”的關(guān)系?！纠?.2】人機(jī)對弈人與計算機(jī)進(jìn)行對弈的部分圖如圖1-2為所示。圖1-2人機(jī)對弈圖返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第12頁。特點(diǎn)：圖中將每一個棋盤看作一個數(shù)據(jù)元素，則數(shù)據(jù)元素之間的關(guān)系要比表1-1要復(fù)雜許多。圖中數(shù)據(jù)元素之間是一對多關(guān)系，即一個數(shù)據(jù)元素向上和一個數(shù)據(jù)元素相連（稱為雙親結(jié)點(diǎn)），向下和多個數(shù)據(jù)元素相連（稱為孩子結(jié)點(diǎn)）。我們將這種關(guān)系稱為“樹型結(jié)構(gòu)”。4）圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的任意數(shù)據(jù)元素之間都可以有關(guān)系，元素之間存在著“多對多”的關(guān)系。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第13頁。（【例1.3】制定教學(xué)計劃在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)先修課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)先修課程。比如，計算機(jī)專業(yè)課程的開設(shè)情況如表1-2所示。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第14頁。教學(xué)計劃的關(guān)系圖如圖1-3所示。圖1-3教學(xué)計劃關(guān)系圖特點(diǎn)：圖中數(shù)據(jù)元素存在著多對多的任意關(guān)系。一個結(jié)點(diǎn)可能有多個直接前驅(qū)和直接后繼。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第15頁。1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)在計算機(jī)中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實(shí)現(xiàn)。本書將介紹常用的兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系是：存儲結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身映像，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。

返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第16頁。1.順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系。【例1.4】對于表1-1提出的學(xué)生信息登記表進(jìn)行存儲，假定每個元素占用50個存儲單元，數(shù)據(jù)從1000號單元開始由低地址向高地址存放，對應(yīng)的順序存儲結(jié)構(gòu)如表1-3所示。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第17頁。順序存儲結(jié)構(gòu)的主要特點(diǎn)：可實(shí)現(xiàn)對各數(shù)據(jù)元素的隨機(jī)訪問。這是因?yàn)橹灰来鎯Φ氖椎刂芬约懊總€數(shù)據(jù)元素所占的存儲單元，就可以計算出各數(shù)據(jù)元素的存儲地址。不利于修改，在對數(shù)據(jù)元素進(jìn)行插入、刪除運(yùn)算時可能要移動一系列的數(shù)據(jù)元素。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第18頁。2.鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。【例1.5】對于表1-1學(xué)生信息登記表進(jìn)行鏈?zhǔn)酱鎯r，在每個數(shù)據(jù)元素后方附加一個指向“下一個結(jié)點(diǎn)地址”的指針字段，用于存放后繼數(shù)據(jù)元素的存儲地址，每個數(shù)據(jù)元素的地址是隨機(jī)的，可以不連續(xù)。對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)見表1-4所示。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第19頁。鏈?zhǔn)酱鎯Y(jié)構(gòu)的主要特點(diǎn)：利于修改，在對數(shù)據(jù)元素進(jìn)行插入、刪除運(yùn)算時，僅需修改數(shù)據(jù)元素的指針字段值，而不必移動數(shù)據(jù)元素。由于邏輯上相鄰的數(shù)據(jù)元素在存儲位置中不一定相鄰，因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能對數(shù)據(jù)元素進(jìn)行隨機(jī)訪問。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第20頁。1.1.4抽象數(shù)據(jù)類型1．抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型（AbstractDataType，簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。2．抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型實(shí)際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法?？梢杂靡粋€三元組表示：ADT=（Ｄ，Ｓ，Ｐ）其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第21頁。抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)類型，抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)的服務(wù)（或稱操作）。抽象數(shù)據(jù)類型有些類似于pascal語言中的記錄（record）類型和c語言中的構(gòu)造（struct）類型，但它增加了相關(guān)的服務(wù)。3．ADT的兩個重要特征（1）數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。（2）數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。返回到本節(jié)目錄1.1.4抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第22頁。1.2算法和算法分析1.2.1算法的概念1.2.2算法分析1.2.3相關(guān)C語言知識回顧返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第23頁。1.2.1算法的概念1．算法的定義瑞士著名的計算機(jī)科學(xué)家N.Wirth所提出的著名公式“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，所謂算法，就是為解決特定問題而采取的步驟和方法。2．算法的特性一個算法應(yīng)該具有下列特性：（1）有窮性：一個算法必須（對任何合法的輸入值）在執(zhí)行有限步之后結(jié)束。（2）確定性：算法中的每一條指令必須有確切的含義，不會產(chǎn)生二義性。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第24頁。（3）可行性：算法中描述的操作都可以通過執(zhí)行有限次基本操作來實(shí)現(xiàn)。（4）輸入：一個算法有零個或多個輸入。（5）輸出：一個算法必有一個或多個輸出。3．算法的評價要設(shè)計一個好的算法通常需要考慮以下幾方面的要求：（1）正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。（2）可讀性：為了便于理解、測試和修改算法，算法應(yīng)該具有良好的可讀性。返回到本節(jié)目錄1.2.1算法的概念數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第25頁。（3）健壯性：當(dāng)輸入非法的數(shù)據(jù)時，算法應(yīng)能恰當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。（4）高效性：對同一個問題，執(zhí)行時間越短，算法的效率越高。（5）低存儲量：完成相同的功能，執(zhí)行算法所占用的存儲空間應(yīng)盡可能的少。返回到本節(jié)目錄1.2.1算法的概念數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第26頁。4．算法的描述為了表示一個算法，可以用多種不同的方法，常用的有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、N-S流程圖等表示。本書采用C的描述語言實(shí)現(xiàn)對各種數(shù)據(jù)結(jié)構(gòu)及算法的操作描述，算法是以函數(shù)形式描述，描述如下：類型標(biāo)識符函數(shù)名(形式參數(shù)表)/*算法說明*/{語句序列}返回到本節(jié)目錄1.2.1算法的概念數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第27頁。1.2.2算法分析在算法滿足正確性的前提下，如何評價不同算法的優(yōu)劣呢？通常主要考慮算法的時間復(fù)雜度和空間復(fù)雜度這兩方面。一般情況下，鑒于運(yùn)算空間（內(nèi)存）較為充足，所以把算法的時間復(fù)雜度作為重點(diǎn)分析。1.時間復(fù)雜度（TimeComplexity）一個算法所需的運(yùn)算時間通常與所解決問題的規(guī)模大小有關(guān)。問題規(guī)模是一個和輸入有關(guān)的量，用n表示問題規(guī)模的量，把算法運(yùn)行所需的時間T表示為n的函數(shù)，記為T(n)。不同的T(n)算法，當(dāng)n增長時，運(yùn)算時間增長的快慢很不相同。一個算法所需的執(zhí)行時間就是該算法中所有語句執(zhí)行次數(shù)之和。當(dāng)n逐漸增大時T(n)的極限情況，一般簡稱為時間復(fù)雜度。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第28頁。當(dāng)討論一個程序的運(yùn)行時間時，注重的不是T(n)的具體值，而是它的增長率。T(n)的增長率與算法中數(shù)據(jù)的輸入規(guī)模緊密相關(guān)，而數(shù)據(jù)輸入規(guī)模往往用算法中的某個變量的函數(shù)來表示，通常是f(n)。隨著數(shù)據(jù)輸入規(guī)模的增大，f(n)的增長率與T(n)的增長率相近，因此T(n)同f(n)在數(shù)量級上是一致的。記作：T(n)=O(f(n))其中，大寫字母O為Order(數(shù)量級)的字頭，f(n)為函數(shù)形式，如T(n)=O(n2)。返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第29頁。注意，當(dāng)T(n)為多項(xiàng)式時，可只取其最高次冪項(xiàng)并省略其系數(shù)，其它的次冪項(xiàng)及系數(shù)均略去不寫。一般地，對于足夠大的n，常用的時間復(fù)雜性存在以下順序：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)算法時間復(fù)雜度的數(shù)量級越大，表示該算法的效率越低，反之越高。例如O(1)為常數(shù)數(shù)量級,，即算法的時間復(fù)雜性與輸入規(guī)模n無關(guān)。返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第30頁?！纠?.6】分析以下算法的時間復(fù)雜度。x=0;y=0;for(k=1;k<=n;k++)x++;（1）執(zhí)行n次for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;（2）執(zhí)行n2次

解：T(n)=n+n2T(n)=O(n2)上述算法中的基本運(yùn)算是語句（2），其執(zhí)行頻率為n2。則T(n)=n2=O(n2)返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第31頁?！纠?.7】分析以下算法的時間復(fù)雜度。i=1;while(i<=n)i=2*i;(1)執(zhí)行f(n)次解：設(shè)語句（1）執(zhí)行次數(shù)是f(n)，則2f(n)≤n得到T(n)=O(log2n)返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第32頁?！纠?.8】求兩個矩陣相乘的函數(shù)的時間復(fù)雜度。voidmult(inta[],intb[],intc[]){/*以二維數(shù)組存儲矩陣元素，c為a和b的乘積*/for(i=1;i<=n;++i)(1)執(zhí)行n次for(j=1;j<=n;++j)(2)執(zhí)行n2次{c[i,j]=0;for(k=1;k<=n;++k)(3)執(zhí)行n3次c[i,j]+=a[i,k]*b[k,j];}}解：嵌套循環(huán)為每層循環(huán)次數(shù)的乘積，因?yàn)槭窃摵瘮?shù)為三重循環(huán)，所以時間復(fù)雜度為O(n3)。返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第33頁。2.空間復(fù)雜度（SpaceComplexity）一個算法的空間復(fù)雜度是指程序運(yùn)行開始到結(jié)束所需要的存儲空間。包括算法本身所占用的存儲空間、輸入/輸出數(shù)據(jù)占用的存儲空間以及算法在運(yùn)行過程中的工作單元和實(shí)現(xiàn)算法所需輔助空間。類似于算法的時間復(fù)雜度，算法所需存儲空間的量度記作：S(n)=O(f(n))表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲量的增長率與f(n)的增長率相同。返回到本節(jié)目錄1.2.2算法分析數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第34頁。1.2.3相關(guān)C語言知識回顧1．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，它最早出現(xiàn)在高級程序設(shè)計語言中，用以描述操作對象的特性。高級語言中的數(shù)據(jù)類型可分為兩類：一類是原子類型，如C語言中的基本類型（整型、實(shí)型、字符型等）指針和空類型等不可再分的值；另一類是結(jié)構(gòu)類型，如數(shù)組、結(jié)構(gòu)體等通過若干成分（可以是原子類型或結(jié)構(gòu)類型）構(gòu)造而成的。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第35頁。1.2.3相關(guān)C語言知識回顧（1）數(shù)組類型數(shù)組中的每一個元素都屬于同一個數(shù)據(jù)類型。數(shù)組有一維數(shù)組和多維數(shù)組，數(shù)組名標(biāo)識一個數(shù)組，下標(biāo)指示一個數(shù)組元素在該數(shù)組中的順序位置，下標(biāo)從0～n-1（n為數(shù)據(jù)元素個數(shù)）。例如，inta[10];定義了包含10個整數(shù)的數(shù)組a，數(shù)組下標(biāo)范圍0～9。（2）結(jié)構(gòu)體類型結(jié)構(gòu)體是是一種復(fù)合的數(shù)據(jù)類型，該結(jié)構(gòu)體類型內(nèi)可以有多個成員，每個結(jié)構(gòu)體成員可以有不同的數(shù)據(jù)類型。基本格式如下：返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第36頁?！靖袷健縮truct結(jié)構(gòu)體名/*定義結(jié)構(gòu)體類型*/{成員列表;};struct結(jié)構(gòu)體名變量名表;

/*定義結(jié)構(gòu)體變量*/返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第37頁。（3）結(jié)構(gòu)體類型指針對結(jié)構(gòu)體成員的引用方法當(dāng)結(jié)構(gòu)體類型的指針指向某一結(jié)構(gòu)體變量時，就可以使用該指針對其指向的結(jié)構(gòu)體變量內(nèi)的各成員進(jìn)行引用。引用的方法為：指針名->成員名等價于：(*指針名).成員名等價于：結(jié)構(gòu)體變量名.成員名在本書中，在程序內(nèi)大量使用結(jié)構(gòu)體類型的指針，所以大都采用第一種寫法。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第38頁。（4）用typedef定義類型除了可以直接使用C提供的標(biāo)準(zhǔn)類型名和自己聲明的結(jié)構(gòu)體類型外，還可以用typedef聲明新的類型名來代替已有的類型名。其基本定義格式如下：【格式】typedef原類型名

新類型名;其中，typedef為關(guān)鍵字，表示重定義。原類型名是C語言提供的任意一種數(shù)據(jù)類型，可以是簡單數(shù)據(jù)類型，也可以是構(gòu)造數(shù)據(jù)類型。新類型名為原類型名的一個別名。使用新類型名就像使用原類型名那樣定義變量。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第39頁。2．動態(tài)存儲分配函數(shù)C語言提供了動態(tài)分配函數(shù)來實(shí)現(xiàn)動態(tài)存儲分配。最常用的動態(tài)存儲分配函數(shù)有以下兩個。（1）分配內(nèi)存空間函數(shù)malloc()【格式】(類型名*)malloc(要分配的內(nèi)存字節(jié)數(shù)size)【功能】在內(nèi)存中分配一個長度為size的連續(xù)存儲空間，返回值是新分配存儲空間的首地址，若內(nèi)存不足，則返回NULL。其中，類型名表示把該存儲空間用于何種數(shù)據(jù)類型。（類型名*）表示把malloc函數(shù)返回值強(qiáng)制轉(zhuǎn)換為該類型指針。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第40頁。（2）釋放內(nèi)存空間函數(shù)free()【格式】free(指向要釋放單元的指針名)【功能】釋放該指針?biāo)傅囊粔K存儲空間，該空間系統(tǒng)可另作它用。注意這個指針?biāo)傅目臻g必須是由malloc()函數(shù)和calloc()函數(shù)分配的才行。free函數(shù)無返回值。例如：int*pt;pt=(int*)malloc(sizeof(int));free(pt);程序段表示釋放pt指向的存儲空間。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第41頁。3．函數(shù)的定義與調(diào)用在本書中，絕大多數(shù)的算法都是編寫成C語言的函數(shù)，這些函數(shù)需要通過編寫相應(yīng)的主函數(shù)才能被執(zhí)行。（1）函數(shù)的定義函數(shù)的定義如下：【格式】函數(shù)類型函數(shù)名（形參表）{內(nèi)部變量定義函數(shù)主體語句返回語句}

返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第42頁。（2）函數(shù)的調(diào)用【格式】函數(shù)類型

函數(shù)名（實(shí)參表）;【說明】1．實(shí)參表中各參數(shù)應(yīng)與形參表中各參數(shù)類型及個數(shù)相符。2．在調(diào)用函數(shù)時，表達(dá)式應(yīng)與該函數(shù)的類型相符，如果該函數(shù)有返回值時，在調(diào)用時要將該函數(shù)的返回值賦給相同類型的變量。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第43頁。4．TurboC2.0中的漢字顯示在TurboC2.0中，如果想輸入和顯示漢字，需要使用UCDOS漢字系統(tǒng)。但現(xiàn)在的Windows操作系統(tǒng)不支持UCDOS漢字系統(tǒng)的16位顯示。下面介紹一種能在WindowsXP系統(tǒng)環(huán)境下，在TurboC2.0中使用UCDOS的漢字系統(tǒng)的方法。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第44頁。（1）將UCDOS的核心文件進(jìn)行兼容性設(shè)置（有的機(jī)器可省略這步，直接執(zhí)行（2））。點(diǎn)“開始”菜單->“所有程序”->“附件”->“程序兼容性向?qū)А?>“我想手動定位程序”->“瀏覽”->\ucdos\->win98->256色，640X480->程序工作正確嗎？選“是，設(shè)置此程序?yàn)橐恢笔褂眉嫒菪栽O(shè)置。”完成。有的UCDOS版本的核心文件是knlvga.exe，也要照此進(jìn)行兼容性設(shè)置。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第45頁。（2）運(yùn)行UCDOS系統(tǒng)文件的方法。進(jìn)入到命令提示符（MS-DOS狀態(tài)）（“開始”->“程序”->“附件”->“命令提示符”）切換到UCDOS目錄。（帶下劃線文字為輸入的命令信息，“↙”表示回車鍵。假設(shè)UCDOS文件夾在C盤根目錄內(nèi)，可輸入如下命令：）C:\DocumentsandSettings>cd\↙

（回到C盤根目錄下）C:\>cdUcdos↙

（進(jìn)入UCDOS的目錄）返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第46頁。這時不要運(yùn)行UCDOS.BAT，分別一項(xiàng)一項(xiàng)命令運(yùn)行。如：C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙C:\UDOS>↙

（五筆輸入，如不用五筆可省略此步）

（注：可直接輸入命令名，如輸入“rd16↙”，省略擴(kuò)展名“.com”）

返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第47頁。就可以順利進(jìn)入ucdos。然后，退出UCDOS目錄，再進(jìn)入tc目錄運(yùn)行tc.exe文件就可以在TurboC2.0中順利的輸入和顯示漢字了。如：C:\UDOS>cd\↙C:\>cdtc↙

（假定TurboC2.0的文件夾名稱為TC）C:\TC>tc.exe↙(可直接輸入tc↙即可)即可進(jìn)行TurboC2.0輸入并運(yùn)行C語言源程序了。返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第48頁。（3）常用的TurboC2.0快捷鍵Alt+F：文件菜單①Load打開文件

②Save保存

③Writeto另存為

④Quit退出Alt+R：運(yùn)行菜單Run（或Ctrl+F9）

運(yùn)行程序

UserScreen(或Alt+F5)查看運(yùn)行結(jié)果Alt+E：編輯（顯示光標(biāo)，有時調(diào)試有錯時可將光標(biāo)重新顯示在編輯區(qū)）F9：編譯系統(tǒng)查錯返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第49頁。（4）更改漢字輸入法Alt+F1區(qū)位Alt+F2全拼Alt+F3雙拼Alt+F5五筆（必須在UCDOS中輸入wb命令才能用此項(xiàng)）Alt+F6英文單次按右shift鍵

可顯示或隱藏中文輸入法返回到本節(jié)目錄1.2.3相關(guān)C語言知識回顧數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第50頁。1.3本章小結(jié)本章主要介紹了有關(guān)數(shù)據(jù)結(jié)構(gòu)的以下幾方面：（1）數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算方法。（2）數(shù)據(jù)的邏輯結(jié)構(gòu)包括：集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)四種基本類型。（3）數(shù)據(jù)的存儲結(jié)構(gòu)包括：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。（4）算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法具有：有窮性、確定性、正確性、輸入、輸出等特性。（5）算法的時間復(fù)雜度與空間復(fù)雜度。返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第51頁。數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語言版）

中國水利水電出版社數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第52頁。第2章線性表本章主要介紹下列內(nèi)容線性表的定義和基本操作線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第53頁。本章目錄2.1線性表的基本概念1

2.2順序表2

2.3鏈表32.4線性表的應(yīng)用舉例4

2.5本章小結(jié)5結(jié)束數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第54頁。2.1線性表的基本概念2.1.1線性表的定義2.1.2線性表的基本操作返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第55頁。2.1.1

線性表的定義1.線性表的定義線性表是具有相同數(shù)據(jù)類型的n（n>=0）個數(shù)據(jù)元素的有限序列，通常記為：（a1，a2，…ai-1，ai，ai+1，…an）

其中n為表長，當(dāng)n=0時稱為空表。

在線性表中相鄰元素之間存在著順序關(guān)系。如對于元素ai

而言，ai-1

稱為

ai

的直接前驅(qū)，ai+1

稱為

ai

的直接后繼。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第56頁。2.線性表的特點(diǎn)（1）有且僅有一個開始結(jié)點(diǎn)（a1），它沒有直接前驅(qū)；（2）有且僅有一個終端結(jié)點(diǎn)（an），它沒有直接后繼；（3）除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外，其余的結(jié)點(diǎn)都有且僅有一個直接前驅(qū)和一個直接后繼。2.1.1

線性表的定義返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第57頁。2.1.2

線性表的基本操作數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層次上的，而運(yùn)算的具體實(shí)現(xiàn)是建立在存儲結(jié)構(gòu)上的。下面定義的線性表的基本操作僅是定義在邏輯結(jié)構(gòu)上的，每一個操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲結(jié)構(gòu)之后才能完成。線性表的基本操作有：（1）初始化線性表InitList(L)。其作用是建立一個空表L（即建立線性表的構(gòu)架，但不包含任何數(shù)據(jù)元素）。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第58頁。（2）求線性表的長度GetLength(L)。其作用是返回線性表L的長度（即所含數(shù)據(jù)元素的個數(shù)）。（3）求線性表中第i個元素GetElem(L,i,x)。其作用是在1≤i≤GetLength(L)返回成功，并用x存儲線性表L的第i個元素的值。（4）按值查找操作Locate(L,x)。在線性表L查找一個與給定值x相等的數(shù)據(jù)元素，其作用是若存在一個或多個與x相等的數(shù)據(jù)元素，則返回的元素所在位置的最小值或地址值；否則返回0或NULL值。2.1.2

線性表的基本操作返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第59頁。（5）插入操作InsElem(L,i,x)。其作用是在線性表L的第i個位置上插入一個值為

x的新元素，使線性表L由（a1，a2，…ai-1，ai，ai+1，…an）變?yōu)椋╝1，a2，…ai-1，x，ai，ai+1，…an）。其中1≤i≤GetLength(L)+1。（6）刪除操作DelElem(L,i,x)。其作用是刪除線性表L的第i個位置的數(shù)據(jù)元素并用x將其存儲，使線性表L由（a1，a2，…ai-1，ai，ai+1，…an）變?yōu)椋╝1，a2，…ai-1，ai+1，…an）。其中1≤i≤GetLength(L)。（7）輸出元素值DispList(L)。其作用是依次掃描線性表L，并輸出各元素的值。2.1.2

線性表的基本操作返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第60頁。2.2順序表2.2.1順序表2.2.2順序表的基本操作實(shí)現(xiàn)返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第61頁。1.順序表的定義數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示通常有兩種形式，即順序存儲表示和鏈?zhǔn)酱鎯Ρ硎?。線性表的順序存儲表示又稱為順序表。線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把用這種存儲形式存儲的線性表稱為順序表。假設(shè)順序表(a1，a2，…ai-1，ai，ai+1，…an)，每個數(shù)據(jù)元素占用d個存儲單元，則元素ai的存儲位置為：Loc(ai)=Loc(a1)+(i-1)×d1≤i≤n2.2.1順序表返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第62頁。其中，Loc(a1)是順序表第一個元素a1的存儲位置，通稱為順序表的起始地址。順序存儲結(jié)構(gòu)示意圖如圖2-1所示。順序表的存儲特點(diǎn)：（1）順序表的邏輯順序和物理順序是一致的。（2）順序表中任意一個數(shù)據(jù)元素都可以隨機(jī)存取，所以順序表是一種隨機(jī)存取的存儲結(jié)構(gòu)。2.2.1順序表返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第63頁。2.順序表的類型定義#defineMAXLEN100/*定義常量MAXLEN為100表示存儲空間總量*/#defineOK/*定義常量OK為1表示成功*/#defineERROR0/*定義常量ERROR為0表示失敗*/#defineOVER-1/*定義常量OVER為-1表示結(jié)束*/typedefintElemType;/*定義ElemType為int類型*/typedefstruct/*順序表存儲類型*/{ElemTypedata[MAXLEN];/*存放線性表的數(shù)組*/intLength;/*Length是順序表的長度*/}SeqList;2.2.1順序表返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第64頁。2.2.2順序表的基本操作實(shí)現(xiàn)1．順序表的初始化順序表的初始化即構(gòu)造一個空順序表L，將表L的實(shí)際長度置0，算法描述見算法2.1。算法2.1

voidInitList(SeqList*L)

{L->Length=0;

/*初始的化順序表為空*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第65頁。2．順序表的建立初始化順序表后向表中輸入n個元素建立表L，算法描述見算法2.2。算法2.2voidCreateList(SeqList*L,intn){inti;printf("請輸入各個元素值：\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第66頁。3．求順序表的長度操作返回順序表L的Length值，算法描述見算法2.3。算法2.3intGetLength(SeqList*L){returnL->Length;}

4．查找操作順序表的查找分為按值與按序號查找，下面將分別介紹這兩種方法的實(shí)現(xiàn)，讀者可根據(jù)具體的問題相應(yīng)選擇所需的查找方法。2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第67頁。（1）按號查找查找順序表中第i個元素的值，在i無效時返回出錯，有效時返回成功，并用x存儲第i個元素的值，算法描述見算法2.4。算法2.4intGetElem(SeqList*L,inti,ElemType*x){if(i<1||i>L->Length)returnERROR;else{*x=L->data[i-1];returnOK;}}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第68頁。2）按值查找操作順序表中的按值查找是指在順序表中查找與給定值x相等的數(shù)據(jù)元素的所在位置，算法描述見算法2.5。算法2.5intLocate(SeqList*L,ElemTypex){

inti=0;while(i<=L->Length&&L->data[i]!=x)i++;if(i>L->Length)

returnERROR;elsereturni+1;

/*返回的是元素位置*/}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第69頁。2.2.2順序表的基本操作實(shí)現(xiàn)5．插入操作線性表的插入是指在表的第i個位置上插入一個值為x的新元素，插入后使原表長增1，原順序表如圖2-2所示。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第70頁。5．插入操作步驟如下：

(1)將an～ai之間的所有結(jié)點(diǎn)依次后移，為新元素讓出第i個位置，如圖2-3所示。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第71頁。5．插入操作步驟如下：(2)將新結(jié)點(diǎn)x插入到第i個位置，如圖2-4所示。(3)順序表的長度增1，插入成功，并返回，算法描述見算法2.6。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第72頁。5．插入操作算法2.6int

InsElem(SeqList*L,inti,ElemTypex){intj;

if(L->Length>=MAXLEN){printf("順序表已滿！");returnOVER;

/*表滿，不能插入*/}if(i<1||i>L->Length+1)

/*檢查給定的插入位置的正確性*/{printf("插入位置出錯！");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置為表尾，則不需移動直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)

/*結(jié)點(diǎn)移動*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*順序表長度增1*/returnOK;

/*插入成功，返回*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第73頁。5．插入操作插入算法的時間性能分析：順序表插入操作大約需移動表中一半數(shù)據(jù)元素，其時間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第74頁。2.2.2順序表的基本操作實(shí)現(xiàn)6.刪除操作

線性表的刪除操作是指將第i個元素從順序表中去掉，刪除后順序表表長減1，原順序表如圖2-5所示。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第75頁。6.刪除操作步驟如下：(1)將要刪除的元素值賦給指針變量*x，如圖2-6所示返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第76頁。6.刪除操作步驟如下：(2)將ai+1～an之間的結(jié)點(diǎn)依次順序向前移動，如圖2-7所示。(3)順序表的長度減1，刪除成功，并返回，算法描述見算法2.7。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第77頁。6.刪除操作算法2.7intDelElem(SeqList*L,inti,ElemType*x)

{int

j;if(L->Length==0){printf("順序表為空！");returnERROR;

/*表空，不能刪除*/}if(i<1||i>L->Length)

/*檢查是否空表及刪除位置的合法性*/{printf("不存在第i個元素");returnERROR;}*x=L->data[i-1];/*用指針變量*x返回刪除的元素值*/for(j=i;j<=L->Length-1;j++)

/*結(jié)點(diǎn)移動*/L->data[j-1]=L->data[j];L->Length--;

/*順序表長度減1*/returnOK;

/*刪除成功，返回*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第78頁。6.刪除操作刪除算法的時間性能分析：與插入操作相同，其時間主要消耗在了移動表中元素上，（大約需要移動表中一半的元素），顯然該算法的時間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第79頁。2.2.2順序表的基本操作實(shí)現(xiàn)7．順序表的輸出操作掃描順序表L，輸出各元素的值，算法描述見算法2.8。算法2.8voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第80頁。2.3鏈表2.3.1單鏈表2.3.2單鏈表的基本操作實(shí)現(xiàn)2.3.3鏈表的變形返回到總目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第81頁。2.3.1單鏈表1.單鏈表的定義線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息，這樣構(gòu)成的鏈表稱為線性單向鏈接表，簡稱單鏈表，其結(jié)點(diǎn)結(jié)構(gòu)如圖2-8所示。數(shù)據(jù)域后繼指針域datanext圖2-8單鏈表的結(jié)點(diǎn)示意圖其中，data部分稱為數(shù)據(jù)域，用于存儲一個數(shù)據(jù)元素（結(jié)點(diǎn)Node）的信息。next部分稱為指針域，用于存儲其直接后繼的存儲地址的信息。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第82頁。2.3.1單鏈表單鏈表分為帶頭結(jié)點(diǎn)（其next域指向鏈表第一個結(jié)點(diǎn)的存儲地址）和不帶頭結(jié)點(diǎn)兩種類型。在許多情況下，帶頭結(jié)點(diǎn)的鏈表中每個結(jié)點(diǎn)的存儲地址均放在其前驅(qū)結(jié)點(diǎn)中，這樣算法對所有的結(jié)點(diǎn)處理可一致化，因此，本節(jié)討論的單鏈表均指帶頭結(jié)點(diǎn)的單鏈表。帶頭結(jié)點(diǎn)的單鏈表如圖2-9所示。

圖2-9帶頭結(jié)點(diǎn)的單鏈表其中，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息；頭結(jié)點(diǎn)的指針域存儲鏈表中第一個結(jié)點(diǎn)的地址。當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL或用∧表示），則此表為空表。在非空表中，當(dāng)某個結(jié)點(diǎn)的指針域?yàn)榭眨硎舅鼮殒湵淼淖詈笠粋€結(jié)點(diǎn)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第83頁。2.3.1單鏈表鏈?zhǔn)酱鎯μ攸c(diǎn)：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針來表示元素之間的邏輯關(guān)系，不再有邏輯順序與物理存儲順序一致的特點(diǎn)，是非順序存儲結(jié)構(gòu)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第84頁。2.3.1單鏈表2.單鏈表的類型定義#defineOK1#defineERROR0#defineOVER-1typedefcharElemType;/*定義ElemType為char類型*/typedefstructnode/*單鏈表存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structnode*next;/*定義結(jié)點(diǎn)的指針域*/}LinkList;返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第85頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)1.單鏈表的初始化單鏈表的初始化即構(gòu)造一個僅包含頭結(jié)點(diǎn)的空單鏈表L，算法描述見算法2.9。算法2.9

LinkList*InitList(){/*申請一塊LinkList類型的存儲單元的操作，并將其地址賦值給頭指針變量L*/LinkList*L;

L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;returnL;/*頭結(jié)點(diǎn)L指針域?yàn)榭眨硎究真湵?/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第86頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)2．單鏈表的建立（1）頭插法建表在初始化鏈表后，每讀取有效的數(shù)據(jù)都為其生成新結(jié)點(diǎn)s，并將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)s的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表L的表頭上，直到循環(huán)結(jié)束為止，算法描述見算法2.10。算法2.10voidCreateList(LinkList*L){LinkList*s;charch;while((ch=getchar())!='#')/*判斷輸入數(shù)據(jù)是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)*/s->data=ch;/*將數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=L->next;/*將新結(jié)點(diǎn)的指針域存放頭結(jié)點(diǎn)的指針域*/L->next=s;/*將新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后*/}}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第87頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)（2）尾插法建表頭插法建立鏈表雖然算法簡單易理解，但生成的鏈表中結(jié)點(diǎn)的次序和原輸入的次序相反。而尾插法建立鏈表可實(shí)現(xiàn)次序的一致，該算法依舊在初始化鏈表后，但需增加一個尾指針last，使其指向當(dāng)前鏈表的尾結(jié)點(diǎn)，算法描述見算法2.11。算法2.11voidCreateList(LinkList*L){LinkList*s,*last;charch;last=L;/*last始終指向尾結(jié)點(diǎn)，開始時指向頭結(jié)點(diǎn)*/while((ch=getchar())!='#')/*判斷輸入數(shù)據(jù)是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)*/s->data=ch;/*將數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=NULL;/*將新結(jié)點(diǎn)的指針域?yàn)榭?/last->next=s;/*將新結(jié)點(diǎn)插入表尾*/last=s;/*將last指針指向表尾結(jié)點(diǎn)*/}}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第88頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)3．求單鏈表的長度求長度就是求單鏈表中數(shù)據(jù)元素的個數(shù)。求帶頭結(jié)點(diǎn)的單鏈表L的長度需設(shè)一個動態(tài)指針p指向頭結(jié)點(diǎn)，計數(shù)器j初始值為0，p指針?biāo)附Y(jié)點(diǎn)后面若還有結(jié)點(diǎn)，p就向后移動，每次移動一次，計數(shù)器j值增1，直到p所指結(jié)點(diǎn)后面為空結(jié)束，則計數(shù)器j的值即為表的長度，算法描述見算法2.12。算法2.12intGetLength(LinkList*L){LinkList*p;intj=0;p=L;/*p指向鏈表的頭結(jié)點(diǎn)*/while(p->next!=NULL)/*判斷p所指結(jié)點(diǎn)后面是否為空*/{p=p->next;/*p向所指結(jié)點(diǎn)的后面移動*/j++;/*計數(shù)器值增1*/}returnj;/*計數(shù)器j的值為表長度*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第89頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)4．查找操作單鏈表的查找分為按值與按序號查找，下面將分別介紹這兩種方法的實(shí)現(xiàn)，讀者可根據(jù)具體的問題相應(yīng)選擇所需的查找方法。（1）按值查找算法思路：從鏈表的第一個元素結(jié)點(diǎn)開始，由前向后依次比較單鏈表中各結(jié)點(diǎn)數(shù)據(jù)域中的值，若某結(jié)點(diǎn)數(shù)據(jù)域中的值與給定的值x相等，則返回該結(jié)點(diǎn)的指針值p；否則繼續(xù)向后比較直到表結(jié)束。若整個單鏈表中沒有這樣的結(jié)點(diǎn)，則返回空NULL值，算法描述見算法2.13。算法2.13LinkList*Locate(LinkList*L,ElemTypex){LinkList*p;p=L->next;/*p指向鏈表的第一個結(jié)點(diǎn)*/while(p!=NULL&&p->data!=x)p=p->next;returnp;}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第90頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)（2）按序號查找算法思路：從鏈表的頭結(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)序號是否是第i個，若是，則返回該結(jié)點(diǎn)指針值p；否則繼續(xù)向后查找直到表結(jié)束。若沒有第i個結(jié)點(diǎn)，則返回空NULL值，算法描述見算法2.14。算法2.14LinkList*GetList(LinkList*L,inti){LinkList*p;intj=0;p=L;/*p指向鏈表的頭結(jié)點(diǎn)*/while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)/*判斷與給定的序號是否相等*/returnp;elsereturnNULL;}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第91頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)5．插入操作順序表的插入操作需要移動大量的數(shù)據(jù)元素，而鏈表的插入只需修改指針而無需移動原表元素，那鏈表的插入操作是如何實(shí)現(xiàn)呢？（1）在已知結(jié)點(diǎn)p之后插入一新結(jié)點(diǎn)s已知結(jié)點(diǎn)p為鏈表中任意結(jié)點(diǎn)，先創(chuàng)建一個以x為值的新結(jié)點(diǎn)s，則插入操作步驟如下：先將結(jié)點(diǎn)s的指針域指向結(jié)點(diǎn)p的下一個結(jié)點(diǎn)（執(zhí)行語句s->next=p->next）。再將結(jié)點(diǎn)p的指針域改為指向新結(jié)點(diǎn)s（執(zhí)行語句p->next=s）。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第92頁。5．插入操作插入結(jié)點(diǎn)的過程如圖2-10所示，算法描述見算法2.15。注：插入操作的①與②語句執(zhí)行順序不能顛倒，否則原p指針其后的鏈表將丟失。算法2.15voidIns_Elem(LinkList*p,ElemTypex){LinkList*s;s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)s*/s->data=x;/*將數(shù)據(jù)x放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=p->next;/*將新結(jié)點(diǎn)s的指針域與p結(jié)點(diǎn)后面元素相連*/p->next=s;/*將p與新結(jié)點(diǎn)s鏈接*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第93頁。5．插入操作（2）在第i個位置插入新結(jié)點(diǎn)s由于單鏈表的結(jié)點(diǎn)結(jié)構(gòu)是單向后指的，因此要完成此操作需要找到第i結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即第i－1結(jié)點(diǎn)的指針p，此時可調(diào)用按序號查找GetList()函數(shù)求出p指針地址，然后在調(diào)用在已知結(jié)點(diǎn)p后方插入新結(jié)點(diǎn)Ins_Elem()函數(shù)操作即可，算法描述見算法2.16。算法2.16intInsElem(LinkList*L,inti,ElemTypex){LinkList*p;p=GetList(L,i-1);/*調(diào)用按序號查找函數(shù)GetList()，求出第i-1個元素地址p*/if(p!=NULL)/*判斷查找的元素地址p是否存在*/{Ins_Elem(p,x);/*調(diào)用在已知結(jié)點(diǎn)p后插入結(jié)點(diǎn)函數(shù)Ins_Elem()*/returnOK;}elsereturnERROR;}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第94頁。5．插入操作插入算法的時間性能分析：鏈表插入操作主要時間耗費(fèi)在查找操作上，其時間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第95頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)6．刪除操作順序表的刪除操作同樣需要移動大量的數(shù)據(jù)元素，而鏈表的刪除只需修改指針而無需移動原表元素，那鏈表的刪除操作是如何實(shí)現(xiàn)呢？（1）刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)s已知結(jié)點(diǎn)p為鏈表中除終端結(jié)點(diǎn)以外的任意結(jié)點(diǎn)，先將結(jié)點(diǎn)s中的數(shù)據(jù)域中的值賦給指針變量*x，則刪除操作步驟如下：結(jié)點(diǎn)p指針域指向結(jié)點(diǎn)s下一個結(jié)點(diǎn)（執(zhí)行語句p->next=s->next）。②釋放s結(jié)點(diǎn)空間（執(zhí)行語句free(s)）。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第96頁。6．刪除操作刪除結(jié)點(diǎn)的過程如圖2-11所示，算法描述見算法2.17。

圖2-11在結(jié)點(diǎn)p之后刪除結(jié)點(diǎn)s算法2.17voidDel_Elem(LinkList*p,ElemType*x){LinkList*s;s=p->next;/*s為要刪除結(jié)點(diǎn)*/*x=s->data;/*將要刪除的數(shù)據(jù)放入指針變量*x中*/p->next=s->next;/*將p結(jié)點(diǎn)的指針域與s結(jié)點(diǎn)后面元素相連*/free(s);/*釋放結(jié)點(diǎn)s*/}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第97頁。6．刪除操作（2）刪除未知結(jié)點(diǎn)（如第i個結(jié)點(diǎn)）s首先求出第i結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（第i-1結(jié)點(diǎn)）p的地址，可調(diào)用按序號查找GetList()函數(shù)求出p指針地址，然后再調(diào)用刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)s的DelList()函數(shù)操作即可。算法中注意if(p!=NULL&&p->next!=NULL)語句,只有當(dāng)?shù)趇-1結(jié)點(diǎn)存在即（p!=NULL）而又不是終端結(jié)點(diǎn)即（p->next!=NULL）時，才能確定被刪除結(jié)點(diǎn)存在，算法描述見算法2.18。算法2.18intDelElem(LinkList*L,inti,ElemType*x){LinkList*p;p=GetList(L,i-1);/*調(diào)用按序號查找第i-1個元素地址p函數(shù)*/if(p!=NULL&&p->next!=NULL){Del_Elem(p,x);/*調(diào)用刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)函數(shù)*/returnOK;}elsereturnERROR;}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第98頁。6．刪除操作刪除算法的時間性能分析：鏈表刪除操作也主要時間耗費(fèi)在查找操作上，其時間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第99頁。2.3.2單鏈表的基本操作實(shí)現(xiàn)7．單鏈表的輸出操作掃描單鏈表L，輸出各元素的值，算法描述見算法2.19。算法2.19voidDispList(LinkList*L){LinkList*p;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}}返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第100頁。2.3.3鏈表的變形1．循環(huán)單鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于單鏈表而言，最后一個結(jié)點(diǎn)的指針域?yàn)榭?，如果將該鏈表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)，就構(gòu)成了循環(huán)單鏈表，如圖2-12所示。由此，從表中的任意結(jié)點(diǎn)出發(fā)均可找到表中的其他結(jié)點(diǎn)。在循環(huán)單鏈表上的操作基本上與非循環(huán)的單鏈表相同，只是將原來判斷指針是否為NULL，改為是否是頭指針L即可。圖2-12帶頭結(jié)點(diǎn)的循環(huán)單鏈表返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第101頁。2.3.3鏈表的變形2．雙鏈表（1）雙鏈表的定義在單鏈表結(jié)點(diǎn)中只有一個指向直接后繼的指針域next，這樣從某個結(jié)點(diǎn)出發(fā)只能順指針方向?qū)ふ宜暮罄^結(jié)點(diǎn)。若要尋找結(jié)點(diǎn)的直接前驅(qū)，則需從頭指針出發(fā)查找前驅(qū)。若希望能夠快速查找一個結(jié)點(diǎn)的直接前驅(qū)，則可以再增加一個指向其直接前驅(qū)的指針域prior，這樣就構(gòu)成了雙向鏈接表，簡稱雙鏈表，其結(jié)點(diǎn)結(jié)構(gòu)如圖2-13所示。圖2-13雙鏈表的結(jié)點(diǎn)示意圖其中，data部分稱為數(shù)據(jù)域，用于存儲一個數(shù)據(jù)元素（結(jié)點(diǎn)Node）的信息。prior部分稱為前驅(qū)指針域，用于存儲其直接前驅(qū)的存儲地址的信息。next部分稱為后繼指針域，用于存儲其直接后繼的存儲地址的信息。前驅(qū)指針域數(shù)據(jù)域后繼指針域priordatanext返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第102頁。2．雙鏈表（2）雙鏈表的類型定義typedefcharElemType;/*定義ElemType為char類型*/typedefstructdunode/*雙鏈表存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structdunode*prior;/*定義結(jié)點(diǎn)的前驅(qū)指針域*/structdunode*next;/*定義結(jié)點(diǎn)的后繼指針域*/}DuLinkList;返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第103頁。2．雙鏈表為了算法對所有的結(jié)點(diǎn)處理可一致化，與單鏈表一樣，本章討論的雙鏈表均指帶頭結(jié)點(diǎn)的雙鏈表。帶頭結(jié)點(diǎn)的雙鏈表如圖2-14所示。其中，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息，頭結(jié)點(diǎn)的前驅(qū)指針域?yàn)榭眨碞ULL或用∧表示），后繼指針域存儲鏈表中第一個結(jié)點(diǎn)的地址。當(dāng)頭結(jié)點(diǎn)的后繼指針域?yàn)榭眨碞ULL或用∧表示），則此表為空表。在非空表中，當(dāng)某個結(jié)點(diǎn)的后繼指針域?yàn)榭?，表示它為鏈表的最后一個結(jié)點(diǎn)。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第104頁。2．雙鏈表（3）雙鏈表的基本運(yùn)算在雙鏈表中，有些操作（如求鏈表的長度、查找某個結(jié)點(diǎn)等）僅涉及一個方向的指針，其算法與單鏈表的操作相同，但在插入和刪除操作時卻有很大的區(qū)別。①在雙鏈表中p指針指向的結(jié)點(diǎn)前插入新結(jié)點(diǎn)s操作先創(chuàng)建一個以x為值的新結(jié)點(diǎn)s，在p結(jié)點(diǎn)之前插入結(jié)點(diǎn)s，則插入操作步驟如下：將結(jié)點(diǎn)s的prior域指向結(jié)點(diǎn)p的前一個結(jié)點(diǎn)（執(zhí)行語句s->prior=p->prior）。將結(jié)點(diǎn)p的前一個結(jié)點(diǎn)的next域指向結(jié)點(diǎn)s（執(zhí)行語句p->prior->next=s）。將結(jié)點(diǎn)s的next域指向p結(jié)點(diǎn)（執(zhí)行語句s->next=p）。將結(jié)點(diǎn)p的prior域指向結(jié)點(diǎn)s。（執(zhí)行語句p->prior=s）。返回到本節(jié)目錄數(shù)據(jù)結(jié)構(gòu)(C語言版)全文共607頁，當(dāng)前為第105頁。2．雙鏈表插入結(jié)點(diǎn)的過程如圖2-15所示，算法描述見算法2.20。注：以上操作的步