第2章線性表(修改)

第2章線性表●

本章要點(diǎn)

●

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

●線性表的順序存儲(chǔ)

●

線性表的鏈?zhǔn)酱鎯?chǔ)

●

順序表和鏈表的比較●

本章難點(diǎn)

●

順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)●

2.1線性表的邏輯結(jié)構(gòu)●2.1.1線性表的類型定義線性表是一種線性結(jié)構(gòu)，線性結(jié)構(gòu)的數(shù)據(jù)元素之間是一種線性關(guān)系，線性關(guān)系的特點(diǎn)如下：

●在一個(gè)線性表中的數(shù)據(jù)元素的類型是相同的，數(shù)據(jù)元素一個(gè)接一個(gè)的排列。

●存在一個(gè)唯一的被稱作“第一個(gè)”的數(shù)據(jù)元素。

●存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素。

●除第一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；除最后一個(gè)之外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。一個(gè)線性表是n(n≥0)個(gè)同類型數(shù)據(jù)元素a1,a2,a3,…，an的有限序列。記作：（a1,a2,a3,…,an）從定義可以看出，線性表強(qiáng)調(diào)兩個(gè)特性：（1）任何數(shù)據(jù)元素ai

(i=1,…，n)必須是同類型的數(shù)據(jù)，例如，如果是記錄，則必須是含有相同數(shù)據(jù)項(xiàng)的記錄；如果是整數(shù)，則必須都是整數(shù)，不能將不同性質(zhì)的數(shù)據(jù)列在一個(gè)線性表內(nèi)。（2）另一個(gè)是數(shù)據(jù)元素的有序性，數(shù)據(jù)元素在表中的位置決定了它的序號(hào)。按照這個(gè)次序，元素ai-1

稱為ai

的直接前趨，ai

稱為ai-1

的直接后繼（i=1,2,3,…，n）。a1是表中第一個(gè)元素，它沒(méi)有前趨；an是表中最后一個(gè)元素，它沒(méi)有后繼。表中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。長(zhǎng)度為0的線性表稱為空表。稱i為ai在線性表中的位序?！?.1.1線性表的類型定義

【例1】英文字母表（A，B，…，Z）是線性表，表中每個(gè)字母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）

【例2】一副撲克牌的點(diǎn)數(shù)（2，3，…，10，J，Q，K，A）也是一個(gè)線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)數(shù)

【例3】學(xué)生成績(jī)表中，每個(gè)學(xué)生及其成績(jī)是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。將數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表成為文件。舉例其抽象數(shù)據(jù)類型的定義如下：

ADTList{

數(shù)據(jù)對(duì)象：Data＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈Data,i=2,...,n}}

線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一個(gè)集合即可。

●2.1.1線性表的類型定義數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層次上的，而運(yùn)算的具體實(shí)現(xiàn)是建立在存儲(chǔ)結(jié)構(gòu)上的，每一種操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲(chǔ)結(jié)構(gòu)之后才能完成。對(duì)于線性表，常用的運(yùn)算有如下幾種：(1)置空表（結(jié)構(gòu)初始化）

init_seqlist(L)；

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。⑵求線性表的長(zhǎng)度。

list_length(L);初始條件：線性表L已存在。操作結(jié)果：返回L中元素個(gè)數(shù)?！?.1.2線性表的基本操作⑶定位:訪問(wèn)線性表的第i個(gè)元素。

get_node(L,i);初始條件：線性表L已存在。操作結(jié)果：返回L中第i個(gè)元素的值或地址。⑷查找:在線性表中查找滿足某種條件的數(shù)據(jù)元素。

location_list(L,x);

初始條件：線性表L已存在。操作結(jié)果：返回L中值為給定值x的數(shù)據(jù)元素。●2.1.2線性表的基本操作⑸插入:在線性表的第i個(gè)元素之前，插入一個(gè)同類型的元素。

insert_list(L,i,x);初始條件：線性表L已存在。操作結(jié)果：在L的第i個(gè)位置插入一個(gè)值為x的新元素。⑹刪除:刪除線性表中第i個(gè)元素。

delete_list(L,i);初始條件：線性表L已存在。操作結(jié)果：在L中刪除序號(hào)為i的數(shù)據(jù)元素。⑺清除表:將已有線性表變?yōu)榭毡恚磩h除表中所有元素。

●2.1.2線性表的基本操作

一種數(shù)據(jù)結(jié)構(gòu)只有在內(nèi)存中正確表示出來(lái)，才能實(shí)現(xiàn)其基本操作。數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示通常有兩種形式，即順序存儲(chǔ)表示和鏈?zhǔn)酱鎯?chǔ)表示。線性表的順序表示又稱為順序表。

2.2.1順序表

用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，這種存儲(chǔ)方式稱為線性表的順序存儲(chǔ)結(jié)構(gòu)。它以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的。

●

2.2線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下基本特點(diǎn)：(1)存儲(chǔ)空間必須是連續(xù)的，預(yù)分配；(2)邏輯順序與物理順序一致，用物理上的相鄰來(lái)表示邏輯上的線性關(guān)系。(3)任意相鄰元素之間無(wú)空閑空間，且相距為L(zhǎng)(4)已知基地址，可以計(jì)算出任意元素的存儲(chǔ)地址a1a2…ai-1aiai+1…an…length-1線性表的順序存儲(chǔ)設(shè)a1的存儲(chǔ)地址為L(zhǎng)oc(a1)，稱為基址，每個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)單元，則第i個(gè)數(shù)據(jù)元素的地址為：

Loc(ai)＝Loc(a1)+(i-1)*d１≤i≤n

已知順序表的首地址和每個(gè)元素所占地址單元的個(gè)數(shù)，就可求出第i個(gè)數(shù)據(jù)元素的地址?！?.2.1順序表所以稱順序表為一種隨機(jī)存取的結(jié)構(gòu)知識(shí)點(diǎn)回顧:用typedef定義類型可以用typedef聲明新的類型名來(lái)代替已有的類型名。例1：typedef

intCOUNT;COUNTI,j;例2：typedef

struct{intmonth;

intday;

intyear;}DATE;新類型名DATEDATEbirthday;DATE*p;說(shuō)明：對(duì)于上結(jié)構(gòu)體，typedef

