第2章線性表主講教師:***時(shí)間:2025.07.01目錄CONTENTS01線性表的類型定義02線性表的順序存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)03線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)目錄CONTENTS線性表的類型定義2.12.1.1線性表的概念、特點(diǎn)與邏輯結(jié)構(gòu)線性表（表）：n（n≥0）個(gè)具有相同類型的數(shù)據(jù)元素的有限序列（a1,a2,…,ai,…,an）線性表的長(zhǎng)度：線性表中數(shù)據(jù)元素的個(gè)數(shù)空表：長(zhǎng)度等于零的線性表ai（1≤i≤n）稱為數(shù)據(jù)元素下角標(biāo)

i表示該元素在線性表中的位置或序號(hào)元素ai（1≤i≤n）只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。2.1.1線性表的概念、特點(diǎn)與邏輯結(jié)構(gòu)邏輯特征1.數(shù)據(jù)元素個(gè)數(shù)的有限性a1ai-1aiana22.數(shù)據(jù)元素類型的相同性3.數(shù)據(jù)元素類型的抽象性4.相鄰數(shù)據(jù)元素的序偶關(guān)系，且a1無(wú)前驅(qū)，an無(wú)后繼序偶：兩個(gè)具有固定次序的元素組成的序列，記作<a，b>，且稱a是b

的前驅(qū)，b是a

的后繼L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))數(shù)據(jù)元素的類型需要根據(jù)實(shí)際的具體問(wèn)題而確定，在定義中是不具體的，而是抽象的2.1.1線性表的概念、特點(diǎn)與邏輯結(jié)構(gòu)2025/8/116（A,B,C,D,……,Z）例2分析學(xué)生成績(jī)表數(shù)據(jù)元素都是學(xué)生記錄，

元素間關(guān)系是線性。同一線性表中的元素必定具有相同特性。數(shù)據(jù)元素都是字母，元素間關(guān)系是線性。例1

分析26個(gè)英文字母組成的英文表學(xué)號(hào)姓名數(shù)學(xué)/分語(yǔ)文/分英語(yǔ)/分20200701張三91958820200702李四75898020200703王五95888020200704趙六809085：：：

：：物理/分89669482：化學(xué)/分96908572：2.1.1線性表的概念、特點(diǎn)與邏輯結(jié)構(gòu)思考題

列出幾個(gè)你在現(xiàn)實(shí)生活中看見(jiàn)的線性表。2.1.2線性表的ADT定義ADTList{數(shù)據(jù)對(duì)象：D={ei|1≤i≤n，n≥0，ei為ElemType類型}基本運(yùn)算}數(shù)據(jù)關(guān)系：R={<ei-1,ei>ei-1,ei￡D,i=2,…,n}InitList（&L）：表的初始化，建一個(gè)空表DestroyList（&L）：銷毀表，釋放表所占用的存儲(chǔ)空間ListEmpty（&L）：判斷表是否為空ClearList（&L）：清空一個(gè)線性表DispList（L）：輸出線性表GetElem（L，i，&e）：在表中取序號(hào)為i

的數(shù)據(jù)元素LocateElem（L，e）：在線性表中查找值等于e

的元素ListInsert（&L，i，e）：在表的第i

個(gè)位置處插入一個(gè)新元素eListDelete（&L，i，e）：刪除表中的第i

