數(shù)據(jù)結(jié)構(gòu)-緒論線性表

第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2有關(guān)概念和術(shù)語1.3算法和算法分析1.3.1算法1.3.2算法設(shè)計的要求1.3.3算法效率的度量1.3.4算法的存儲空間的需求數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第1頁。計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示信息的處理

而信息的表示和組又直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第2頁。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心學科。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第3頁。非數(shù)值計算問題：

數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學方程加以描述。

例1：電話號碼查詢系統(tǒng)

設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號碼。本問題是一種典型的表格問題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關(guān)系。姓名電話號碼尼古拉。。。。。表1-1

線性表結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第4頁。例2：磁盤目錄文件系統(tǒng)

磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推：本問題是一種典型的樹型結(jié)構(gòu)問題，如圖1-1

，數(shù)據(jù)與數(shù)據(jù)成一對多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹形結(jié)構(gòu)。圖1-2

樹形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第5頁。1.2

基本概念和術(shù)語數(shù)據(jù)(Data)

：是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(DataElement)

：是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C={‘A’,’B’,’C,…}。數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第6頁。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(AbstractDataType

，簡稱ADT)：是指一個數(shù)學模型以及定義在該模型上的一組操作。

ADT的定義僅是一組邏輯特性描述，與其在計算機內(nèi)的表示和實現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第7頁。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)在計算機中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。圖1-3

四類基本結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第8頁。

1.3算法和算法分析

1.3.1算法：是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性：（1）有窮性一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。（2）確定性算法中每一條指令必須有確切的含義。不存在二義性。（3）可行性一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。（4）輸入一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。（5）輸出一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第9頁。1.3.2算法設(shè)計的要求評價一個好的算法有以下幾個標準正確性(Correctness

)：算法應(yīng)滿足具體問題的需求。可讀性(Readability)：算法應(yīng)容易供人閱讀和交流。可讀性好的算法有助于對算法的理解和修改。健壯性(Robustness)：算法應(yīng)具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法應(yīng)能適當?shù)刈鞒龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關(guān)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第10頁。1.3.3算法效率的度量事后統(tǒng)計：計算機內(nèi)部進行執(zhí)行時間和實際占用空間的統(tǒng)計。缺點：必須先運行依據(jù)算法編制的程序；依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。事前分析：求出該算法的一個時間界限函數(shù)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第11頁。和算法執(zhí)行時間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機器代碼的質(zhì)量5．計算機執(zhí)行指令的速度數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第12頁。拋開軟硬件等有關(guān)因素，可以認為一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第13頁。算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間量度記作T(n)=O(f(n))，稱作算法的漸近時間復雜度(AsymptoticTimecomplexity)，簡稱時間復雜度。一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復執(zhí)行的次數(shù))來表示?！癘”的定義：若f(n)是正整數(shù)n的一個函數(shù)，則O(f(n))表示

M≥0，使得當n≥n0時，|f(n)|≤M

|f(n0)|。表示時間復雜度的階有：

O(1)：常量時間階O(n)：線性時間階

O(㏒n)

：對數(shù)時間階O(n㏒n)：線性對數(shù)時間階數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第14頁。一個算法的執(zhí)行時間可以看成是所有原操作的執(zhí)行時間之和

