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

數(shù)據(jù)結(jié)構(gòu)用C語(yǔ)言描述耿國(guó)華等編著2/1/20231[重點(diǎn)、難點(diǎn)]鏈表結(jié)構(gòu)，重點(diǎn)掌握單鏈表、循環(huán)鏈表、雙向鏈表，初步掌握靜態(tài)鏈表。2/1/20232[學(xué)習(xí)要點(diǎn)]1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，鏈表是本章的重點(diǎn)和難點(diǎn)。3.熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作：查找、插入和刪除的算法。4.熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。5.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。2/1/20233第2章

線性表

2.1線性表的概念及運(yùn)算2.2線性表的順序存儲(chǔ)2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.4一元多項(xiàng)式的表示及相加2/1/202342.1線性表的概念及運(yùn)算2.1.1線性表的邏輯結(jié)構(gòu)

2.1.2線性表的抽象數(shù)據(jù)類型定義

2/1/20235線性表的定義定義：線性表(LinearList)是由n(n≥0)個(gè)類型相同的數(shù)據(jù)元素a1,a2,…，an組成的有限序列，記做（a1,a2,…，ai-1，ai，ai+1，…，an）。數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。邏輯結(jié)構(gòu)圖：2/1/20236線性表的特點(diǎn)①同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)ai必須屬于同一數(shù)據(jù)對(duì)象。②有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長(zhǎng)度就是表中數(shù)據(jù)元素的個(gè)數(shù)。③有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系<ai,ai+1>。2/1/202372.1.2線性表的抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義

：ADTLinearList{

數(shù)據(jù)元素：D={ai|ai∈D0,i=1,2,…，n

n≥0，D0為某一數(shù)據(jù)對(duì)象}

關(guān)系：Ｓ＝｛<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝基本操作：（1）InitList（L）操作前提：L為未初始化線性表。 操作結(jié)果：將L初始化為空表。（2）DestroyList(L)操作前提：線性表L已存在。操作結(jié)果：將L銷毀。（3）ClearList(L)操作前提：線性表L已存在

。操作結(jié)果：將表L置為空表。

………}ADT

LinearList2/1/202382.2線性表的順序存儲(chǔ)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)

2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算

2/1/20239順序存儲(chǔ)結(jié)構(gòu)的定義定義:采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。假設(shè)線性表中每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為loc(a1)，則第k個(gè)元素的地址為：loc(ai)=loc(a1)+(i-1)×k是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中。2/1/202310...loc(a1)+(maxlen-1)knan

loc(a1)+(n-1)k………iai

loc(a1)+(i-1)k………2a2

Loc(a1)+(2-1)k1a1Loc(a1)邏輯地址內(nèi)存空間狀態(tài)存儲(chǔ)地址順序存儲(chǔ)結(jié)構(gòu)示意圖空閑順序存儲(chǔ)結(jié)構(gòu)示意圖2/1/202311順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義#define maxsize=線性表可能達(dá)到的最大長(zhǎng)度；typedef

struct{

ElemType

elem[maxsize]；/*線性表占用的數(shù)組空間*/

intlast；

/*記錄線性表中最后一個(gè)元素在數(shù)組elem[]

中的位置（下標(biāo)值），空表置為-1*/}SeqList；

注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo)，如a1的序號(hào)為1，而其對(duì)應(yīng)的數(shù)組下標(biāo)為0。

2/1/2023122.2.2線性表順序存儲(chǔ)結(jié)構(gòu)的基本運(yùn)算線性表的基本運(yùn)算：查找操作

插入操作

刪除操作順序表合并算法線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)分析2/1/202313查找操作線性表的兩種基本查找運(yùn)算按序號(hào)查找GetData(L,i)：要求查找線性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]或L->elem[i-1]。按內(nèi)容查找Locate（L,e）:

要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。線性表的查找運(yùn)算算法描述為：2/1/202314線性表的查找運(yùn)算int

