數據結構（C語言描述）

前言

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

2數據結構的發展簡史及其在計算機科學中所處的地位3什么是數據結構

4基本概念和術語

5算法和算法的描述

第一章緒論

本章介紹了數據結構這門學科誕生的背景、發展歷史以及在計算機科學中所處的地位，重點介紹了數據結構有關的概念和術語，讀者學習本章后應能掌握數據、數據元素、邏輯結構、存儲結構、數據處理、數據結構、算法設計等基本概念，并了解如何評價一個算法的好壞。

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

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

1.3什么是數據結構

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

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

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

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

1.5.1算法算法是執行特定計算的有窮過程。這個過程有5個特點：

1.動態有窮：當執行一個算法時，不論是何種情況，在經過了有限步驟后，這個算法一定要終止。

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

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

4.輸出：產生1個或多個結果。

5.可行性：每條指令都充分基本，原則上可由人僅用筆和紙在有限的時間內也能完成。注意：算法和程序是有區別的，即程序未必能滿足動態有窮。在本書中，我們只討論滿足動態有窮的程序，因此“算法”和“程序”是通用的。

1.5.2算法的描述

一個算法可以用自然語言、數字語言或約定的符號來描述，也可以用計算機高級程序語言來描述，如Pascal語言、C語言或偽代碼等。本書選用C語言作為描述算法的工具。現簡單說明C語言的語法結構如下：1．預定義常量和類型：

#defineTRUE1；

#defineFALSE-1；

#defineERRORNULL；2．函數的形式

[數據類型]函數名（[形式參數]）

[形式參數說明；]{內部數據說明；執行語句組；

}/*函數名*/〈函數的定義主要由函數名和函數體組成，函數體用花括號“{”和“}”括起來。函數中用方括號括起來的部分為可選項，函數名之間的圓括號不可省略。函數的結果可由指針或別的方式傳遞到函數之外。執行語句可由各種類型的語句所組成，兩個語句之間用“；”號分隔。可將函數中的表達式的值通過return語句返回給調用它的函數。最后的花括號“}”之后的/*函數名*/為注釋部分，可舍。

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

switch（〈表達式〉）

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

break；

case判斷值2；語句組2；

break；

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

break；

[default：語句組；

break；]}注意：switchcase語句是先計算表達式的值，然后用其值與判斷值相比較，若它們相一致時，就執行相應的case下的語句組；若不一致，則執行default下的語句組；其中的方括號代表可選項。

5．循環語句⑴for語句

for（〈表達式1〉；〈表達式2〉；〈表達式3〉）{循環體語句；}

首先計算表達式1的值，然后求表達式2的值，若結果非零則執行循環體語句，最后對表達式3運算，如此循環，直到表達式2的值為零時止。⑵while語句

while（〈條件表達式〉）

{循環體語句；

}while循環首先計算條件表達式的值，若條件表達式的值非零，則執行循環體語句，然后再次計算條件表達式，重復執行，直到條件表達式的值為假時退出循環，執行該循環之后的語句。⑶do-while語句

do{循環體語句

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

min函數，用于求一個或幾個表達式中的最小值；

abs函數，用于求表達式的絕對值；

eof函數，用于判定文件是否結束；

eoln函數，用于判斷文本行是否結束。例計算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；}上述算法所用到的運算有乘法、加法、賦值和比較，其基本運算為乘法操作。在上述算法的執行過程中，對外循環變量i的每次取值，內循環變量j循環i次。因為內循環每執行一次，內循環體語句w=w*j只作一次乘法操作，即當內循環變量j循環i次時，內循環體的語句w=w*j作i次乘法。所以，整個算法所作的乘法操作總數是：f（n）=1+2+3+…n=n（n-1）/2。1.5.3算法評價設計一個好的算法應考慮以下幾個方面：1．正確性

“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個層次：①程序不含語法錯誤；②程序對于幾組輸入數據能夠得出滿足規格說明要求的結果；③程序對于精心選擇的典型、苛刻而帶有刁難性的幾組數據能夠得出滿足規格說明要求的結果；④程序對一切合法的輸入數據都能產生滿足規格說明要求的結果。

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

