電子教案·《數(shù)據(jù)結(jié)構(gòu)——C語言描述(第二版)》課件

1、普通高等教育“十一五”國家級規(guī)劃教材21世紀(jì)高職高專新概念教材 數(shù)據(jù)結(jié)構(gòu)C語言描述(第二版) 前 言 二十一世紀(jì)是科學(xué)技術(shù)高速發(fā)展的信息時代，而計算機是處理信息的主要工具，因此，人們已經(jīng)認(rèn)識到，計算機知識已成為人類當(dāng)代文化的一個重要組成部分。 計算機科學(xué)技術(shù)以驚人的速度向前發(fā)展，它的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計算領(lǐng)域發(fā)展到各種非數(shù)值計算領(lǐng)域。在非數(shù)值計算領(lǐng)域里，數(shù)據(jù)處理的對象已從簡單的數(shù)值發(fā)展到一般的符號，進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù)。在這里，面臨的主要問題是：針對每一種新的應(yīng)用領(lǐng)域的處理對象，如何選擇合適的數(shù)據(jù)表示（構(gòu)構(gòu)），如何有效地組織計算機存貯，并在此基礎(chǔ)上又如何有效地實現(xiàn)對象之間的“運算”

2、關(guān)系。傳統(tǒng)的解決數(shù)值計算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計算問題的需要，必須進(jìn)行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論。因此，“數(shù)據(jù)結(jié)構(gòu)”課程已成為計算機類專業(yè)的一門重要專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的中級課程，主要培養(yǎng)學(xué)生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴學(xué)生如何編寫效率高、結(jié)構(gòu)好的程序。本書作為計算機大專系列教材之一，在內(nèi)容的選取、概念的引入、文字的敘述以及例題和習(xí)題的選擇等方面，都力求遵循面向應(yīng)用、邏輯結(jié)構(gòu)簡明合理、由淺入深、深入淺出、循序漸進(jìn)、便于自學(xué)的原則，突出其實用性與應(yīng)用性。全書共分十章。書中，安排了相當(dāng)?shù)钠鶃斫榻B這些基本數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用。 教學(xué)要求1了

3、解：數(shù)據(jù)結(jié)構(gòu)這門學(xué)科發(fā)展歷史以及在計算機科學(xué)中所處的地位。2掌握：與數(shù)據(jù)結(jié)構(gòu)有關(guān)的概念和術(shù)語。3掌握：如何評價一個算法的好壞。 第一章 緒論主要內(nèi)容1.1 引言1.2 數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計算機科學(xué)中所處的地位1.3 什么是數(shù)據(jù)結(jié)構(gòu) 1.4 基本概念和術(shù)語1.5 算法和算法的描述1.1 引言 眾所周知，二十世紀(jì)四十年代，電子數(shù)字計算機問世的直接原因是解決彈道學(xué)的計算問題。早期，電子計算機的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計算，其處理的對象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計算。近三十年來，電子計算機的發(fā)展異常迅猛，這不僅表現(xiàn)在計算機本身運算速度不斷提高、信息存儲量日益擴(kuò)大、價

4、格逐步下降，更重要的是計算機廣泛地應(yīng)用于情報檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計算的范圍，而滲透到人類社會活動的一切領(lǐng)域。與此相應(yīng)，計算機的處理對象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。 因此，再把電子數(shù)字計算機簡單地看作是進(jìn)行數(shù)值計算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計算機科學(xué)的觀點，是把計算機程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而電子計算機則是加工處理數(shù)據(jù)（信息）的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對象又多為非數(shù)值

5、性數(shù)據(jù)。因此，單憑程序設(shè)計人員的經(jīng)驗和技巧已難以設(shè)計出效率高、可靠性強的程序。于是，就要求人們對計算機程序加工的對象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系數(shù)據(jù)結(jié)構(gòu)（Date Structure）。1.2 數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計算機科學(xué)中所處的地位發(fā)展史：1、 “數(shù)據(jù)結(jié)構(gòu)”作為一門獨立的課程在國外是從1968年才開始設(shè)立的。 2、 1968年美國唐歐克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機程序設(shè)計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。地位：1、“數(shù)據(jù)結(jié)構(gòu)”在計算機科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。2、數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬

6、件和計算機軟件三者之間的一門核心課程。3、數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計（特別是非數(shù)值性程序設(shè)計）的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1.3 什么是數(shù)據(jù)結(jié)構(gòu)計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計算機算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法

7、的選擇和效率。運算是由計算機來完成，這就要設(shè)計相應(yīng)的插入、刪除和修改的算法 。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計中計算機操作的對象以及它們之間的關(guān)系和運算的一門學(xué)科。1.4 基本概念和術(shù)語 1數(shù)據(jù) 數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述。在計算機科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個個人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。 表 1-1 個人書庫2結(jié)點結(jié)點也叫數(shù)據(jù)元素，它是組成數(shù)

