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

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

線性表及其抽象數(shù)據(jù)類(lèi)型2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.6一元多項(xiàng)式的表示及相加2.4棧和隊(duì)列2.5循環(huán)線性鏈表和雙向鏈表1數(shù)據(jù)結(jié)構(gòu)第2章線性表2.1線性表及其抽象數(shù)據(jù)類(lèi)型

定義：線性表(LinearList)是由n(n≥0)個(gè)類(lèi)型相同的數(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數(shù)據(jù)結(jié)構(gòu)第2章線性表特點(diǎn)：①同一性：線性表由同類(lèi)數(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線性表及其抽象數(shù)據(jù)類(lèi)型

3數(shù)據(jù)結(jié)構(gòu)第2章線性表抽象數(shù)據(jù)類(lèi)型定義：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銷(xiāo)毀。

………p11}ADT

LinearList返回2.1線性表及其抽象數(shù)據(jù)類(lèi)型

4數(shù)據(jù)結(jié)構(gòu)第2章線性表2.2線性表的順序存儲(chǔ)結(jié)構(gòu)定義:采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱(chēng)為順序表。假設(shè)線性表中每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為loc(a1)，則第i個(gè)元素的地址為：loc(ai)=loc(a1)+(i-1)×k是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中。5數(shù)據(jù)結(jié)構(gòu)第2章線性表...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)示意圖空閑2.2線性表的順序存儲(chǔ)結(jié)構(gòu)6數(shù)據(jù)結(jié)構(gòu)第2章線性表C語(yǔ)言定義#definemaxsize

線性表可能達(dá)到的最大長(zhǎng)度typedef

struct{

ElemType

elem[maxsize]；

intlast；

}SeqList； 2.2線性表的順序存儲(chǔ)結(jié)構(gòu)7數(shù)據(jù)結(jié)構(gòu)第2章線性表基本運(yùn)算①查找操作②插入操作③刪除操作2.2線性表的順序存儲(chǔ)結(jié)構(gòu)8數(shù)據(jù)結(jié)構(gòu)第2章線性表①查找操作按序號(hào)查找GetData(L,i)：要求查找線性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]。按內(nèi)容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)9數(shù)據(jù)結(jié)構(gòu)第2章線性表按內(nèi)容查找Locate（L,e）:int

Locate(SeqListL，ElemTypee){ i=0;while((i<=L.last)&&(L.elem[i]!=e))i++;if(i<=L.last)return(i+1);else return(-1);}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)10數(shù)據(jù)結(jié)構(gòu)第2章線性表2.2線性表的順序存儲(chǔ)②插入操作是指在表的第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）。例如：線性表(4,9,15,28,30,30,42,51,62)，需在第4個(gè)元素之前插入一個(gè)元素“21”。則需要將第9個(gè)位置到第4個(gè)位置的元素依次后移一個(gè)位置，然后將“21”

插入到第4個(gè)位置。

(4,9,15,2128,30,30,42,51,62)

#defineOK1#defineERROR0

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--)L->elem[k+1]=L->elem[k];

L->elem[i-1]=e;

L->last++;return(OK);}

時(shí)間復(fù)雜度：

O(n)11數(shù)據(jù)結(jié)構(gòu)第2章線性表③刪除操作是指將表的第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)。

int

DelList(SeqList*L,int

i,ElemType*e){

intk;if((i<1)||(i>L->last+1)){

printf(“刪除位置不合法！”)；

return(ERROR)；

}*e=L->elem[i-1];

for(k=i;k<=L->last;k++)L->elem[k-1]=L->elem[k];L->last--;return(OK);}時(shí)間復(fù)雜度：O(n)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)12數(shù)據(jù)結(jié)構(gòu)第2章線性表2.2線性表的順序存儲(chǔ)結(jié)構(gòu)例2-1