Locate(SeqListL，ElemTypee){ i=0;/*i為掃描計(jì)數(shù)器，初值為0，即從第一個(gè)元素開始比較*/while((i<=L.last)&&(L.elem[i]!=e)

)i++;/*順序掃描表，直到找到值為key的元素,或掃描到表尾而沒(méi)找到*/if(i<=L.last)

return(i);/*若找到值為e的元素，則返回其序號(hào)*/

else return(-1);/*若沒(méi)找到，則返回空序號(hào)*/}2/1/202315插入操作線性表的插入運(yùn)算是指在表的第i(1≤i≤n+1)個(gè)位置，插入一個(gè)新元素e，使長(zhǎng)度為n的線性表(e1，…，ei-1，ei，…，en)變成長(zhǎng)度為n+1的線性表（e1，…,ei-1，e，ei，…，en）。

線性表的插入運(yùn)算算法。2/1/202316插入算法示意圖

已知：線性表

(4,9,15,28,30,30,42,51,62)，需在第4個(gè)元素之前插入一個(gè)元素“21”。則需要將第9個(gè)位置到第4個(gè)位置的元素依次后移一個(gè)位置，然后將“21”插入到第4個(gè)位置，序號(hào)移動(dòng)元素插入元素12345678109491528303042516249152830304262514915212830304262512/1/202317插入運(yùn)算int

InsList(SeqList*L,int

i,ElemTypee){intk;if((i<1)||(i>L->last+2))/*首先判斷插入位置是否合法*/{printf(“插入位置i值不合法”)；return(ERROR);}

if(L->last>=maxsize-1){printf(“表已滿無(wú)法插入”)；return(ERROR);}

for(k=L->last;k>=i-1;k--)/*為插入元素而移動(dòng)位置*/L->elem[k+1]=L->elem[k];L->elem[i-1]=e;/*在C語(yǔ)言中數(shù)組第i個(gè)元素的下標(biāo)為i-1*/

L->last++;

return(OK);}

算法演示（此處連接算法演示程序）。2/1/202318刪除操作

線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個(gè)元素刪去，使長(zhǎng)度為n的線性表

(e1，…,ei-1，ei，ei+1，…，en)，變成長(zhǎng)度為n-1的線性表(e1，…,ei-1，

ei+1，…，en)。

算法思路示意

算法實(shí)現(xiàn)2/1/202319刪除算法示意

將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個(gè)元素刪除。

序號(hào)123456781094915212830304262514915213030425162刪除28后2/1/202320刪除算法

int

DelList(SeqList*L,int

i,ElemType*e)/*在順序表L中刪除第i個(gè)數(shù)據(jù)元素，并用指針參數(shù)e返回其值*/{intk;

if((i<1)||(i>L->last+1)){printf(“刪除位置不合法！”)；return(ERROR)；}*e=L->elem[i-1];

/*將刪除的元素存放到e所指向的變量中*/

for(k=i;i<=L->last;k++)L->elem[k-1]=L->elem[k];/*將后面的元素依次前移*/L->last--;

return(OK);}

2/1/202321合并算法已知

：有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列，編寫一個(gè)算法，將它們合并成一個(gè)順序表LC，要求LC也是非遞減有序排列。

算法思想：設(shè)表LC是一個(gè)空表，為使LC也是非遞減有序排列，可設(shè)兩個(gè)指針i、j分別指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，則當(dāng)前先將LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j]，當(dāng)前先將LA.elem[i]插入到表LC中，如此進(jìn)行下去，直到其中一個(gè)表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中。算法實(shí)現(xiàn)此處連接算法演示2/1/202322順序表合并算法實(shí)現(xiàn)voidmerge(SeqList*LA,SeqList*LB,SeqList*LC){i=0;j=0;k=0;

while(i<=LA->last&&j<=LB->last)

if(LA->elem[i]<=LB->elem[j])

{

LC->elem[k]=LA->elem[i];i++;k++;}

else

{

LC->elem[k]=LB->elem[j];j++;k++;}

while(i<=LA->last)

/*當(dāng)表LA長(zhǎng)則將表LA余下的元素賦給表LC*/

{

LC->elem[k]=LA->elem[i];

i++;k++;}

while(j<=LB->last)/*當(dāng)表LB長(zhǎng)則將表LB余下的元素賦給表LC*/

{

LC->elem[k]=LB->elem[j];j++;k++;}

LC->last=LA->last+LB->last;}2/1/202323順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：1.無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；