后跟一個(gè)無(wú)命名的結(jié)構(gòu)體類型例3：typedef

structNode{elemtypedata;

structNode*next;}ListNode,*LinkList;Typedef與#define區(qū)別如：Typedef

intCOUNT;和#defineCOUNTint

二者不同#define是在預(yù)編譯時(shí)處理的，只能做簡(jiǎn)單的字符串替換。而typedef是在編譯時(shí)處理的，它可以像定義變量的方法那樣聲明一個(gè)類型。如：COUNTI,j;順序表的虛擬實(shí)現(xiàn)：在高級(jí)語(yǔ)言中，數(shù)組是采用順序存儲(chǔ)的，所以我們可以用數(shù)組類型來(lái)說(shuō)明順序表的存儲(chǔ)方式。即順序表類型定義

●2.2.1順序表#defineMAXSIZE100//表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為100typedef

int

ElemType//ElemType的類型可根據(jù)實(shí)際情況而定，這里假設(shè)為int

typedef

struct{Elemtype

data[MAXSIZE];//最多有MAXSIZE個(gè)數(shù)據(jù)元素

intlength;//存放數(shù)據(jù)元素的實(shí)際個(gè)數(shù)

}SeqList;//定義了一個(gè)新類型：順序表類型SeqListlist;

//定義一個(gè)變量：順序表list為了能夠?qū)樞虮磉M(jìn)行整體引用，通常將data和length封裝成一個(gè)結(jié)構(gòu)體作為順序表的類型。知識(shí)點(diǎn)回顧：結(jié)構(gòu)體中成員的表示表長(zhǎng)＝list.length=n；表空標(biāo)志list.length=0；表滿標(biāo)志list.length=MAXSIZE；即0<=length<=MAXSIZE數(shù)據(jù)元素list.data[0]～list.data[list.length-1]注意：下標(biāo)要減1

根據(jù)C語(yǔ)言規(guī)則，定義一個(gè)指向SeqList類型的指針變量更方便，即定義一個(gè)指向順序表SeqList的指針變量pslist

SeqList*pslist;存儲(chǔ)空間的動(dòng)態(tài)分配：sizeof()函數(shù)：返回各種數(shù)據(jù)類型所占用的存儲(chǔ)空間大小malloc(unsignedsize)函數(shù)：每次調(diào)用時(shí)，要求一塊內(nèi)存空間聲明格式：

void*malloc(unsigneg

intsize);

size表示所需內(nèi)存空間大小，單位是字節(jié)。如果成功分配內(nèi)存空間，函數(shù)返回第一個(gè)字節(jié)的指針。這時(shí)須另外加上類型的轉(zhuǎn)換，使函數(shù)返回的指針?lè)纤渲玫念愋汀?/p>

fp=(數(shù)據(jù)類型*)malloc(sizeof(數(shù)據(jù)類型))

說(shuō)明：如果內(nèi)存空間不足，malloc()將會(huì)配置失敗且返回一個(gè)空指針，需確定內(nèi)存配置成功，即返回有效的指針，接著才能使用這塊內(nèi)存，否則將產(chǎn)生未知的結(jié)果。

獲得線性表的存儲(chǔ)空間：

pslist=(SeqList*)malloc(sizeof(SeqList));●2.2.1順序表#defineMAXSIZE100typedef

int

ElemTypetypedef

struct{Elemtype

data[MAXSIZE];

intlength;}SeqList;SeqListlist,*pslist;

//定義一個(gè)順序表list,一個(gè)指向順序表的指針pslistpslist=(SeqList*)malloc(sizeof(SeqList));另一種存儲(chǔ)表示（略）#defineLIST-INIT-SIZE100#defineLISTINCREMENT10Typedef

struct{

Elemtype*elem;

intlength;

int

listsize;}Seqlist;pslist是一個(gè)指針變量，存放的是順序表的地址。表示方法：表長(zhǎng)pslist->length；

//

等同于(*pslist).length

表空標(biāo)志pslist->length=0；表滿標(biāo)志pslist->length=MAXSIZE；數(shù)據(jù)元素pslist->data[0]～pslist->data[pslist->length-1]a1a2…ai-1aiai+1…an…01…i-2i-1i…n-1MAXSIZE-1a1a2…ai-1aiai+1…an…pslist->datapslist->length-1●2.2.1順序表注意：

①存放線性表結(jié)點(diǎn)的向量空間的大小MAXSIZE應(yīng)仔細(xì)選值，使其既能滿足表結(jié)點(diǎn)的數(shù)目增加的需求，又不致于預(yù)先定義過(guò)大而浪費(fèi)存儲(chǔ)空間。

②由于C語(yǔ)言中向量的下標(biāo)從0開(kāi)始，所以若L是SqList類型的指針變量，則a1和an分別存儲(chǔ)在L.pslist[0]和L.pslist[length-1]中。

注意問(wèn)題：參數(shù)：值傳遞和地址傳遞的區(qū)別參數(shù)傳遞的方向邊界值的處理：在第一個(gè)元素前插入在最后一個(gè)元素后插入當(dāng)刪除或插入元素時(shí)，線性表的長(zhǎng)度改變指定的數(shù)據(jù)元素的位置是否合法●2.2.2順序表的基本運(yùn)算⒈順序表的初始化初始化即構(gòu)造一個(gè)空表。算法分析將pslist設(shè)為指針參數(shù)，動(dòng)態(tài)分配存儲(chǔ)空間需考慮問(wèn)題：（1）動(dòng)態(tài)分配空間是否成功（2）表中l(wèi)ength值設(shè)為0初始化算法實(shí)現(xiàn)：SeqList*init_SeqList(){SeqList*pSlist;

pSlist=(SeqList*)malloc(sizeof(SeqList));if(pSlist!=NULL)

pSlist->length=0;else

printf(“Outofspace!”);

return(pSlist);}main(){SeqList*pSlist;

pSlist=init_Seqlist();}●2.2.2順序表的基本運(yùn)算