習題一1．簡述下列術語：數據、結點、邏輯結構、存儲結構、數據處理、數據結構和數據類型。2．試根據以下信息：校友姓名、性別、出生年月、畢業時間、所學專業、現在工作單位、職稱、職務、電話等，為校友錄構造一種適當的數據結構（作圖示意），并定義必要的運算和用文字敘述相應的算法思想。3．什么是算法？算法的主要特點是什么？4．如何評價一個算法？1線性表的邏輯結構

本章學習導讀線性表（Linearlist）是最簡單且最常用的一種數據結構。這種結構具有下列特點：存在一個唯一的沒有前驅的（頭）數據元素；存在一個唯一的沒有后繼的（尾）數據元素；此外，每一個數據元素均有一個直接前驅和一個直接后繼數據元素。通過本章的學習，讀者應能掌握線性表的邏輯結構和存儲結構，以及線性表的基本運算以及實現算法。

2線性表的順序存儲結構

3線性表的鏈式存儲結構

4一元多項式的表示及相加

2.1線性表的邏輯結構

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

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

Insert(L,i,x)插入：在給定的線性表L中，在第i個元素之前插入數據元素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的數據元素的個數。6．

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

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

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

Merge(A,B,C)合并：將給定的線性表A和B合并為線性表C。上面我們定義了線性表的邏輯結構和基本操作。在計算機內，線性表有兩種基本的存儲結構：順序存儲結構和鏈式存儲結構。下面我們分別討論這兩種存儲結構以及對應存儲結構下實現各操作的算法。2.2線性表的順序存儲結構

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

若定義數組A[n]={a0，a1，a2，…，an-1}，假設每一個數組元素占用d個字節，則數組元素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。其結構如圖2-2所示。若定義數組A[n][m]，表示此數組有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二維數組

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

序號元素

序號元素

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

在長度為num(0≤num≤MAXNUM-2)的順序表List的第i(0≤i≤num+1)個數據元素之前插入一個新的數據元素x時，需將最后一個即第num個至第i個元素（共num-i+1個元素）依次向后移動一個位置，空出第i個位置，然后把x插入到第i個存儲位置，插入結束后順序表的長度增加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在數組中插入元素

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

