配套課件-數(shù)據(jù)結(jié)構(gòu)(C語言描述)

數(shù)據(jù)結(jié)構(gòu)（C語言描述）

前言

二十一世紀(jì)是科學(xué)技術(shù)高速發(fā)展的信息時(shí)代，而計(jì)算機(jī)是處理信息的主要工具，因此，人們已經(jīng)認(rèn)識到，計(jì)算機(jī)知識已成為人類當(dāng)代文化的一個(gè)重要組成部分。計(jì)算機(jī)科學(xué)技術(shù)以驚人的速度向前發(fā)展，它的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域。在非數(shù)值計(jì)算領(lǐng)域里，數(shù)據(jù)處理的對象已從簡單的數(shù)值發(fā)展到一般的符號，進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù)。在這里，面臨的主要問題是：針對每一種新的應(yīng)用領(lǐng)域的處理對象，如何選擇合適的數(shù)據(jù)表示（構(gòu)構(gòu)），如何有效地組織計(jì)算機(jī)存貯，并在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對象之間的“運(yùn)算”關(guān)系。傳統(tǒng)的解決數(shù)值計(jì)算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計(jì)算問題的需要，必須進(jìn)行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論。因此，“數(shù)據(jù)結(jié)構(gòu)”課程已成為計(jì)算機(jī)類專業(yè)的一門重要專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的中級課程，主要培養(yǎng)學(xué)生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴學(xué)生如何編寫效率高、結(jié)構(gòu)好的程序。本書作為計(jì)算機(jī)大專系列教材之一，在內(nèi)容的選取、概念的引入、文字的敘述以及例題和習(xí)題的選擇等方面，都力求遵循面向應(yīng)用、邏輯結(jié)構(gòu)簡明合理、由淺入深、深入淺出、循序漸進(jìn)、便于自學(xué)的原則，突出其實(shí)用性與應(yīng)用性。全書共分十章。書中，安排了相當(dāng)?shù)钠鶃斫榻B這些基本數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用。進(jìn)入章節(jié)1引言

2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)算機(jī)科學(xué)中所處的地位3什么是數(shù)據(jù)結(jié)構(gòu)

4基本概念和術(shù)語

5算法和算法的描述

第一章緒論

本章介紹了數(shù)據(jù)結(jié)構(gòu)這門學(xué)科誕生的背景、發(fā)展歷史以及在計(jì)算機(jī)科學(xué)中所處的地位，重點(diǎn)介紹了數(shù)據(jù)結(jié)構(gòu)有關(guān)的概念和術(shù)語，讀者學(xué)習(xí)本章后應(yīng)能掌握數(shù)據(jù)、數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)等基本概念，并了解如何評價(jià)一個(gè)算法的好壞。

1.1引言眾所周知，二十世紀(jì)四十年代，電子數(shù)字計(jì)算機(jī)問世的直接原因是解決彈道學(xué)的計(jì)算問題。早期，電子計(jì)算機(jī)的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計(jì)算，其處理的對象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計(jì)算。近三十年來，電子計(jì)算機(jī)的發(fā)展異常迅猛，這不僅表現(xiàn)在計(jì)算機(jī)本身運(yùn)算速度不斷提高、信息存儲(chǔ)量日益擴(kuò)大、價(jià)格逐步下降，更重要的是計(jì)算機(jī)廣泛地應(yīng)用于情報(bào)檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計(jì)算的范圍，而滲透到人類社會(huì)活動(dòng)的一切領(lǐng)域。與此相應(yīng)，計(jì)算機(jī)的處理對象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。

因此，再把電子數(shù)字計(jì)算機(jī)簡單地看作是進(jìn)行數(shù)值計(jì)算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計(jì)算機(jī)科學(xué)的觀點(diǎn)，是把計(jì)算機(jī)程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而電子計(jì)算機(jī)則是加工處理數(shù)據(jù)（信息）的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計(jì)人員的經(jīng)驗(yàn)和技巧已難以設(shè)計(jì)出效率高、可靠性強(qiáng)的程序。于是，就要求人們對計(jì)算機(jī)程序加工的對象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系——數(shù)據(jù)結(jié)構(gòu)（DateStructure）。1.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)算機(jī)科學(xué)中所處的地位發(fā)展史：1、“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國外是從1968年才開始設(shè)立的。2、1968年美國唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。地位：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。

1.3什么是數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運(yùn)算是由計(jì)算機(jī)來完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。1.4基本概念和術(shù)語1．?dāng)?shù)據(jù)

數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個(gè)個(gè)人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。

表1-1個(gè)人書庫2．結(jié)點(diǎn)結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。例如，在表1-1所示的個(gè)人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個(gè)基本單位來考慮，故該數(shù)據(jù)由10個(gè)結(jié)點(diǎn)構(gòu)成。一般情況下，一個(gè)結(jié)點(diǎn)中含有若干個(gè)字段（也叫數(shù)據(jù)項(xiàng)）。例如，在表1-1所示的表格數(shù)據(jù)中，每個(gè)結(jié)點(diǎn)都有登錄號、書號、書名、作者、出版社和價(jià)格等六個(gè)字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。3．邏輯結(jié)構(gòu)結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯上有一種線性關(guān)系，它指出了10個(gè)結(jié)點(diǎn)在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4．存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲(chǔ)表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。5．?dāng)?shù)據(jù)處理數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡單計(jì)算等的操作過程。在早期，計(jì)算機(jī)主要用于科學(xué)和工程計(jì)算，進(jìn)入八十年代以后，計(jì)算機(jī)主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計(jì)資料表明，現(xiàn)在計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例達(dá)到80%以上，隨著時(shí)間的推移和計(jì)算機(jī)應(yīng)用的進(jìn)一步普及，計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例必將進(jìn)一步增大。6．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（DataElement）之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。為了敘述上的方便和避免產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)（StorageStructure）。7．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是指程序設(shè)計(jì)語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計(jì)語言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計(jì)語言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

8．算法簡單地說就是解決特定問題的方法（關(guān)于算法的嚴(yán)格定義，在此不作討論）。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計(jì)算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。一般說來，在數(shù)值算法中主要進(jìn)行算術(shù)運(yùn)算，而在非數(shù)值算法中主要進(jìn)行比較和邏輯運(yùn)算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。1.5算法和算法的描述

1.5.1算法算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有5個(gè)特點(diǎn)：

1.動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。

2.確定性：算法中的每條指令都必須是清楚的，指令無二義性。

3.輸入：具有0個(gè)或0個(gè)以上由外界提供的量。

4.輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。

5.可行性：每條指令都充分基本，原則上可由人僅用筆和紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。注意：算法和程序是有區(qū)別的，即程序未必能滿足動(dòng)態(tài)有窮。在本書中，我們只討論滿足動(dòng)態(tài)有窮的程序，因此“算法”和“程序”是通用的。

1.5.2算法的描述

