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

數(shù)據(jù)結(jié)構(gòu)第二章線性表內(nèi)容提要線性表的類型定義2.1線性表的順序表示和實(shí)現(xiàn)2.2線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3基本要求（1）掌握線性表的邏輯結(jié)構(gòu)。（2）掌握順序存儲(chǔ)結(jié)構(gòu)的操作及其效率分析。（3）掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念及操作。重點(diǎn)線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法，從時(shí)間和空間復(fù)雜度的角度比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。

難點(diǎn)線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上基本操作的算法實(shí)現(xiàn)。

基本要求、重點(diǎn)、難點(diǎn)線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個(gè)“第一元素”；2．集合中必存在唯一的一個(gè)“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。

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

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

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

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

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

含有n個(gè)數(shù)據(jù)元素的線性表是一個(gè)數(shù)據(jù)結(jié)構(gòu)

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

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

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

typedef

int

ElemType;

typedefcharElemType

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

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

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

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

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作

加工型操作

}ADTList結(jié)構(gòu)初始化操作

InitList(&L)

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

初始條件：A[]中存在線性表的n個(gè)數(shù)據(jù)元素。操作結(jié)果：構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的線性表L。操作定義結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表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)（線性表判空）初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。ListLength(L)（求線性表的長(zhǎng)度）初始條件：操作結(jié)果：線性表L已存在。返回線性表L

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

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

是L中的元素，則以pre_e

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

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

帶回L

中第i

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

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

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

的每個(gè)數(shù)據(jù)元素調(diào)用函數(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)初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。PutElem(&L,i,e)初始條件：操作結(jié)果：L中第i個(gè)元素賦值和e相同。線性表L已存在，且1≤i≤LengthList(L)。操作定義

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

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

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

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

即要求對(duì)線性表作如下操作：

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

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

LocateElem(LA,e,equal)

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

GetElem(Lb,i,&e);

//取Lb中第i個(gè)數(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);

//求線性表的長(zhǎng)度

Lb_len=ListLength(Lb);

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

//union算法

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

2-2從集合B

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

union(List

&La,ListLb){

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

//union

GetElem(Lb,i,&e);//取Lb中第i個(gè)數(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);//構(gòu)造(空的)線性表LA算法例2-3

已知線性表LA和LB中的元素按值非降序排列,將LA和LB歸并為一個(gè)新的線性表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)操作示例（三）算法思想設(shè)表LC是一個(gè)空表，為使LC也是非遞減有序排列，設(shè)兩個(gè)位置指針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)直到其中一個(gè)表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中

void

MergeList(ListLa,ListLb,List&Lc){

//本算法將非遞減的有序表La和Lb歸并為L(zhǎng)c}

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

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

//若Lb還有剩余元素InitList(Lc);//構(gòu)造空的線性表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線性表類型的實(shí)現(xiàn)順序映象最簡(jiǎn)單的一種順序映象方法是：

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

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

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

采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。

a1a2

…ai-1

ai

…an線性表的起始地址稱作線性表的基地址以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：

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

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

LOC(ai)=

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

↑基地址2.2線性表類型的實(shí)現(xiàn)順序映象圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖

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

struct{

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

*elem;//存儲(chǔ)空間基址int

length;//當(dāng)前長(zhǎng)度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

(以sizeof(ElemType)為單位)

順序存儲(chǔ)結(jié)構(gòu)可以借助于高級(jí)程序設(shè)計(jì)語言中的一維數(shù)組來表示。線性表的順序存儲(chǔ)結(jié)構(gòu)用C語言定義如下：Status

InitList_Sq(SqList

&L){

//構(gòu)造一個(gè)空的線性表

}//InitList_Sq算法時(shí)間復(fù)雜度：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的實(shí)現(xiàn)：23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，查詢操作是將順序表中的元素逐個(gè)和給定值e相比較。線性表操作LocateElem

的實(shí)現(xiàn)：

int

LocateElem_Sq(SqListL,ElemTypee,

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

//

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

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

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

的實(shí)現(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>表的長(zhǎng)度增加線性表操作ListInsert的實(shí)現(xiàn)：算法分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

Status

ListInsert_Sq(SqList

&L,inti,ElemTypee){//

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

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

//ListInsert_Sq

算法時(shí)間復(fù)雜度為: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;//表長(zhǎng)增1returnOK;……線性表操作ListInsert的實(shí)現(xiàn)：考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率為，

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

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

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

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}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>表的長(zhǎng)度減少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

線性表操作ListDelete的實(shí)現(xiàn)：算法分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(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;//表長(zhǎng)減1算法時(shí)間復(fù)雜度為:

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

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

假設(shè)刪除第

i個(gè)元素的概率為

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

若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：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)缺點(diǎn)？回答：優(yōu)點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)的線性表是可以隨機(jī)存取其中的任意元素。缺點(diǎn)：（1）數(shù)據(jù)元素最大個(gè)數(shù)通常需預(yù)先確定，存儲(chǔ)空間不便于擴(kuò)充。（2）插入與刪除運(yùn)算的效率很低。46

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

2．順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。（）

3．順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。（）

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

5．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。（）

6．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。（）

小結(jié)

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

鏈?zhǔn)接诚?.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表問題引入1.順序存儲(chǔ)結(jié)構(gòu)通常需要在程序編譯前就規(guī)定好數(shù)據(jù)元素的多少(即數(shù)組長(zhǎng)度)，事先難估計(jì)，多了造成浪費(fèi)存儲(chǔ)空間，少了不夠用；2.順序存儲(chǔ)結(jié)構(gòu)在插入和刪除運(yùn)算中可能需要大量移動(dòng)元素，降低程序執(zhí)行效率。基于上述兩點(diǎn)，需要引入鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。注意：與順序存儲(chǔ)結(jié)構(gòu)的不同點(diǎn)是數(shù)據(jù)元素在內(nèi)存中的位置不一定相鄰，即每一個(gè)數(shù)據(jù)元素都有一個(gè)鏈接字段，用來存放下一個(gè)數(shù)據(jù)元素的地址，形成鏈表結(jié)構(gòu)。1線性表的鏈?zhǔn)酱鎯?chǔ)表示

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

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