在長度為num(0≤num≤MAXNUM-1)的順序表List，刪除第i(0≤i≤num)個數據元素，需將第i至第num個數據元素的存儲位置（num-i+1）依次前移，并使順序表的長度減1，返回TRUE值，若i＜0或i＞num，則無法刪除，返回FALSE值，如圖2-6所示。其算法如下：【算法2.2順序表的刪除】intDelete(ElemtypeList[],int*num,inti){/*在線性表List[]中，*num為表尾元素下標位置，刪除第i個元素，線性表的元素減1，若成功，則返回TRUE；否則返回FALSE。*/intj;if(i<0||i>*num){printf(“Error!”);returnFALSE; /*刪除位置出錯！*/}for(j=i+1;j<=*num;j++)List[j-1]=List[j]; /*數據元素前移*/(*num)--; /*長度減1*/returnTRUE;}從上述兩個算法來看，很顯然，在線性表的順序存儲結構中插入或刪除一個數據元素時，其時間主要耗費在移動數據元素上。而移動元素的次數取決于插入或刪除元素的位置。假設Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素次數的平均次數為假設qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素時所需移動元素次數的平均次數為如果在線性表的任何位置插入或刪除元素的概率相等，即則可見，在順序存儲結構的線性表中插入或刪除一個元素時，平均要移動表中大約一半的數據元素。若表長為n，則插入和刪除算法的時間復雜度都為O(n)。在順序存儲結構的線性表中其他的操作也可直接實現，在此不再講述。例：將有序線性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并為Lc={1,2,4,5,6,7,7,8,9}。分析：Lc中的數據元素或者是La中的數據元素，或者是Lb中的數據元素，則只要先將Lc置為空表，然后將La或Lb中的元素逐個插入到Lc中即可。設兩個指針i和j分別指向La和Lb中的某個元素，若設i當前所指的元素為a，j當前所指的元素為b，則當前應插入到Lc中的元素c為c={ａ當ａ≤ｂ時ｂ當ａ＞ｂ時，很顯然，指針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．順序表存儲結構的特點線性表的順序存儲結構中任意數據元素的存儲地址可由公式直接導出，因此順序存儲結構的線性表是可以隨機存取其中的任意元素。也就是說定位操作可以直接實現。高級程序設計語言提供的數組數據類型可以直接定義順序存儲結構的線性表，使其程序設計十分方便。但是，順序存儲結構也有一些不方便之處，主要表現在：（1）數據元素最大個數需預先確定，使得高級程序設計語言編譯系統需預先分配相應的存儲空間。（2）插入與刪除運算的效率很低。為了保持線性表中的數據元素的順序，在插入操作和刪除操作時需移動大量數據。這對于插入和刪除操作頻繁的線性表、以及每個數據元素所占字節較大的問題將導致系統的運行速度難以提高。（3）順序存儲結構的線性表的存儲空間不便于擴充。當一個線性表分配順序存儲空間后，如果線性表的存儲空間已滿，但還需要插入新的元素，則會發生“上溢”錯誤。在這種情況下，如果在原線性表的存儲空間后找不到與之連續的可用空間，則會導致運算的失敗或中斷。2.3線性表的鏈式存儲結構

從線性表的順序存儲結構的討論中可知，對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存儲結構，而應采用本節要介紹的鏈式存儲結構。線性表的鏈式存儲結構就是用一組任意的存儲單元（可以是不連續的）存儲線性表的數據元素。對線性表中的每一個數據元素，都需用兩部分來存儲：一部分用于存放數據元素值，稱為數據域；另一部分用于存放直接前驅或直接后繼結點的地址（指針），稱為指針域，我們把這種存儲單元稱為結點。在鏈式存儲結構方式下，存儲數據元素的結點空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系由指針域來確定。鏈式存儲方式可用于表示線性結構，也可用于表示非線性結構。2.3.1線性鏈表

1．線性鏈表線性鏈表是線性表的鏈式存儲結構，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。因此，在存儲線性表中的數據元素時，一方面要存儲數據元素的值，另一方面要存儲各數據元素之間的邏輯順序，為此，將每一個存儲結點分為兩部分：一部分用于存儲數據元素的值，稱為數據域；另一部分用于存放下一個數據元素的存儲結點的地址，即指向后繼結點，稱為指針域。此種形式的鏈表因只含有一個指針域，又稱為單向鏈表，簡稱單鏈表。圖2-7(a)所示為一個空線性鏈表。圖2-6(b)所示為一個非空線性鏈表（a0，a1，a2，…，an-1）。a0a1an-1

headhead…(a)(b)圖2-7線性鏈表的存儲結構上圖中，通常在線性鏈表的第一結點之前附設一個稱為頭結點的結點。頭結點的數據域可以不存放任何數據，也可以存放鏈表的結點個數的信息。對空線性表，附加頭結點的指針域為空（NULL或0表示），用∧表示。頭指針head指向鏈表附加頭結點的存儲位置。對于鏈表的各種操作必須從頭指針開始。在C語言中，定義鏈表結點的形式如下：struct結構體名

{數據成員表；

struct結構體名*指針變量名；}例如，下面定義的結點類型中，數據域包含三個數據項：學號、姓名、成績。Structstudent{charnum[8]; /*數據域*/charname[8]; /*數據域*/intscore; /*數據域*/structstudent*next; /*指針域*/}假設h,p,q為指針變量，可用下列語句來說明：structstudent*h,*p,*q;在C語言中，用戶可以利用malloc函數向系統申請分配鏈表結點的存儲空間，該函數返回存儲區的首地址，如：p=(structstudent*)malloc(sizeof(structstudent));指針p指向一個新分配的結點。如果要把此結點歸還給系統，則用函數free(p)來實現。２．線性鏈表的基本操作下面給出的單鏈表的基本操作實現算法都是以圖2-7所示的帶頭結點的單鏈表為數據結構基礎。單鏈表結點結構定義為：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定義為指針的指針類型，若定義為指針類型，將無法帶回函數中建立的頭指針值。（2）單鏈表的插入操作1）已知線性鏈表head，在p指針所指向的結點后插入一個元素x。在一個結點后插入數據元素時，操作較為簡單，不用查找便可直接插入。操作過程如圖2-8所示。headpps

head(a)插入前…a0a1aian-1

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

ai…a0a1…相關語句如下：【算法2.4單鏈表的后插入】{s=(slnodetype*)malloc(sizeof(slnodetype));s->data=x;s->next=p->next;p->next=s;}2）已知線性鏈表head，在p指針所指向的結點前插入一個元素x。前插時，必須從鏈表的頭結點開始，找到P指針所指向的結點的前驅。設一指針q從附加頭結點開始向后移動進行查找，直到p的前趨結點為止。然后在q指針所指的結點和p指針所指的結點之間插入結點s。操作過程如圖2-9所示。相關語句如下：【算法2.5單鏈表的結點插入】{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個數據元素插入一個數據元素x*/slnodetype*p,*q,*s;intj=0;p=h;while(p!=NULL&&j<i-1){p=q->next;j++; /*尋找第i-1個結點*/}if(j!=i-1){printf(“Error!”);returnFALSE; /*插入位置錯誤*/}if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)returnFALSE;s->data=x;s->next=p->next;q->next=s;returnTRUE;}例：下面C程序中的功能是，首先建立一個線性鏈表head={3，5，7，9}，其元素值依次為從鍵盤輸入正整數（以輸入一個非正整數為結束）；在線性表中值為x的元素前插入一個值為y的數據元素。若值為x的結點不存在，則將y插在表尾。#include“stdlib.h”#include“stdio.h”structslnode{intdata;structslnode*next;} /*定義結點類型*/main(){intx,y,d;structslnode*head,*p,*q,*s;head=NULL; /*置鏈表空*/q=NULL;scanf(“%d”,&d);/*輸入鏈表數據元素*/while(d>0){p=(structslnode*)malloc(sizeof(structslnode));/*申請一個新結點*/p->data=d;p->next=NULL;if(head==NULL)head=p;/*若鏈表為空，則將頭指針指向當前結點p*/elseq->next=p;/*鏈表不為空時，則將新結點鏈接在最后*/q=p;/*將指針q指向鏈表的最后一個結點*/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）單鏈表的刪除操作若要刪除線性鏈表h中的第i個結點，首先要找到第i個結點并使指針p指向其前驅第i-1個結點，然后刪除第i個結點并釋放被刪除結點空間。操作過程如圖2-10所示。其算法如下：【算法2.7單鏈表的刪除】intDelet(slnodetype*h,inti){/*在鏈表h中刪除第i個結點*/slnodetype*p,*s;intj;p=h;j=0;while(p->next!=NULL&&j<i-1){p=p->next;j=j+1;/*尋找第i-1個結點,p指向其前驅*/}if(j!=i-1){printf(“Error!”);/*刪除位置錯誤!*/returnFALSE;}s=p->next;p->next=p->next->next;/*刪除第i個結點*/free(s);/*釋放被刪除結點空間*/returnTRUE;}