8、據(jù)的基本單位。在程序中通常把結(jié)點作為一個整體進(jìn)行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數(shù)據(jù)由10個結(jié)點構(gòu)成。一般情況下，一個結(jié)點中含有若干個字段（也叫數(shù)據(jù)項）。例如，在表1-1所示的表格數(shù)據(jù)中，每個結(jié)點都有登錄號、書號、書名、作者、出版社和價格等六個字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。3邏輯結(jié)構(gòu)結(jié)點和結(jié)點之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點之間在邏輯上有一種線性關(guān)系，它指出了10個結(jié)點在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4存儲結(jié)構(gòu)數(shù)

9、據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計算機中可以有多種存儲表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。5數(shù)據(jù)處理數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。在早期，計算機主要用于科學(xué)和工程計算，進(jìn)入八十年代以后，計算機主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計資料表明，現(xiàn)在計算機用于數(shù)據(jù)處理的時間比例達(dá)到80%以上，隨著時間的推移和計算機應(yīng)用的進(jìn)一步普及，計算機用于數(shù)據(jù)處理的時間比例必將進(jìn)一步增大。6數(shù)據(jù)結(jié)構(gòu)（Data Structure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（Data Element）之間抽象化的相

10、互關(guān)系和這種關(guān)系在計算機中的存儲表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，而且確保經(jīng)過這些運算后所得到的新結(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)稱為存儲結(jié)構(gòu)（Storage Structure）。7數(shù)據(jù)類型數(shù)據(jù)類型是指程序設(shè)計語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進(jìn)行的運算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)

11、計中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。 8算法 簡單地說就是解決特定問題的方法（關(guān)于算法的嚴(yán)格定義，在此不作討論）。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。一般說來，在數(shù)值算法中主要進(jìn)行算術(shù)運算

12、，而在非數(shù)值算法中主要進(jìn)行比較和邏輯運算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。1.5 算法和算法的描述1.5.1 算法算法是執(zhí)行特定計算的有窮過程。這個過程有5個特點： 1.動態(tài)有窮：當(dāng)執(zhí)行一個算法時，不論是何種情況，在經(jīng)過了 有限步驟后，這個算法一定要終止。 2.確定性：算法中的每條指令都必須是清楚的，指令無二義性。 3.輸入：具有0個或0個以上由外界提供的量。 4.輸出：產(chǎn)生1個或多個結(jié)果。 5.可行性：每條指令都充分基本，原則上可由人僅用筆和紙在 有限的時間

13、內(nèi)也能完成。 注意：算法和程序是有區(qū)別的，即程序未必能滿足動態(tài)有窮。在本 書中，我們只討論滿足動態(tài)有窮的程序，因此“算法”和“程序” 是通用的。一個算法可以用自然語言、數(shù)字語言或約定的符號來描述，也可以用計算機高級程序語言來描述，如Pascal語言、C語言或偽代碼等。本書選用C語言作為描述算法的工具?，F(xiàn)簡單說明C語言的語法結(jié)構(gòu)如下：1.5.2 算法的描述 1預(yù)定義常量和類型： # define TRUE 1； # define FALSE -1； # define ERROR NULL；2函數(shù)的形式 數(shù)據(jù)類型 函數(shù)名 （形式參數(shù)） 形式參數(shù)說明； 內(nèi)部數(shù)據(jù)說明； 執(zhí)行語句組； /*函數(shù)名*/

14、函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號“”和“”括起來。函數(shù)中用方括號括起來的部分為可選項，函數(shù)名之間的圓括號不可省略。函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外。執(zhí)行語句可由各種類型的語句所組成，兩個語句之間用“；”號分隔?？蓪⒑瘮?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.