2.可方便地隨機(jī)存取表中的任一元素。

缺點(diǎn)：1.插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低；

2.由于順序表要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。2/1/2023242.3線性表的鏈?zhǔn)酱鎯?chǔ)鏈表定義：

采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表?，F(xiàn)在我們從兩個(gè)角度來(lái)討論鏈表：1.從實(shí)現(xiàn)角度看，鏈表可分為動(dòng)態(tài)鏈表和靜態(tài)鏈表；2.從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。

2/1/2023252.3.1單鏈表

2.3.2單鏈表上的基本運(yùn)算

2.3.3循環(huán)鏈表

2.3.4雙向鏈表

*2.3.5靜態(tài)鏈表

2.3.6順序表和鏈表的比較鏈表2/1/2023262.3.1單鏈表

結(jié)點(diǎn)（Node）為了正確地表示結(jié)點(diǎn)間的邏輯關(guān)系，必須在存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值的同時(shí)，存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這兩部分信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)（Node）。單鏈表：鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，我們將這種鏈表稱為單鏈表。單鏈表包括兩個(gè)域：數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值；指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址（或位置）。頭指針：指向鏈表頭結(jié)點(diǎn)的指針。2/1/202327單鏈表的示例圖頭指針H存儲(chǔ)地址數(shù)據(jù)域指針域1D437B1313C119HNULL25F3731A737G1943E25312/1/202328單鏈表節(jié)點(diǎn)關(guān)系datanextdatanextdatanext指針域數(shù)據(jù)域前驅(qū)后續(xù)P->nextP

P

PP->pre2/1/202329帶頭結(jié)點(diǎn)的單鏈表示意圖有時(shí)為了操作的方便，還可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的空單鏈表

帶頭結(jié)點(diǎn)的單鏈表

∧Ha1a2…Han

∧2/1/202330單鏈表的存儲(chǔ)結(jié)構(gòu)描述typedef

structNode/*結(jié)點(diǎn)類型定義*/{ElemTypedata；

structNode*next；}Node,*LinkList；/*LinkList為結(jié)構(gòu)指針類型*/

2/1/2023312.3.2單鏈表上的基本運(yùn)算線性表的基本運(yùn)算：建立單鏈表

單鏈表查找

單鏈表插入操作

單鏈表刪除

算法應(yīng)用示例：求單鏈表的長(zhǎng)度

求兩個(gè)集合的差

2/1/202332建立單鏈表頭插法建表

算法描述：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。c1∧sL∧L

ci-1∧c2c1∧ci

s…c1∧2/1/202333建立單鏈表c1∧H

∧S指向新申請(qǐng)的節(jié)點(diǎn)S-->data=c1H-->next=ssc1∧H

s2/1/202334頭插法建表H

c2s①

H-->next=S①H-->nextc1∧2/1/202335頭插法建表H

c2s①

S-->next

=H-->next①H-->nextc1∧②

H-->next=S②H

c2c1∧2/1/202336頭插法建表H

c2c1∧H

cici-1c1∧注：頭插法得到的單鏈表的邏輯順序與輸入元素順序相反，即為逆序建表。2/1/202337頭插法建表算法Linklist