⒉插入算法順序表的插入是指在線性表的第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素（如：x)，使長(zhǎng)度為n的線性表（a1,…,ai－1,ai,…,an）變成長(zhǎng)度為n+1的線性表：（a1,…,ai－1,x,ai,…,an）算法分析⑴將ai～an順序向后移動(dòng)，為新元素讓出位置；⑵將x置入空出的第i個(gè)位置；⑶修改length指針（修改表長(zhǎng)），使之仍指向最后一個(gè)元素?！?.2.2順序表的基本運(yùn)算j的取值范圍：

i-1<=j<=length-1移動(dòng)語(yǔ)句：For(j=length-1;j>=i-1;j--)data[j+1]=data[j];i-1n-1自下而上的向下移動(dòng)j起始位置需考慮問(wèn)題：

(1)分配時(shí)由于向量空間大小在聲明時(shí)確定，當(dāng)L-＞length=MAXSIZE時(shí)，表空間已滿，不可再做插入操作；

(2)當(dāng)插入位置i的值為i＞length+1或i＜1時(shí)為非法位置，不可做正常插入操作；

(3)移動(dòng)元素時(shí)是整體自下而上的順序；

(4)length值增1；插入算法實(shí)現(xiàn)：int

insert_list(SeqList*pslist,inti,Elemtypex){intj;if(pslist->length==MAXSIZE){printf(“表滿\n”);return-1;}if(i<1||i>pslist->length+1){printf(“位置錯(cuò)”)；

return(0);}●2.2.2順序表的基本運(yùn)算

for(j=pslist->length-1;j>=i-1;j--)

pslist->data[j+1]=pslist->data[j];

/*結(jié)點(diǎn)向后移*/

pslist->data[i-1]=x;

/*插入新元素*/

pslist->length++;

/*length仍指向最后元素*/return1;}●2.2.2順序表的基本運(yùn)算時(shí)間復(fù)雜度分析：設(shè)在第i個(gè)位置插入的概率為Pi＝平均移動(dòng)次數(shù)Eis(n)=＝

＝n/2

說(shuō)明做插入操作時(shí)，需要移動(dòng)一半的數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n)?！?.2.2順序表的基本運(yùn)算⒊刪除運(yùn)算與線性表插入運(yùn)算相對(duì)，將線性表的第i個(gè)元素刪除的操作是使長(zhǎng)度為n的線性表（a1,…,ai-1,ai,ai+1,…,an

）變成長(zhǎng)度為n-1的線性表（a1,…,ai-1,ai+1,…,an-1

）算法分析⑴將ai+1～an順序向前移動(dòng)。⑵修改length指針(修改表長(zhǎng))，使之仍指向最后一個(gè)元素。●2.2.2順序表的基本運(yùn)算in-1自上而下的向上移動(dòng)j起始位置j的取值范圍：

i<=j<=length-1移動(dòng)語(yǔ)句：For(j=i;j<=length-1;j++)data[j-1]=data[j];需考慮問(wèn)題：(1)如果需ai，應(yīng)先返回ai的值。(2)檢查要?jiǎng)h除位置的有效性，1≤i≤n；(3)當(dāng)表空時(shí)不能做刪除，因表空時(shí)pslist->length的值為0，條件（i<1||i>pslist->length）也包括對(duì)表空的檢查（符合i>length）；(4)移動(dòng)元素時(shí)是整體自上而下的順序；(5)length值減1；

刪除算法實(shí)現(xiàn)int

delete_list(SeqList*pslist,inti){intj;if(i<1||i>pslist->length){printf(“不存在第i個(gè)元素\n”);return(0);}for(j=i;j<=pslist->length-1;j++)

pslist->data[j-1]=pslist->data[j];

pslist->length--;return1;}●2.2.2順序表的基本運(yùn)算時(shí)間復(fù)雜度分析：刪除第i個(gè)位置的概率為Pi＝平均移動(dòng)次數(shù)Ede(n)=＝＝說(shuō)明刪除運(yùn)算時(shí)平均需要移動(dòng)一半的數(shù)據(jù)元素，時(shí)間復(fù)雜度為O(n)?！?.2.2順序表的基本運(yùn)算⒋按值查找線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素，并返回查找成功與否標(biāo)志。算法分析從第一個(gè)元素a1起依次和x比較，直到找到一個(gè)與x相等的數(shù)據(jù)元素，則返回它在順序表中的存儲(chǔ)下標(biāo)或序號(hào)(二者差一)；如果沒(méi)有找到，返回-1。●2.2.2順序表的基本運(yùn)算

順序表按值查找算法實(shí)現(xiàn)int

location_seqlist(SeqList*pslist,elemtypex){inti;i=0;while(i<=pslist->length-1&&pslist->data[i]!=x)i++;if(i>pslist->length-1)return–1;elsereturni;/*返回存儲(chǔ)位置*/}●2.2.2順序表的基本運(yùn)算時(shí)間復(fù)雜度分析：本算法的主要運(yùn)算是比較，比較次數(shù)與x的位置有關(guān)，也與表長(zhǎng)有關(guān)?！?.2.2順序表的基本運(yùn)算

找到找不到最好情況1次O(1)

n+1次O(1)最壞情況n次O(n)n+1次O(n)平均情況n/2次O(n)n+1次O(n)●2.2.2順序表的基本運(yùn)算⒌查找操作查找順序表中第i個(gè)位置上的元素值，并將該元素的值返回。

查找操作算法實(shí)現(xiàn)Elemtype

Get_Node(SeqList*pslist,inti){

if(i>=1&&i<=pslist->length)

return(pslist->data[i-1]);else{printf(“Notexit.\n”);return(-1);}}

求表長(zhǎng)算法實(shí)現(xiàn)int