一個(gè)算法可以用自然語言、數(shù)字語言或約定的符號來描述，也可以用計(jì)算機(jī)高級程序語言來描述，如Pascal語言、C語言或偽代碼等。本書選用C語言作為描述算法的工具。現(xiàn)簡單說明C語言的語法結(jié)構(gòu)如下：1．預(yù)定義常量和類型：

#defineTRUE1；

#defineFALSE-1；

#defineERRORNULL；2．函數(shù)的形式

[數(shù)據(jù)類型]函數(shù)名（[形式參數(shù)]）

[形式參數(shù)說明；]{內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；

}/*函數(shù)名*/〈函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號“{”和“}”括起來。函數(shù)中用方括號括起來的部分為可選項(xiàng)，函數(shù)名之間的圓括號不可省略。函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外。執(zhí)行語句可由各種類型的語句所組成，兩個(gè)語句之間用“；”號分隔?？蓪⒑瘮?shù)中的表達(dá)式的值通過return語句返回給調(diào)用它的函數(shù)。最后的花括號“}”之后的/*函數(shù)名*/為注釋部分，可舍。

3．賦值語句簡單賦值：〈變量名〉=〈表達(dá)式〉，它表示將表達(dá)式的值賦給左邊的變量；〈變量〉++，它表示變量加1后賦值給變量；〈變量〉--，它表示變量減1后賦值給變量；成組賦值：1.（〈變量1〉，〈變量2〉，〈變量3〉，…〈變量k〉）=（〈表達(dá)式1〉，〈表達(dá)式2〉，〈表達(dá)式3〉，…〈表達(dá)式k〉）；2.〈數(shù)組名1〉[下標(biāo)1…下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1…下標(biāo)2]串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉；條件賦值：〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉：〈表達(dá)式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變量2互換；4．條件選擇語句if（〈表達(dá)式〉）語句；if（〈表達(dá)式〉）語句1；else語句2；情況語句

switch（〈表達(dá)式〉）

{case判斷值1；語句組1；

break；

case判斷值2；語句組2；

break；

……case判斷值n；語句組n；

break；

[default：語句組；

break；]}注意：switchcase語句是先計(jì)算表達(dá)式的值，然后用其值與判斷值相比較，若它們相一致時(shí)，就執(zhí)行相應(yīng)的case下的語句組；若不一致，則執(zhí)行default下的語句組；其中的方括號代表可選項(xiàng)。

5．循環(huán)語句⑴for語句

for（〈表達(dá)式1〉；〈表達(dá)式2〉；〈表達(dá)式3〉）{循環(huán)體語句；}

首先計(jì)算表達(dá)式1的值，然后求表達(dá)式2的值，若結(jié)果非零則執(zhí)行循環(huán)體語句，最后對表達(dá)式3運(yùn)算，如此循環(huán)，直到表達(dá)式2的值為零時(shí)止。⑵while語句

while（〈條件表達(dá)式〉）

{循環(huán)體語句；

}while循環(huán)首先計(jì)算條件表達(dá)式的值，若條件表達(dá)式的值非零，則執(zhí)行循環(huán)體語句，然后再次計(jì)算條件表達(dá)式，重復(fù)執(zhí)行，直到條件表達(dá)式的值為假時(shí)退出循環(huán)，執(zhí)行該循環(huán)之后的語句。⑶do-while語句

do{循環(huán)體語句

}while（〈條件表達(dá)式〉）該循環(huán)語句首先執(zhí)行循環(huán)體語句。然后再計(jì)算條件表達(dá)式的值，若條件表達(dá)式成立，則再次執(zhí)行循環(huán)體，再計(jì)算條件表達(dá)式的值，直到條件表達(dá)式的值為零，即條件不成立時(shí)結(jié)束循環(huán)。6．輸入、輸出語句輸入語句：用函數(shù)scanf實(shí)現(xiàn)，特別當(dāng)數(shù)據(jù)為字符時(shí)，用getchar函數(shù)實(shí)現(xiàn)。輸出語句：用printf函數(shù)實(shí)現(xiàn)，當(dāng)要輸出字符數(shù)據(jù)時(shí)，用putchar函數(shù)實(shí)現(xiàn)。7．其他一些語句（1）return表達(dá)式或return：用于函數(shù)結(jié)束。（2）break語句：可用在循環(huán)語句或case語句中結(jié)束循環(huán)過程或跳出情況語句。（3）exit語句：表示出現(xiàn)異常情況時(shí)，控制退出語句。8．注釋形式可用/*字符串*/或者單行注釋或//文字序列。9．一些基本的函數(shù)如：max函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最大值；

min函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最小值；

abs函數(shù)，用于求表達(dá)式的絕對值；

eof函數(shù)，用于判定文件是否結(jié)束；

eoln函數(shù)，用于判斷文本行是否結(jié)束。例計(jì)算f=1！+2！+3！+…+n！，用C語言描述。voidfactorsum（n）

intn；{inti，j；intf，w；

f=0；

for（i=1，i〈=n；i++）

{w=1；

for（j=1，j〈=i；j++）

w=w*j；

f=f+w；}return；}上述算法所用到的運(yùn)算有乘法、加法、賦值和比較，其基本運(yùn)算為乘法操作。在上述算法的執(zhí)行過程中，對外循環(huán)變量i的每次取值，內(nèi)循環(huán)變量j循環(huán)i次。因?yàn)閮?nèi)循環(huán)每執(zhí)行一次，內(nèi)循環(huán)體語句w=w*j只作一次乘法操作，即當(dāng)內(nèi)循環(huán)變量j循環(huán)i次時(shí)，內(nèi)循環(huán)體的語句w=w*j作i次乘法。所以，整個(gè)算法所作的乘法操作總數(shù)是：f（n）=1+2+3+…n=n（n-1）/2。1.5.3算法評價(jià)設(shè)計(jì)一個(gè)好的算法應(yīng)考慮以下幾個(gè)方面：1．正確性

“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個(gè)層次：①程序不含語法錯(cuò)誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；④程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。

2．運(yùn)行時(shí)間運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間。它大致等于計(jì)算機(jī)執(zhí)行一種簡單操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等）所需要的時(shí)間與算法中進(jìn)行簡單操作次數(shù)的乘積。通常把算法中包含簡單操作次數(shù)的多少叫做算法的時(shí)間復(fù)雜性，它是一個(gè)算法運(yùn)行時(shí)間的相對量度。3．占用的存儲(chǔ)空間一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。分析一個(gè)算法所占用的存儲(chǔ)空間要從各方面綜合考慮。算法在運(yùn)行過程中所占用的存儲(chǔ)空間的大小被定義為算法的空間復(fù)雜性。它包括局部變量所占用的存儲(chǔ)空間和系統(tǒng)為了實(shí)現(xiàn)遞歸所使用的堆棧這兩個(gè)部分。算法的空間復(fù)雜性一般以數(shù)量級的形式給出。4．簡單性最簡單和最直接的算法往往不是最有效的，但算法的簡單性使得證明其正確性比較容易，同時(shí)便于編寫、修改、閱讀和調(diào)試，所以還是應(yīng)當(dāng)強(qiáng)調(diào)和不容忽視的。不過對于那些需要經(jīng)常使用的算法來說，高效率（即盡量減少運(yùn)行時(shí)間和壓縮存儲(chǔ)空間）比簡單性更為重要。本章小結(jié)本章主要介紹了如下一些基本概念：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。數(shù)據(jù)：數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。結(jié)點(diǎn)：結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。邏輯結(jié)構(gòu)：結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)處理：數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡單計(jì)算等的操作過程。數(shù)據(jù)類型：數(shù)據(jù)類型是指程序設(shè)計(jì)語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計(jì)語言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。

