2￥-two(天津科技大學(xué))

第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2.4一元多項式的表示及相加10/8/20241第二章線性表2.1線性表的類型定義線性表(LinearList)：由n(n≧)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：

(a1，a2，…,an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）

10/8/20242第二章線性表例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡健康情況王小林790631男18

健康陳紅790632女20

一般劉建平790633男21

健康張立立790634男17

神經(jīng)衰弱……..……..…….…….…….10/8/20243第二章線性表例4、一副撲克的點數(shù)（2，3，4，…，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表中，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。

線性表是一種典型的線性結(jié)構(gòu)。

10/8/20244第二章線性表含有n個元素的線性表是一個數(shù)據(jù)結(jié)構(gòu)

Linear_list=(D,R)其中D={ai|ai

D0,i=1,2,,n,n0}R={N},N={<ai-1,

ai>|ai-1,

ai

D0

,i=2,3,,n}D0為某個數(shù)據(jù)對象（可為任何數(shù)據(jù)類型）對應(yīng)的邏輯圖如下：線性表與線性結(jié)構(gòu)的關(guān)系。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。抽象數(shù)據(jù)類型的定義為：P19a1a2ai-1aian……10/8/20245第二章線性表線性表的操作還有合并、拷貝、排序等復(fù)雜運算

例2-1利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=A∪B。

voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){

getelem(lb，I，e);

if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

時間復(fù)雜度為O(mn)

10/8/20246第二章線性表例2-2巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算法如下：

voidmergelist(listla，listlb，list&lc)

initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){

getelem(la，I，ai);getelem(lb，j，bj);10/8/20247第二章線性表if(ai<=bj){listinsert(lc，++k，ai);++I;}

else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){

getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){

getelem((lb，j++，bj);listinsert(lc，++k，bi);}}//MergeList算法的時間復(fù)雜度分析(O(m+n))

10/8/20248第二章線性表

2.2線性表的順序存儲結(jié)構(gòu)1順序表把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第I+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(aI)之間滿足下列關(guān)系：

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

線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(I-1)*l

10/8/20249第二章線性表由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。

#defineListSize100

typedef

int

DataType;

typedef

struc{

DataType

data[ListSize];

intlength;}Sqlist;10/8/202410第二章線性表2順序表上實現(xiàn)的基本操作

在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.data[I-1]。

以下主要討論線性表的插入和刪除兩種運算。

1、插入線性表的插入運算是指在表的第I(1≦i≦n+1個位置上，插入一個新結(jié)點x，10/8/202411第二章線性表使長度為n的線性表

(a1，…ai-1，ai，…，an)

變成長度為n+1的線性表

(a1，…ai-1，x，ai，…，an)算法如下

VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1)

printf(“Positionerror”);returnERROR

10/8/202412第二章線性表

if(l.length>=ListSize)

printf(“overflow”);exit(overflow);for(j=l.length-1;j>=I-1;j--)l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}10/8/202413第二章線性表算法的復(fù)雜度分析這里的問題規(guī)模是表的長度，設(shè)它的值為n。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是n-I+1。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。當(dāng)I=n+1時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復(fù)雜度O（1）；當(dāng)I=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，其時間復(fù)雜度為O（n）。10/8/202414第二章線性表由于插入可能在表中任何位置上進行，因此需分析算法的平均復(fù)雜度在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-I+1。故

Eis(n)=

pi(n-I+1)

不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點的機會是均等的，則

p1=p2=p3=…=pn+1=1/(n+1)

因此，在等概率插入的情況下，

Eis(n)=

(n-I+1)/(n+1)=n/2

10/8/202415第二章線性表

也就是說，在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。

2、刪除線性表的刪除運算是指將表的第i(1≦i≦n)結(jié)點刪除，使長度為n的線性表：

(a1，…ai-1，ai，ai+1…，an)

變成長度為n-1的線性表

(a1，…ai-1，ai+1，…，an)10/8/202416第二章線性表

VoiddeleteList(Sqlist*L，intI){

intj;if(I<1||I>l.length)

printf(“Positionerror”);returnERRORfor(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}

10/8/202417第二章線性表該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。若I=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點；若I=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。

刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點，令Ede(n)表示所需移動結(jié)點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n-i，故

Ede(n)=

pi(n-I)

式中，pi表示刪除表中第i個結(jié)點的概率。10/8/202418第二章線性表在等概率的假設(shè)下，p1=p2=p3=…=pn=1/n

可得：

Ede(n)=

(n-I)/n=(n-1)/2

即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)?？捎懻摼€性表的其它操作在順序存儲結(jié)構(gòu)上的實現(xiàn)方法和時間復(fù)雜度的分析。可討論例2-1和例2-2的操作在順序存儲結(jié)構(gòu)的線性表中的實現(xiàn)方法和時間復(fù)雜度的分析。

10/8/202419第二章線性表建立一個順序存儲的線性表

voidcreatsqlist(SqList*L){inti;

pritnt(“請輸入線性表元素個數(shù)\n”);

scanf(“%d”,&(*L).len);

printf(“請輸入%d個元素\n”,(*L).len);for(i=0;I<(*L).len;I++)scanf(“%d”,&(*L).elem[I].key);}

10/8/202420第二章線性表順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點：隨機存取缺點：1插入、刪除需移動大量元素