list_length(SeqList*pslist){

return(pslist->length);//求pslist所指向順序表的長(zhǎng)度

}⒍求表長(zhǎng)求線性表的長(zhǎng)度，并返回長(zhǎng)度值?！?.2.2順序表的基本運(yùn)算算法5和算法6的時(shí)間復(fù)雜度均為O(1)【例2.1】順序表的劃分。將順序表(a1,a2,…，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大。?！?.2.3順序表的應(yīng)用12268111910…10118122619…劃分前劃分后算法分析從第二個(gè)元素開(kāi)始⑴當(dāng)前數(shù)據(jù)比a1大時(shí)，不改變其位置，繼續(xù)比較下一個(gè)。⑵當(dāng)前數(shù)據(jù)比a1小時(shí)，將其前面的元素依次向后移動(dòng)一個(gè)位置，然后將其置入對(duì)應(yīng)單元?！?.2.3順序表的應(yīng)用12268111910…將26和12比較，比12大，不用變化，再比較8和12，比12小，則12、26均向后移動(dòng)需要一個(gè)變量來(lái)存放比較的位置，此算法用i來(lái)表示數(shù)組下標(biāo)位置。1<=i<=length當(dāng)需要移動(dòng)元素時(shí)，需要一個(gè)變量表示移動(dòng)的范圍，用j表示。0<=j<=i-1基準(zhǔn)(12)的位置會(huì)發(fā)生變化，也需要存儲(chǔ)起來(lái)，用x來(lái)存儲(chǔ)。x=data[0]移動(dòng)元素時(shí)，當(dāng)前正比較的值防止被覆蓋也需要存儲(chǔ)起來(lái)。Y=data[i]算法主體是循環(huán)結(jié)構(gòu)，由i來(lái)控制，請(qǐng)同學(xué)們自己編寫(xiě)?！?.2.3順序表的應(yīng)用

voidpart(SeqList*L){int

i,j;

elemtype

x,y;x=L->data[0];for(i=1;i<=L->length-1;i++)if(L->data[i]<x){y=L->data[i];for(j=i-1;j>=0;j--)L->data[j+1]=L->data[j];L->data[0]=y;}}●2.2.3順序表的應(yīng)用【例2.2】順序表的合并。已知順序表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的順序表LC，且LC中的數(shù)據(jù)元素仍按值非遞減有序排列。

LA=(1，4，7，10)

LB=(2，3，9，12，16)

LC=(1，2，3，4，7，9，10，12，16)算法分析設(shè)LC為空表，依次掃描LA和LB，比較當(dāng)前元素，將較小值的元素賦給LC，直到一個(gè)線性表掃描完畢，然后將未完的順序表中余下部分賦給LC即可。三個(gè)順序表都需要設(shè)個(gè)變量存當(dāng)前的位置。

voidunion(SeqListLA,SeqList

LB,SeqList*LC){int

i,j,k;i=0;j=0;k=0;while(i<=LA.length-1&&j<=LB.length-1)if(LA.data[i]<LB.data[j])LC->data[k++]=LA.data[i++];elseLC->data[k++]=LB.data[j++];while(i<=LA.length-1)LC->data[k++]=LA.data[i++];while(j<=LB.length-1)LC->data[k++]=LB.data[j++];LC->length=LA.length+LB.length;}●2.2.3順序表的應(yīng)用從前面看到，順序存儲(chǔ)結(jié)構(gòu)有特點(diǎn)：（1）邏輯順序與物理順序一致（2）隨機(jī)存取但是，也存在一些缺點(diǎn)：（1）插入、刪除等操作要移動(dòng)元素（2）存儲(chǔ)空間是預(yù)分配的，不靈活，浪費(fèi)空間（3）表的存儲(chǔ)空間難擴(kuò)充●

2.3線性表的鏈?zhǔn)酱鎯?chǔ)那么，有沒(méi)有一種靈活的存儲(chǔ)方式呢？回答是肯定的！——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但是有優(yōu)點(diǎn)，同樣也存在缺點(diǎn)線性表的鏈?zhǔn)酱鎯?chǔ)方式：（1）是用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。（2）為了表示線性關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需要存儲(chǔ)直接后繼的存儲(chǔ)位置（也可以是前驅(qū)）。這兩部分信息組成數(shù)據(jù)元素的ai的存儲(chǔ)映象，稱為結(jié)點(diǎn)（Node）。它包括兩個(gè)域：數(shù)據(jù)域和指針域。n個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。又由于每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱為單鏈表。●

2.3線性表的鏈?zhǔn)酱鎯?chǔ)●2.3.1線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)⑴存儲(chǔ)空間不一定連續(xù)⑵邏輯關(guān)系由指針來(lái)體現(xiàn)(3)邏輯上相鄰，物理上不一定相鄰(4)非隨機(jī)存?。樞虼嫒。?，即訪問(wèn)任何一個(gè)元素的時(shí)間不同。如磁帶和CD注意：

鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。

●2.3.1線性鏈表存儲(chǔ)地址數(shù)據(jù)域指針110E150120D110125A160140C120150FNULL160B140125頭指針head鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例：有線性表h＝（A,B,C,D,E,F），其對(duì)應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖所示。●2.3.1線性鏈表datanext虛擬實(shí)現(xiàn)：利用高級(jí)語(yǔ)言中的指針來(lái)實(shí)現(xiàn)。結(jié)點(diǎn)定義如下：typedef

structNode{elemtypedata;

structNode*next;}ListNode,*LinkList;結(jié)點(diǎn)（Node）

單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而起始結(jié)點(diǎn)無(wú)前趨，故設(shè)頭指針head指向起始結(jié)點(diǎn)。定義頭指針變量：LinkListhead;

LinkNode*p;

LinkListhead;注意：

①LinkList和LNode*是不同名字的同一個(gè)指針類型（命名的不同是為了概念上更明確）

②LinkList類型的指針變量head表示它是單鏈表的頭指針

③LNode*類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針●2.3.1線性鏈表ABCDE∧Fhead鏈表的邏輯結(jié)構(gòu)nextdataPpdatapnext算法中各個(gè)域的表示如定義一個(gè)指針p：Linklistp(*p).data(*p).nextHead==NULL不帶頭結(jié)點(diǎn)的空表ABCDE∧head不帶頭結(jié)點(diǎn)的鏈表這種鏈表稱為不帶頭結(jié)點(diǎn)的鏈表，但是首結(jié)點(diǎn)無(wú)前驅(qū)，很多操作需要單獨(dú)考慮首結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)的處理和其它結(jié)點(diǎn)不同，因?yàn)榈谝粋€(gè)結(jié)點(diǎn)加入時(shí)鏈表為空，它沒(méi)有直接前驅(qū)結(jié)點(diǎn)，其地址就是整個(gè)鏈表的指針需要放在鏈表的頭指針變量中；而其它結(jié)點(diǎn)有直接前驅(qū)結(jié)點(diǎn)，其地址放入直接前驅(qū)結(jié)點(diǎn)的指針域?！暗谝粋€(gè)結(jié)點(diǎn)”問(wèn)題在很多操作中都會(huì)遇到，如鏈表中插入結(jié)點(diǎn)時(shí)，將結(jié)點(diǎn)插在第一個(gè)位置和其它位置不同，刪除結(jié)點(diǎn)時(shí)，刪除第一個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的處理不同。