個(gè)元素2.1.2線性表的ADT定義線性表中數(shù)據(jù)元素的類型可以為簡(jiǎn)單類型，也可以為復(fù)雜類型。許多實(shí)際應(yīng)用問(wèn)題所涉的基本操作有很大相似性，不應(yīng)為每個(gè)具體應(yīng)用單獨(dú)編寫一個(gè)程序。從具體應(yīng)用中抽象出共性的邏輯結(jié)構(gòu)和基本操作（抽象數(shù)據(jù)類型），然后實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)和基本操作。030102線性表的順序存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)2.2使用數(shù)組存儲(chǔ)，大小在程序運(yùn)行期間固定。存儲(chǔ)方式是按邏輯順序依次存儲(chǔ)數(shù)據(jù)元素。存儲(chǔ)結(jié)構(gòu)定義需指定數(shù)組大小。靜態(tài)順序表01增加表頭結(jié)點(diǎn)，包含數(shù)組首地址、實(shí)際元素個(gè)數(shù)和數(shù)組大小。數(shù)組空間在程序執(zhí)行過(guò)程中動(dòng)態(tài)申請(qǐng)和釋放。動(dòng)態(tài)順序表02優(yōu)點(diǎn)是存儲(chǔ)密度大、便于隨機(jī)訪問(wèn)、存儲(chǔ)實(shí)現(xiàn)簡(jiǎn)單。缺點(diǎn)是連續(xù)性、靜態(tài)性和運(yùn)算不方便性。適用于數(shù)據(jù)量基本不變、查找頻繁的場(chǎng)景。特點(diǎn)032.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)typedefstruct{ElemType*elem;

//指向數(shù)據(jù)元素的基地址intlength;

//線性表的當(dāng)前長(zhǎng)度intListSize;//數(shù)組的大小}SeqList; //順序表類型其中elem成員存放元素，length成員存放線性表的實(shí)際長(zhǎng)度。動(dòng)態(tài)順序表類型定義說(shuō)明：注意邏輯位序和物理位序相差1。這里，假設(shè)ElemType為char類型補(bǔ)充：C語(yǔ)言的動(dòng)態(tài)分配函數(shù)（<stdlib.h>）malloc(m)開(kāi)辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址sizeof(x)計(jì)算變量x的長(zhǎng)度。free(p)釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量補(bǔ)充：數(shù)組定義typedefstruct{ElemType*elem;intlength;}SqList//順序表類型typedefstruct{ElemTypeelem[MAXSIZE];intlength;}SqList//順序表類型數(shù)組靜態(tài)分配數(shù)組動(dòng)態(tài)分配SqListL;L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)

有序順序表的存儲(chǔ)方式與順序表類似，不同的是將數(shù)據(jù)元素按某個(gè)（或多個(gè)）數(shù)據(jù)項(xiàng)的值升序或降序排列。這種存儲(chǔ)結(jié)構(gòu)主要用于查找算法，可以提高查找算法的效率。有序順序表通常采用數(shù)組來(lái)定義不需要增加頭結(jié)點(diǎn)。有序順序表2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)初始化基本操作插入刪除創(chuàng)建查找154322.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)1.初始化線性表InitList(L)

構(gòu)造一個(gè)空的線性表L。實(shí)際上只需將length成員設(shè)置為0即可。void

InitList(SeqList&L){L.elem=(ElemType*)malloc(sizeofElemType)*Maxsize);

//分配存放線性表的順序表空間

L.length=0;L.ListSize=MAXSIZE；

}2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)voidCreateList(SeqList&L，intn){intk=;InitList（L）；for（k=0;k<n;k++)scanf(&L.elem[k]);L.length=k;}2、創(chuàng)建順序表初始化新表

逐個(gè)輸入數(shù)據(jù)元素2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)voidCreateList(SqList&L，ElemTypea[]，intn){inti=0,k=0;L=(SqList*)malloc(sizeof(SqList));while(i<n) //i掃描a中元素{L->data[k]=a[i];k++;i++; //k記錄插入到L中的元素個(gè)數(shù)}L->length=k;}2、創(chuàng)建順序表a[0..n-1]

順序表L─整體創(chuàng)建順序表。傳遞順序表指針2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)順序表？？？L1010

順序表指針的含義順序表的空間順序表LSeqList*L;L=(SeqList*)malloc(sizeof(SeqList));1010通過(guò)順序表指針L操作順序表算法參數(shù)說(shuō)明2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)

順序表指針引用voidCreateList(SqList*&L，ElemTypea[]，intn)引用參數(shù)：將執(zhí)行結(jié)果回傳給實(shí)參引用符號(hào)“&”放在形參L的前面。輸出型參數(shù)均為使用“&”，不論參數(shù)值是否改變。2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)3.插入算法ListInsert(&L，i，x)在順序表L的第i（1≤i≤ListLength(L)+1）個(gè)位置上插入新的元素x。

01i-1n-1nia1a2…aiai+1…anxi+1插入完成lengthnn+12.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)boolListInsert(SeqList&L，inti，ElemTypex){intj;if(L.length==Maxsize||i<1||i>L.length+1)returnfalse; //參數(shù)錯(cuò)誤時(shí)返回false

for(j=L.length-1;j>i-1;j--)

//將elem[i-1..n-1]元素后移一個(gè)位置

L.elem[j+1]=L.elem[j];L.elem[i-1]=x; //插入元素eL.length++; //順序表長(zhǎng)度增1returntrue; //成功插入返回true}插入算法如下：a1a2…ai…an…ai+1i2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)算法最好時(shí)間復(fù)雜度為O(1)算法最壞時(shí)間復(fù)雜度為O(n)當(dāng)i=1時(shí)，移動(dòng)次數(shù)為n，達(dá)到最大值。當(dāng)i=n+1時(shí)，移動(dòng)次數(shù)為0；

對(duì)于本算法來(lái)說(shuō)，元素移動(dòng)的次數(shù)不僅與表長(zhǎng)L->length=n有關(guān)，而且與插入位置i有關(guān)：

2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)平均情況分析：

