數(shù)據(jù)結構-線性表

數(shù)據(jù)結構第二章線性表內容提要線性表的類型定義2.1線性表的順序表示和實現(xiàn)2.2線性表的鏈式表示和實現(xiàn)2.3基本要求（1）掌握線性表的邏輯結構。（2）掌握順序存儲結構的操作及其效率分析。（3）掌握鏈式存儲結構的概念及操作。重點線性表的邏輯結構和存儲結構，線性表在順序結構和鏈式結構上實現(xiàn)基本操作的方法，從時間和空間復雜度的角度比較線性表兩種存儲結構的不同特點及其適用場合。

難點線性表在順序結構和鏈式結構上基本操作的算法實現(xiàn)。

基本要求、重點、難點線性結構的基本特征為:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅。

線性結構是一個數(shù)據(jù)元素的有序（次序）集線性表是一種最簡單的線性結構。2.1線性表的類型定義比較典型的線性結構：線性表、棧、隊列、串等。2.1線性表的類型定義

線性表(linear_list)是n個數(shù)據(jù)元素的有限序列，記作（a1,a2,…，ai-1，ai，ai+1，…，an）

其中：數(shù)據(jù)元素可以是各種類型（整、實、記錄類型等）2.1線性表的類型定義

例如：英文字母表(‘A’,‘B’,…,‘Z’)就是一個簡單的線性表，其中數(shù)據(jù)元素是單個英文字母。例如：一副撲克牌的點數(shù)（2，3，4…，J，Q，K，A），其中數(shù)據(jù)元素是每張牌的點數(shù)。例如：在較為復雜的線性表中，數(shù)據(jù)元素(dataelements)可以是由若干數(shù)據(jù)項組成的記錄類型。2.1線性表的類型定義

線性表的數(shù)學模型（形式定義）

含有n個數(shù)據(jù)元素的線性表是一個數(shù)據(jù)結構

linear_list=（D,R）其中：D={ai|ai∈ElemType

，1≤i≤n，n≥0} R=｛<ai,ai+1>|1≤i≤n-1}

說明：（1）線性表的數(shù)據(jù)元素可以是各種類型（原子類型、結構類型）

typedef

int

ElemType;

typedefcharElemType

等（2）同一線性表中的數(shù)據(jù)元素必須具有相同的特性，屬同一類型（3）關系R是一個有序偶對的集合，即對于非空的線性表（a1,a2,…，ai-1,ai,ai+1,…,an），ai-1

領先于ai，表示了數(shù)據(jù)元素之間的相鄰關系，稱ai-1

是ai的直接前驅，ai是ai-1的直接后繼（4）n表示線性表中數(shù)據(jù)元素的個數(shù)，n=0時稱為空表線性表的抽象數(shù)據(jù)類型定義如下：ADTList{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

結構初始化操作結構銷毀操作

引用型操作

加工型操作

}ADTList結構初始化操作

InitList(&L)

操作結果：構造一個空的線性表L。CreateList(&L,A[],n)

初始條件：A[]中存在線性表的n個數(shù)據(jù)元素。操作結果：構造一個含n個數(shù)據(jù)元素的線性表L。操作定義結構銷毀操作DestroyList(&L)初始條件：線性表L已存在。操作結果：銷毀線性表L。

操作定義ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作操作定義

ListEmpty(L)（線性表判空）初始條件：操作結果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。ListLength(L)（求線性表的長度）初始條件：操作結果：線性表L已存在。返回線性表L

中元素個數(shù)。操作定義

PriorElem(L,cur_e,&pre_e)（求前驅）初始條件：操作結果：線性表L已存在。若cur_e

是L中的元素，則以pre_e

帶回它的前驅，否則操作失敗，pre_e無定義。NextElem(L,cur_e,&next_e)（求后繼）初始條件：操作結果：線性表L已存在。若cur_e是L中的元素，則以next_e帶回它的后繼，否則操作失敗，next_e無定義。操作定義