CreateFromHead(){LinkListL;Node*s;intflag=1;

/*設(shè)置一個(gè)標(biāo)志，初值為1，當(dāng)輸入“$”時(shí)，flag為0，建表結(jié)束*/L=(Linklist)malloc(sizeof(Node))；/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/

L->next=NULL;

while(flag){c=getchar();

if(c!=’$’)/*為讀入的字符分配存儲(chǔ)空間*/{s=(Node*)malloc(sizeof(Node));s->data=c;s->next=L->next;L->next=s;}else

flag=0;}}

2/1/202338尾插法建表（建表及插入第一個(gè)節(jié)點(diǎn)）H

①

r-->next=Sc1r②

r=SS指向新申請(qǐng)的節(jié)點(diǎn)S-->data=c1∧s2/1/202339尾插法建表（插入第二個(gè)節(jié)點(diǎn)）H

c2①

r-->next=S①c1r②

r=Ss∧②2/1/202340尾插法建表H

c2c1rs∧注：尾插法得到的單鏈表的邏輯順序與輸入元素順序相同，即為順序建表。H

c1c2ci

∧rs2/1/202341尾插法建表算法Linklist

CreateFromTail()/*將新增的字符追加到鏈表的末尾*/{LinkListL;Node*r,*s;intflag=1;

L=(Node*)malloc(sizeof(Node));/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/L->next=NULL;r=L;/*r指針始終動(dòng)態(tài)指向鏈表的當(dāng)前表尾*/

while(flag)/*標(biāo)志，初值為1。輸入“$”時(shí)flag為0，建表結(jié)束*/

{ c=getchar();

if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s}else{flag=0;r->next=NULL;}}}2/1/202342單鏈表查找按序號(hào)查找

算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)（L->next）開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向頭結(jié)點(diǎn)（pL->next），用j做記數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)（初值為0），當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。算法實(shí)現(xiàn)，算法演示。 2/1/202343按序號(hào)查找算法實(shí)現(xiàn)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1≤i≤n)，則返回該結(jié)點(diǎn)的存儲(chǔ)位置;否則返回NULL*/Node*

Get(LinkListL,inti){Node*p；

p=L；j=0；/*從頭結(jié)點(diǎn)開始掃描*/while((p->next!=NULL)&&(j<i){p=p->next；j++；/*掃描下一結(jié)點(diǎn)*/}/*已掃描結(jié)點(diǎn)計(jì)數(shù)器*/if（i==j）returnp；/*找到了第i個(gè)結(jié)點(diǎn)*/elsereturnNULL；/*找不到，i≤0或i>n*/}2/1/202344按值查找

算法描述：按值查找是指在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。算法實(shí)現(xiàn)，算法演示。單鏈表查找2/1/202345按值查找算法實(shí)現(xiàn)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p，否則返回NULL*/Node*Locate(LinkList

L,ElemTypekey){Node*p;p=L->next;/*從表中第一個(gè)結(jié)點(diǎn)比較*/while(p!=NULL)if(p->data!=key) p=p->next;elsebreak;/*找到結(jié)點(diǎn)key，退出循環(huán)*/returnp;}2/1/202346單鏈表插入操作算法描述：

要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素e，需要首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)并由指針pre指示，然后申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由指針s指示，其數(shù)據(jù)域的值為e，并修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向s，然后使s結(jié)點(diǎn)的指針域指向第i個(gè)結(jié)點(diǎn)。esa1……an∧ai-1aiespreLa1……an∧preai-1ai2/1/202347單鏈表插入H

a1aian∧sai-1epre①與ai鏈接S->next=pre->next②ai-1與ai斷鏈插入epre->next=s2/1/202348單鏈表插入操作算法實(shí)現(xiàn)voidInsList(LinkList

L,int

i,ElemTypee){/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)結(jié)點(diǎn)之前插入值為e的新結(jié)點(diǎn)。*/

Node*pre,*s;

pre=L;intk=0;

while(pre!=NULL&&k<i-1)/*先找到第i-1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置,使指針Pre指向它*/

{pre=pre->next;

k=k+1;}