●2.3.3線性鏈表的基本運(yùn)算說(shuō)明：

起始結(jié)點(diǎn)和其他結(jié)點(diǎn)的不同處理：由于起始結(jié)點(diǎn)的位置是存放在表頭指針中，而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中，插入起始結(jié)點(diǎn)時(shí)要將頭指針指向起始結(jié)點(diǎn)。

空表和非空表的不同處理：若讀入的第一個(gè)數(shù)據(jù)就是結(jié)束標(biāo)志，則鏈表head是空表，尾指針r也為空，結(jié)點(diǎn)*r不存在；否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，將其指針域置空。●2.3.3線性鏈表的基本運(yùn)算頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長(zhǎng)度等附加信息。指針域存放首元結(jié)點(diǎn)的地址head∧帶頭結(jié)點(diǎn)的空表ABCD∧Ehead附加頭結(jié)點(diǎn)的鏈表頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)Head－>next==NULL頭結(jié)點(diǎn)是在鏈表的起始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)，有兩個(gè)優(yōu)點(diǎn)：⑴由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，故在鏈表的第一個(gè)位置上的操作與表中其他位置上操作一致，無(wú)須進(jìn)行特殊處理。⑵無(wú)論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針，故此空表和非空表的處理也統(tǒng)一了?！?.3.2動(dòng)態(tài)內(nèi)存分配

動(dòng)態(tài)內(nèi)存分配指在程序執(zhí)行過(guò)程中動(dòng)態(tài)地分配或回收存儲(chǔ)空間，在需要時(shí)，由系統(tǒng)即時(shí)分配。⒈malloc()函數(shù)

void*malloc(unsigned

intsize)

在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長(zhǎng)度為size的連續(xù)空間。例p=(long*)malloc(8)

/*開(kāi)辟長(zhǎng)度為8個(gè)字節(jié)的內(nèi)存空間，并把起始地址賦給一個(gè)指向long型的指針變量p*/注意當(dāng)函數(shù)未能成功分配存儲(chǔ)空間（如內(nèi)存不足）時(shí)，返回一個(gè)NULL指針，即調(diào)用該函數(shù)時(shí)檢測(cè)返回值是否為NULL并執(zhí)行相應(yīng)的操作?！?.3.2動(dòng)態(tài)內(nèi)存分配例：動(dòng)態(tài)分配程序

#include<stdio.h>

/*標(biāo)準(zhǔn)輸入輸出文件*/#include<stdlib.h>

/*動(dòng)態(tài)分配文件*/main(){intcount,*array;

if(array=(int*)malloc(10*sizeof(int)))==NULL){printf(“error!”);exit(1);}for(count=0;count<10;count++)

array[count]=count;for(count=0;count<10;count++)printf(“%2d”,array[count]);}⑴分配10個(gè)整型的連續(xù)存儲(chǔ)空間，并返回一個(gè)指向其起始地址的整型指針。⑵將整型指針地址賦給array。⑶檢測(cè)返回值是否為NULL?！?.3.2動(dòng)態(tài)內(nèi)存分配

⒉free函數(shù)當(dāng)分配的內(nèi)存空間不用時(shí)，要釋放存儲(chǔ)空間。

voidfree(void*p)釋放指針p所指向的內(nèi)存區(qū)。參數(shù)p是先前調(diào)用malloc函數(shù)時(shí)返回的指針。注意

malloc函數(shù)是對(duì)存儲(chǔ)區(qū)進(jìn)行分配，free函數(shù)是釋放已經(jīng)不用的內(nèi)存區(qū)域，這樣就可以實(shí)現(xiàn)對(duì)內(nèi)存區(qū)域進(jìn)行動(dòng)態(tài)分配并進(jìn)行簡(jiǎn)單的管理。p1=malloc(10*sizeof(int));Free(p1);1.單鏈表的初始化創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表。算法設(shè)計(jì)為單鏈表結(jié)構(gòu)及表頭結(jié)點(diǎn)申請(qǐng)空間，若申請(qǐng)成功，則返回線性表?！?.3.3線性鏈表的基本運(yùn)算●2.3.3線性鏈表的基本運(yùn)算創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表

LinkList

init_NullList(){Lnode*pLlist;

pLlist=(LinkList)malloc(sizeof(ListNode));/*申請(qǐng)表頭結(jié)點(diǎn)*/

if(pLlist!=NULL)

pLlist->next=NULL;else

printf(“outofspace!”);

return(pLlist);}●2.3.3線性鏈表的基本運(yùn)算2.求表長(zhǎng)求表長(zhǎng)即求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)。設(shè)L是帶表頭結(jié)點(diǎn)的單鏈表。算法設(shè)計(jì)設(shè)動(dòng)態(tài)指針p和計(jì)數(shù)器count，p先指向頭結(jié)點(diǎn)，即p=L，計(jì)數(shù)器count=0，p所指結(jié)點(diǎn)后面若還有結(jié)點(diǎn)，p向后移動(dòng)，計(jì)數(shù)器count加1，直到p所指結(jié)點(diǎn)后面無(wú)結(jié)點(diǎn)，計(jì)數(shù)器count的值即為表長(zhǎng)。

對(duì)于線性鏈表，可以從頭指針(head)開(kāi)始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。這個(gè)過(guò)程叫“遍歷”。指針后移操作：

p=(*p).nextABCD∧Eheadp●2.3.3線性鏈表的基本運(yùn)算帶表頭結(jié)點(diǎn)的單鏈表求表長(zhǎng)

int