head…

…

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

p(a)尋找第i個結點指向其前驅ppsan-1

ai+1aiai-1(p!=NULL&&j<i-1)與(p->next!=NULL&&j<i-1)的不同。從線性鏈表的插入與刪除算法中，我們可以看到要取鏈表中某個結點，必須從鏈表的頭結點開始一個一個地向后查找，即我們不能直接存取線性鏈表中的某個結點，這是因為鏈式存儲結構不是隨機存儲結構。雖然在線性鏈表中插入或刪除結點不需要移動別的數據元素，但算法尋找第i-1個或第i個結點的時間復雜度為O(n)。例：假設已有線性鏈表La，編制算法將該鏈表逆置。利用頭結點和第一個存放數據元素的結點之間不斷插入后繼元素結點。如圖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循環鏈表循環鏈表(CircularLinkedList)是另一種形式的鏈式存儲結構。是將單鏈表的表中最后一個結點指針指向鏈表的表頭結點，整個鏈表形成一個環，這樣從表中任一結點出發都可找到表中其他的結點。圖2-12（a）為帶頭結點的循環單鏈表的空表形式，圖2-12（b）為帶頭結點的循環單鏈表的一般形式。帶頭結點的循環鏈表的操作實現算法和帶頭結點的單鏈表的操作實現算法類同，差別在于算法中的條件在單鏈表中為p!=null或p->next!=null；而在循環鏈表中應改為p!=head或p->next!=head。在循環鏈表中，除了頭指針head外，有時還加了一個尾指針rear，尾指針read指向最后一結點，從最后一個結點的指針又可立即找到鏈表的第一個結點。在實際應用中，使用尾指針代替頭指針來進行某些操作，往往更簡單。

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