∑(原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間)這種衡量效率的辦法所得出的不是時間量，而是一種增長趨勢的量度。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第15頁。下面以(c)程序段為例，進行時間復雜度的分析。步驟1：先把所有語句改為基本操作。Intj=1; 1a:if(j<=n) n+1{ k=1; n*1 b:if(k<=n) n*(n+1) { x=x+1; n*n k++; n*n gotob; }j++; n*1gotoa;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第16頁。步驟2：分析每一條語句的語句頻度，標到每條語句后邊，如上。步驟3：統(tǒng)計總的語句頻度：1+n+1+n+n(n+1)+n^2+n^2+n=3n^2+4n+2。步驟4：判斷最大語句頻度為n^2，所以時間復雜度為O(n^2)。其中O表示等價無窮小。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時間的關(guān)系為：

O(2n)<O(n!)<O(nn)

當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第17頁。有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例2：冒泡排序法。Voidbubble_sort(inta[]，intn){change=false;for(i=n-1;change=TURE;i>1&&change;--i)for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}

最好情況：0次最壞情況：1+2+3+?+n-1=n(n-1)/2

平均時間復雜度為：O(n2)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第18頁。1.3.4

算法的空間分析空間復雜度(Spacecomplexity)：是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。記作：S(n)=O(f(n))其中：n為問題的規(guī)模(或大小)該存儲空間一般包括三個方面：指令常數(shù)變量所占用的存儲空間(程序本身);

輸入數(shù)據(jù)所占用的存儲空間(輸入數(shù)據(jù));

輔助(存儲)空間(輔助變量)。一般地，算法的空間復雜度指的是輔助空間。

一維數(shù)組a[n]：空間復雜度O(n)

二維數(shù)組a[n][m]：空間復雜度O(n*m)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第19頁。第2章

線性表

線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①

存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素；②存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素；③

除第一個元素外，每個元素均有唯一一個直接前驅(qū)；④

除最后一個元素外，每個元素均有唯一一個直接后繼。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第20頁。2.1

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

線性表(LinearList)：是由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時，稱為空表。當n>0時，將非空的線性表記作：(a1，a2，…an)a1稱為線性表的第一個(首)結(jié)點，an稱為線性表的最后一個(尾)結(jié)點。2.1.1

線性表的定義數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第21頁。a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第22頁。2.1.2

線性表的邏輯結(jié)構(gòu)線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號?！艟€性表中的結(jié)點可以是單值元素(每個元素只有一個數(shù)據(jù)項)。例1:26個英文字母組成的字母表：(A，B，C、…、Z）

◆線性表中的結(jié)點可以是記錄型元素，每個元素含有多個數(shù)據(jù)項，每個項稱為結(jié)點的一個域。每個元素有一個可以唯一標識每個結(jié)點的數(shù)據(jù)項組，稱為關(guān)鍵字。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第23頁。例2、學生健康情況登記表如下：…….…….…….……..……..健康17男790634張立健康21男790633劉建平一般20女790632陳紅健康18男790631王小林健康情況年齡性別學號姓名數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第24頁。

◆若線性表中的結(jié)點是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。

◆

線性表是一種相當靈活的數(shù)據(jù)結(jié)構(gòu)，其長度可根據(jù)需要增長或縮短。

◆對線性表的數(shù)據(jù)元素可以訪問、插入和刪除。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第25頁。2.1.3

線性表的抽象數(shù)據(jù)類型定義ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個空的線性表L；數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第26頁。ListLength(L)初始條件：線性表L已存在；操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE；….GetElem(L,i,&e)初始條件：線性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值；ListInsert(L,i,&e)初始條件：線性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：在線性表L中的第i個位置插入元素e；…}ADTList數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第27頁。2.2

線性表的順序存儲

順序存儲：把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。順序存儲的線性表的特點：

◆線性表的邏輯順序與物理順序一致;

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)。設(shè)有非空的線性表：(a1，a2，…an)。順序存儲如圖2-1所示。2.2.1

線性表的順序存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第28頁。

在具體的機器環(huán)境下：設(shè)線性表的每個元素需占用l個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+l

線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(i-1)*l

…a1a2…ai…an…Loc(a1)Loc(ai)+(i-1)*l

圖2-1

線性表的順序存儲表示數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第29頁。由于在高級語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，利用C++語言的結(jié)構(gòu)類型來定義順序表類型。#defineListSize100//表容量

typedefintDataType;//以int為例

structSqlist{DataTypedata[ListSize];intlenth;//當前表中元素數(shù)};數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第30頁。2.2.2

順序表的基本操作

順序存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。以下將對幾種主要的操作進行討論。1順序線性表初始化

StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem_array)returnERROR;else{L->length=0;returnOK;}}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第31頁。2

順序線性表的插入

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個位置上插入一個新結(jié)點e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實現(xiàn)步驟(1)

將線性表L中的第i個至第n個結(jié)點后移一個位置。(2)將結(jié)點e插入到結(jié)點ai-1之后。(3)線性表長度加1。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第32頁。算法描述StatusInsert_SqList(Sqlist*L，inti，ElemTypee)