length_LinkList(LinkListL){Lnode*p;

intcount;p=L;

/*p指向頭結(jié)點(diǎn)*/count=0;while(p->next!=NULL){p=p->next;count++;

/*p所指的是第count個(gè)結(jié)點(diǎn)*/}returncount;}此操作遍歷了整個(gè)鏈表，時(shí)間復(fù)雜度：O(n)此處注意：p->next!=NULL與p!=NULL不同請(qǐng)同學(xué)們說(shuō)出，哪兒不同？●2.3.3線性鏈表的基本運(yùn)算3.查找操作⑴鏈表中按序號(hào)查找（查找指定位置的結(jié)點(diǎn)）按序號(hào)查找是線性表的一種常用運(yùn)算，其功能是對(duì)給定的鏈表查找表中第i個(gè)結(jié)點(diǎn)，并用一個(gè)指針變量指向該結(jié)點(diǎn)。算法設(shè)計(jì)從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第i個(gè)，若是，則返回該結(jié)點(diǎn)的指針；否則繼續(xù)判斷后一個(gè)，直到表結(jié)束為止。沒(méi)有第i個(gè)結(jié)點(diǎn)時(shí)返回空。請(qǐng)同學(xué)們現(xiàn)在自己編寫(xiě)這個(gè)算法

當(dāng)做遍歷操作時(shí)候，while條件都要加上while(p->next！=NULL&&？？)或while(p->next！=NULL||？？)或while(p！=NULL&&？？)或while(p！=NULL||？？)i的合法位置為１－n，j的取值范圍0-n若i<1，則while條件中j<i為永假，while不會(huì)執(zhí)行。此時(shí)j==0;

(i可能與j相等)若i>n+1，則while條件中j<i-1為永真，while退出條件時(shí)p->next＝＝NULL，此時(shí)j=n;

(i與j肯定不相等)若1<=i<=n+1，執(zhí)行while，退出while時(shí)為j==I;

(i與j肯定相等)

由此，可根據(jù)下面條件來(lái)判定位置是否合理，即是否找到第i個(gè)位置元素

if(i==j&&i!=0)●2.3.3線性鏈表的基本運(yùn)算ListNode*Get_LinkList(LinlList

Llist,inti)/*在單鏈表Llist中查找第i個(gè)結(jié)點(diǎn)，找到返回其指針，否則返回空指針*/{intj=0;

ListNode*p;p=Llist;while(p->next!=NULL&&j<i){p=p->next;j++;}if(i==j&&i!=0)return(p);else

return(NULL);}按序號(hào)查找鏈表數(shù)據(jù)元素算法一還有其他的表示方法嗎？Int

Getelem(linklist

l,intI,int*e){P=L->next;J=1;While(p&&j<i) {p=p->next;++j;}If(!p||j>i)return-1;E=p->data;Return1;}算法二：●2.3.3線性鏈表的基本運(yùn)算⑵按值查找操作算法分析從鏈表的第一個(gè)結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)值是否等于x，若是，返回該結(jié)點(diǎn)的指針；否則繼續(xù)判斷后一個(gè)，直到表結(jié)束，找不到時(shí)返回空。

ListNode*Locate_Linklist(LinkList

Llist,Elemtypex){ListNode*p;p=Llist->next;/*設(shè)置初值*/while(p!=NULL&&p->data!=x)p=p->next;/*未達(dá)到尾結(jié)點(diǎn)，又未找到值等于x的結(jié)點(diǎn)時(shí)，繼續(xù)找*/

return(p);/*找到值為x的結(jié)點(diǎn)，返回它的地址*/}查找算法的時(shí)間復(fù)雜度均為O(n)算法

(1)分配時(shí)由于向量空間大小在聲明時(shí)確定，當(dāng)L-＞length=MAXSIZE時(shí)，表空間已滿，不可再做插入操作；

(2)當(dāng)插入位置i的值為i＞n+1或i＜1時(shí)為非法位置，不可做正常插入操作；

(3)移動(dòng)元素時(shí)是整體自下而上的順序；

(4)length值增1；4.插入操作在順序表的插入算法中需考慮問(wèn)題：鏈表的插入算法與順序表插入算法相比較：（1）不存在“表滿”（2）插入位置合理性判斷1<=i<=n+1（3）不需要移動(dòng)元素（4）不需要length設(shè)p指向單鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p后面。a1a2an∧head…ai-1ai……xps①s->next=p->next;②p->next=s;●2.3.3線性鏈表的基本運(yùn)算①②注意兩個(gè)指針的操作順序不能交換，否則p結(jié)點(diǎn)后面的結(jié)點(diǎn)將被斷開(kāi)，不能實(shí)現(xiàn)正確插入。在第i位置之前插入一個(gè)值為x的結(jié)點(diǎn)，算法如下：Int

insert_LinkList(LinkListhead,inti,Elemtypee){P=head;j=0;While(P&&j<i-1) {p=p->next; ++j; }If(!p||j>i-1)return-1;S=(linklist)malloc(sizeof(listnode));S->data=e;S->next=p->next;P->next=s;Return1;}●2.3.3線性鏈表的基本運(yùn)算5.鏈表中刪除結(jié)點(diǎn)在順序表中刪除算法需考慮問(wèn)題：(1)如果需ai，應(yīng)先返回ai的值(2)檢查要?jiǎng)h除位置的有效性，1≤i≤n(3)當(dāng)表空時(shí)不能做刪除(4)移動(dòng)元素時(shí)是整體自上而下的順序(5)length值減1；在鏈表中刪除算法需考慮問(wèn)題：(1)如果需ai，應(yīng)先返回ai的值(2)檢查要?jiǎng)h除位置的有效性，1≤i≤n(3)當(dāng)表空時(shí)不能做刪除(4)不需要移動(dòng)元素(5)不需要設(shè)Length值(6)刪除的結(jié)點(diǎn)空間用free釋放設(shè)s指向單鏈表中某個(gè)結(jié)點(diǎn)，刪除s，首先要找到s的前驅(qū)結(jié)點(diǎn)p，指針操作由下：p->next=s->next;free(s);a1ai+1an∧headai-1ai……p●2.3.3線性鏈表的基本運(yùn)算s刪除鏈表中第i個(gè)結(jié)點(diǎn)的基本步驟如下：①找到第i-1個(gè)結(jié)點(diǎn)；若存在，繼續(xù)進(jìn)行，否則結(jié)束。②若存在第i個(gè)結(jié)點(diǎn)，則繼續(xù)③，否則結(jié)束。③刪除第i個(gè)結(jié)點(diǎn)，結(jié)束。●2.3.3線性鏈表的基本運(yùn)算刪除鏈表中第i個(gè)結(jié)點(diǎn)的算法如下：int