if(k!=i-1){printf(“插入位置不合理！”)；return;}s=(Node*)malloc(sizeof(Node));/*為e申請(qǐng)一個(gè)新的結(jié)點(diǎn)*/s->data=e;/*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/s->next=pre->next;pre->next=s;}

2/1/202349單鏈表最后一個(gè)元素怎么查找？H

a1aian∧ai-1preWhile（?）{pre=pre-->next;}pre!=null插入位置1≤i≤m+12/1/202350單鏈表刪除算法描述： 欲在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，則首先要通過(guò)計(jì)數(shù)方式找到第i-1個(gè)結(jié)點(diǎn)并使p指向第i-1個(gè)結(jié)點(diǎn)，而后刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。pa1…ai-1ai…an∧pa1…L…an∧ai-1aiai+1rL2/1/202351單鏈表刪除H

ai+1aian∧rai-1p②①①

r=p-->next②

p-->next=p-->next-->next③

free（r）這個(gè)節(jié)點(diǎn)用指針p怎么表示？p-->next-->next2/1/202352單鏈表刪除H

an-1aian∧ai-1pWhile（?）{pre=pre-->next;}P->next!=null刪除位置1≤i≤mpp2/1/202353單鏈表刪除算法實(shí)現(xiàn)voidDelList(LinkList

L,int

i,ElemType*e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并保存其值到變量*e中*/{

Node*p,*r;p=L;intk=0;

while(p->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)*/{p=p->next;k=k+1;}if(k!=i-1)/*即while循環(huán)是因?yàn)閜->next=NULL而跳出的*/{printf(“刪除結(jié)點(diǎn)的位置i不合理！”);returnERROR;}r=p->next;p->next=p->next->next/*刪除結(jié)點(diǎn)r*/free(r);/*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/}2/1/202354求單鏈表的長(zhǎng)度

算法描述：可以采用“數(shù)”結(jié)點(diǎn)的方法來(lái)求出單鏈表的長(zhǎng)度，用指針p依次指向各個(gè)結(jié)點(diǎn),從第一個(gè)元素開始“數(shù)”，一直“數(shù)”到最后一個(gè)結(jié)點(diǎn)（p->next=NULL）。

int

ListLength(LinkListL)/*L為帶頭結(jié)點(diǎn)的單鏈表*/{Node*p;p=L->next; j=0;/*用來(lái)存放單鏈表的長(zhǎng)度*/

while(p!=NULL){ p=p->next;j++;}returnj;}2/1/202355求兩個(gè)集合的差已知：以單鏈表表示集合，假設(shè)集合A用單鏈表LA表示，集合B用單鏈表LB表示，設(shè)計(jì)算法求兩個(gè)集合的差，即A-B。算法思想：由集合運(yùn)算的規(guī)則可知，集合的差A(yù)-B中包含所有屬于集合A而不屬于集合B的元素。具體做法是，對(duì)于集合A中的每個(gè)元素e，在集合B的鏈表LB中進(jìn)行查找，若存在與e相同的元素，則從LA中將其刪除。算法實(shí)現(xiàn)算法演示鏈接2/1/202356求兩個(gè)集合的差算法實(shí)現(xiàn)voidDifference(LinkList

LA,LinkListLB)/*此算法求兩個(gè)集合的差集*/{Node*pre;*p,*r;pre=LA;p=LA->next;/*p向表中的某一結(jié)點(diǎn)，pre始終指向p的前驅(qū)*/

while(p!=NULL){q=LB->next;/*掃描LB中的結(jié)點(diǎn)，尋找與LA中*P結(jié)點(diǎn)相同的結(jié)點(diǎn)*/while(q!=NULL&&q->data!=p->data)q=q->next;if(q!=NULL){r=p;pre->next=p->next;p=p->next;free(r);}else{pre=p;p=p->next;}}}2/1/2023572.3.3循環(huán)鏈表

循環(huán)鏈表(CircularLinkedList)

是一個(gè)首尾相接的鏈表。特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。

帶頭結(jié)點(diǎn)循環(huán)單鏈表示意圖。2/1/202358循環(huán)鏈表L

aianai-1∧2/1/202359帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖

L(a)空鏈表

2/1/202360帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖（b）帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式

a1……ai-1aianL2/1/202361帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖a1……ai-1aian*(rear->next)*rear(c)采用尾指針的循環(huán)單鏈表的一般形式

rear2/1/202362循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表

已知：有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為L(zhǎng)A。 算法思想：先找到兩個(gè)鏈表的尾，并分別由指針p、q指向它們，然后將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來(lái)，并修改第二個(gè)表的尾Q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。

2/1/202363循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表a1……ai-1aianb1……bi-1bibn

pqLALB2/1/202364循環(huán)單鏈表合并算法實(shí)現(xiàn)LinkListmerge_1(LinkListLA,LinkListLB)/*此算法將兩個(gè)鏈表的首尾連接起來(lái)*/{Node*p,*q;p=LA;q=LB;while(p->next!=LA)p=p->next; /*找到表LA的表尾*/while(q->next!=LB)q=q->next; /*找到表LB的表尾*/q->next=LA;/*修改表LB的尾指針，使之指向表LA的頭結(jié)點(diǎn)*/p->next=LB->next;/*修改表LA的尾指針，使之指向表LB中的第一個(gè)結(jié)點(diǎn)*/

free(LB);return(LA);}2/1/2023652.3.4雙向鏈表

雙向鏈表：在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙

(向)鏈表

(DoubleLinkedList)。雙向鏈表的結(jié)構(gòu)定義：

typedef

struct

Dnode {ElemTypedata；

struct

DNode*prior，*next；

}DNode, *DoubleList；2/1/202366雙鏈表的結(jié)構(gòu)定義雙鏈表的結(jié)點(diǎn)結(jié)構(gòu)

后繼指針域priordatanext前驅(qū)指針域數(shù)據(jù)域2/1/202367雙向循環(huán)鏈表示意圖

a1

a2

a3LL空的雙向循環(huán)鏈表

非空的雙向循環(huán)鏈表

2/1/202368雙向鏈表的前插操作算法描述：欲在雙向鏈表第i個(gè)結(jié)點(diǎn)之前插入一個(gè)的新的結(jié)點(diǎn)，則指針的變化情況如圖所示。

es②④①③

…

bp

a

…p->priors->prior=p->priorp->prior->next=ss->next=pp->prior=s2/1/202369雙向鏈表的前插操作算法實(shí)現(xiàn)void

DlinkIns(DoubleList

L,int

i,ElemTypee)

{DNode

*s,*p; …/*首先檢查待插入的位置i是否合法*/

…/*若位置i合法，則讓指針p指向它*/s=(DNode*)malloc(sizeof(DNode));if(s){s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnTRUE;}

else

returnFALSE;}

算法演示連接。2/1/202370雙向鏈表的刪除操作算法描述：欲刪除雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。

a

b

cp②①……

…

c

a

…p->prior->next=p>nextp->next->prior=p>priorp>nextp>priorp>prior->nextp>next->prior2/1/202371雙向鏈表的刪除操作算法實(shí)現(xiàn)int

DlinkDel(DoubleList

L,int

i,ElemType

*e)

{ DNode

*p; …/*首先檢查待插入的位置i是否合法*/

…/*若位置i合法，則讓指針p指向它*/ *e=p->data; p->prior->next=p->next; p->next->prior=p->prior;

free(p); returnTRUE;}2/1/202372雙向鏈表應(yīng)用舉例已知：設(shè)一個(gè)循環(huán)雙鏈表L=（a,b,c,d）編寫一個(gè)算法將鏈表轉(zhuǎn)換為L(zhǎng)=（b,a,c,d）。算法思想：實(shí)際上是交換表中前兩個(gè)元素的次序。算法實(shí)現(xiàn)：void swap(DLinkListL){DNode*p,*q,*h;h=L->next; /*h指向表中的第一個(gè)結(jié)點(diǎn)，即a*/p=h->next; /*p指向b結(jié)點(diǎn)*/q=h->prior; /*保存a結(jié)點(diǎn)的前驅(qū)*/h->next=p->next;p->next->prior=h;/*變換指針指向*/p->prior=q;p->next=h;L->next=p; }

2/1/202373*2.3.5靜態(tài)鏈表基本概念：

游標(biāo)實(shí)現(xiàn)鏈表的方法：定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池）。當(dāng)申請(qǐng)結(jié)點(diǎn)時(shí)，每個(gè)結(jié)點(diǎn)應(yīng)含有兩個(gè)域：data域和next域。data域存放結(jié)點(diǎn)的數(shù)據(jù)信息，next域?yàn)橛螛?biāo)指示器，指示后繼結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組中的相對(duì)位置（即數(shù)組下標(biāo)）。數(shù)組的第0個(gè)分量可以設(shè)計(jì)成表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的next域指示了表中第一個(gè)結(jié)點(diǎn)的位置，為0表示靜態(tài)單鏈表的結(jié)束。我們把這種用游標(biāo)指示器實(shí)現(xiàn)的單鏈表叫做靜態(tài)單鏈表(StaticLinkedList)。靜態(tài)鏈表的結(jié)構(gòu)定義，靜態(tài)鏈表的插入和刪除操作示例?；静僮鳎撼跏蓟⒎峙浣Y(jié)點(diǎn)與結(jié)點(diǎn)回收、前插操作、刪除。