a1

a2

…

aiai+1

…

an

在線性表L中共有n+1個(gè)可以插入元素的地方因此插入算法的平均時(shí)間復(fù)雜度為O(n)。此時(shí)需要將ai～an的元素均后移一個(gè)位置，共移動(dòng)n-i+1個(gè)元素。在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為：2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)4.刪除算法ListDelete(L，i)刪除順序表L的第i（1≤i≤ListLength(L)）個(gè)元素。

0i-1n-1ia1a2ai+1…anaien-2an-1length刪除完成nn-1…2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)boolListDelete(SeqList&L，inti，ElemType&e){intj;if(i<1||i>L.length)

//參數(shù)錯(cuò)誤時(shí)返回falsereturnfalse;

e=L->data[i-1];for(j=i;j<=L.length-1;j++)

//將data[i..n-1]元素前移

L->elem[j-1]=L->elem[j];L->length--; //順序表長(zhǎng)度減1returntrue; //成功刪除返回true}刪除算法如下：a1a2…ai…an…ai+1ianai+12.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)當(dāng)i=n時(shí)，移動(dòng)次數(shù)為0；當(dāng)i=1時(shí)，移動(dòng)次數(shù)為n-1。刪除算法最好時(shí)間復(fù)雜度為O(1)刪除算法最壞時(shí)間復(fù)雜度為O(n)對(duì)于本算法來(lái)說(shuō)，元素移動(dòng)的次數(shù)也與表長(zhǎng)n和刪除元素的位置i有關(guān)：2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)平均情況分析：a1

a2

…

ai

ai+1…

an

在刪除元素ai時(shí)，若為等概率情況，則pi=在線性表L中共有n個(gè)可以刪除元素的地方此時(shí)需要將ai+1～an的元素均前移一個(gè)位置，共移動(dòng)n-(i+1)+1=n-i個(gè)元素。所以在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為：因此刪除算法的平均時(shí)間復(fù)雜度為O(n)。2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)intLocateElem(SeqList*L，ElemTypex){inti=0;while(i<L.length&&L->elem[i]!=x)i++;if(i>=L.length)return0;elsereturni+1;}5.按元素值查找LocateElem(&L，x)

順序查找第一個(gè)值域與x相等的元素的邏輯位序。若這樣的元素不存在，則返回值為0。平均時(shí)間復(fù)雜度為O(n)2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)boolGetElem(SqList*L，inti，ElemType&e){if(i<1||i>L->length)returnfalse;e=L.elem[i-1];returntrue;}

6.取第i個(gè)數(shù)據(jù)元素值GetElem(L，i，e)

返回L中第i（1≤i≤ListLength(L)）個(gè)元素的值，存放在e中。體現(xiàn)順序表的隨機(jī)存取特性本算法的時(shí)間復(fù)雜度為O(1)。2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)boolListEmpty(SeqList*L){return(L->length==0);}7.判定是否為空表ListEmpty(L)回一個(gè)值表示L是否為空表。若L為空表，則返回true，否則返回false。2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)intListLength(SqList*L){return(L.length);}8.求線性表的長(zhǎng)度ListLength(L)返回順序表L的長(zhǎng)度。實(shí)際上只需返回length成員的值即可。2.2.2順序表的基本運(yùn)算的實(shí)現(xiàn)查找、插入、刪除算法的平均時(shí)間復(fù)雜度為：O(n)顯然，順序表的空間復(fù)雜度S(n)=O(1)（沒(méi)有占用輔助空間）。2.2.3順序表的應(yīng)用舉例順序表應(yīng)用算法設(shè)計(jì)：