del_LinkList(LinkList

pList,inti){Listnode*p,*q;intj;p=pList;j=0;while((*p).next!=NULL&&j<i-1){p=(*p).next;++j;}if((*p).next==NULL||j>i-1)returnERROR;q=(*p).next;(*p).next=(*q).next;free(q);returnOK;}●2.3.3線性鏈表的基本運(yùn)算通過(guò)前面的基本操作：⑴在單鏈表上插入、刪除結(jié)點(diǎn)，必須知道其前驅(qū)結(jié)點(diǎn)。⑵單鏈表不具有按序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)，只能從頭指針開(kāi)始一個(gè)個(gè)順序進(jìn)行?！?.3.3線性鏈表的基本運(yùn)算練習(xí)：已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是—b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是__c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是_____d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是______e.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是______P=P—>next;P—>next=P;P—>next=P—>next—>next;P=P—>next—>next;While(P!=NULL)P=P—>next;While(Q—>next!=NULL){P=Q;Q=Q—>next；}(7)While(P—>next!=Q)P=P—>next;(8)While(P—>next—>next!=Q)P=P—>next;(9)While(P—>next—>next!=NULL)P=P—>next;(10)Q=P;(11)Q=P—>next;(12)P=L;(13)L=L—>next;(14)free(Q);由此可知：要?jiǎng)h除的結(jié)點(diǎn)為Q結(jié)點(diǎn)練習(xí)：a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是—

（11）（3）（14）b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是__(10)(12)(8)(11)(3)(14)c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是_____(10)(12)(7)(3)(14)d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是______(12)(10)(11)(3)(14)e.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是______(9)(11)(3)(14)或(10)/(11)(6)(3)(14)簡(jiǎn)述下列算法的功能

int

A(LinklistL)L為不帶頭結(jié)點(diǎn)的鏈表

{if(L&&L—>next){Q=L;L=L—>next;P=L;while(P—>next)P=P—>next;P—>next=Q;Q—>next=NULL;}return(1);}如果L的長(zhǎng)度不小于2，則將首元結(jié)點(diǎn)刪掉并插入到表尾。對(duì)于線性鏈表，可以從頭指針(head)開(kāi)始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。創(chuàng)建單鏈表無(wú)論對(duì)鏈表進(jìn)行何種運(yùn)算，第一步必須建立該線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(即鏈表)，然后再對(duì)該鏈表進(jìn)行需要的運(yùn)算。鏈表的建立要經(jīng)過(guò)以下步驟進(jìn)行：算法設(shè)計(jì)初始狀態(tài)，頭指針head=NULL，尾指針r=NULL。按線性表中元素的順序依次讀入數(shù)據(jù)元素，不是結(jié)束標(biāo)志時(shí)，申請(qǐng)結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，直到讀入結(jié)束標(biāo)志?！?.3.3補(bǔ)充⑴在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表鏈表與順序表不同，是一種動(dòng)態(tài)管理存儲(chǔ)結(jié)構(gòu)。鏈表中的每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不是預(yù)先分配，而是需要時(shí)生成的，因此建立單鏈表需從空表開(kāi)始，每讀入一個(gè)數(shù)據(jù)元素申請(qǐng)一個(gè)結(jié)點(diǎn)，然后插入在鏈表頭部（頭指針指向新結(jié)點(diǎn)）。例：建立線性表（35,47,28,86,79）●2.3.3補(bǔ)充35∧∧4728867935∧4735∧284735∧86284735∧在鏈表頭部插入建立單鏈表●2.3.3補(bǔ)充建立單鏈表算法１

LinkListCreat_LinkList1(){LinkListL;

ListNode*p;

inta;

intflag;L=NULL;

scanf(“%d”,&a);while(a!=flag){p=(Lnode*)malloc(sizeof(Lnode));p->data=a;p->next=L;L=p;

scanf(“%d”,&a);}returnL;}●2.3.3補(bǔ)充⑵在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表在頭部插入建立單鏈表簡(jiǎn)單，但讀入的數(shù)據(jù)順序與生成鏈表中元素的順序相反，若希望次序一致，則用在尾部插入結(jié)點(diǎn)的方法。例：建立線性表（35,47,28,86,79）算法分析初始狀態(tài)，頭指針head=NULL，尾指針rear=NULL。按線性表中元素的順序依次讀入數(shù)據(jù)，不是結(jié)束標(biāo)志時(shí)，申請(qǐng)結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到rear所指結(jié)點(diǎn)后面，rear指向新結(jié)點(diǎn)?！?.3.3補(bǔ)充35∧∧3535353547∧4728∧472886∧47288679∧在鏈表尾部插入建立單鏈表headheadheadheadheadheadrearrearrearrearrearrear●2.3.3補(bǔ)充建立單鏈表算法２