15、數(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； 注意：switch case語句是先計算表達(dá)式的值，然后用其值與判斷值相比較，若它們相一致時，就執(zhí)行相應(yīng)的ca

16、se下的語句組；若不一致，則執(zhí)行default下的語句組；其中的方括號代表可選項。5循環(huán)語句 for語句 for（表達(dá)式1；表達(dá)式2；表達(dá)式3）循環(huán)體語句；首先計算表達(dá)式1的值，然后求表達(dá)式2的值，若結(jié)果非零則執(zhí)行循環(huán)體語句，最后對表達(dá)式3運算，如此循環(huán)，直到表達(dá)式2的值為零時止。 while語句 while （條件表達(dá)式） 循環(huán)體語句； while循環(huán)首先計算條件表達(dá)式的值，若條件表達(dá)式的值非零，則執(zhí)行循環(huán)體語句，然后再次計算條件表達(dá)式，重復(fù)執(zhí)行，直到條件表達(dá)式的值為假時退出循環(huán)，執(zhí)行該循環(huán)之后的語句。 do-while語句 do 循環(huán)體語句 while（條件表達(dá)式）該循環(huán)語句首先執(zhí)行循環(huán)體

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

18、 max函數(shù)，用于求一個或幾個表達(dá)式中的最大值； min函數(shù)，用于求一個或幾個表達(dá)式中的最小值； abs函數(shù)，用于求表達(dá)式的絕對值； eof函數(shù)，用于判定文件是否結(jié)束； eoln函數(shù)，用于判斷文本行是否結(jié)束。例 計算f=1！+2！+3！+n！，用C語言描述。void factorsum（n） int n；int i，j；int f，w； f=0； for （i=1，i=n；i+） w=1； for （j=1，j=i；j+） w=w*j； f=f+w； return；上述算法所用到的運算有乘法、加法、賦值和比較，其基本運算為乘法操作。在上述算法的執(zhí)行過程中，對外循環(huán)變量i的每次取值，內(nèi)循環(huán)變量j

19、循環(huán)i次。因為內(nèi)循環(huán)每執(zhí)行一次，內(nèi)循環(huán)體語句w=w*j只作一次乘法操作，即當(dāng)內(nèi)循環(huán)變量j循環(huán)i次時，內(nèi)循環(huán)體的語句w=w*j作i次乘法。所以，整個算法所作的乘法操作總數(shù)是：f（n）=1+2+3+n=n（n-1）/2。1.5.3 算法評價 設(shè)計一個好的算法應(yīng)考慮以下幾個方面： 1正確性 “正確”的含義在通常的用法中有很大的差別，大體可分為以下四個層次：程序不含語法錯誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。 2運行時間運行時間是指一個算法在計算機

20、上運算所花費的時間。它大致等于計算機執(zhí)行一種簡單操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等）所需要的時間與算法中進(jìn)行簡單操作次數(shù)的乘積。通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復(fù)雜性，它是一個算法運行時間的相對量度。3占用的存儲空間一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲空間 和算法運行過程中臨時占用的存儲空間。分析一個算法所占用的存儲空間要從各方面綜合考慮。算法在運行過程中所占用的存儲空間的大小被定義為算法的空間復(fù)雜性。它包括局部變量所占用的存儲空間和系統(tǒng)為了實現(xiàn)遞歸所使用的堆棧這兩個部分。算法的空間復(fù)雜性一般以數(shù)量級

21、的形式給出。4簡單性最簡單和最直接的算法往往不是最有效的，但算法的簡單性使得證明其正確性比較容易，同時便于編寫、修改、閱讀和調(diào)試，所以還是應(yīng)當(dāng)強調(diào)和不容忽視的。不過對于那些需要經(jīng)常使用的算法來說，高效率（即盡量減少運行時間和壓縮存儲空間）比簡單性更為重要。本章小結(jié)本章主要介紹了如下一些基本概念：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計算機中的存儲表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。數(shù)據(jù)：數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動

22、所做的描述。在計算機科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。結(jié)點：結(jié)點也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。邏輯結(jié)構(gòu)：結(jié)點和結(jié)點之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)：數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)處理：數(shù)據(jù)處理是指對數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。數(shù)據(jù)類型：數(shù)據(jù)類型是指程序設(shè)計語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。 習(xí) 題 一1簡述下列術(shù)語：數(shù)據(jù)、結(jié)點、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)

23、類型。2試根據(jù)以下信息：校友姓名、性別、出生年月、畢業(yè)時間、所學(xué)專業(yè)、現(xiàn)在工作單位、職稱、職務(wù)、電話等，為校友錄構(gòu)造一種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)（作圖示意），并定義必要的運算和用文字?jǐn)⑹鱿鄳?yīng)的算法思想。3什么是算法？算法的主要特點是什么？4如何評價一個算法？教學(xué)要求1了解：線性表的定義和基本運算。2掌握：線性表的兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述方式，以及這兩種存儲結(jié)構(gòu)上的基本運算的實現(xiàn)算法。3了解：線性表處理一元多項式的操作方法及其算法的實現(xiàn)。4掌握：線性表的兩種存儲結(jié)構(gòu)的特點及其具體實現(xiàn)。第二章 線性表主要內(nèi)容2.1 線性表的邏輯結(jié)構(gòu)2.2 線性表的順序存儲結(jié)構(gòu) 2.3 線性表的鏈?zhǔn)酱鎯?/p>

24、結(jié)構(gòu)2.4 一元多項式的表示及相加 2.5實訓(xùn) 2.1 線性表的邏輯結(jié)構(gòu)線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素的含義廣泛，在不同的具體情況下，可以有不同的含義。例如：英文字母表（A，B，C，Z）是一個長度為26的線性表，其中的每一個字母就是一個數(shù)據(jù)元素；再如，某公司2000年每月產(chǎn)值表（400，420，500，600，650）(單位：萬元)是一個長度為12的線性表，其中的每一個數(shù)值就是一個數(shù)據(jù)元素。上述兩例中的每一個數(shù)據(jù)元素都是不可分割的，在一些復(fù)雜的線性表中，每一個數(shù)據(jù)元素又可以由若干個數(shù)據(jù)項組成，在這種情況下，通常將數(shù)據(jù)元素稱為記錄（record），例如，圖2-1的某單位職工工資