數(shù)據(jù)采用順序表存儲(chǔ)，利用順序表的基本操作來(lái)完成求解任務(wù)。2.2.3順序表的應(yīng)用舉例【例2.2】將兩個(gè)有序表A和B，歸并成一個(gè)有序順序表voidMergeSqList(SeqListA，SeqListB，，SeqList&C){inti=j=k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*(A.length+B.length));while(i<A.length&&j<B.length)if(A.elem[i]<B.elem[j])C.elem[k++]=A.elem[i++];elseC.elem[k++]=B.elem[j++];兩個(gè)有序表均沒(méi)有遍歷完2.2.3順序表的應(yīng)用舉例while(i<A.length)C.elem[k++]=A.elem[i++];while(j<B.length)C.elem[k++]=B.elem[j++];C.length=kC.ListSize=C.length}本算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(m+n)。2.2.3順序表的應(yīng)用舉例【例2.3】求兩個(gè)集合的并、交和差。（1）求A∪B的算法思想viodunion(SeqListA,B,&C){inti,j,k;c.elem=(ElemType*)malloc(sizeof(ElemType)*(A.length+B.length));for(i=0;i<A.length;i++)C[i]=A[i]k=A.length;for(j=0;j<B.length;j++

{i=0;while(i<A.length&&B[j]!=A[i])i++;

if(i>=A.length)C[k++]=B[j];}//endforC.lenght=k;C.ListSize=(A.length+B.length);}2.2.3順序表的應(yīng)用舉例【例2.3】求兩個(gè)集合的并、交和差。（2）求A∩B的算法viodintersection(SeqListA,B,&C){inti,j,k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*min(A.length,B.length));for(i=0;i<A.length;i++)//逐個(gè)取a中的元素

{j=0;while(j<B.length&&B[j]!=A[i])j++;//與b中的元素逐個(gè)比較

if(j<B.length)C[k++]=A[i];}C.lenght=k;C.ListSize=max(A.length,B.length);}2.2.3順序表的應(yīng)用舉例【例2.3】求兩個(gè)集合的并、交和差。（3）求A--B的算法思想voiddifference(SeqListA,B,&C){inti,j,k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*max(A.length，B.length));for(i=0;i<A.length;i++)//逐個(gè)取a中的元素

{j=0;while(j<B.length&&B[j]!=A[i])j++;//與b中的元素逐個(gè)比較

if(j>=B.length)C[k++]=A[i];}//endforC.lenght=k;C.ListSize=max(A.length,B.length);}順序表（順序存儲(chǔ)結(jié)構(gòu)）的特點(diǎn)利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致。在訪問(wèn)線性表時(shí)，可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。因此可以粗略地認(rèn)為，訪問(wèn)每個(gè)元素所花時(shí)間相等。這種存取元素的方法被稱為隨機(jī)存取法。01OPTION02OPTION順序表的優(yōu)缺點(diǎn)時(shí)間：可以隨機(jī)存取表中任一元素?？臻g：存儲(chǔ)密度大（結(jié)點(diǎn)本身所占存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占存儲(chǔ)量）。優(yōu)點(diǎn)：時(shí)間：在插入、刪除某一元素時(shí)，需要移動(dòng)大量元素?？臻g：浪費(fèi)存儲(chǔ)空間，屬于靜態(tài)存儲(chǔ)形式，數(shù)據(jù)元素的個(gè)數(shù)不能

自由擴(kuò)充。鏈表為克服這一缺點(diǎn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)2.32.3.1單鏈表存儲(chǔ)結(jié)構(gòu)單鏈表：線性表的鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)思想：用一組任意的存儲(chǔ)單元存放線性表0200020803000325…………a1a2a3a4例：(a1,a2,a3,a4)的單鏈表存儲(chǔ)0200

3250300∧存儲(chǔ)特點(diǎn)：邏輯次序和物理次序不一定相同2.元素之間的邏輯關(guān)系用指針表示1.存儲(chǔ)方式連續(xù)不連續(xù)零散分布2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)0200020803000325…………a1a2a3a40200

3250300∧觀察1：?jiǎn)捂湵碛扇舾山Y(jié)點(diǎn)構(gòu)成觀察2：?jiǎn)捂湵淼慕Y(jié)點(diǎn)只有一個(gè)指針域結(jié)點(diǎn)數(shù)據(jù)域指針域datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域data：存儲(chǔ)數(shù)據(jù)元素指針域next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址1存儲(chǔ)方式2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)0200020803000325…………a1a2a3a40200

3250300∧頭指針：指向第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭誏a1a2an∧非空表L=null空表空表和非空表不統(tǒng)一，有什么缺點(diǎn)？L1存儲(chǔ)方式2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)頭指針：指向第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭誏a1a2an∧L∧非空表空表頭結(jié)點(diǎn)簡(jiǎn)化了對(duì)邊界的處理——插入、刪除、構(gòu)造等頭結(jié)點(diǎn)：在第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)typedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLNode*next;//指針域}LNode,*LinkList;//*LinkList為L(zhǎng)Node類型的指針LNode*pLinkList