：有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列，編寫(xiě)一個(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中。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){LC->elem[k]=LA->elem[i];i++;k++;}while(j<=LB->last){LC->elem[k]=LB->elem[j];j++;k++;}LC->last=LA->last+LB->last+1;}13數(shù)據(jù)結(jié)構(gòu)第2章線性表優(yōu)點(diǎn)：②可方便地隨機(jī)存取表中的任一元素。缺點(diǎn)：①插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低；①無(wú)須為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；②由于順序表要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。返回2.2線性表的順序存儲(chǔ)結(jié)構(gòu)14數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義:采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱(chēng)為鏈表。動(dòng)態(tài)鏈表靜態(tài)鏈表單鏈表雙鏈表循環(huán)鏈表實(shí)現(xiàn)角度鏈接方式15數(shù)據(jù)結(jié)構(gòu)第2章線性表單鏈表：鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域結(jié)點(diǎn)（Node）：?jiǎn)捂湵戆▋蓚€(gè)域數(shù)據(jù)域：指針域：用來(lái)存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)值用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址（或位置）頭指針：指向鏈表頭結(jié)點(diǎn)的指針。為了正確地表示結(jié)點(diǎn)間的邏輯關(guān)系，必須在存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值的同時(shí)，存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這兩部分信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)16數(shù)據(jù)結(jié)構(gòu)第2章線性表單鏈表頭指針H存儲(chǔ)地址數(shù)據(jù)域指針域1D437B1313C119HNULL25F3731A737G1943E2531AHBCDEFGH∧2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)17數(shù)據(jù)結(jié)構(gòu)第2章線性表單鏈表頭結(jié)點(diǎn)H∧帶頭結(jié)點(diǎn)的空單鏈表帶頭結(jié)點(diǎn)的單鏈表EFGH∧H2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)18數(shù)據(jù)結(jié)構(gòu)第2章線性表單鏈表存儲(chǔ)結(jié)構(gòu)描述typedef

structNode{

ElemTypedata；

structNode*next；}Node,*LinkList；2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)19數(shù)據(jù)結(jié)構(gòu)第2章線性表單鏈表的基本運(yùn)算①建立單鏈表②單鏈表查找③單鏈表插入操作④單鏈表刪除⑤求單鏈表的長(zhǎng)度2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)20數(shù)據(jù)結(jié)構(gòu)第2章線性表①建立單鏈表頭插法建表sA∧s指向新申請(qǐng)的結(jié)點(diǎn)s->data=A;H∧sA∧插入第一個(gè)結(jié)點(diǎn)：插入某一個(gè)結(jié)點(diǎn)：H∧A∧sB∧從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止?！立賡->next=H->next;②H->next=s;順序可以顛倒嗎？H∧初始化空表2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)21數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)①建立單鏈表頭插法建表算法

Linklist

CreateFromHead(){

LinkListL;Node*s;charc;

intflag=1;L=(Linklist)malloc(sizeof(Node))；

L->next=NULL;while(flag){c=getchar();if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;

s->next=L->next;L->next=s;

}else flag=0;}}22數(shù)據(jù)結(jié)構(gòu)第2章線性表①建立單鏈表尾插法建表sA∧s指向新申請(qǐng)的結(jié)點(diǎn)s->data=A;H∧sA∧插入第一個(gè)結(jié)點(diǎn)：插入某一個(gè)結(jié)點(diǎn)：sB∧將新結(jié)點(diǎn)插到當(dāng)前單鏈表的表尾上。增加一個(gè)尾指針r，使之指向當(dāng)前單鏈表的表尾。r->next=s;r=s;順序可以顛倒嗎？H∧初始化空表rrH∧A∧rr2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)23數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)②建立單鏈表尾插法建表算法

Linklist

CreateFromTail(){

LinkListL;Node*r,*s;

intflag=1;charc;L=(Node*)malloc(sizeof(Node));L->next=NULL;r=L;

while(flag){c=getchar();if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL;

}}}24數(shù)據(jù)結(jié)構(gòu)第2章線性表②單鏈表查找按序號(hào)查找設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針L出發(fā)，從第一個(gè)結(jié)點(diǎn)（L->next）開(kāi)始順著鏈域掃描。用指針p指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向第一個(gè)結(jié)點(diǎn)（p=L->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)。