25、表就是一個線性表，表中每一個職工的工資就是一個記錄，每個記錄包含八個數(shù)據(jù)項：職工號、姓名、基本工資。職工號姓名基本工資崗位工資獎金應(yīng)發(fā)工資扣款實發(fā)工資1201張強54030020010402010201301周敏500200200900208801202徐黎芬55030020010503010201105黃承振53025020098020960圖2-1 職工工資表 矩陣也是一個線性表，但它是一個比較復(fù)雜的線性表。在矩陣中，我們可以把每行看成是一個數(shù)據(jù)元素，也可以把每列看成是一個數(shù)據(jù)元素，而其中的每一個數(shù)據(jù)元素又是一個線性表。綜上所述，一個線性表是n0個數(shù)據(jù)元素a0，a1，a2，an-1的有限序

26、列。如果n0，則除a0和an-1外，有且僅有一個直接前趨和一個直接后繼數(shù)據(jù)元素，ai（0in-1）為線性表的第i個數(shù)據(jù)元素，它在數(shù)據(jù)元素ai-1之后，在ai+1之前。a0為線性表的第一個數(shù)據(jù)元素，而an-1是線性表的最后一個數(shù)據(jù)元素；若n=0，則為一個空表，表示無數(shù)據(jù)元素。因此，線性表或者是一個空表（n=0），或者可以寫成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。抽象數(shù)據(jù)類型線性表的定義如下：LinearList=(D,R)其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1 R=| ai-1，aiD, i=0,1,2, ，n-1 Elemset為某一數(shù)

27、據(jù)對象集；n為線性表的長度。線性表的主要操作有如下幾種：1 Initiate(L) 初始化：構(gòu)造一個空的線性表L。2 Insert(L,i,x) 插入：在給定的線性表L中，在第i個元素之前插入數(shù)據(jù)元素x。線性表L長度加1。3 Delete(L,i) 刪除：在給定的線性表L中，刪除第i個元素。線性表L的長度減1。4 Locate(L,x) 查找定位：對給定的值x，若線性表L中存在一個元素ai與之相等，則返回該元素在線性表中的位置的序號i，否則返回Null（空）。5 Length(L) 求長度：對給定的線性表L，返回線性表L的數(shù)據(jù)元素的個數(shù)。6 Get(L,i) 存?。簩o定的線性表L，返回第i（

28、0iLength(L)-1）個數(shù)據(jù)元素，否則返回Null。7 Traverse(L) 遍歷：對給定的線性表L，依次輸出L的每一個數(shù)據(jù)元素。8 Copy(L,C) 復(fù)制：將給定的線性表L復(fù)制到線性表C中。9 Merge(A,B,C) 合并：將給定的線性表A和B合并為線性表C。上面我們定義了線性表的邏輯結(jié)構(gòu)和基本操作。在計算機內(nèi)，線性表有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。下面我們分別討論這兩種存儲結(jié)構(gòu)以及對應(yīng)存儲結(jié)構(gòu)下實現(xiàn)各操作的算法。2.2 線性表的順序存儲結(jié)構(gòu)在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)。2.2.1 線性表的順序存儲結(jié)構(gòu)

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

30、。 1一維數(shù)組若定義數(shù)組An= a0，a1，a2，an-1，假設(shè)每一個數(shù)組元素占用d個字節(jié)，則數(shù)組元素A0，A1，A2，An-1的地址分別為Loc(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。其結(jié)構(gòu)如圖2-2所示。 若定義數(shù)組Anm，表示此數(shù)組有n行m列，如下圖2-3所示。 0 1 2 j m-10 a00 a01 a02 a0j a0 m-1a10 a11 a12 a1j a1 m-1a20 a21 a22 a2j a2 m-1i ai0 ai1 ai2 aij ai m-1 n-1 an-1 ,0 an-1,1 an-1,2 an-1,j an-1,m

31、-1圖2-3 二維數(shù)組二維數(shù)組在C語言中，二維數(shù)組的保存是按照行方式存儲的，先將第一行元素排好，接著排第二行元素，直至所有行的元素排完。如圖2-4所示。圖2-4 二維數(shù)組存儲示意圖 2.2.2 線性表在順序存儲結(jié)構(gòu)下的運算可用C語言描述順序存儲結(jié)構(gòu)下的線性表（順序表）如下：#define TRUE 1 #define FALSE 0#define MAXNUM Elemtype ListMAXNUM ; /*定義順序表List*/int num=-1; /*定義當(dāng)前數(shù)據(jù)元素下標(biāo)，并初始化*/我們還可將數(shù)組和表長封裝在一個結(jié)構(gòu)體中：struct Linear_list Elemtype List

32、MAXNUM; /*定義數(shù)組域*/ int length; /*定義表長域*/1. 順序表的插入操作 序號 元素 序號 元素在長度為num(0numMAXNUM-2)的順序表List的第i(0inum+1)個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素x時，需將最后一個即第num個至第i個元素（共num-i+1個元素）依次向后移動一個位置，空出第i個位置，然后把x插入到第i個存儲位置，插入結(jié)束后順序表的長度增加1，返回TRUE值；若i0或inum+1，則無法插入，返回FALSE。如圖2-5所示。在長度為num(0numMAXNUM-2)的順序表List的第i(0inum+1)個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)