p2.存儲(chǔ)結(jié)構(gòu)定義2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)LNode*p注意區(qū)分指針變量和結(jié)點(diǎn)變量?jī)蓚€(gè)不同的概念若p->data=ai,則p->next->data=ai+1指針變量p：表示結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p：表示一個(gè)結(jié)點(diǎn)2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)時(shí)間：插入、刪除等操作不必移動(dòng)數(shù)據(jù)，只需修改鏈接指針，修改

效率較高。空間：數(shù)據(jù)元素的個(gè)數(shù)可以自由擴(kuò)充。優(yōu)點(diǎn)：時(shí)間：存取效率不高，必須采用順序存取，即存取數(shù)據(jù)元素時(shí)，只能按鏈表的順序進(jìn)行訪問(wèn)（順藤摸瓜）?？臻g：存儲(chǔ)密度小。缺點(diǎn)：3.存儲(chǔ)結(jié)構(gòu)的特點(diǎn)2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)4.不帶頭結(jié)點(diǎn)的單鏈表表頭之前插入結(jié)點(diǎn)（1）p->next=L;（2）L=p;2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)4.不帶頭結(jié)點(diǎn)的單鏈表在表尾之后插入結(jié)點(diǎn)q->next=p;p->next=NULL;2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)4.不帶頭結(jié)點(diǎn)的單鏈表在鏈表中間插入結(jié)點(diǎn)（1）p->next=q->next;（2）q->next=p;2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)5.帶頭結(jié)點(diǎn)的單鏈表p->next=q->next;q->next=p;2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)6．帶結(jié)構(gòu)信息的單鏈表typedefstructLNode{//定義單鏈表結(jié)點(diǎn)類型

ElemTypedata;structLNode*next;}LNode,*LinkList;typedefstructHNode{LinkListhead,rear;intlength;}HNode2.3.1單鏈表存儲(chǔ)結(jié)構(gòu)思考題：線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的差異？2.3.2單鏈表的基本運(yùn)算1.初始化線性表InitList(&L)

該運(yùn)算建立一個(gè)空的單鏈表，即創(chuàng)建一個(gè)頭結(jié)點(diǎn)。voidInitList(LinkList&L){L=(LinkList*)malloc(sizeof(LNode));

//創(chuàng)建頭結(jié)點(diǎn)

L->next=NULL;}∧L2.3.2單鏈表的基本運(yùn)算從一個(gè)空表開(kāi)始，創(chuàng)建一個(gè)頭結(jié)點(diǎn)。依次輸入數(shù)據(jù)元素，生成新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到結(jié)束為止。Lai-1a1…ais（1）頭插法建表注意：鏈表的結(jié)點(diǎn)順序與邏輯次序相反。2.創(chuàng)建單鏈表CreateList(&L)2.3.2單鏈表的基本運(yùn)算void