習(xí)題一1．簡述下列術(shù)語：數(shù)據(jù)、結(jié)點(diǎn)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型。2．試根據(jù)以下信息：校友姓名、性別、出生年月、畢業(yè)時(shí)間、所學(xué)專業(yè)、現(xiàn)在工作單位、職稱、職務(wù)、電話等，為校友錄構(gòu)造一種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)（作圖示意），并定義必要的運(yùn)算和用文字?jǐn)⑹鱿鄳?yīng)的算法思想。3．什么是算法？算法的主要特點(diǎn)是什么？4．如何評價(jià)一個(gè)算法？1線性表的邏輯結(jié)構(gòu)

本章學(xué)習(xí)導(dǎo)讀線性表（Linearlist）是最簡單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。這種結(jié)構(gòu)具有下列特點(diǎn)：存在一個(gè)唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素；存在一個(gè)唯一的沒有后繼的（尾）數(shù)據(jù)元素；此外，每一個(gè)數(shù)據(jù)元素均有一個(gè)直接前驅(qū)和一個(gè)直接后繼數(shù)據(jù)元素。通過本章的學(xué)習(xí)，讀者應(yīng)能掌握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及線性表的基本運(yùn)算以及實(shí)現(xiàn)算法。

2線性表的順序存儲(chǔ)結(jié)構(gòu)

3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

4一元多項(xiàng)式的表示及相加

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

線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素的含義廣泛，在不同的具體情況下，可以有不同的含義。例如：英文字母表（A，B，C，…，Z）是一個(gè)長度為26的線性表，其中的每一個(gè)字母就是一個(gè)數(shù)據(jù)元素；再如，某公司2000年每月產(chǎn)值表（400，420，500，…，600，650）(單位：萬元)是一個(gè)長度為12的線性表，其中的每一個(gè)數(shù)值就是一個(gè)數(shù)據(jù)元素。上述兩例中的每一個(gè)數(shù)據(jù)元素都是不可分割的，在一些復(fù)雜的線性表中，每一個(gè)數(shù)據(jù)元素又可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，在這種情況下，通常將數(shù)據(jù)元素稱為記錄（record），例如，圖2-1的某單位職工工資表就是一個(gè)線性表，表中每一個(gè)職工的工資就是一個(gè)記錄，每個(gè)記錄包含八個(gè)數(shù)據(jù)項(xiàng)：職工號、姓名、基本工資……。職工號姓名基本工資崗位工資獎(jiǎng)金應(yīng)發(fā)工資扣款實(shí)發(fā)工資1201張強(qiáng)54030020010402010201301周敏500200200900208801202徐黎芬55030020010503010201105黃承振53025020098020960┇┇┇┇┇┇┇┇圖2-1職工工資表矩陣也是一個(gè)線性表，但它是一個(gè)比較復(fù)雜的線性表。在矩陣中，我們可以把每行看成是一個(gè)數(shù)據(jù)元素，也可以把每列看成是一個(gè)數(shù)據(jù)元素，而其中的每一個(gè)數(shù)據(jù)元素又是一個(gè)線性表。綜上所述，一個(gè)線性表是n≥0個(gè)數(shù)據(jù)元素a0，a1，a2，…，an-1的有限序列。如果n>0，則除a0和an-1外，有且僅有一個(gè)直接前趨和一個(gè)直接后繼數(shù)據(jù)元素，ai（0≤i≤n-1）為線性表的第i個(gè)數(shù)據(jù)元素，它在數(shù)據(jù)元素ai-1之后，在ai+1之前。a0為線性表的第一個(gè)數(shù)據(jù)元素，而an-1是線性表的最后一個(gè)數(shù)據(jù)元素；若n=0，則為一個(gè)空表，表示無數(shù)據(jù)元素。因此，線性表或者是一個(gè)空表（n=0），或者可以寫成：（a0，a1，a2，…，ai-1，ai，ai+1，…，an-1）。抽象數(shù)據(jù)類型線性表的定義如下：LinearList=(D,R)其中，D={ai|ai∈ElemSet,i=0,1,2,…，n-1n≥1}R={<ai-1，ai>|ai-1，ai∈D,i=0,1,2,…，n-1}Elemset為某一數(shù)據(jù)對象集；n為線性表的長度。線性表的主要操作有如下幾種：1．

Initiate(L)初始化：構(gòu)造一個(gè)空的線性表L。2．

Insert(L,i,x)插入：在給定的線性表L中，在第i個(gè)元素之前插入數(shù)據(jù)元素x。線性表L長度加1。3．

Delete(L,i)刪除：在給定的線性表L中，刪除第i個(gè)元素。線性表L的長度減1。4．

Locate(L,x)查找定位：對給定的值x，若線性表L中存在一個(gè)元素ai與之相等，則返回該元素在線性表中的位置的序號i，否則返回Null（空）。5．

Length(L)求長度：對給定的線性表L，返回線性表L的數(shù)據(jù)元素的個(gè)數(shù)。6．

Get(L,i)存取：對給定的線性表L，返回第i（0≤i≤Length(L)-1）個(gè)數(shù)據(jù)元素，否則返回Null。7．

Traverse(L)遍歷：對給定的線性表L，依次輸出L的每一個(gè)數(shù)據(jù)元素。8．

Copy(L,C)復(fù)制：將給定的線性表L復(fù)制到線性表C中。9．

Merge(A,B,C)合并：將給定的線性表A和B合并為線性表C。上面我們定義了線性表的邏輯結(jié)構(gòu)和基本操作。在計(jì)算機(jī)內(nèi)，線性表有兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。下面我們分別討論這兩種存儲(chǔ)結(jié)構(gòu)以及對應(yīng)存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)各操作的算法。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)。2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前驅(qū)元素一定存儲(chǔ)在后繼元素的前面。由于線性表的所有數(shù)據(jù)元素屬于同一數(shù)據(jù)類型，所以每個(gè)元素在存儲(chǔ)器中占用的空間大小相同，因此，要在該線性表中查找某一個(gè)元素是很方便的。假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為Loc(a0)，每一個(gè)數(shù)據(jù)元素占d字節(jié)，則線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為：Loc(ai)=Loc(a0)+id在程序設(shè)計(jì)語言中，通常利用數(shù)組來表示線性表的順序存儲(chǔ)結(jié)構(gòu)。這是因?yàn)閿?shù)組具有如下特點(diǎn)：（1）數(shù)據(jù)中的元素間的地址是連續(xù)的；（2）數(shù)組中所有元素的數(shù)據(jù)類型是相同的。而這與線性表的順序存儲(chǔ)空間結(jié)構(gòu)是類似的。1．一維數(shù)組