33、元素x時，需將最后一個即第num個至第i個元素（共num-i+1個元素）依次向后移動一個位置，空出第i個位置，然后把x插入到第i個存儲位置，插入結(jié)束后順序表的長度增加1，返回TRUE值；若i0或inum+1，則無法插入，返回FALSE。如圖2-5所示。 序號 元素 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 序號 元素 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum插入x圖2-5 在數(shù)組中插入元素其算法如下：【算法2.1 順序表的插入】int Insert(Elemtype

34、 List,int *num,int i,Elemtype x)/*在順序表List中，*num為表尾元素下標(biāo)位置，在第i個元素前插入數(shù)據(jù)元素x，若成功，返回TRUE，否則返回FALSE。*/ int j; if (i*num+1) printf(“Error!”); /*插入位置出錯*/ return FALSE; if (*num=MAXNUM-1) printf(“overflow!”); return FALSE; /*表已滿*/for (j=*num;j=i;j-)Listj+1=Listj; /*數(shù)據(jù)元素后移*/Listi=x; /*插入x*/(*num)+; /*長度加1*/re

35、turn TRUE;注：順序表List的最大數(shù)據(jù)元素個數(shù)為MAXNUM，num標(biāo)識為順序表的當(dāng)前表尾（numMAXNUM-1）。順序表的刪除操作 序號 元素 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum圖2-6 在數(shù)組中刪除元素在長度為num(0numMAXNUM-1)的順序表List，刪除第i(0inum)個數(shù)據(jù)元素，需將第i至第num個數(shù)據(jù)元素的存儲位置（num-i+1）依次前移，并使順序表的長度減1，返回TRUE值，若i0或inum，則無法刪除，返

36、回FALSE值，如圖2-6所示。其算法如下：【算法2.2 順序表的刪除】int Delete(Elemtype List,int *num,int i)/*在線性表List中，*num為表尾元素下標(biāo)位置，刪除第i個元素，線性表的元素減1，若成功，則返回TRUE；否則返回FALSE。*/int j;if(i*num) printf(“Error!”); return FALSE; /*刪除位置出錯！*/ for(j=i+1;j=*num;j+) Listj-1=Listj; /*數(shù)據(jù)元素前移*/ (*num)-; /*長度減1*/return TRUE; 從上述兩個算法來看，很顯然，在線性表的順

37、序存儲結(jié)構(gòu)中插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動數(shù)據(jù)元素上。而移動元素的次數(shù)取決于插入或刪除元素的位置。假設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的平均次數(shù)為假設(shè)qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素時所需移動元素次數(shù)的平均次數(shù)為如果在線性表的任何位置插入或刪除元素的概率相等，即 則 可見，在順序存儲結(jié)構(gòu)的線性表中插入或刪除一個元素時，平均要移動表中大約一半的數(shù)據(jù)元素。若表長為n，則插入和刪除算法的時間復(fù)雜度都為O(n)。在順序存儲結(jié)構(gòu)的線性表中其他的操作也可直接實現(xiàn)，在此不再講述。例：將有序線性表La=

38、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中的元素逐個插入到Lc中即可。設(shè)兩個指針i和j分別指向La和Lb中的某個元素，若設(shè)i當(dāng)前所指的元素為a，j當(dāng)前所指的元素為b，則當(dāng)前應(yīng)插入到Lc中的元素c為c=當(dāng)時當(dāng)時 ，很顯然，指針i和j的初值均為1，在所指元素插入Lc后，i，j在La或Lb中順序后移。算法如下：void merge(Elemtype La,Elemtype Lb,Elemtype *Lc) int i,j,k; int La_