CreateListF(LinkList&L){InitList(L)；//初始化為空表，

創(chuàng)建頭結(jié)點(diǎn)，其next域置為NULLLNode*s;intx;//設(shè)數(shù)據(jù)元素的類型為intscanf(＂%d＂,&x);

頭插法建表算法如下：∧L2.3.2單鏈表的基本運(yùn)算while(x!=Minint){s=(LinkList)malloc(sizeof(LNode));//創(chuàng)建數(shù)據(jù)結(jié)點(diǎn)ss->data=x;s->next=L->next;L->next=s;//將s插在原開(kāi)始結(jié)點(diǎn)之前，頭結(jié)點(diǎn)之后scanf(＂%d＂,&x);}}Lai-1a1…aiss->next=L->next;L->next=s;2.3.2單鏈表的基本運(yùn)算La1aj…aisr

（2）尾插法建表注意：鏈表的結(jié)點(diǎn)順序與邏輯次序相同。從一個(gè)空表開(kāi)始，創(chuàng)建一個(gè)頭結(jié)點(diǎn)。依次輸入數(shù)據(jù)元素，生成新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，直到結(jié)束為止。增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)2.3.2單鏈表的基本運(yùn)算voidCreateListR(LinkNode&L){InitList(L)；//初始化為空表Lnode*s,*r=L;//r始終指向尾結(jié)點(diǎn)，開(kāi)始時(shí)指向頭結(jié)點(diǎn)

intx;//設(shè)數(shù)據(jù)元素的類型為intscanf(＂%d＂,&x);

尾插法建表算法如下：∧Lr2.3.2單鏈表的基本運(yùn)算while(x!=flag)//flag為輸入結(jié)束標(biāo)志

{s=（LinkList）malloc(sizeof(LNode));s->data=x;r->next=s;//將結(jié)點(diǎn)s插入結(jié)點(diǎn)r的后面

r=s;//r指向新的尾結(jié)點(diǎn)

scanf(＂%d＂,&x);}r->next=NULL;//對(duì)于非空表，最后結(jié)點(diǎn)的指針域放空指針

//尾結(jié)點(diǎn)next域置為NULL}rLa1ai-1…aisr->next=s2.3.2單鏈表的基本運(yùn)算3.求線性表的長(zhǎng)度ListLength(L)

返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

intListLength(LinkList*L){

LNode*p=L;/*p指向頭結(jié)點(diǎn)*/intj=0;//p指向頭結(jié)點(diǎn)，j置為0（即頭結(jié)點(diǎn)的序號(hào)為0）

初始時(shí)L∧…pj=02.3.2單鏈表的基本運(yùn)算while(p->next){p=p->next;j++;}//p所指的是第j個(gè)結(jié)點(diǎn)

returnj;

//循環(huán)結(jié)束，p指向尾結(jié)點(diǎn)，其序號(hào)j為結(jié)點(diǎn)個(gè)數(shù)}循環(huán)結(jié)束時(shí)L∧pj為結(jié)點(diǎn)個(gè)數(shù)…2.3.2單鏈表的基本運(yùn)算

（1）按序號(hào)查找GetElem(L，i，&e)

在單鏈表L中從頭開(kāi)始找到第i個(gè)結(jié)點(diǎn)，若存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，則將其data域值賦給變量e。4.查找算法2.3.2單鏈表的基本運(yùn)算boolGetElem(LinkList*L，inti，ElemType&e){intj=1;LinkNode*p=L->next; //p指向第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，j置為1while(j<i&&p!=NULL)

{ j++; p=p->next;}找第i個(gè)結(jié)點(diǎn)p循環(huán)結(jié)束時(shí)Lean∧…i…p2.3.2單鏈表的基本運(yùn)算if(!p||j>i) //不存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，返回falsereturnfalse;else //存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)，返回true{e=p->data;returntrue;}}Lean∧…i…p算法的時(shí)間復(fù)雜度為O(n)

不具有隨機(jī)存取特性2.3.2單鏈表的基本運(yùn)算（2）按元素值查找LocateElem(L，x)

在單鏈表L中從頭開(kāi)始找第一個(gè)值域與x相等的結(jié)點(diǎn)，若存在這樣的結(jié)點(diǎn)，則返回位置，否則返回0。

intLocateElem(LinkNode*L，ElemTypeX){inti=1;LinkNode*p=L->next; //p指向開(kāi)始結(jié)點(diǎn)，i置為1while(p!=NULL&&p->data!=x){p=p->next; //查找data值為x的結(jié)點(diǎn)，其序號(hào)為ii++;}

循環(huán)結(jié)束時(shí)Lx∧…i…p2.3.2單鏈表的基本運(yùn)算Lx∧…i…if(p==NULL) //不存在元素值為x的結(jié)點(diǎn)，返回0return(0);else //存在元素值為x的結(jié)點(diǎn)，返回其邏輯序號(hào)ireturn(i);}2.3.2單鏈表的基本運(yùn)算5.插入算法（1）后插結(jié)點(diǎn)操作插入操作：將值為x的新結(jié)點(diǎn)s插入到p結(jié)點(diǎn)之后。特點(diǎn)：只需修改相關(guān)結(jié)點(diǎn)的指針域，不需要移動(dòng)結(jié)點(diǎn)。2.3.2單鏈表的基本運(yùn)算abx…p…s

s->next=p->next

p->next=s插入操作語(yǔ)句描述如下：

s->next=p->next;

p->next=s;單鏈表插入結(jié)點(diǎn)演示P結(jié)點(diǎn)next的修改盡可能放在后面執(zhí)行2.3.2單鏈表的基本運(yùn)算5.插入算法（2）前插結(jié)點(diǎn)操作插入操作：將值為x的新結(jié)點(diǎn)s插入到q結(jié)點(diǎn)之后。查找操作：查找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)q。2.3.2單鏈表的基本運(yùn)算插入算法ListInsert(&L，i，e)

先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)p，若存在這樣的結(jié)點(diǎn)，將值為x的結(jié)點(diǎn)結(jié)點(diǎn)s插入到其后。boolListInsert(LinkList&L，inti，ElemTypex){intj=0;LNode*p=L，*s; //p指向頭結(jié)點(diǎn)，j置為0

if(i<=0)returnfalse;//參數(shù)i錯(cuò)誤，返回falsewhile(j<i-1&&p!=NULL)

{ j++; p=p->next;}查找第i-1個(gè)結(jié)點(diǎn)L∧…i-1…p2.3.2單鏈表的基本運(yùn)算if(p==NULL) //未找到第i-1個(gè)結(jié)點(diǎn)，返回falsereturnfalse;else //找到第i-1個(gè)結(jié)點(diǎn)p，插入新結(jié)點(diǎn)并返回true{ s=(LinkList*)malloc(sizeof(LNode)); s->data=x; //創(chuàng)建新結(jié)點(diǎn)s，其data域置為x s->next=p->next; //將s插入到p之后

p->next=s; returntrue;}}插入L∧…i-1…pes2.3.2單鏈表的基本運(yùn)算abx…p…p->next=p->next->next刪除操作語(yǔ)句描述如下：

p->next=p->next->next;單鏈表刪除結(jié)點(diǎn)演示為了釋放被刪除結(jié)點(diǎn)，操作語(yǔ)句描述如下：

q=p->next;p->next=q->next;free(q);2.3.2單鏈表的基本運(yùn)算6.刪除算法（刪除第i個(gè)結(jié)點(diǎn)）

先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)q，若存在這樣的結(jié)點(diǎn)，且也存在后繼結(jié)點(diǎn)，則刪除該后繼結(jié)點(diǎn)。

boolListDelete(LinkNode*&L，inti，ElemType&e){intj=0;LNode*p=L，*q; //p指向頭結(jié)點(diǎn)，j置為0if(i<=0)returnfalsewhile(j<i-1&&p!=NULL) //查找第i-1個(gè)結(jié)點(diǎn)

{ j++; p=p->next;}查找第i-1個(gè)結(jié)點(diǎn)L∧…i-1…p2.3.2單鏈表的基本運(yùn)算if(p==NULL) //未找到第i-1個(gè)結(jié)點(diǎn)，返回false returnfalse;else //找到第i-1個(gè)結(jié)點(diǎn)p{s=p->next; //q指向第i個(gè)結(jié)點(diǎn)

if(s==NULL) //若不存在第i個(gè)結(jié)點(diǎn)，返回false returnfalse;e=s->data;p->next=s->next; //從單鏈表中刪除q結(jié)點(diǎn)

free(s); //釋放q結(jié)點(diǎn)

returntrue; //返回true表示成功刪除第i個(gè)結(jié)點(diǎn)

}}刪除第i個(gè)結(jié)點(diǎn)L∧…i-1…p2.3.2單鏈表的基本運(yùn)算6.刪除算法（刪除值為x的結(jié)點(diǎn)）