Node*Get(LinkListL,inti){Node*p；

p=L；

j=0；

while((p->next!=NULL)&&(j<i)){

p=p->next；

j++；

}if（i==j）returnp；

elsereturnNULL；

}2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)25數(shù)據(jù)結(jié)構(gòu)第2章線性表③單鏈表查找按值查找指在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。

查找過(guò)程從單鏈表的頭指針指向的第一個(gè)結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。

Node*Locate(LinkList

L,ElemTypekey){Node*p;p=L->next;while(p!=NULL)if(p->data!=key)

p=p->next;

elsebreak;returnp;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)26數(shù)據(jù)結(jié)構(gòu)第2章線性表③單鏈表插入要在帶頭結(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)。se∧×①s->next=pre->next;②pre->next=s;順序可以顛倒嗎？a1a2ai-1aian∧……preL2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)27算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)④單鏈表插入

voidInsList(LinkList

L,int

i,ElemTypee){ Node*pre,*s;

intk=0;pre=L;while(pre!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(k!=i-1){

printf(“插入位置不合理！”)；

return;}s=(Node*)malloc(sizeof(Node));s->data=e;

s->next=pre->next;pre->next=s;}28數(shù)據(jù)結(jié)構(gòu)第2章線性表④單鏈表刪除欲在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，則首先要通過(guò)計(jì)數(shù)方式找到第i-1個(gè)結(jié)點(diǎn)并使pre指向第i-1個(gè)結(jié)點(diǎn)，而后刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間?！痢羛re->next=pre->next->next;a1a2ai-1aian∧……preai+1rL

free(r);2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)29算法實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)⑤單鏈表刪除

voidDelList(LinkList

L,int

i,ElemType*e){Node*pre,*r;pre=L;intk=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(k!=i-1){

printf(“刪除結(jié)點(diǎn)的位置i不合理！”);returnERROR;}

r=pre->next;pre->next=pre->next->next;free(r);returnOK;}30數(shù)據(jù)結(jié)構(gòu)第2章線性表⑤求單鏈表的長(zhǎng)度可以采用“數(shù)”結(jié)點(diǎn)的方法來(lái)求出單鏈表的長(zhǎng)度，用指針p依次指向各個(gè)結(jié)點(diǎn),從第一個(gè)元素開(kāi)始“數(shù)”，一直“數(shù)”到最后一個(gè)結(jié)點(diǎn)（p->next=NULL）。算法實(shí)現(xiàn)

int

ListLength(LinkListL){Node*p;p=L->next; j=0;while(p!=NULL){ p=p->next;j++;}returnj;}2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)31數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例2-2有兩個(gè)單鏈表LA和LB，其元素均為非遞減有序排列，編寫(xiě)一個(gè)算法，將它們合并成一個(gè)單鏈表LC，要求LC也是非遞減有序排列。要求：新表LC利用原表的存儲(chǔ)空間。

LinkList

MergeLinkList(LinkList

LA,LinkListLB){Node*pa,*pb;

LinkListLC;pa=LA->next;pb=LB->next;LC=LA;LC->next=NULL;r=LC;while(pa->next!=NULL&&pb->next!=NULL){if(pa->data<=pb->data){r->next=pa;r=pa;pa=pa->next;}else{r->next=pb;r=pb;pb=pb->next;}}if(pa)r->next=pa;elser->next=pb;free(LB);return(LC);}返回32數(shù)據(jù)結(jié)構(gòu)第2章線性表循環(huán)鏈表(CircularLinkedList)：是一個(gè)首尾相接的鏈表。特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱(chēng)為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。L帶頭結(jié)點(diǎn)的空循環(huán)鏈表a1a2ai-1aian……L帶頭結(jié)點(diǎn)的循環(huán)單鏈表a1a2ai-1aian……采用尾指針的循環(huán)單鏈表rear2.5循環(huán)線性鏈表和雙向鏈表33數(shù)據(jù)結(jié)構(gòu)第2章線性表循環(huán)鏈表(CircularLinkedList)例2-3有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫(xiě)一個(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)。a1a2ai-1aian……LAb1b2bi-1bibn……LBpq