head…

…

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

ai例：將兩個循環鏈表首尾相接。La為第一個循環鏈表表尾指針，Lb為第二個循環鏈表表尾指針。合并后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循環鏈表的合并…………

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

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

和單鏈的循環表類似，雙向鏈表也可以有循環表，讓頭結點的前驅指針指向鏈表的最后的一個結點，讓最后一個結點的后繼指針指向頭結點。圖2-14為雙向鏈表示意圖，其中圖(b)是一個循環雙向鏈表。若p為指向雙向鏈表中的某一個結點ai的指針，則顯然有：p->next->prior==p->prior->next==p在雙向鏈表中，有些操作如：求長度、取元素、定位等，因僅需涉及一個方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時，則需同時修改兩個方向上的指針，兩者的操作的時間復雜度均為O(n)。2．雙向鏈表的基本操作（1）在雙向鏈表中插入一個結點在雙向鏈表的第i個元素前插入一個結點時，可用指針p指該結點（稱p結點），先將新結點的prior指向p結點的前一個結點，其次將p結點的前一個結點的next指向新結點，然后將新結點的next指向p結點，最后將p結點的prior指向新結點。操作過程如圖2-15所示。(a)插入前（b）插入后圖2-15在雙向鏈表中插入結點ai-1ais∧x∧pai-1aip①②③④sx其算法如下：【算法2.8雙向鏈表的插入】intinsert_dul(dlnodetype*head,inti,Elemtypex){/*在帶頭結點的雙向鏈表中第i個位置之前插入元素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;}討論：我們在雙向鏈表中進行插入操作時，還需注意下面兩種情況：1）當在鏈表中的第一個結點前插入新結點時，新結點的prior應為空，原鏈表第一個結點的prior應指向新結點，新結點的next應指向原鏈表的第一個結點。2）當在鏈表的最后一個結點后插入新結點時，新結點的next應為空，原鏈表的最后一個結點的next應指向新結點，新結點的prior應指向原鏈表的最后一個結點。（2）在雙向鏈表中刪除一個結點在雙向鏈表中刪除一個結點時，可用指針p指向該結點（稱p結點），然后將p結點的前一個結點的next指向p結點的下一個結點，再將p的下一個結點的prior指向p的上一個結點。如圖2-16所示，圖2-16在雙向鏈表中刪除一個結點①②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;}討論：我們在雙向鏈表中進行刪除操作時，還需注意下面兩種情況：1）當刪除鏈表的第一個結點時，應將鏈表開始結點的指針指向鏈表的第二個結點，同時將鏈表的第二個結點的prior置為NULL。2）當刪除鏈表的最后一個結點時，只需將鏈表的最后一個結點的上一個結點的next置為NULL即可。上面我們詳細講解了鏈式存儲結構，鏈式存儲結構克服了順序存儲結構的缺點：它的結點空間可以動態申請和釋放；它的數據元素的邏輯次序靠結點的指針來指示，不需要移動數據元素。但是鏈式存儲結構也有不足之處：（1）每個結點中的指針域需額外占用存儲空間。當每個結點的數據域所占字節不多時，指針域所占存儲空間的比重就顯得很大。（2）鏈式存儲結構是一種非隨機存儲結構。對任一結點的操作都要從頭指針依指針鏈查找到該結點，這增加了算法的復雜度。2.4一元多項式的表示及相加

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

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

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

1．什么是順序存儲結構？什么是鏈式存儲結構？2．線性表的順序存儲結構和鏈式存儲結構各有什么特點？3．設線性表中數據元素的總數基本不變，并很少進行