GetElem(L,i,&e)（求線性表中某個元素）初始條件：操作結果：線性表L已存在以e

帶回L

中第i

個數(shù)據(jù)元素值。LocateElem(L,e,compare())（定位函數(shù)）初始條件：操作結果：線性表L已存在,compare()為判定函數(shù)。返回L中第1個與e滿足關系

compare()的元素的位序，若不存在這樣的元素，則返回0。且1≤i≤LengthList(L)。操作定義

ListTraverse(L,visit())（遍歷線性表）初始條件：操作結果：線性表L已存在,visit()為數(shù)據(jù)元素的訪問函數(shù)。依次對L

的每個數(shù)據(jù)元素調用函數(shù)visit()，一旦visit()失敗，則遍歷操作失敗。操作定義ClearList(&L)(線性表置空)ListInsert(&L,i,e) (插入數(shù)據(jù)元素)PutElem(&L,i,e) (改變數(shù)據(jù)元素的值)ListDelete(&L,i,&e)(刪除數(shù)據(jù)元素)加工型操作操作定義

ClearList(&L)初始條件：操作結果：線性表L已存在。將L重置為空表。PutElem(&L,i,e)初始條件：操作結果：L中第i個元素賦值和e相同。線性表L已存在，且1≤i≤LengthList(L)。操作定義

ListInsert(&L,i,e)初始條件：操作結果：線性表L已存在在L的第i個元素之前插入新的元素e,L的長度增1。

ListDelete(&L,i,&e)初始條件：操作結果：線性表L已存在刪除L中第i個元素，并以e帶回其值,L的長度減1。,1≤i≤LengthList(L)+1。,1≤i≤LengthList(L)。操作定義

假設:有兩個集合A和B分別用兩個線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個新的集合A＝A∪B。例2-1

可利用上述定義的線性表實現(xiàn)其它更復雜的操作。

即要求對線性表作如下操作：

擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。操作示例（一）1．從線性表LB中依次察看每個數(shù)據(jù)元素;2．依值在線性表LA中進行查訪;

3．若不存在，則插入之。GetElem(LB,i,&e)

LocateElem(LA,e,equal)

ListInsert(&LA,n+1,e)操作步驟：

GetElem(Lb,i,&e);

//取Lb中第i個數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之void

union(List

&La,ListLb){

La_len=ListLength(La);

//求線性表的長度

Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){}}

//union算法

已知一個非純集合B，試構造一個純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合。例

2-2從集合B

取出元素放入集合A要求集合A中同樣元素不能有兩個以上因此，算法的策略和例2-1相同.操作示例（二）void

union(List

&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}

//union

GetElem(Lb,i,&e);//取Lb中第i個數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素，則插入之for(i=1;i<=Lb_len;i++){}InitList(La);//構造(空的)線性表LA算法例2-3

已知線性表LA和LB中的元素按值非降序排列,將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按非降序排列.

LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)

則

LC=(2,3,5,6,8,8,9,11,11,15,20)操作示例（三）算法思想設表LC是一個空表，為使LC也是非遞減有序排列，設兩個位置指針i、j分別指向表LA和LB中的元素，k指向LC中的元素

ijk

LA=(2,2,3)LB=(1,3,3,4)LC=（）(1)循比LA.list［i］>LB.list［j］:則先將LB.list［j］插入到表LC中環(huán)較LA.list［i］≤LB.list［j］:則先將LA.list［i］插入到表LC中

(2)直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中

void