39、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(ab) 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 (jn

40、ext=NULL; return TRUE; 注意：形參h定義為指針的指針類型，若定義為指針類型，將無法帶回函數(shù)中建立的頭指針值。（2）單鏈表的插入操作1）已知線性鏈表head，在p指針?biāo)赶虻慕Y(jié)點后插入一個元素x。在一個結(jié)點后插入數(shù)據(jù)元素時，操作較為簡單，不用查找便可直接插入。操作過程如圖2-8所示。 headpps head(a) 插入前a0a1aian-1ai+1(b) 插入后圖2-8 單鏈表的后插入xxsan-1aia0a1相關(guān)語句如下：【算法2.4 單鏈表的后插入】 s=(slnodetype*)malloc(sizeof(slnodetype); s-data=x; s-next=

41、p-next;p-next=s;2）已知線性鏈表head，在p指針?biāo)赶虻慕Y(jié)點前插入一個元素x。前插時，必須從鏈表的頭結(jié)點開始，找到P指針?biāo)赶虻慕Y(jié)點的前驅(qū)。設(shè)一指針q從附加頭結(jié)點開始向后移動進(jìn)行查找，直到p的前趨結(jié)點為止。然后在q指針?biāo)傅慕Y(jié)點和p指針?biāo)傅慕Y(jié)點之間插入結(jié)點s。 操作過程如圖2-9所示。相關(guān)語句如下：【算法2.5 單鏈表的結(jié)點插入】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 單鏈表的前插入