2存儲空間不能充分利用

3表的容量難以擴充10/8/202421第二章線性表2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的順序表示的特點是用物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這一特點使我們可以隨機存取表中的任一結(jié)點，但它也使得插入和刪除操作會移動大量的結(jié)點.為避免大量結(jié)點的移動，我們介紹線性表的另一種存儲方式--鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈表(LinkedList)。10/8/202422第二章線性表1線性鏈表（單鏈表）鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：10/8/202423第二章線性表

其中：存儲數(shù)據(jù)元素信息的data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結(jié)只有一個鏈域，故將這種鏈表稱為線性鏈表或單鏈表（SingleLinked)。

顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即null（圖示中也可用^表示)。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)datanext10/8/202424第二章線性表單鏈表示意圖如下：

……110……130135……160頭指針head165170……200205…………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………

16510/8/202425第二章線性表headbat

cat

eat

mat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。用C語言描述的單鏈表如下：Typedefchardatatype;

Typedef

structnode{

datatypedata;

structnode*next;}listnode;10/8/202426第二章線性表

typedef

listnode*linklist;

listnode*p;

linklisthead;注意區(qū)分指針變量和結(jié)點變量這兩個不同的概念。P為動態(tài)變量，它是通過標(biāo)準(zhǔn)函數(shù)生成的，即

p=(listnode*)malloc(sizeof(listnode));函數(shù)malloc分配了一個類型為listnode的結(jié)點變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點變量不再需要了，又可通過標(biāo)準(zhǔn)函數(shù)

free(p)釋放所指的結(jié)點變量空間。指針變量P和（其值為結(jié)點地址）和結(jié)點變量*P之間的關(guān)系。10/8/202427第二章線性表一、建立單鏈表假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種：

1、頭插法建表該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。10/8/202428第二章線性表

linklistcreatelistf(void){charch;

linklisthead;

listnode*p;head=null;

ch=getchar();while(ch!=‵\n′{p=(listnode*)malloc(sizeof(listnode));

p–>data=ch;p–>next=head;

10/8/202429第二章線性表

head=p;

ch=getchar();}return(head);}10/8/202430第二章線性表

listlinkcreatelist(intn){intdata;

linklisthead;

listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));

scanf((〝%d〞，&p–>data);p–>next=head;head=p;}10/8/202431第二章線性表

return(head);}2、尾插法建表

頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例：10/8/202432第二章線性表

linklist

creater(){charch;

linklisthead;

listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;else

10/8/202433第二章線性表

r–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}

說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點的位置是存放在頭指針（指針變量）中，

10/8/202434第二章線性表而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，那么會帶來以下兩個優(yōu)點：

a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就10/8/202435第二章線性表和在表的其它位置上的操作一致，無需進行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。其算法如下：linklistcreatelistr1(){charch;

linklisthead=(linklist)malloc(sizeof(listnode));

listnode*p，*r

10/8/202436第二章線性表

r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}10/8/202437第二章線性表上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理：

p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的時間復(fù)雜度均為O(n)。10/8/202438第二章線性表二、查找運算

1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1≦i≦n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：10/8/202439第二章線性表Listnode*getnode(linklisthead，inti){

intj;

listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;10/8/202440第二章線性表

elsereturnNULL;}

2、按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：10/8/202441第二章線性表Listnode*locatenode(linklisthead，intkey){

listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。10/8/202442第二章線性表三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點*p，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：10/8/202443第二章線性表單鏈表插入結(jié)點時指針變化情況

b

a

a

b

x

ppq插入前插入后snext=pnext;pnext=s;10/8/202444第二章線性表具體算法如下：

voidinsertnode(linklisthead，datetypex，inti){

listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;

q–>next=p–next;p–>next=q;

}

10/8/202445第二章線性表設(shè)鏈表的長度為n，合法的插入位置是1≦i≦n+1。注意當(dāng)i=1時，getnode找到的是頭結(jié)點，當(dāng)

i=n+1時，getnode找到的是結(jié)點an。因此，用i-1做實參調(diào)用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復(fù)雜度亦為O(n)。四、刪除運算刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點

ai-1的指針域next中，所以我們必須首先找到

10/8/202446第二章線性表

ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。具體算法如下：

bpc（單鏈表刪除結(jié)點時指針變化情況）××rap->next=p->next->next10/8/202447第二章線性表

voiddeletelist(linklisthead，

inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}10/8/202448第二章線性表設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1≦i≦n時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點（即p–>next!=NULL）時，才能確定被刪結(jié)點存在。顯然此算法的時間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。10/8/202449第二章線性表2.3.2循環(huán)鏈表

循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：10/8/202450第二章線性表

a1an

….head⑴非空表⑵空表在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)10/8/202451第二章線性表在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是(rear–>next)—>next和rear，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。10/8/202452第二章線性表例、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個線性表的運算。

linklist

connect(linklist

reara，linklist

rearb){

linklistp=reara—>next;

reara—>next=(rearb—>next)—>next

free(rearb—>next);

rearb—>next=p;

return(rearb);}10/8/202453第二章線性表2.3.3雙鏈表

雙向鏈表(Doublelinkedlist):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：

typedefstructdlistnode{

datatypedata;

strucdlistnode