先在單鏈表L中找到值為x結(jié)點(diǎn)p，若存在這樣的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)。

boolListDelete(LinkList&L，ElemType&e){LinkLists,p=L;while(p->next&&p->next->data!=x)p=p->next;//查找值為x的結(jié)點(diǎn)

if(!p){printf(＂結(jié)點(diǎn)不存在\n＂);returnfalse;}else{s=p->next;//s指向第i個(gè)結(jié)點(diǎn)

p->next=s->next;//從鏈表中刪除

free(s);//釋放*sreturntrue;}}查找值為x的結(jié)點(diǎn)L∧…x…p2.3.2單鏈表的基本運(yùn)算7.歸并算法ListMerge(L1,L2,&L)兩個(gè)有序單鏈表L1和L2。設(shè)計(jì)一個(gè)算法，將它們合并成一個(gè)有序單鏈表L。二路歸并示意圖二路歸并L1L2L2.3.2單鏈表的基本運(yùn)算voidListMerge(LinkListL1,L2,&L)

{LinkListL,h1,h2,h;h1=L1->next;h2=L2->next;//初始化L=L1;h=L;while(h1&&h2)//從h1和h2選擇較小者鏈接到*h后

if(h1->data<=h2->data){h->next=h1;h=h1;h1=h1->next;}//h1小，鏈接*h1else{h->next=h2;h=h2;h2=h2->next;}//h2小，鏈接*h2if(h1)h->next=h1;//鏈接h1的剩余部分if(h2)h->next=h2;//鏈接h2的剩余部分

}2.3.2單鏈表的基本運(yùn)算8.逆置算法ListReverse(&L)

【例（補(bǔ)充）】假設(shè)有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L=（a1，a2，…，an）。設(shè)計(jì)一個(gè)算法將所有結(jié)點(diǎn)逆置，即：

L=（an，an-1，…，a1）∧La1a2an∧…p頭插法建表2.3.2單鏈表的基本運(yùn)算8.逆置算法ListReverse(&L)voidReverse(LinkNode*&L){LinkNode*p=L->next，*q;L->next=NULL;

∧La1a2an∧…p將L拆分為兩個(gè)部分2.3.2單鏈表的基本運(yùn)算8逆置算法ListReverse(&L)while(p!=NULL){q=p->next; //臨時(shí)保存p的后繼結(jié)點(diǎn)p->next=L->next;

//將p結(jié)點(diǎn)采用頭插法連接

L->next=p;p=q;}}∧La1a2an∧…p頭插法建表2.3.3雙向鏈表在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)物理結(jié)點(diǎn)增加一個(gè)指向后繼結(jié)點(diǎn)的指針域和一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針域

雙鏈表。2.3.3雙向鏈表為什么要討論雙向鏈表?p單鏈表：?jiǎn)捂湵淼慕Y(jié)點(diǎn)有指示直接后繼的指針域找后繼結(jié)點(diǎn)方便即：查找某結(jié)點(diǎn)的后繼結(jié)點(diǎn)的執(zhí)行時(shí)間為