若定義數(shù)組A[n]={a0，a1，a2，…，an-1}，假設(shè)每一個(gè)數(shù)組元素占用d個(gè)字節(jié)，則數(shù)組元素A[0]，A[1]，A[2]，…，A[n-1]的地址分別為Loc(A[0])，Loc(A[0])+d，Loc(A[0])+2d，…，Loc(A[0])+（n-1）d。其結(jié)構(gòu)如圖2-2所示。若定義數(shù)組A[n][m]，表示此數(shù)組有n行m列，如下圖2-3所示。

012…j

…m-10a00a01a02…a0j…a0m-1a10a11a12…a1j…a1m-1a20a21a22…a2j…a2m-1iai0ai1ai2…aij…aim-1n-1an-1,0an-1,1an-1,2…an-1,j…an-1,m-1

圖2-3二維數(shù)組

２．二維數(shù)組在C語言中，二維數(shù)組的保存是按照行方式存儲(chǔ)的，先將第一行元素排好，接著排第二行元素，直至所有行的元素排完。如圖2-4所示。圖2-4二維數(shù)組存儲(chǔ)示意圖2.2.2線性表在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算可用C語言描述順序存儲(chǔ)結(jié)構(gòu)下的線性表（順序表）如下：#defineTRUE1#defineFALSE0#defineMAXNUM<順序表最大元素個(gè)數(shù)>ElemtypeList[MAXNUM]; /*定義順序表List*/intnum=-1; /*定義當(dāng)前數(shù)據(jù)元素下標(biāo)，并初始化*/我們還可將數(shù)組和表長封裝在一個(gè)結(jié)構(gòu)體中：structLinear_list{ElemtypeList[MAXNUM]; /*定義數(shù)組域*/intlength; /*定義表長域*/}1.順序表的插入操作

序號元素

序號元素

在長度為num(0≤num≤MAXNUM-2)的順序表List的第i(0≤i≤num+1)個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素x時(shí)，需將最后一個(gè)即第num個(gè)至第i個(gè)元素（共num-i+1個(gè)元素）依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置，然后把x插入到第i個(gè)存儲(chǔ)位置，插入結(jié)束后順序表的長度增加1，返回TRUE值；若i＜0或i＞num+1，則無法插入，返回FALSE。如圖2-5所示。

在長度為num(0≤num≤MAXNUM-2)的順序表List的第i(0≤i≤num+1)個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素x時(shí)，需將最后一個(gè)即第num個(gè)至第i個(gè)元素（共num-i+1個(gè)元素）依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置，然后把x插入到第i個(gè)存儲(chǔ)位置，插入結(jié)束后順序表的長度增加1，返回TRUE值；若i＜0或i＞num+1，則無法插入，返回FALSE。如圖2-5所示。

序號元素

0

a01a12a2┇┇i-1ai-1i

aii+1ai+1i+2

ai+2┇┇numanum

序號元素0a01a12a2

┇┇i-1ai-1ixi+1aii+2ai+1

┇┇numanum

插入x圖2-5在數(shù)組中插入元素

其算法如下：【算法2.1順序表的插入】intInsert(ElemtypeList[],int*num,inti,Elemtypex){/*在順序表List[]中，*num為表尾元素下標(biāo)位置，在第i個(gè)元素前插入數(shù)據(jù)元素x，若成功，返回TRUE，否則返回FALSE。*/intj;if(i<0||i>*num+1){printf(“Error!”); /*插入位置出錯(cuò)*/returnFALSE;}if(*num>=MAXNUM-1){printf(“overflow!”);returnFALSE; /*表已滿*/｝for(j=*num;j>=i;j--)List[j+1]=List[j]; /*數(shù)據(jù)元素后移*/List[i]=x; /*插入x*/(*num)++; /*長度加1*/returnTRUE;}注：順序表List的最大數(shù)據(jù)元素個(gè)數(shù)為MAXNUM，num標(biāo)識為順序表的當(dāng)前表尾（num≤MAXNUM-1）。２．順序表的刪除操作

序號元素0

a01a1

2a2┇┇i-1ai-1iai+1i+1ai+2┇┇numanum

0a01a1

2

a2┇┇i-1ai-1iai

i+1ai+1┇┇numanum

圖2-6在數(shù)組中刪除元素

在長度為num(0≤num≤MAXNUM-1)的順序表List，刪除第i(0≤i≤num)個(gè)數(shù)據(jù)元素，需將第i至第num個(gè)數(shù)據(jù)元素的存儲(chǔ)位置（num-i+1）依次前移，并使順序表的長度減1，返回TRUE值，若i＜0或i＞num，則無法刪除，返回FALSE值，如圖2-6所示。其算法如下：【算法2.2順序表的刪除】intDelete(ElemtypeList[],int*num,inti){/*在線性表List[]中，*num為表尾元素下標(biāo)位置，刪除第i個(gè)元素，線性表的元素減1，若成功，則返回TRUE；否則返回FALSE。*/intj;if(i<0||i>*num){printf(“Error!”);returnFALSE; /*刪除位置出錯(cuò)！*/}for(j=i+1;j<=*num;j++)List[j-1]=List[j]; /*數(shù)據(jù)元素前移*/(*num)--; /*長度減1*/returnTRUE;}從上述兩個(gè)算法來看，很顯然，在線性表的順序存儲(chǔ)結(jié)構(gòu)中插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)數(shù)據(jù)元素上。而移動(dòng)元素的次數(shù)取決于插入或刪除元素的位置。假設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的平均次數(shù)為假設(shè)qi是刪除第i個(gè)元素的概率，則在長度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的平均次數(shù)為如果在線性表的任何位置插入或刪除元素的概率相等，即則可見，在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入或刪除一個(gè)元素時(shí)，平均要移動(dòng)表中大約一半的數(shù)據(jù)元素。若表長為n，則插入和刪除算法的時(shí)間復(fù)雜度都為O(n)。在順序存儲(chǔ)結(jié)構(gòu)的線性表中其他的操作也可直接實(shí)現(xiàn)，在此不再講述。例：將有序線性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并為Lc={1,2,4,5,6,7,7,8,9}。分析：Lc中的數(shù)據(jù)元素或者是La中的數(shù)據(jù)元素，或者是Lb中的數(shù)據(jù)元素，則只要先將Lc置為空表，然后將La或Lb中的元素逐個(gè)插入到Lc中即可。設(shè)兩個(gè)指針i和j分別指向La和Lb中的某個(gè)元素，若設(shè)i當(dāng)前所指的元素為a，j當(dāng)前所指的元素為b，則當(dāng)前應(yīng)插入到Lc中的元素c為c={ａ當(dāng)ａ≤ｂ時(shí)ｂ當(dāng)ａ＞ｂ時(shí)，很顯然，指針i和j的初值均為1，在所指元素插入Lc后，i，j在La或Lb中順序后移。算法如下：voidmerge(ElemtypeLa[],ElemtypeLb[],Elemtype**Lc){inti,j,k;intLa_length,Lb_length;i=j=0;k=0;La_length=Length(La);Lb_length(Lb)=Length(Lb); /*取表La,Lb的長度*/Initiate(Lc); /*初始化表Lc*/While(i<=La_length&&j<=Lb_length){a=get(La,i);b=get(Lb,j);if(a<b){insert(Lc,++k,a);++i;}else{insert(Lc,++k,b);++j;}} /*將La和Lb的元素插入到Lc中*/while(i<=La_length){a=get(La,i);insert(Lc,++k,a);}while(j<=lb_length){b=get(La,i);insert(Lc,++k,b);}}

3．順序表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)線性表的順序存儲(chǔ)結(jié)構(gòu)中任意數(shù)據(jù)元素的存儲(chǔ)地址可由公式直接導(dǎo)出，因此順序存儲(chǔ)結(jié)構(gòu)的線性表是可以隨機(jī)存取其中的任意元素。也就是說定位操作可以直接實(shí)現(xiàn)。高級程序設(shè)計(jì)語言提供的數(shù)組數(shù)據(jù)類型可以直接定義順序存儲(chǔ)結(jié)構(gòu)的線性表，使其程序設(shè)計(jì)十分方便。但是，順序存儲(chǔ)結(jié)構(gòu)也有一些不方便之處，主要表現(xiàn)在：（1）數(shù)據(jù)元素最大個(gè)數(shù)需預(yù)先確定，使得高級程序設(shè)計(jì)語言編譯系統(tǒng)需預(yù)先分配相應(yīng)的存儲(chǔ)空間。（2）插入與刪除運(yùn)算的效率很低。為了保持線性表中的數(shù)據(jù)元素的順序，在插入操作和刪除操作時(shí)需移動(dòng)大量數(shù)據(jù)。這對于插入和刪除操作頻繁的線性表、以及每個(gè)數(shù)據(jù)元素所占字節(jié)較大的問題將導(dǎo)致系統(tǒng)的運(yùn)行速度難以提高。（3）順序存儲(chǔ)結(jié)構(gòu)的線性表的存儲(chǔ)空間不便于擴(kuò)充。當(dāng)一個(gè)線性表分配順序存儲(chǔ)空間后，如果線性表的存儲(chǔ)空間已滿，但還需要插入新的元素，則會(huì)發(fā)生“上溢”錯(cuò)誤。在這種情況下，如果在原線性表的存儲(chǔ)空間后找不到與之連續(xù)的可用空間，則會(huì)導(dǎo)致運(yùn)算的失敗或中斷。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