a1a2…...an^

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針。空指針線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?.3.1線性鏈表鏈?zhǔn)酱鎯?chǔ)通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示。由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表。頭指針頭指針何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。

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

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

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

struct

LNode{

ElemType

data；/*結(jié)點(diǎn)的數(shù)據(jù)域*/

struct

LNode

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

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

1.線性鏈表的初始化

建立一個(gè)空的線性鏈表。對(duì)于帶頭結(jié)點(diǎn)的單鏈表，設(shè)定一個(gè)頭指針指向頭結(jié)點(diǎn)。并且設(shè)置頭結(jié)點(diǎn)的指針域?yàn)榭铡oidInitList(LinkList&H){H=(LNode*)malloc(sizeof(LNode));/*申請(qǐng)一個(gè)頭結(jié)點(diǎn)*/if(!H)returnERROR;/*申請(qǐng)失敗*/H->next=NULL;/*頭結(jié)點(diǎn)的指針域置空*/}單鏈表操作的實(shí)現(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);}建立結(jié)點(diǎn)的算法2.建立有n個(gè)結(jié)點(diǎn)的單鏈表單鏈表操作的實(shí)現(xiàn)鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過程。void

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

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

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

Search_list(LinkListH,inte){

LinkListp; p=H->next;

while(p)

if(p->data==e)returnOK; elsep=p->next; returnERROR;}單鏈表操作的實(shí)現(xiàn)4.線性鏈表的查找5.單鏈表的插入在鏈表中插入一個(gè)元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結(jié)點(diǎn)應(yīng)預(yù)先生成：S=(LinkList)malloc(m);S->data=x;單鏈表操作的實(shí)現(xiàn)StatusListInsert(LinkList&L,inti,ElemTypee)/*在單鏈表L的第i個(gè)位置上插入值為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;}單鏈表結(jié)點(diǎn)插入的演示單鏈表操作的實(shí)現(xiàn)5.單鏈表的刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點(diǎn)相連free(q)；//刪除b結(jié)點(diǎn)，徹底釋放p->next思考：省略free(q)語句行不行？(p->next)->next××單鏈表操作的實(shí)現(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;}單鏈表結(jié)點(diǎn)的刪除演示單鏈表操作的實(shí)現(xiàn)算法要求：已知：線性表A、B，分別由單鏈表LA,LB

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

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

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)單鏈表操作的實(shí)現(xiàn)算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。單鏈表操作的實(shí)現(xiàn)La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

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

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

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

while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入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；//初始化

單鏈表操作的實(shí)現(xiàn)單鏈表的特點(diǎn)

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

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

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

（1）操作基本相同

（2）差別：

a.查找單鏈表：從表頭開始查表頭結(jié)點(diǎn)O(1)

查表尾結(jié)點(diǎn)

O(n)

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

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

查表頭O(1)rear->next

b.判定是否到鏈尾：?jiǎn)捂湵韕->next==NULL

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

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

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

Bm

A

(1)p

(2)q

(3)

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

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

Bm

A

p(1)

(2)

釋放（3）

(4)

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

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

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

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

data數(shù)據(jù)域雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)：aiprior指向前驅(qū)

next

指向后繼雙鏈表的結(jié)構(gòu)定義如下：typedef

struct

DuLNode{

ElemTypedata;

struct

DuLNode*prior

struct

DuLNode*next;}DuLNode,*DuLinkList;

由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)與直接后繼結(jié)點(diǎn)變得非常方便。設(shè)指針p指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立：

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

1.雙向鏈表的插入操作

雙向鏈表插入操作

2.3.2雙向鏈表

s=newLNo