p->next=LB->next;q->next=LA;free(LB);2.5循環(huán)線性鏈表和雙向鏈表34數(shù)據(jù)結(jié)構(gòu)第2章線性表循環(huán)鏈表(CircularLinkedList)算法實(shí)現(xiàn)1LinkListmerge_1(LinkListLA,LinkListLB){Node*p,*q;p=LA;q=LB;while(p->next!=LA)p=p->next; while(q->next!=LB)q=q->next;

p->next=LB->next;free(LB);

q->next=LA;

return(LA);}時(shí)間復(fù)雜度為

O(n)2.5循環(huán)線性鏈表和雙向鏈表35數(shù)據(jù)結(jié)構(gòu)第2章線性表循環(huán)鏈表(CircularLinkedList)例2-3有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫(xiě)一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為L(zhǎng)A。采用帶尾指針的循環(huán)鏈表，執(zhí)行時(shí)間可降低為O(1)。a1a2ai-1aian……RAb1b2bi-1bibn……RBpRA->next=RB->next->next;RB->next=p;free(RB->next);2.5循環(huán)線性鏈表和雙向鏈表36數(shù)據(jù)結(jié)構(gòu)第2章線性表循環(huán)鏈表(CircularLinkedList)算法實(shí)現(xiàn)2LinkListmerge_2(LinkListRA,LinkListRB){Node*p;

p=RA->next;RA->next=RB->next->next;

free(RB->next);RB->next=p;return(RB);}2.5循環(huán)線性鏈表和雙向鏈表37數(shù)據(jù)結(jié)構(gòu)第2章線性表雙向鏈表(DoubleLinkedList)在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱(chēng)之為雙(向)鏈表。結(jié)構(gòu)定義：typedef

struct

Dnode{

ElemTypedata；

struct

DNode*prior，*next；}DNode, *DoubleList；datapriornext定義：2.5循環(huán)線性鏈表和雙向鏈表38數(shù)據(jù)結(jié)構(gòu)第2章線性表雙向鏈表(DoubleLinkedList)示意圖：L空的雙向循環(huán)鏈表L非空的雙向循環(huán)鏈表abc2.5循環(huán)線性鏈表和雙向鏈表39數(shù)據(jù)結(jié)構(gòu)第2章線性表雙向鏈表(DoubleLinkedList)前插操作：ab……esp×①①

p->prior->next=s;②②s->prior=p->prior;順序可以顛倒嗎？×③③p->prior=s;④④s->next=p;順序可以顛倒嗎？順序可以顛倒嗎？2.5循環(huán)線性鏈表和雙向鏈表40數(shù)據(jù)結(jié)構(gòu)第2章線性表2.3線性表的鏈?zhǔn)酱鎯?chǔ)雙向鏈表(DoubleLinkedList)前插操作算法實(shí)現(xiàn)：int

DlinkIns(DoubleList

L,int

i,ElemTypee){

DNode*s,*p;

p=search(L,i);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;}elsereturnFALSE;}41數(shù)據(jù)結(jié)構(gòu)第2章線性表2.5循環(huán)線性鏈表和雙向鏈表雙向鏈表(DoubleLinkedList)刪除操作：abc……p×①p->prior->next=p->next;①×②②p->next->prior=p->prior;free(p);42數(shù)據(jù)結(jié)構(gòu)第2章線性表2.5循環(huán)線性鏈表和雙向鏈表雙向鏈表(DoubleLinkedList)刪除操作算法實(shí)現(xiàn)：int

DlinkDel(DoubleList

L,inti){

DNode*p;

p=search(L,i);

p->prior->next=p->next;p->next->prior=p->prior;free(p);