{intj;if(i<0||i>L->length-1)returnERROR;if(L->length>=MAX_SIZE){printf(“線性表溢出!\n”);returnERROR;}for(j=L->length–1;j>=i-1;--j)L->Elem_array[j+1]=L->Elem_array[j];/*i-1位置以后的所有結(jié)點后移*/L->Elem_array[i-1]=e;/*在i-1位置插入結(jié)點*/L->length++;returnOK;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第33頁。

時間復雜度分析

在線性表L中的第i個元素之前插入新結(jié)點，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復雜度。設(shè)在線性表L中的第i個元素之前插入結(jié)點的概率為Pi，不失一般性，設(shè)各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動結(jié)點的次數(shù)為n-i+1?？偟钠骄苿哟螖?shù)：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運算，平均要移動表上一半結(jié)點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第34頁。3順序線性表的刪除

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除結(jié)點ai(1≦i≦n)，使其成為線性表：

L=(a1，…ai-1，ai+1，…，an)

實現(xiàn)步驟(1)

將線性表L中的第i+1個至第n個結(jié)點依此向前移動一個位置。(2)線性表長度減1。算法描述ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第35頁。if(L->length==0){printf(“線性表L為空!\n”);returnERROR;}elseif(i<1||i>L->length){printf(“要刪除的數(shù)據(jù)元素不存在!\n”);returnERROR;}else{x=L->Elem_array[i-1];/*保存結(jié)點的值*/for(k=i;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];

/*i位置以后的所有結(jié)點前移*/L->length--;return(x);}}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第36頁。

時間復雜度分析

刪除線性表L中的第i個元素，其時間主要耗費在表中結(jié)點的移動操作上，因此，可用結(jié)點的移動來估計算法的時間復雜度。設(shè)在線性表L中刪除第i個元素的概率為Pi，不失一般性，設(shè)刪除各個位置是等概率，則Pi=1/n，而刪除時移動結(jié)點的次數(shù)為n-i。則總的平均移動次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運算，平均要移動表上一半結(jié)點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第37頁。2.3線性表的鏈式表示和實現(xiàn)2.3.1線性鏈表鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第38頁。

其中：data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結(jié)只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。

顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于最后一個結(jié)點無后繼，故結(jié)點的指針域為空，即NULL（圖示中常用^表示)。datanext數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第39頁。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)示意圖如下：165head:110130160165170200205135......hat200......cat135eat170......matnullbat130fat110......jat205lat160......數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第40頁。單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。用C++語言描述的單鏈表如下：typedefcharDataType;structLNode{DataTypedata;LNode*next;};eatmat…h(huán)eadbatcat^數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第41頁。一旦p所指的結(jié)點變量不再需要了，應(yīng)該通過deletep；(或用free(p))釋放所指的結(jié)點變量空間。pdatanextLNode*p,*head;p為動態(tài)變量指針，它可以存放Lnode內(nèi)存塊的首地址，能利用標準函數(shù)使得p與一塊內(nèi)存空間關(guān)聯(lián)，即

p=newLNode;//C++p=(structLNode*)malloc(sizeof(structLNode));/*C*/new分配了一個類型為LNode的結(jié)點變量的空間并將其首地址放入指針變量p中。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第42頁。一、建立單鏈表