LinkListCreat_LinkList2(){LinkListL;

ListNode*p,*rear;

inta;

intflag;L=rear=NULL;

scanf(“%d”,&a);while(a!=flag){p=(Lnode*)malloc(sizeof(Lnode));p->data=a;if(L==NULL)L=p;

/*處理第一個(gè)結(jié)點(diǎn)*/elserear->next=p;

/*其它結(jié)點(diǎn)的處理*/rear=p;

/*指向新的尾結(jié)點(diǎn)*/

scanf(“%d”,&a);}if(rear!=NULL)rear->next=NULL;returnL;}●2.3.3補(bǔ)充循環(huán)鏈表是另一種形式的鏈表結(jié)構(gòu)。即將最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表表頭結(jié)點(diǎn)，使得鏈表頭尾相連，就構(gòu)成了單循環(huán)鏈表。在循環(huán)鏈表中，從表中的任意結(jié)點(diǎn)出發(fā)均可找到表中的其它結(jié)點(diǎn)。其操作基本與非循環(huán)鏈表相同，只是將原來(lái)判斷指針是否為NULL改為是否指向頭結(jié)點(diǎn)。head●2.3.4循環(huán)鏈表及運(yùn)算a1a2anhead…a1a2an…h(huán)ead對(duì)于單鏈表，只能從頭結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表，而對(duì)于單循環(huán)鏈表，則可以從表中任意結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表。不用頭指針，改用指向尾結(jié)點(diǎn)的指針rb來(lái)標(biāo)識(shí)，可以提高操作效率。例對(duì)兩個(gè)單循環(huán)鏈表L1、L2的連接操作，是將L2的第一個(gè)結(jié)點(diǎn)接到L1的尾結(jié)點(diǎn)，若用頭指針標(biāo)識(shí)，則需要找到第一個(gè)鏈表的尾結(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)，若用尾指針ra、rb標(biāo)識(shí)，則時(shí)間復(fù)雜度為O(1)，算法如下：●2.3.4循環(huán)鏈表及運(yùn)算單循環(huán)鏈表的連接

LinkList

connect(LinkList

ra,rb){ListNode*p;p=ra->next;

ra->next=rb->next->next;

free(rb->next);

rb->next=p;

return(rb);}……●2.3.4循環(huán)鏈表及運(yùn)算單鏈表的結(jié)點(diǎn)中只有一個(gè)指向其后繼結(jié)點(diǎn)的指針域next。若已知某結(jié)點(diǎn)的指針p，其后繼結(jié)點(diǎn)的指針則為p->next，而查找其前驅(qū)結(jié)點(diǎn)只能從該鏈表的頭指針開(kāi)始，順著各結(jié)點(diǎn)的next域進(jìn)行，即查找后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，查找前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。如果也希望找前驅(qū)的時(shí)間復(fù)雜度為O(1)，則只能付出空間的代價(jià)，每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，結(jié)點(diǎn)的結(jié)構(gòu)如下：typedef

struct

dolnode{Elemtypedata;

struct

dolnode*prior,*next;}DulNode,*DulList;priordatanext●2.3.5雙向鏈表及運(yùn)算和單鏈表相似，雙向鏈表通常也用頭指針標(biāo)識(shí)，也可以帶頭結(jié)點(diǎn)和做成循環(huán)結(jié)構(gòu)。a1a2an…pheadhead●2.3.5雙向鏈表及運(yùn)算設(shè)p指向雙向循環(huán)鏈表的某一結(jié)點(diǎn)，則表示*p結(jié)點(diǎn)之前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針，即與p相等。同樣，表示*p結(jié)點(diǎn)之后繼結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針，也與p相等，則

p->next->prior＝p->prior->next=p雙向循環(huán)鏈表給運(yùn)算帶來(lái)的最大好處是可以很容易地找到結(jié)點(diǎn)的前驅(qū)和后繼。在雙向循環(huán)鏈表中查找一個(gè)結(jié)點(diǎn)，若該結(jié)點(diǎn)的序號(hào)i小于等于n/2，則可以從頭指針開(kāi)始，沿每個(gè)結(jié)點(diǎn)的next指針掃描，否則從尾指針開(kāi)始，沿每個(gè)結(jié)點(diǎn)的prior指針掃描，平均每次訪問(wèn)n/4個(gè)結(jié)點(diǎn)，但是以增加每個(gè)結(jié)點(diǎn)的存儲(chǔ)空間為代價(jià)?！?.3.5雙向鏈表及運(yùn)算在雙向鏈表中插入結(jié)點(diǎn)操作：⑴s->prior=p->prior;⑵p->prior->next=s;⑶s->next=p;⑷p->prior=s;……px⑴⑵⑶⑷s●2.3.5雙向鏈表及運(yùn)算（4）放到最后面是最保險(xiǎn)的請(qǐng)同學(xué)們寫(xiě)出當(dāng)p指向第i-1個(gè)結(jié)點(diǎn)時(shí)的操作●2.3.5雙向鏈表及運(yùn)算算法：帶頭結(jié)點(diǎn)的雙向鏈表L的第i個(gè)位置上插入值為x的元素。int

insert_DubList(DulList

L,int

i,Elemtypex){

if(!(p=GetElem_DuL(L,i)))returnERROR;if(!(s=(DulList)malloc(sizeof(DulNode)))returnERROR;s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return(1);}在雙向鏈表中刪除結(jié)點(diǎn)x…p⑴⑵操作：⑴p->prior->next=p->next;⑵p->next->prior=p->prior;⑶free(p);●2.3.5雙向鏈表及運(yùn)算●2.3.5雙向鏈表及運(yùn)算算法：刪除雙向鏈表L上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)。int

Del_DubList(DulList

L,inti){if(!(p=GetElem_DuL(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next-<prior=p->prior;

free(p);return(1);}}●

2.4順序表與鏈表的比較及應(yīng)用舉例2.4.1順序表與鏈表的比較本章討論了線性表的邏輯結(jié)構(gòu)和兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表。⒈順序表的優(yōu)點(diǎn)⑴方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)。⑵不用為表示結(jié)點(diǎn)間的邏輯關(guān)系增加額外的存儲(chǔ)空間。⑶順序表具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)。⒉順序表的缺點(diǎn)⑴做插入、刪除時(shí)，平均移動(dòng)一半元素，對(duì)n較大效率低。⑵需預(yù)先分配足夠大空間，估計(jì)過(guò)大，大量閑置，分配過(guò)小，造成溢出。●2.4.1順序表與鏈表的比較⒊鏈表的優(yōu)點(diǎn)⑴對(duì)線性表的插入、刪除不需要移動(dòng)數(shù)據(jù)。⑵每個(gè)結(jié)點(diǎn)動(dòng)態(tài)分配存儲(chǔ)空間，不會(huì)出現(xiàn)大量存儲(chǔ)空間空閑。⒋鏈表的缺點(diǎn)⑴因?yàn)椴灰筮壿嬌舷噜彽脑匚锢砩弦蚕噜?，所以必須為表示結(jié)點(diǎn)間的邏輯關(guān)系增加額外的存儲(chǔ)空間。⑵因