從線性表的順序存儲(chǔ)結(jié)構(gòu)的討論中可知，對于大的線性表，特別是元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用本節(jié)要介紹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元（可以是不連續(xù)的）存儲(chǔ)線性表的數(shù)據(jù)元素。對線性表中的每一個(gè)數(shù)據(jù)元素，都需用兩部分來存儲(chǔ)：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放直接前驅(qū)或直接后繼結(jié)點(diǎn)的地址（指針），稱為指針域，我們把這種存儲(chǔ)單元稱為結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)方式下，存儲(chǔ)數(shù)據(jù)元素的結(jié)點(diǎn)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系由指針域來確定。鏈?zhǔn)酱鎯?chǔ)方式可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。2.3.1線性鏈表

1．線性鏈表線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。因此，在存儲(chǔ)線性表中的數(shù)據(jù)元素時(shí)，一方面要存儲(chǔ)數(shù)據(jù)元素的值，另一方面要存儲(chǔ)各數(shù)據(jù)元素之間的邏輯順序，為此，將每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)點(diǎn)的地址，即指向后繼結(jié)點(diǎn)，稱為指針域。此種形式的鏈表因只含有一個(gè)指針域，又稱為單向鏈表，簡稱單鏈表。圖2-7(a)所示為一個(gè)空線性鏈表。圖2-6(b)所示為一個(gè)非空線性鏈表（a0，a1，a2，…，an-1）。a0a1an-1

headhead…(a)(b)圖2-7線性鏈表的存儲(chǔ)結(jié)構(gòu)上圖中，通常在線性鏈表的第一結(jié)點(diǎn)之前附設(shè)一個(gè)稱為頭結(jié)點(diǎn)的結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存放任何數(shù)據(jù)，也可以存放鏈表的結(jié)點(diǎn)個(gè)數(shù)的信息。對空線性表，附加頭結(jié)點(diǎn)的指針域?yàn)榭眨∟ULL或0表示），用∧表示。頭指針head指向鏈表附加頭結(jié)點(diǎn)的存儲(chǔ)位置。對于鏈表的各種操作必須從頭指針開始。在C語言中，定義鏈表結(jié)點(diǎn)的形式如下：struct結(jié)構(gòu)體名

{數(shù)據(jù)成員表；

struct結(jié)構(gòu)體名*指針變量名；}例如，下面定義的結(jié)點(diǎn)類型中，數(shù)據(jù)域包含三個(gè)數(shù)據(jù)項(xiàng)：學(xué)號、姓名、成績。Structstudent{charnum[8]; /*數(shù)據(jù)域*/charname[8]; /*數(shù)據(jù)域*/intscore; /*數(shù)據(jù)域*/structstudent*next; /*指針域*/}假設(shè)h,p,q為指針變量，可用下列語句來說明：structstudent*h,*p,*q;在C語言中，用戶可以利用malloc函數(shù)向系統(tǒng)申請分配鏈表結(jié)點(diǎn)的存儲(chǔ)空間，該函數(shù)返回存儲(chǔ)區(qū)的首地址，如：p=(structstudent*)malloc(sizeof(structstudent));指針p指向一個(gè)新分配的結(jié)點(diǎn)。如果要把此結(jié)點(diǎn)歸還給系統(tǒng)，則用函數(shù)free(p)來實(shí)現(xiàn)。２．線性鏈表的基本操作下面給出的單鏈表的基本操作實(shí)現(xiàn)算法都是以圖2-7所示的帶頭結(jié)點(diǎn)的單鏈表為數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。單鏈表結(jié)點(diǎn)結(jié)構(gòu)定義為：Typedefstructslnode{Elemtypedata;structslnode*next;}slnodetype;slnodetype

*p,*q,*s;（1）初始化【算法2.3單鏈表的初始化】intInitiate(slnodetype**h){if((*h=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)returnFALSE;(*h)->next=NULL;returnTRUE;}注意：形參h定義為指針的指針類型，若定義為指針類型，將無法帶回函數(shù)中建立的頭指針值。（2）單鏈表的插入操作1）已知線性鏈表head，在p指針?biāo)赶虻慕Y(jié)點(diǎn)后插入一個(gè)元素x。在一個(gè)結(jié)點(diǎn)后插入數(shù)據(jù)元素時(shí)，操作較為簡單，不用查找便可直接插入。操作過程如圖2-8所示。headpps