問題：假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，逐個輸入這些字符型的數(shù)據(jù)，并以換行符‘$’為輸入結(jié)束標記。動態(tài)地建立單鏈表的常用方法有如下兩種：1、頭插法建表該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當前鏈表的表頭上，直到讀入結(jié)束標志(比如$）為止。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第43頁。voidCreateList1(LNode*&h){charch;LNode*p; h=NULL;cin>>ch;while(ch!=$′){ p=newLNode; p–>data=ch;p–>next=h;h=p;cin>>ch;}}LNode*CreateList(){charch;LNode*h,*p;h=NULL;cin>>ch;while(ch!=‵$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}returnh;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第44頁。#include<iostream.h>structLNode{chardata;LNode*next;};LNode*CreateList(){charch;LNode*h,*p;h=NULL;cin>>ch;while(ch!=‵$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}returnh;}voidCreateList1(LNode*&h){charch;LNode*p; h=NULL;

cin>>ch;while(ch!=$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}}voidprint(LNode*h){LNode*p=h;while(p!=NULL){cout<<p->data<<‘‘;p=p->next;}cout<<endl;}voidmain(){LNode*h1,*h2;h1=CreateList();CreateList1(h2);print(h1);print(h2);}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第45頁。2、尾插法建表頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當前鏈表的表尾上。為此必須增加一個尾指針r，使其始終指向當前鏈表的尾結(jié)點。例：LNode*creat(){charch;LNode*p,*r,*head;head=r=NULL;cin>>ch;while(ch!=‘$’){p=newLNode;p–>data=ch;if(head==NULL)head=p;

elser->next=p;r=p;cin>>ch;}if(r!=NULL)r->next=NULL;returnhead;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第46頁。頭結(jié)點（哨兵結(jié)點）引入：增加一個表頭結(jié)點，數(shù)據(jù)域可根據(jù)需要使用或不用。特點：a、表中第一個結(jié)點和在表的其它位置上的操作一致，無需進行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點。因此空表和非空表的處理統(tǒng)一。NULLhead有頭結(jié)點的空表head=無頭結(jié)點的空表LNode*creat(){LNode*r,*h;charch;h=newLNode;r=h;cin>>ch;while(ch!=‘$’){r->next=newLNode;r=r->next;r->data=ch;cin>>ch;}r->next=NULL;returnh;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第47頁。上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，在實際使用時間，可作下列判定與處理：

p=newLNode;if(p==NULL)錯誤處理；

數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第48頁。二、查找運算1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當1<=i<=n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第49頁。LNode*getnode(head，i)//i>=1//在鏈表head中取第i個數(shù)據(jù)，鏈表有頭結(jié)點{

p=head;j=0;//計數(shù)用

while(p–>next&&j<i){p=p–>next;j++;}if(i==j)returnp;

elsereturnNULL;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第50頁。2、按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：LNode*locatenode(head，key){p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;

}該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復雜度的分析類似于按序號查找。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第51頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化xai-1ai數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第52頁。ai-1aixai-1aix數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第53頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq->next=p->next;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第54頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq->next=p->next;p->next=q;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第55頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq->next=p->next;p->next=q;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第56頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq->next=p->next;p->next=q;定位ai-1并將指針p指向它；數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第57頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq=newLNode;q->data=x;q->next=p->next;p->next=q;定位ai-1并將指針p指向它；數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第58頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化ai-1aixpqq=newLNode;q->data=x;q->next=p->next;p->next=q;p=getnode(head，i-1);功能：在頭指針為head的鏈表中定位第i-1個結(jié)點,并返回結(jié)點位置。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第59頁。三、插入運算

voidinsertnode(head，x，i){LNode*p，*q;p=getnode(head，i-1);if(p==NULL){cout<<“positionerror”<<endl; returnERROR;}q=newLNode;q–>data=x;q–>next=p–>next;p–>next=q;}LNode*getnode(head，i){p=head;j=0;//計數(shù)用

while(p–>next&&j<i){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第60頁。四、刪除運算刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第61頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第62頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第63頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第64頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;問題：鏈表的邏輯結(jié)構(gòu)已正確了，但結(jié)點ai空間丟了。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第65頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第66頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;r數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第67頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;r數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第68頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1pp->next=p->next->next;p=getnode(head，i-1);r=p->next;p->next=r->next;deleter;r數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第69頁。四、刪除運算voiddeletelist(head，i){LNode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;deleter;}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第70頁。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。作業(yè)：（1）鏈表是有序的，現(xiàn)在插入數(shù)據(jù)x，要求插入后仍然有序（2）鏈表是有序的，現(xiàn)在刪除數(shù)據(jù)x，若x不存在，輸出一段提示信息。要求：按鏈表有頭結(jié)點和無頭結(jié)點兩種情況分別寫出并上機調(diào)試通過。（3）鏈表逆轉(zhuǎn)（沒有頭結(jié)點）數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第71頁。五、靜態(tài)鏈1、靜態(tài)鏈表的概念用一維數(shù)組來實現(xiàn)線性鏈表，這種用一維數(shù)組表示的線性鏈表，稱為靜態(tài)鏈表。靜態(tài)：體現(xiàn)在表的容量是一定的。（數(shù)組的大?。╂湵恚翰迦肱c刪除同前面所述的動態(tài)鏈表方法相同2、靜態(tài)鏈表的類型定義#defineMAXSIZE1000//鏈表的最大長度

structComponent{

ElemTypedata;

intcur;};ComponentVList[MAXSIZE];數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第72頁。SLinkList類型的數(shù)組變量是結(jié)構(gòu)數(shù)組，每一數(shù)組分量包括兩個域：data：用于存儲線性表元素；cur：用于存儲直接后繼元素在數(shù)組中的位置靜態(tài)鏈表圖示0h=5數(shù)組下標靜態(tài)鏈表與線性鏈表的區(qū)別？？線性鏈表圖示地址a18a22a4-1a30123456789101010a11026a21014a40a310101012101410221024102610281030102010181016h=1020數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第73頁。例：靜態(tài)鏈表的操作設(shè)插入和刪除只在表的頭上進行（棧）h=7（5，7，2，3）（8，5，7，2，3）h=0表中加入x01234793-15123567891001234793-1512356789102.(1)VList[i].data=x;1.在VList中找空位置i(比如0)(2)VList[i].cur=h;x7(3)h=i;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第74頁?？瘴恢玫臉俗R：將所有空位置構(gòu)成鏈表，用av表示鏈首012342793-11058451-12365678910av=02.(1)Vlist[i].data=x;1.在VList中找空位置i(2)Vlist[i].cur=h;(3)h=i;if(av==-1)無空間處理else{i=av;av=VList[i].curVList[i].data=x;VList[i].cur=h;h=i;}刪除：if(h!=-1){x=VList[h].data; i=h; h=VList[i].cur;VList[i].cur=av;av=i;

}h=7空表初始化：開始，表是空的，所以：for(i=0;i<n-1;i++)a[i]=i+1;a[n-1]=-1;av=0;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第75頁。2.3.2循環(huán)鏈表循環(huán)鏈表是一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第76頁。⑴非空表⑵空表

在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)

a1an…h(huán)ead數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第77頁。在很多實際問題中，表的操作常常是在表的尾位置上進行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是rear–>next—>next和rear，顯然，查找時間都是O(1)。因此，實際中也常采用尾指針表示單循環(huán)鏈表.。

a1an…rear數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第78頁。

由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第79頁。2.3.3雙向鏈表

雙向鏈表(Doublelinkedlist):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：structDuLNode{datatypedata;DuLNode*prior，*next;};結(jié)點存儲前趨結(jié)點的地址存儲數(shù)據(jù)元素存儲后繼結(jié)點的地址指針域數(shù)據(jù)域指針域數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第80頁。

雙鏈表一般由頭指針唯一確定的，將頭結(jié)點和尾結(jié)點鏈接起來構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述：

p—>prior—>next=p=p—>next—>prior

L（c）非空的雙向循環(huán)鏈表

(b)空的雙向循環(huán)鏈表Lpabc數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第81頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxai-1aiq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第82頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;ai-1ai數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第83頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxai-1aiq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第84頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針所指的結(jié)點：ai-1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第85頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針所指的結(jié)點：ai-1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第86頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針所指的結(jié)點：ai-1

雙向鏈表的插入、刪除靈活；鏈表維護的工作量大，所需的存儲空間較大。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第87頁。2．4一元多項式的表示及相加Pn(x)=pnxn+pn-1xn-1+…

p1x+p0Qm(x)=qmxm+qm-1xm-1+…

q1x+q0一、一元多項式的表示多項式的操作是表處理的典型用例。數(shù)學上,一元多項式可按降冪寫成：（指數(shù)為正整數(shù)的情況）其中：pn、qm不為0數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第88頁。存儲結(jié)構(gòu)：用線性鏈表表示。增加頭結(jié)點，每個結(jié)點有coef:系數(shù)exp指數(shù)next：指針其中，頭結(jié)點的exp為-1。coefexpnext多項式A(x)=5x17+9x8+

3x+7ha51798317∧0-1數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第89頁。例：求兩多項式的和多項式

A(x)=5x17+9x8+3x+7B(x)=–9x8+22x7+8x二、一元多項式的相加算法一元多項式相加運算規(guī)則：指數(shù)相同的項系數(shù)相加A(x)B(x)相加的和多項式為

C(x)=A(x)+B(x)=5x17+22

x7+11x+7

設(shè)多項式A(x)，B(x)分別用帶表頭結(jié)點的線性鏈表ha,hb表示,完成:ha=ha+hb數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第90頁。一元多項式加法算法主要步驟分別對兩個鏈表ha、hb進行掃描，設(shè)工作指針pa、pb分別指向兩個多項式當前進行比較的結(jié)點，q指針指向pa的前驅(qū)，初始：

q=ha;pa=ha->next;pb=hb->next;若pa,pb都不為空：則比較兩者指數(shù)：

pa->exp>pb->exp：q,pa后移；pa->exp=pb->exp：將pb所指結(jié)點的系數(shù)“加”到pa所指結(jié)點的系數(shù)上；若和為0，則pa所指結(jié)點刪除。

q,pa,pb調(diào)整pa->exp<pb->exp：從表hb中復制pb所指結(jié)點的coef,exp，并將其插入到

ha表pa所指結(jié)點之前；若pb不空：hb表中從pb開始的結(jié)點插入到ha表尾上數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第91頁。intcomp(inta,intb){if(a>b)return-1;if(a==b)return0;elsereturn1;}PloyAdd(ha,hb){q=ha;pa=ha->next;pb=hb->next;while(pa!=NULL&&pb!=NULL)switch(comp(pa->exp,pb->exp)){case-1:q=pa;pa=pa->next; break;case0:pa->coef+=pb->coef;if(pa->coef==0){ q->next=pa->next; deletepa; pa=q;}elseq=pa; pa=pa->next; pb=pb->next; break;case1:r=newNode;r->coef=pb->coef;r->exp=pb->exp;q->next=r;r->next=pa;q=r;pb=pb->next;break;}while(pb!=NULL){r=newNode;r->coef=pb->coef;r->exp=pb->exp;q->next=r;r->next=pa;q=r;pb=pb->next;}}while改成：while(pb!=hb)在改成循環(huán)鏈后，此while可省去。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第92頁。1、線性表v的數(shù)據(jù)遞增有序，試將x插入表中并保持有序性（1）表順序表示（2）鏈表表示（3）帶有頭結(jié)點的鏈表2、寫一個線性表的轉(zhuǎn)置算法（順序和鏈表表示兩種情況）（a1,a2,….,an)變?yōu)椋╝n,an-1,….,a1)數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第93頁。3、寫一個類（用模板）實現(xiàn)順序表示的線性表。template<classT>classLi{ T*p; intlen; intmax;public:…….}數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第94頁。實習題目：

hc=ha*hb要求：（1）輸入形式：以系數(shù)指數(shù)<Enter>的遞減序輸入，最后以00<Enter>結(jié)束（2）輸出，見格式例：5x9-7x2+6x-5輸入為：輸出為：9-7210005X^9-7X^2+6X-5數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第95頁。第3章

棧和隊列棧和隊列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它們都來自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作受限”的線性表。棧在計算機的實現(xiàn)有多種方式：◆硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內(nèi)存的特殊區(qū)域來實現(xiàn)。這類堆棧容量有限，但速度很快；◆軟堆棧：這類堆棧主要在內(nèi)存中實現(xiàn)。堆棧容量可以達到很大。在實現(xiàn)方式上，又有動態(tài)方式和靜態(tài)方式兩種。本章將討論棧和隊列的基本概念、存儲結(jié)構(gòu)、基本操作以及這些操作的具體實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第96頁。3.1

棧3.1.1

棧的基本概念1

棧的概念

棧(Stack)：是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出LIFO

(LastInFirstOut)或先進后出FILO

(FirstInLastOut)線性表。

棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。

棧底(Bottom)：是固定端，又稱為表頭。

空棧：當表中沒有元素時稱為空棧。數(shù)據(jù)結(jié)構(gòu)-緒論線性表全文共146頁，當前為第97頁。

設(shè)棧S=(a1，a2，…an)，則a1稱為棧底元素，an為棧頂元素，如圖3-1所示。棧中元素按a1，a2，…an的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。即棧的修改是按后進先出的原則進行的。圖3-1順序棧示意圖a1a2aian????bottom