42、sxpa0ai-1aian-1q headx0aai-1an-1ai headqps（a）插入前【算法2.6 單鏈表的前插入】int insert(slnodetype *h,int i,Elemtype x)/*在鏈表h中，在第i個數(shù)據(jù)元素插入一個數(shù)據(jù)元素x */ slnodetype *p,*q,*s; int j=0; p=h; while(p!=NULL&jnext;j+; /*尋找第i-1個結(jié)點*/ if ( j!=i-1) printf(“Error!”);return FALSE; /*插入位置錯誤*/ if (s=(slnodetype*)malloc(sizeof(slnod

43、etype)=NULL) return FALSE; s-data=x; s-next=p-next; q-next=s; return TRUE;例：下面C程序中的功能是，首先建立一個線性鏈表head=3，5，7，9，其元素值依次為從鍵盤輸入正整數(shù)（以輸入一個非正整數(shù)為結(jié)束）；在線性表中值為x的元素前插入一個值為y的數(shù)據(jù)元素。若值為x的結(jié)點不存在，則將y插在表尾。#include “stdlib.h”#include “stdio.h”struct slnodeint data;struct slnode *next; /*定義結(jié)點類型*/main()int x,y,d;struct sln

44、ode *head,*p,*q,*s; head=NULL; /*置鏈表空*/ q=NULL; scanf(“%d”,&d); /*輸入鏈表數(shù)據(jù)元素*/ while(d0) p=(struct slnode*)malloc(sizeof(struct slnode); /*申請一個新結(jié)點*/ p-data=d; p-next=NULL; if(head=NULL) head=p; /*若鏈表為空，則將頭指針指向當(dāng)前結(jié)點p*/ else q-next=p; /*鏈表不為空時，則將新結(jié)點鏈接在最后*/ q=p; /*將指針q指向鏈表的最后一個結(jié)點*/ scanf(“%d”,&d); scanf(“

45、%d,%d”,&x,&y); s=(struct slnode*)malloc(sizeof(struct slnode); 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）單鏈表的刪除操作若要刪除線性鏈表h中的第i個結(jié)點，首先要找到第i個結(jié)點并使指針p指向其前驅(qū)第i-1個結(jié)點，然后刪除第i個結(jié)點并釋放被刪除結(jié)點空間。操作過程如圖2-10所示。其算法如下：【算法2.7 單鏈表的刪除】int Delet(slnodet

46、ype *h,int i) /*在鏈表h中刪除第i個結(jié)點*/ slnodetype *p,*s; int j; p=h;j=0; while(p-next!=NULL&jnext;j=j+1; /*尋找第i-1個結(jié)點,p指向其前驅(qū)*/ if(j!=i-1) printf(“Error!”); /*刪除位置錯誤!*/ return FALSE; s=p-next; p-next=p-next-next; /*刪除第i個結(jié)點*/ free(s); /*釋放被刪除結(jié)點空間*/ return TRUE; head head (b)刪除并釋放第i個結(jié)點圖2-10 在線性鏈表中刪除一個結(jié)點的過程aiai-

47、1ai+1an-1p(a) 尋找第i個結(jié)點指向其前驅(qū)ppsan-1ai+1aiai-1(p!=NULL&jnext!=NULL&jnext; head-next=NULL; while(p!=NULL) q=p-next; p-next=head-next; head-next=p; p=q;a0a1an-1a3pqa0a1an-1a3pqa1a0an-1a3pqa0a1an-1a3 head head head head圖2-11 單鏈表逆置2.3.2 循環(huán)鏈表循環(huán)鏈表(Circular Linked List)是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。是將單鏈表的表中最后一個結(jié)點指針指向鏈表的表頭結(jié)點，

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

49、鏈表的空表形式 head (b)循環(huán)鏈表的一般形式圖2-12 循環(huán)鏈表a0a1an-1ai例：將兩個循環(huán)鏈表首尾相接。La為第一個循環(huán)鏈表表尾指針，Lb為第二個循環(huán)鏈表表尾指針。合并后Lb為新鏈表的尾指針。Void merge(slnodetype *La,slnodetype *Lb) slnodetype *p; p=La-next; Lb-next= La-next; La-next=p-next; free(p); (a)a0a1an-1b0b1bn-1a0a1an-1a0a1an-1LaLbLb(b)圖2-13 循環(huán)鏈表的合并如圖2-13所示，在這個算法中，時間復(fù)雜度為O(1)。2.

50、3.3 雙向鏈表1雙向鏈表在單鏈表的每個結(jié)點中只有一個指示后繼的指針域，因此從任何一個結(jié)點都能通過指針域找到它的后繼結(jié)點；若需找出該結(jié)點的前驅(qū)結(jié)點，則此時需從表頭出發(fā)重新查找。換句話說，在單鏈表中，查找某結(jié)點的后繼結(jié)點的執(zhí)行時間為O(1)，而查找其前驅(qū)結(jié)點的執(zhí)行時間為O(n)。我們可用雙向鏈表來克服單鏈表的這種缺點，在雙向鏈表中，每一個結(jié)點除了數(shù)據(jù)域外，還包含兩個指針域，一個指針（next）指向該結(jié)點的后繼結(jié)點，另一個指針（prior）指向它的前驅(qū)結(jié)點。雙向鏈表的結(jié)構(gòu)可定義如下：typedef struct nodeElemtype data; struct node *prior,*next

51、; dlnodetype;prior next head(a) 空雙向鏈表a0a1an-1 head(b) 非空的雙向鏈表 圖2-14 雙向鏈表和單鏈的循環(huán)表類似，雙向鏈表也可以有循環(huán)表，讓頭結(jié)點的前驅(qū)指針指向鏈表的最后的一個結(jié)點，讓最后一個結(jié)點的后繼指針指向頭結(jié)點。圖2-14為雙向鏈表示意圖，其中圖(b)是一個循環(huán)雙向鏈表。若p為指向雙向鏈表中的某一個結(jié)點ai的指針，則顯然有：p-next-prior=p-prior-next=p在雙向鏈表中，有些操作如：求長度、取元素、定位等，因僅需涉及一個方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時，則需同時修改兩個方向上的指針，兩者的

52、操作的時間復(fù)雜度均為O(n)。2雙向鏈表的基本操作（1）在雙向鏈表中插入一個結(jié)點在雙向鏈表的第i個元素前插入一個結(jié)點時，可用指針p指該結(jié)點（稱p結(jié)點），先將新結(jié)點的prior指向p結(jié)點的前一個結(jié)點，其次將p結(jié)點的前一個結(jié)點的next指向新結(jié)點，然后將新結(jié)點的next指向p結(jié)點，最后將p結(jié)點的prior指向新結(jié)點。操作過程如圖2-15所示。(a)插入前 （b）插入后 圖2-15 在雙向鏈表中插入結(jié)點ai-1ai s x pai-1aip s x 其算法如下：【算法2.8 雙向鏈表的插入】int insert_dul(dlnodetype *head,int i,Elemtype x)/*在帶頭結(jié)

53、點的雙向鏈表中第i個位置之前插入元素x*/ dbnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&jnext; j+; if(j!=i|idata=x;s-prior=p-prior; /*圖中步驟*/p-prior-next=s; /*圖中步驟*/s-next=p; /*圖中步驟*/p-prior=s; /*圖中步驟*/return TRUE;討論：我們在雙向鏈表中進(jìn)行插入操作時，還需注意下面兩種情況：1）當(dāng)在鏈表中的第一個結(jié)點前插入新結(jié)點時，新結(jié)點的prior應(yīng)為空，原鏈表第一個結(jié)點的prior應(yīng)指向新結(jié)點，新結(jié)點的next應(yīng)指向原鏈表的

54、第一個結(jié)點。2）當(dāng)在鏈表的最后一個結(jié)點后插入新結(jié)點時，新結(jié)點的next應(yīng)為空，原鏈表的最后一個結(jié)點的next應(yīng)指向新結(jié)點，新結(jié)點的prior應(yīng)指向原鏈表的最后一個結(jié)點。（2）在雙向鏈表中刪除一個結(jié)點在雙向鏈表中刪除一個結(jié)點時，可用指針p指向該結(jié)點（稱p結(jié)點），然后將p結(jié)點的前一個結(jié)點的next指向p結(jié)點的下一個結(jié)點，再將p的下一個結(jié)點的prior指向p的上一個結(jié)點。如圖2-16所示，圖2-16 在雙向鏈表中刪除一個結(jié)點ai-1aiai+1p【算法2.9 雙向鏈表的刪除】int Delete_dl(dlnodetype *head,int i) dlnodetype *p,*s; int j;

55、p=head; j=0; while (p!=NULL&jnext; j+; if(j!=i|iprior-next=p-next; /*圖中步驟*/p-next-prior=p-prior; /*圖中步驟*/free(s);return TRUE;討論：我們在雙向鏈表中進(jìn)行刪除操作時，還需注意下面兩種情況：1）當(dāng)刪除鏈表的第一個結(jié)點時，應(yīng)將鏈表開始結(jié)點的指針指向鏈表的第二個結(jié)點，同時將鏈表的第二個結(jié)點的prior置為NULL。2）當(dāng)刪除鏈表的最后一個結(jié)點時，只需將鏈表的最后一個結(jié)點的上一個結(jié)點的next置為NULL即可。上面我們詳細(xì)講解了鏈?zhǔn)酱鎯Y(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)克服了順序存儲結(jié)構(gòu)的缺點：它

56、的結(jié)點空間可以動態(tài)申請和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，不需要移動數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯Y(jié)構(gòu)也有不足之處：（1）每個結(jié)點中的指針域需額外占用存儲空間。當(dāng)每個結(jié)點的數(shù)據(jù)域所占字節(jié)不多時，指針域所占存儲空間的比重就顯得很大。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種非隨機存儲結(jié)構(gòu)。對任一結(jié)點的操作都要從頭指針依指針鏈查找到該結(jié)點，這增加了算法的復(fù)雜度。2.4 一元多項式的表示及相加符號多項式的表示及其操作是線性表處理的典型用例，在數(shù)學(xué)上，一個一元多項式Pn(x) 可以表示為 ：Pn(x)=a0+a1x+a2x2+anxn (最多有n+1項)aixi是多項式的第i項（0in），其中ai為系數(shù)，x為變量

57、，i為指數(shù)。它有n+1個系數(shù)，因此，在計算機里，它可用一個線性表P來表示：P=（a0,a1,a2,，an）假設(shè)Qn(x)是一元m次多項式，同樣可用線性表Q來示：Q=（b0,b1,b2,，bm）若mnext;qb=Bh-next;/*qa和qb分別指向兩個鏈表的第一結(jié)點*/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);

58、qa+; /*相加后系數(shù)不為零時*/ else s=qa+;free(s);s=qb+;free(s); /*相加后系數(shù)為零時*/ else if(qa-expexp) r-next=qa;r=qa;qa+;/*多項式Ah的指數(shù)值小*/ else r-next=qb;r=qb;qb+;/*多項式Bh的指數(shù)值小*if(qa=NULL) r-next=qb; else r-next=qa;/*鏈接多項式Ah或Bh中的剩余結(jié)點*/return (Ch);本章小結(jié)本章主要介紹了如下一些基本概念：線性表：一個線性表是n0個數(shù)據(jù)元素a0，a1，a2，an-1的有限序列。線性表的順序存儲結(jié)構(gòu)：在計算機中用一

59、組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)就是用一組任意的存儲單元結(jié)點（可以是不連續(xù)的）存儲線性表的數(shù)據(jù)元素。表中每一個數(shù)據(jù)元素，都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅(qū)或直接后繼結(jié)點的地址（指針）的指針域組成。循環(huán)鏈表：循環(huán)鏈表(Circular Linked List)是將單鏈表的表中最后一個結(jié)點指針指向鏈表的表頭結(jié)點，整個鏈表形成一個環(huán)，從表中任一結(jié)點出發(fā)都可找到表中其他的結(jié)點。循環(huán)鏈表：循環(huán)鏈表(Circular Linked List)是將單鏈表的表中最后一個結(jié)點指針指向鏈表的表頭結(jié)點，整個鏈表形成一個環(huán)，從

60、表中任一結(jié)點出發(fā)都可找到表中其他的結(jié)點。雙向鏈表：雙向鏈表中，在每一個結(jié)點除了數(shù)據(jù)域外，還包含兩個指針域，一個指針（next）指向該結(jié)點的后繼結(jié)點，另一個指針（prior）指向它的前驅(qū)結(jié)點。除上述基本概念以外，學(xué)生還應(yīng)該了解：線性表的基本操作（初始化、插入、刪除、存取、復(fù)制、合并）、順序存儲結(jié)構(gòu)的表示、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的表示、一元多項式Pn(x)，掌握順序存儲結(jié)構(gòu)（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）。習(xí) 題 二1什么是順序存儲結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯Y(jié)構(gòu)？2線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)各有什么特點？3設(shè)線性表中數(shù)據(jù)元素的總數(shù)基本不變，并很少