2/1/202374靜態(tài)鏈表的結(jié)構(gòu)定義#defineMaxsize=鏈表可能達(dá)到的最大長(zhǎng)度typedef

struct{

ElemTypedata;

intcursor;}Component,StaticList[Maxsize];

2/1/202375靜態(tài)鏈表的插入和刪除操作示例已知：線性表

a，b，c，d，f，g，h，i），Maxsize=110123456789100123456789101a2b3c4d9f6g8h8i0e51a2b3c4d9f6g7h8i0e51a2b3c4d5f6g7h8i0012345678910(a)初始化(b)插入e后(c)刪除h后2/1/202376靜態(tài)鏈表初始化算法描述：初始化操作是指將這個(gè)靜態(tài)單鏈表初始化為一個(gè)備用靜態(tài)單鏈表。設(shè)space為靜態(tài)單鏈表的名字，av為備用單鏈表的頭指針，其算法如下：voidinitial(StaticList

space,int*av){intk;space[0]->cursor=0;/*設(shè)置靜態(tài)單鏈表的頭指針指向位置0*/

for(k=0;k<Maxsize-1;k++)

space[k]->cursor=k+1;/*連鏈*/space[Maxsize-1]=0;/*標(biāo)記鏈尾*/*av=1;/*設(shè)置備用鏈表頭指針初值*/}