O(1)雙向鏈表：在單鏈表的每個(gè)結(jié)點(diǎn)里面再增加一個(gè)指向其直接前驅(qū)的指針域prior，使得鏈表中形成兩個(gè)方向不同的鏈。沒(méi)有指示之間前驅(qū)的指針域找前驅(qū)結(jié)點(diǎn)難，必須從表頭指針出發(fā)即：查找某結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的執(zhí)行時(shí)間為

O(n)2.3.3雙向鏈表線性表(a1,a2,…,ai,…,an)映射邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)a1an∧…L帶頭結(jié)點(diǎn)雙鏈表示意圖2.3.3雙向鏈表從任一結(jié)點(diǎn)出發(fā)可以快速找到其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)；從任一結(jié)點(diǎn)出發(fā)可以訪問(wèn)其他結(jié)點(diǎn)。雙鏈表的優(yōu)點(diǎn)：a1an∧…L2.3.3雙向鏈表typedefstructDLNode //雙鏈表結(jié)點(diǎn)類型{ElemTypedata;structDLNode*prior，*next; //指向前驅(qū)、后繼結(jié)點(diǎn)}DLNode，*DLinkList;

對(duì)于雙鏈表，采用類似于單鏈表的類型定義，其結(jié)點(diǎn)類型DLinkList聲明如下：2.3.3雙向鏈表abc…ps操作語(yǔ)句：

s->prior=p->prior

p->prior->next=s

s->next=p

p->prior=s

在p結(jié)點(diǎn)之前插入結(jié)點(diǎn)s…（1）雙鏈表插入結(jié)點(diǎn)操作插入完畢p結(jié)點(diǎn)next的修改盡可能放在后面執(zhí)行2.3.3雙向鏈表abcp操作語(yǔ)句：

p->prior->next=p->next；

p->next->prior=p>prior；

free(p)…

刪除p結(jié)點(diǎn)（2）雙鏈表刪除結(jié)點(diǎn)操作刪除完畢2.3.4循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)形式。

單循環(huán)鏈表：將表中尾結(jié)點(diǎn)的指針域改為指向表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此從表中任一結(jié)點(diǎn)出發(fā)均可找到鏈表中其他結(jié)點(diǎn)。雙循環(huán)鏈表：形成兩個(gè)環(huán)。結(jié)點(diǎn)類型與非循環(huán)單鏈表的相同結(jié)點(diǎn)類型與非循環(huán)雙鏈表的相同2.3.4循環(huán)鏈表線性表(a1,a2,…,ai,…,an)映射邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)a1a2an…L帶頭結(jié)點(diǎn)單循環(huán)鏈表示意圖1、單循環(huán)鏈表2.3.4循環(huán)鏈表鏈表中沒(méi)有空指針域p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件：p->next==L與非循環(huán)單鏈表相比，單循環(huán)鏈表：a1a2an…Lp1、單循環(huán)鏈表2.3.4循環(huán)鏈表

某線性表最常用的操作是在尾元素之后插入一個(gè)元素和刪除第一個(gè)元素，故采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭結(jié)點(diǎn)指針的單循環(huán)鏈表C.雙鏈表

D.僅有尾結(jié)點(diǎn)指針的單循環(huán)鏈表示例1、單循環(huán)鏈表