head(a)插入前…a0a1aian-1

…ai+1(b)插入后圖2-8單鏈表的后插入xxsan-1

ai…a0a1…相關(guān)語句如下：【算法2.4單鏈表的后插入】{s=(slnodetype*)malloc(sizeof(slnodetype));s->data=x;s->next=p->next;p->next=s;}2）已知線性鏈表head，在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)元素x。前插時(shí)，必須從鏈表的頭結(jié)點(diǎn)開始，找到P指針?biāo)赶虻慕Y(jié)點(diǎn)的前驅(qū)。設(shè)一指針q從附加頭結(jié)點(diǎn)開始向后移動(dòng)進(jìn)行查找，直到p的前趨結(jié)點(diǎn)為止。然后在q指針?biāo)傅慕Y(jié)點(diǎn)和p指針?biāo)傅慕Y(jié)點(diǎn)之間插入結(jié)點(diǎn)s。操作過程如圖2-9所示。相關(guān)語句如下：【算法2.5單鏈表的結(jié)點(diǎn)插入】{q=head;while(q->next!=p)q=q->next;s=(slnodetype*)malloc(sizeof(slnodetype));s->data=x;s->next=p;q->next=s;}(b)插入后圖2-9單鏈表的前插入sxpa0ai-1aian-1

……qheadx0aai-1an-1

aihead……qps（a）插入前【算法2.6單鏈表的前插入】intinsert(slnodetype*h,inti,Elemtypex){/*在鏈表h中，在第i個(gè)數(shù)據(jù)元素插入一個(gè)數(shù)據(jù)元素x*/slnodetype*p,*q,*s;intj=0;p=h;while(p!=NULL&&j<i-1){p=q->next;j++; /*尋找第i-1個(gè)結(jié)點(diǎn)*/}if(j!=i-1){printf(“Error!”);returnFALSE; /*插入位置錯(cuò)誤*/}if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)returnFALSE;s->data=x;s->next=p->next;q->next=s;returnTRUE;}例：下面C程序中的功能是，首先建立一個(gè)線性鏈表head={3，5，7，9}，其元素值依次為從鍵盤輸入正整數(shù)（以輸入一個(gè)非正整數(shù)為結(jié)束）；在線性表中值為x的元素前插入一個(gè)值為y的數(shù)據(jù)元素。若值為x的結(jié)點(diǎn)不存在，則將y插在表尾。#include“stdlib.h”#include“stdio.h”structslnode{intdata;structslnode*next;} /*定義結(jié)點(diǎn)類型*/main(){intx,y,d;structslnode*head,*p,*q,*s;head=NULL; /*置鏈表空*/q=NULL;scanf(“%d”,&d);/*輸入鏈表數(shù)據(jù)元素*/while(d>0){p=(structslnode*)malloc(sizeof(structslnode));/*申請一個(gè)新結(jié)點(diǎn)*/p->data=d;p->next=NULL;if(head==NULL)head=p;/*若鏈表為空，則將頭指針指向當(dāng)前結(jié)點(diǎn)p*/elseq->next=p;/*鏈表不為空時(shí)，則將新結(jié)點(diǎn)鏈接在最后*/q=p;/*將指針q指向鏈表的最后一個(gè)結(jié)點(diǎn)*/scanf(“%d”,&d);}scanf(“%d,%d”,&x,&y);s=(structslnode*)malloc(sizeof(structslnode));s->data=y;q=head;p=q->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}/*查找元素為x的指針*/s->next=p;q->next=s;/*插入元素y*/}（3）單鏈表的刪除操作若要?jiǎng)h除線性鏈表h中的第i個(gè)結(jié)點(diǎn)，首先要找到第i個(gè)結(jié)點(diǎn)并使指針p指向其前驅(qū)第i-1個(gè)結(jié)點(diǎn)，然后刪除第i個(gè)結(jié)點(diǎn)并釋放被刪除結(jié)點(diǎn)空間。操作過程如圖2-10所示。其算法如下：【算法2.7單鏈表的刪除】intDelet(slnodetype*h,inti){/*在鏈表h中刪除第i個(gè)結(jié)點(diǎn)*/slnodetype*p,*s;intj;p=h;j=0;while(p->next!=NULL&&j<i-1){p=p->next;j=j+1;/*尋找第i-1個(gè)結(jié)點(diǎn),p指向其前驅(qū)*/}if(j!=i-1){printf(“Error!”);/*刪除位置錯(cuò)誤!*/returnFALSE;}s=p->next;p->next=p->next->next;/*刪除第i個(gè)結(jié)點(diǎn)*/free(s);/*釋放被刪除結(jié)點(diǎn)空間*/returnTRUE;}

head…

…

head……(b)刪除并釋放第i個(gè)結(jié)點(diǎn)圖2-10在線性鏈表中刪除一個(gè)結(jié)點(diǎn)的過程aiai-1ai+1an-1

p(a)尋找第i個(gè)結(jié)點(diǎn)指向其前驅(qū)ppsan-1

ai+1aiai-1(p!=NULL&&j<i-1)與(p->next!=NULL&&j<i-1)的不同。從線性鏈表的插入與刪除算法中，我們可以看到要取鏈表中某個(gè)結(jié)點(diǎn)，必須從鏈表的頭結(jié)點(diǎn)開始一個(gè)一個(gè)地向后查找，即我們不能直接存取線性鏈表中的某個(gè)結(jié)點(diǎn)，這是因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是隨機(jī)存儲(chǔ)結(jié)構(gòu)。雖然在線性鏈表中插入或刪除結(jié)點(diǎn)不需要移動(dòng)別的數(shù)據(jù)元素，但算法尋找第i-1個(gè)或第i個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。例：假設(shè)已有線性鏈表La，編制算法將該鏈表逆置。利用頭結(jié)點(diǎn)和第一個(gè)存放數(shù)據(jù)元素的結(jié)點(diǎn)之間不斷插入后繼元素結(jié)點(diǎn)。如圖2-11所示。