2/1/202377靜態(tài)鏈表分配結(jié)點(diǎn)與結(jié)點(diǎn)回收分配結(jié)點(diǎn)int

getnode(int*av)/*從備用鏈表摘下一個(gè)結(jié)點(diǎn)空間，分配給待插入靜態(tài)鏈表中的元素*/{inti=*av;*av=space[*av].cur;returni;}結(jié)點(diǎn)回收voidfreenode(int*av,intk)/*將下標(biāo)為k的空閑結(jié)點(diǎn)插入到備用鏈表*/{space[k].cursor=*av;*av=k;}2/1/202378靜態(tài)鏈表前插操作算法描述：1、先從備用單鏈表上取一個(gè)可用的結(jié)點(diǎn)；2、將其插入到已用靜態(tài)單鏈表第i個(gè)元素之前。voidinsbefore(StaticList

space,int

i,int

*av){j=*av; /*j為從備用表中取到的可用結(jié)點(diǎn)空間的下標(biāo)*/

av=space[av]->cursor; /*修改備用表的頭指針*/

space[j]->data=x; k=space[0]->cursor;/*k為已用靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值*/

for(m=1;m<i-1;m++)/*尋找第i-1個(gè)元素的位置k*/ k=space[k]->cursor;

space[j]->cursor=space[k]->cursor;/*修改游標(biāo)域*/

space[k]->cursor=j;}