MergeList(ListLa,ListLb,List&Lc){

//本算法將非遞減的有序表La和Lb歸并為Lc}

//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{歸并1}while(i<=La_len){歸并2}//若La還有剩余元素while(j<=Lb_len){歸并3}

//若Lb還有剩余元素InitList(Lc);//構造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);算法歸并1

GetElem(La,i,&ai);

GetElem(Lb,j,&bj);

if(ai<=bj){//將ai

插入到Lc

中

ListInsert(Lc,++k,ai);++i;} else{//將bj

插入到Lc

中

ListInsert(Lc,++k,bj);++j;}

GetElem(La,i++,&ai);

ListInsert(Lc,++k,ai);

GetElem(Lb,j++,&bj);

ListInsert(Lc,++k,bj);

歸并2歸并3算法（續(xù)）2.2線性表類型的實現(xiàn)順序映象最簡單的一種順序映象方法是：

令y的存儲位置和x的存儲位置相鄰。順序映象——

以x的存儲位置和y的存儲位置之間某種關系表示邏輯關系<x,y>。2.2線性表類型的實現(xiàn)順序映象

線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系。

采用順序存儲結構的線性表通常稱為順序表。

a1a2

…ai-1

ai

…an線性表的起始地址稱作線性表的基地址以“存儲位置相鄰”表示有序對<ai-1，ai>

即：

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

（一個數(shù)據(jù)元素所占存儲量）所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置。

LOC(ai)=

LOC(a1)+(i-1)×l

↑基地址2.2線性表類型的實現(xiàn)順序映象圖線性表的順序存儲結構示意圖

lll2.2線性表類型的實現(xiàn)順序映象順序映像的C語言描述typedef

struct{

}SqList;#defineLIST_INIT_SIZE80//線性表存儲空間的初始分配量#defineLISTINCREMENT10//線性表存儲空間的分配增量ElemType

*elem;//存儲空間基址int

length;//當前長度int

listsize;//當前分配的存儲容量

(以sizeof(ElemType)為單位)

順序存儲結構可以借助于高級程序設計語言中的一維數(shù)組來表示。線性表的順序存儲結構用C語言定義如下：Status

InitList_Sq(SqList

&L){

//構造一個空的線性表

}//InitList_Sq算法時間復雜度：O(1)L.elem=(ElemType*)malloc

(LIST_

INIT_SIZEsizeof

(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;需要包含#include<malloc.h>需要包含#include<stdlib.h>線性表操作InitList的實現(xiàn)：23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，查詢操作是將順序表中的元素逐個和給定值e相比較。線性表操作LocateElem

的實現(xiàn)：

int

LocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}//LocateElem_Sqi=1;//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;函數(shù)指針！線性表操作LocateElem

的實現(xiàn)：(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)a1a2

…ai-1

ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加線性表操作ListInsert的實現(xiàn)：算法分析:插入元素時，線性表的邏輯結構發(fā)生什么變化？

Status

ListInsert_Sq(SqList

&L,inti,ElemTypee){//

在順序表L的第i個元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1}

//ListInsert_Sq

算法時間復雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1returnOK;……線性表操作ListInsert的實現(xiàn)：考慮移動元素的平均情況:

假設在第

i個元素之前插入的概率為，

則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望值為：

若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：if(L.length>=L.listsize){//當前存儲空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲容量}if(i<1||i>L.length+1)returnERROR;//

插入位置不合法2118307542568721183075例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,

ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

線性表操作ListDelete的實現(xiàn)：算法分析：刪除元素時，線性表的邏輯結構發(fā)生什么變化？a1a2

…ai-1

ai

ai+1

…anStatus

ListDelete_Sq(SqList

&L,inti,ElemType

&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被刪除元素之后的元素左移--L.length;//表長減1算法時間復雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法考慮移動元素的平均情況:

假設刪除第

i個元素的概率為

,則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為：

若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)p大家來思考問題？？？問題：討論順序表的優(yōu)缺點？回答：優(yōu)點：順序存儲結構的線性表是可以隨機存取其中的任意元素。缺點：（1）數(shù)據(jù)元素最大個數(shù)通常需預先確定，存儲空間不便于擴充。（2）插入與刪除運算的效率很低。46

練習一下吧…判斷：1．線性表的邏輯順序與存儲順序總是一致的。（）

2．順序存儲的線性表可以按序號隨機存取。（）

3．順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。（）

4．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。（）

5．在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（）

6．在線性表的順序存儲結構中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關。（）

小結

線性表的順序存儲結構中任意數(shù)據(jù)元素的存儲地址可由公式直接導出，因此順序存儲結構的線性表是可以隨機存取其中的任意元素。但是，順序存儲結構也有一些不方便之處，主要表現(xiàn)在：（1）數(shù)據(jù)元素最大個數(shù)通常需預先確定，使得高級程序設計語言編譯系統(tǒng)需預先分配相應的存儲空間；（2）插入與刪除運算的效率很低。為了保持線性表中的數(shù)據(jù)元素順序，在插入操作和刪除操作時需移動大量數(shù)據(jù)。對于插入和刪除操作頻繁的線性表、將導致系統(tǒng)的運行速度難以提高；（3）存儲空間不便于擴充。當為一個線性表分配順序存儲空間后，若線性表的存儲空間已滿，但還需要插入新的元素，則會發(fā)生“上溢”錯誤。2.3線性表類型的實現(xiàn)

鏈式映象2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表問題引入1.順序存儲結構通常需要在程序編譯前就規(guī)定好數(shù)據(jù)元素的多少(即數(shù)組長度)，事先難估計，多了造成浪費存儲空間，少了不夠用；2.順序存儲結構在插入和刪除運算中可能需要大量移動元素，降低程序執(zhí)行效率?；谏鲜鰞牲c，需要引入鏈式存儲結構。注意：與順序存儲結構的不同點是數(shù)據(jù)元素在內存中的位置不一定相鄰，即每一個數(shù)據(jù)元素都有一個鏈接字段，用來存放下一個數(shù)據(jù)元素的地址，形成鏈表結構。1線性表的鏈式存儲表示

采用一組任意的存儲單元來存放線性表中的數(shù)據(jù)元素，這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素間的邏輯關系通過附加信息－指針來描述。數(shù)據(jù)元素除了具有代表其本身信息的數(shù)據(jù)域外，還有一個用來指示邏輯關系的指針域。這樣的存儲結構稱為結點。數(shù)據(jù)域data指針域next結點node2.3.1線性鏈表

以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。

a1a2…...an^

有時為了操作方便，在第一個結點之前虛加一個“頭結點”，以指向頭結點的指針為鏈表的頭指針?？罩羔樉€性表為空表時，頭結點的指針域為空2.3.1線性鏈表鏈式存儲通過每個結點的指針域將線性表的n個結點按其邏輯順序鏈接在一起，稱為線性表的鏈式存儲表示。由于此類鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表。頭指針頭指針何謂頭指針、頭結點和首元結點？頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。

單鏈表可由一個頭指針唯一確定。頭結點是在鏈表的首元結點之前附設的一個結點；數(shù)據(jù)域或空或存放表長等信息;首元結點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結點。

頭指針頭結點首元結點a1一個線性表的邏輯結構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結構用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個結點的指針，因此關鍵是要尋找第一個結點的地址。7ZHAOH31∴頭指針的值是31舉例上例鏈表的結構示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結點②

有頭結點答：1.在鏈表中設置頭結點有什么好處？2.如何表示空表？頭結點即在鏈表的首元結點之前附設的一個結點，該結點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結點進行統(tǒng)一處理，編程更方便。答：無頭結點時，當頭指針的值為空時表示空表；有頭結點時，當頭結點的指針域為空時表示空表。^頭指針^頭指針頭結點無頭結點有頭結點討論：線性鏈表（單鏈表）：結點中只有一個指針域不帶頭結點的單鏈表，頭指針指向第一個數(shù)據(jù)元素帶頭結點的單鏈表，頭指針指向頭結點，頭結點的數(shù)據(jù)域為空，指針域為第一個數(shù)據(jù)元素的地址不帶頭結點的單鏈表為空表，則頭指針為空，而帶頭結點的，則頭結點的指針域為空2.3.1線性鏈表結點和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針typedef

struct

LNode{

ElemType

data；/*結點的數(shù)據(jù)域*/

struct

LNode

*next；/*結點的指針域*/}LNode,*LinkList;若LNode*p，則p的含義是什么？若p的值非空，則表明p指向某個結點，p->data表示p所指結點中的數(shù)據(jù)域，p->next表示p所指結點中的指針域，若非空，則指向其"后繼"結點。

線性鏈表是一種動態(tài)存儲結構，所占用的存儲空間是在程序的執(zhí)行過程中得到的，當線性鏈表要增加一個結點時，向系統(tǒng)申請一個存儲空間，刪除結點時要將空間釋放。LNode*p;p=(LNode*)malloc(sizeof(LNode));free(p);鏈表結點的申請與釋放

1.線性鏈表的初始化

建立一個空的線性鏈表。對于帶頭結點的單鏈表，設定一個頭指針指向頭結點。并且設置頭結點的指針域為空。voidInitList(LinkList&H){H=(LNode*)malloc(sizeof(LNode));/*申請一個頭結點*/if(!H)returnERROR;/*申請失敗*/H->next=NULL;/*頭結點的指針域置空*/}單鏈表操作的實現(xiàn)LNode*create_list(intn){

LNode*head,*p,*q;

inti; p=(LNode*)malloc(sizeof(LNode));head=p;

for(i=1;i<=n,i++){

q=(LNode*)malloc(sizeof(LNode));

scanf(&q->data);q->next=NULL; p->next=q;p=q;}

return(head);}建立結點的算法2.建立有n個結點的單鏈表單鏈表操作的實現(xiàn)鏈表是一個動態(tài)的結構，它不需要予分配空間，因此生成鏈表的過程是一個結點“逐個插入”的過程。void

ClearList(&L){ while(L->next){

p=L->next; L->next=p->next;

}}//ClearListfree(p);單鏈表操作的實現(xiàn)3.重新置單鏈表為一個空表從線性鏈表的第一個結點開始，依次查找是否存在與給定值相同的元素，若存在，返回OK,否則返回ERROR。int

Search_list(LinkListH,inte){

LinkListp; p=H->next;

while(p)

if(p->data==e)returnOK; elsep=p->next; returnERROR;}單鏈表操作的實現(xiàn)4.線性鏈表的查找5.單鏈表的插入在鏈表中插入一個元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結點應預先生成：S=(LinkList)malloc(m);S->data=x;單鏈表操作的實現(xiàn)StatusListInsert(LinkList&L,inti,ElemTypee)/*在單鏈表L的第i個位置上插入值為e的元素*/{ p=L;j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; returnOK;}單鏈表結點插入的演示單鏈表操作的實現(xiàn)5.單鏈表的刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結點相連free(q)；//刪除b結點，徹底釋放p->next思考：省略free(q)語句行不行？(p->next)->next××單鏈表操作的實現(xiàn)StatusListDelete(LinkList&L,inti,ElemType&e){ p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q); returnOK;}單鏈表結點的刪除演示單鏈表操作的實現(xiàn)算法要求：已知：線性表A、B，分別由單鏈表LA,LB

存儲，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設線性表C由單鏈表LC

存儲。假設：A=（3，5，8，11），B=（2，6，8，9，11）預測：合并后C=（2,3,5,6,8,8,9,11，11）6.鏈表的歸并單鏈表操作的實現(xiàn)用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結點單鏈表操作的實現(xiàn)算法分析：算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針搜索兩個鏈表；比較：比較結點數(shù)據(jù)域中數(shù)據(jù)的大小；插入：將兩個結點中數(shù)據(jù)小的結點插入新鏈表。單鏈表操作的實現(xiàn)La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當前結點Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa單鏈表操作的實現(xiàn)

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//按值排序的單鏈表LA,LB，歸并為LC后也按值排序

free(Lb);//釋放Lb的頭結點}//MergeList_Lpc->next=pa?pa:pb;//插入剩余段

while(pa&&pb)//將pa、pb結點按大小依次插入C中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next}}pa=La-->next;pb=Lb-->next;Lc=pc=La；//初始化

單鏈表操作的實現(xiàn)單鏈表的特點

根據(jù)實際需求來分配存儲空間；插入和刪除不需要移動大量的數(shù)據(jù)元素；只需要修改相應的指針即可。適合存儲結構多變或變化較大的情形。無法實現(xiàn)隨機存取，每次的查找過程均需從頭指針開始。

循環(huán)鏈表(CircularLinkedList)是單鏈表的另一種形式，它是一個首尾相接的鏈表。其特點是將單鏈表最后一個結點的指針域由NULL改為指向頭結點或線性表中的第一個結點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。為了使某些操作實現(xiàn)起來方便，在循環(huán)單鏈表中也可設置一個頭結點。這樣，空循環(huán)鏈表僅由一個自成循環(huán)的頭結點表示。2.3.2循環(huán)鏈表

帶頭結點的循環(huán)單鏈表2.3.2循環(huán)鏈表單鏈表與循環(huán)鏈表的異同：

（1）操作基本相同

（2）差別：

a.查找單鏈表：從表頭開始查表頭結點O(1)

查表尾結點

O(n)

循環(huán)鏈表：從任一點出發(fā)均可

用尾指針表示查表尾O(1)rear

查表頭O(1)rear->next

b.判定是否到鏈尾：單鏈表p->next==NULL

循環(huán)鏈表p->next==L

c.鏈表的合并2.3.2循環(huán)鏈表例有兩個帶頭結點的循環(huán)單鏈表A、B，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為A。

算法思想1（無尾指針必需的方法）：先找到兩個鏈表的尾，并分別由指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結點鏈接起來，并修改第二個表的尾q，使它的鏈域指向第一個表的頭結點。a1a2a3……^nanb1b2b3……^bm

Bm

A

(1)p

(2)q

(3)

(4)2.3.2循環(huán)鏈表

采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)行時間是O(n)。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需要修改指針，無需遍歷，其執(zhí)行時間是O(1)。a1a2a3……nanb1b2b3……bm

Bm

A

p(1)

(2)

釋放（3）

(4)

A(5)2.3.2循環(huán)鏈表voidmerge（LinkList&A,LinkList&B){/*此算法將兩個鏈表首尾連接起來*/

LNode*p;p=A->next;/*保存鏈表A的頭結點地址*/A->next=B->next->next;/*鏈表B的開始結點鏈到鏈表A的終端結點之后*/

free(B->next);/*釋放鏈表B的頭結點*/B->next=p;/*鏈表A的頭結點鏈到鏈表B的終端結點之后*/A=B;}2.3.2循環(huán)鏈表2.3.3雙向鏈表

循環(huán)單鏈表的出現(xiàn)，雖然能夠實現(xiàn)從任一結點出發(fā)沿著鏈能找到其前驅結點，但時間耗費是O(n)。如果希望從表中快速確定某一個結點的前驅，另一個解決方法就是在單鏈表的每個結點里再增加一個指向其前驅的指針域。這樣形成的鏈表中就有兩條方向不同的鏈，我們可稱之為雙(向)鏈表(DoubleLinkedList)。

data數(shù)據(jù)域雙向鏈表結點結構：aiprior指向前驅

next

指向后繼雙鏈表的結構定義如下：typedef

struct

DuLNode{

ElemTypedata;

struct

DuLNode*prior

struct

DuLNode*next;}DuLNode,*DuLinkList;

由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結點的直接前驅結點與直接后繼結點變得非常方便。設指針p指向雙鏈表中某一結點，則有下式成立：

p->prior->next=p=p->next->priorp2.3.2雙向鏈表

1.雙向鏈表的插入操作

雙向鏈表插入操作

2.3.2雙向鏈表

s=newLNo