請讀者比較插入算法與刪除算法中所用的條件算法如下：voidconverse(slnodetype*head){slnodetype*p,*q;p=head->next;head->next=NULL;while(p!=NULL){q=p->next;p->next=head->next;head->next=p;p=q;}a0a1an-1

a3…pqa0a1an-1

a3…pqa1a0an-1

a3…pqa0a1an-1

a3…

head

head

headhead圖2-11單鏈表逆置2.3.2循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。圖2-12（a）為帶頭結(jié)點(diǎn)的循環(huán)單鏈表的空表形式，圖2-12（b）為帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式。帶頭結(jié)點(diǎn)的循環(huán)鏈表的操作實(shí)現(xiàn)算法和帶頭結(jié)點(diǎn)的單鏈表的操作實(shí)現(xiàn)算法類同，差別在于算法中的條件在單鏈表中為p!=null或p->next!=null；而在循環(huán)鏈表中應(yīng)改為p!=head或p->next!=head。在循環(huán)鏈表中，除了頭指針head外，有時(shí)還加了一個(gè)尾指針rear，尾指針read指向最后一結(jié)點(diǎn)，從最后一個(gè)結(jié)點(diǎn)的指針又可立即找到鏈表的第一個(gè)結(jié)點(diǎn)。在實(shí)際應(yīng)用中，使用尾指針代替頭指針來進(jìn)行某些操作，往往更簡單。

head(a)循環(huán)鏈表的空表形式

head…

…

(b)循環(huán)鏈表的一般形式圖2-12循環(huán)鏈表a0a1an-1

ai例：將兩個(gè)循環(huán)鏈表首尾相接。La為第一個(gè)循環(huán)鏈表表尾指針，Lb為第二個(gè)循環(huán)鏈表表尾指針。合并后Lb為新鏈表的尾指針。Voidmerge(slnodetype*La,slnodetype*Lb){slnodetype*p;p=La->next;Lb->next=La->next;La->next=p->next;free(p);}(a)a0a1an-1

b0b1bn-1

a0a1an-1

a0a1an-1

LaLbLb(b)圖2-13循環(huán)鏈表的合并…………

如圖2-13所示，在這個(gè)算法中，時(shí)間復(fù)雜度為O(1)。2.3.3雙向鏈表

1．雙向鏈表在單鏈表的每個(gè)結(jié)點(diǎn)中只有一個(gè)指示后繼的指針域，因此從任何一個(gè)結(jié)點(diǎn)都能通過指針域找到它的后繼結(jié)點(diǎn)；若需找出該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則此時(shí)需從表頭出發(fā)重新查找。換句話說，在單鏈表中，查找某結(jié)點(diǎn)的后繼結(jié)點(diǎn)的執(zhí)行時(shí)間為O(1)，而查找其前驅(qū)結(jié)點(diǎn)的執(zhí)行時(shí)間為O(n)。我們可用雙向鏈表來克服單鏈表的這種缺點(diǎn)，在雙向鏈表中，每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域，一個(gè)指針（next）指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（prior）指向它的前驅(qū)結(jié)點(diǎn)。雙向鏈表的結(jié)構(gòu)可定義如下：typedefstructnode{Elemtypedata;structnode*prior,*next;}dlnodetype;priornexthead(a)空雙向鏈表a0a1……an-1head(b)非空的雙向鏈表圖2-14雙向鏈表

和單鏈的循環(huán)表類似，雙向鏈表也可以有循環(huán)表，讓頭結(jié)點(diǎn)的前驅(qū)指針指向鏈表的最后的一個(gè)結(jié)點(diǎn)，讓最后一個(gè)結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn)。圖2-14為雙向鏈表示意圖，其中圖(b)是一個(gè)循環(huán)雙向鏈表。若p為指向雙向鏈表中的某一個(gè)結(jié)點(diǎn)ai的指針，則顯然有：p->next->prior==p->prior->next==p在雙向鏈表中，有些操作如：求長度、取元素、定位等，因僅需涉及一個(gè)方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時(shí)，則需同時(shí)修改兩個(gè)方向上的指針，兩者的操作的時(shí)間復(fù)雜度均為O(n)。2．雙向鏈表的基本操作（1）在雙向鏈表中插入一個(gè)結(jié)點(diǎn)在雙向鏈表的第i個(gè)元素前插入一個(gè)結(jié)點(diǎn)時(shí)，可用指針p指該結(jié)點(diǎn)（稱p結(jié)點(diǎn)），先將新結(jié)點(diǎn)的prior指向p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，其次將p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)，然后將新結(jié)點(diǎn)的next指向p結(jié)點(diǎn)，最后將p結(jié)點(diǎn)的prior指向新結(jié)點(diǎn)。操作過程如圖2-15所示。(a)插入前（b）插入后圖2-15在雙向鏈表中插入結(jié)點(diǎn)ai-1ais∧x∧pai-1aip①②③④sx其算法如下：【算法2.8雙向鏈表的插入】intinsert_dul(dlnodetype*head,inti,Elemtypex){/*在帶頭結(jié)點(diǎn)的雙向鏈表中第i個(gè)位置之前插入元素x*/dbnodetype*p,*s;intj;p=head;j=0;while(p!=NULL&&j<i){p=p->next;j++;}if(j!=i||i<1){printf(“Error!”);returnFALSE;}if((s=(dlnodetype*)malloc(sizeof(dlnodetype)))==NULL)returnFALSE;s->data=x;s->prior=p->prior;/*圖中步驟①*/p->prior->next=s;/*圖中步驟②*/s->next=p;/*圖中步驟③*/p->prior=s;/*圖中步驟④*/returnTRUE;}討論：我們在雙向鏈表中進(jìn)行插入操作時(shí)，還需注意下面兩種情況：1）當(dāng)在鏈表中的第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)的prior應(yīng)為空，原鏈表第一個(gè)結(jié)點(diǎn)的prior應(yīng)指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的next應(yīng)指向原鏈表的第一個(gè)結(jié)點(diǎn)。2）當(dāng)在鏈表的最后一個(gè)結(jié)點(diǎn)后插入新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)的next應(yīng)為空，原鏈表的最后一個(gè)結(jié)點(diǎn)的next應(yīng)指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的prior應(yīng)指向原鏈表的最后一個(gè)結(jié)點(diǎn)。（2）在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)，可用指針p指向該結(jié)點(diǎn)（稱p結(jié)點(diǎn)），然后將p結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next指向p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，再將p的下一個(gè)結(jié)點(diǎn)的prior指向p的上一個(gè)結(jié)點(diǎn)。如圖2-16所示，圖2-16在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)①②ai-1aiai+1p【算法2.9雙向鏈表的刪除】intDelete_dl(dlnodetype*head,inti){dlnodetype*p,*s;intj;p=head;j=0;while(p!=NULL&&j<i){p=p->next;j++;}if(j!=i||i<1){printf(“Error!”);returnFALSE;}s=p;p->prior->next=p->next;/*圖中步驟①*/p->next->prior=p->prior;/*圖中步驟②*/free(s);returnTRUE;}討論：我們在雙向鏈表中進(jìn)行刪除操作時(shí)，還需注意下面兩種情況：1）當(dāng)刪除鏈表的第一個(gè)結(jié)點(diǎn)時(shí)，應(yīng)將鏈表開始結(jié)點(diǎn)的指針指向鏈表的第二個(gè)結(jié)點(diǎn)，同時(shí)將鏈表的第二個(gè)結(jié)點(diǎn)的prior置為NULL。2）當(dāng)刪除鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，只需將鏈表的最后一個(gè)結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的next置為NULL即可。上面我們詳細(xì)講解了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：（1）每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間。當(dāng)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域所占字節(jié)不多時(shí)，指針域所占存儲(chǔ)空間的比重就顯得很大。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。對任一結(jié)點(diǎn)的操作都要從頭指針依指針鏈查找到該結(jié)點(diǎn)，這增加了算法的復(fù)雜度。2.4一元多項(xiàng)式的表示及相加