2/1/202379靜態(tài)鏈表刪除 算法描述：首先尋找第i-1個(gè)元素的位置，之后通過(guò)修改相應(yīng)的游標(biāo)域進(jìn)行刪除；在將被刪除的結(jié)點(diǎn)空間鏈到可用靜態(tài)單鏈表中，實(shí)現(xiàn)回收。voiddelete(StaticList

space;int

i;int

*av){k=space[0]->cursor;

for(m=1,m<i-1;m++) /*尋找第i-1個(gè)元素的位置k*/k=space[k]->cursor;j=space[k]->cursor;

space[k]->cursor=space[j]->cursor;/*從刪除第i個(gè)元素*/

space[j]->cursor=*av;/*將第i個(gè)元素占據(jù)的空間回收*/

av=j;/*置備用表頭指針以新值*/}2/1/2023802.3.6順序表和鏈表的比較

1．基于空間的考慮

2．基于時(shí)間的考慮

3．基于語(yǔ)言的考慮

2/1/2023812.4一元多項(xiàng)式的表示及相加一個(gè)一元多項(xiàng)式Pn(x)可按升冪的形式寫成：Pn(x)=p0+p1x+p2x2+p3x3+…+pnxn

在計(jì)算機(jī)內(nèi)，可以用一個(gè)線性表P來(lái)表示：

P=（p0，p1，p2，

…，pn）

用單鏈表存儲(chǔ)多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)如下：

typedef

struct

Polynode

{

int

coef;

intexp;

Polynode*next;}Polynode,*Polylist;

2/1/202382建立多項(xiàng)式鏈表算法描述：輸入多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式的鏈表。Polylist

polycreate(){Polynode*head,*rear,*s; int

c,e; rear=head=(Polynode*)malloc(sizeof(Polynode)); /*建立多項(xiàng)式的頭結(jié)點(diǎn)，rear始終指向單鏈表的尾*/

scanf(“%d,%d”,&c,&e);/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng)*/

while(c!=0) /*若c=0，則代表多項(xiàng)式的輸入結(jié)束*/ {s=(Polynode*)malloc(sizeof(Polynode)); /*申請(qǐng)新的結(jié)點(diǎn)*/s->coef=c;s->exp=e;rear->next=s; /*在當(dāng)前表尾做插入*/rear=s; scanf(“%d,%d”,&c,&e);}rear->next=NULL;/*將表的最后一個(gè)結(jié)點(diǎn)的next置NULL，以示表結(jié)束*/

return(head);}2/1/202383多項(xiàng)式的單鏈表表示示意圖說(shuō)明：圖示分別為多項(xiàng)式

A(x)=7+3x+9x8+5x17

B(x)=8x+22x7-9x8

-17031517∧9881-1227-98∧

2/1/202384兩個(gè)多項(xiàng)式相加運(yùn)算規(guī)則：兩個(gè)多項(xiàng)式中所有指數(shù)相同的項(xiàng)的對(duì)應(yīng)系數(shù)相加，若和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；所有指數(shù)不相同的項(xiàng)均復(fù)抄到“和多項(xiàng)式”中。算法實(shí)現(xiàn)，算法演示若p->exp<q->exp，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)

是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移；若p->exp>q->exp，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來(lái)的鏈表上后移；若p->exp=q->exp，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為零時(shí)修改結(jié)點(diǎn)p的系數(shù)域，釋放q結(jié)點(diǎn)；若和