符號多項(xiàng)式的表示及其操作是線性表處理的典型用例，在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可以表示為：Pn(x)=a0+a1x+a2x2+…+anxn(最多有n+1項(xiàng))aixi是多項(xiàng)式的第i項(xiàng)（0≤i≤n），其中ai為系數(shù)，x為變量，i為指數(shù)。它有n+1個(gè)系數(shù)，因此，在計(jì)算機(jī)里，它可用一個(gè)線性表P來表示：P=（a0,a1,a2,…，an）假設(shè)Qn(x)是一元m次多項(xiàng)式，同樣可用線性表Q來示：Q=（b0,b1,b2,…，bm）若m<n，則兩個(gè)多項(xiàng)式相加的結(jié)果Rn(x)=Pn(x)+Qn(x)可用線性表R來表示：R=（a0+b0,a1+b1,a2+b2,…,am+bm,am+1,…,an）我們可以對P、Q和R采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈表存儲(chǔ)結(jié)構(gòu)。使用順序存儲(chǔ)結(jié)構(gòu)可以使多項(xiàng)式相加的算法十分簡單。但是，當(dāng)多項(xiàng)式中存在大量的零系數(shù)時(shí)，這種表示方式就會(huì)浪費(fèi)在量存儲(chǔ)空間。為了有效而合理地利用存儲(chǔ)空間，可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示多項(xiàng)式。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示多項(xiàng)式時(shí)，多項(xiàng)式中每一個(gè)非零系數(shù)的項(xiàng)構(gòu)成鏈表中的一個(gè)結(jié)點(diǎn)，而對于系數(shù)為零的項(xiàng)則不需表示。一般情況下，一元多項(xiàng)式(只表示非零系數(shù)項(xiàng))可寫成：其中ak≠0（k=1,2,…m），em＞em-1＞…＞e0≥0則采用鏈表表示多項(xiàng)式時(shí)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域有兩項(xiàng)：ak表示系數(shù)，em表示指數(shù)。（注意：表示多項(xiàng)式的鏈表應(yīng)該是有序鏈表）

假設(shè)多項(xiàng)式A17(x)=8+3x+9x10+5x17與B10(x)=8x+14x7-9x10已經(jīng)用單鏈表表示，其頭指針分別為Ah與Bh，如圖2-17所示。多項(xiàng)式鏈表中的每一個(gè)非零項(xiàng)結(jié)點(diǎn)結(jié)構(gòu)用C語言描述如下：structpoly{intexp;/*指數(shù)為正整數(shù)*/doublecoef;/*系數(shù)為雙精度型*/structpoly*next;/*指針域*/}將兩個(gè)多項(xiàng)式相加為C17(x)=8+11x+14x7+5x17，其運(yùn)算規(guī)則如下：假設(shè)指針qa和qb分別指向多項(xiàng)式A17(x)和多項(xiàng)式B8(x)中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn)，則比較兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的指數(shù)項(xiàng)，有三種情況：（1）指針qa所指結(jié)點(diǎn)的指數(shù)值＜指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，則保留qa指針?biāo)赶虻慕Y(jié)點(diǎn)，qa指針后移；（2）指針qa所指結(jié)點(diǎn)的指數(shù)值＞指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，則將qb指針?biāo)赶虻慕Y(jié)點(diǎn)插入到qa所指結(jié)點(diǎn)前，qb指針后移；（3）指針qa所指結(jié)點(diǎn)的指數(shù)值＝指針qb所指結(jié)點(diǎn)的指數(shù)值時(shí)，將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加,若和不為零，則修改qa所指結(jié)點(diǎn)的系數(shù)值，同時(shí)釋放qb所指結(jié)點(diǎn)；反之，從多項(xiàng)式A17(x)的鏈表中刪除相應(yīng)結(jié)點(diǎn)，并釋放指針qa和qb所指結(jié)點(diǎn)。Ah-181147-910∧Bh圖2-17多項(xiàng)式表的單鏈存儲(chǔ)結(jié)構(gòu)【算法2.10多項(xiàng)式相加】structpoly*add_poly(structpoly*Ah,structpoly*Bh){structpoly*qa,*qb,*s,*r,*Ch;qa=Ah->next;qb=Bh->next; /*qa和qb分別指向兩個(gè)鏈表的第一結(jié)點(diǎn)*/r=qa;Ch=Ah; /*將鏈表Ah作為相加后的和鏈表*/while(qa!=NULL&&qb!=NULL) /*兩鏈表均非空*/{if(qa->exp==qb->exp) /*兩者指數(shù)值相等*/{x=qa->coef+qb->coef;if(x!=0){qa->coef=x;r->next=qa;r=qa;s=qb++;free(s);qa++;} /*相加后系數(shù)不為零時(shí)*/else{s=qa++;free(s);s=qb++;free(s);} /*相加后系數(shù)為零時(shí)*/}elseif(qa->exp<qb->exp){r->next=qa;r=qa;qa++;} /*多項(xiàng)式Ah的指數(shù)值小*/else{r->next=qb;r=qb;qb++;} /*多項(xiàng)式Bh的指數(shù)值小*}if(qa==NULL)r->next=qb;elser->next=qa; /*鏈接多項(xiàng)式Ah或Bh中的剩余結(jié)點(diǎn)*/return(Ch);}本章小結(jié)

本章主要介紹了如下一些基本概念：線性表：一個(gè)線性表是n≥0個(gè)數(shù)據(jù)元素a0，a1，a2，…，an-1的有限序列。線性表的順序存儲(chǔ)結(jié)構(gòu)：在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元——結(jié)點(diǎn)（可以是不連續(xù)的）存儲(chǔ)線性表的數(shù)據(jù)元素。表中每一個(gè)數(shù)據(jù)元素，都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅(qū)或直接后繼結(jié)點(diǎn)的地址（指針）的指針域組成。循環(huán)鏈表：循環(huán)鏈表(CircularLinkedList)是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。循環(huán)鏈表：循環(huán)鏈表(CircularLinkedList)是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。雙向鏈表：雙向鏈表中，在每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域，一個(gè)指針（next）指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（prior）指向它的前驅(qū)結(jié)點(diǎn)。除上述基本概念以外，學(xué)生還應(yīng)該了解：線性表的基本操作（初始化、插入、刪除、存取、復(fù)制、合并）、順序存儲(chǔ)結(jié)構(gòu)的表示、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示、一元多項(xiàng)式Pn(x)，掌握順序存儲(chǔ)結(jié)構(gòu)（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）。習(xí)題二

1．什么是順序存儲(chǔ)結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？2．線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有什么特點(diǎn)？3．設(shè)線性表中數(shù)據(jù)元素的總數(shù)基本不變，并很少進(jìn)行