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

數(shù)據(jù)結(jié)構(gòu)-線性表LinearListofDataStructuresXXXXXXXXXXXXXXXXXXXXX線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第1頁。前言數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。同樣是結(jié)構(gòu)，從不同的角度來討論，會有不同的分類，如圖1所示。邏輯結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（映像）稱為 數(shù)據(jù)的物理（存儲）結(jié)構(gòu)。線性結(jié)構(gòu)：線性表、棧和隊列、串、數(shù)組和廣義表。圖1線性表的數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第2頁。前言抽象數(shù)據(jù)類型(AbstractDataType簡稱ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實世界。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。抽象數(shù)據(jù)類型描述的一般形式如下：ADT抽象數(shù)據(jù)類型名稱{數(shù)據(jù)對象：……數(shù)據(jù)關(guān)系：……操作集合：操作名1：…………操作名n：}ADT抽象數(shù)據(jù)類型名稱線性表這樣的抽象數(shù)據(jù)類型，其數(shù)學(xué)模型是：數(shù)據(jù)元素的集合，該集合內(nèi)的元素有這樣的關(guān)系：除第一個和最后一個外，每個元素有唯一的前趨和唯一的后繼?？梢杂羞@樣一些操作：插入一個元素、刪除一個元素等。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第3頁。01020304線性表的概念及運算TheConceptsandOperationsofLinearList線性表的順序存儲SequenceStorageofLinearList線性表的鏈?zhǔn)酱鎯inkedStorageofLinearList順序表與鏈表的比較ComparisionbetweenthetwoLinearListsCONTENT線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第4頁。01線性表的概念及運算TheConceptsandOperationsofLinearListPARTONE線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第5頁。1.線性表的概念及運算線性表(LinearList)是由n(n≥0)個類型相同的數(shù)據(jù)元素a1,a2,…，an組成的有限序列，記做（a1,a2,…，ai-1，ai，ai+1，…，an）。對于n>0，除第一個元素?zé)o直接前驅(qū)、最后一個元素?zé)o直接后繼外，其余的每一個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。線性表的特點同一性：線性表由同類數(shù)據(jù)元素組成，每一個ai必須屬于同一數(shù)據(jù)對象。有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個數(shù)。有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系<ai,，ai+1>。圖1.1線性表的邏輯結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第6頁。1.線性表的概念及運算線性表存儲方式實現(xiàn)線性表在計算機中的存放有順序存儲與鏈?zhǔn)酱鎯煞N方式。線性表順序存儲（順序表）：采用靜態(tài)分配方式，借助于C語言的數(shù)組類型，申請一組連續(xù)的地址空間，依次存放表中元素，其邏輯次序會在存儲順序之中。線性表鏈?zhǔn)酱鎯Γㄦ湵恚翰捎脛討B(tài)分配方式，借助于C語言的指針類型，動態(tài)申請與動態(tài)釋放地址空間，故鏈表中的各結(jié)點的物理存儲可以是不連續(xù)的。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第7頁。1.線性表的概念及運算抽象數(shù)據(jù)類型定義：ADTLinearList{數(shù)據(jù)元素：D={ai|ai∈D0,i=1,2,…，nn≥0，D0為某一 數(shù)據(jù)對象}結(jié)構(gòu)關(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置為空表。

線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第8頁。1.線性表的概念及運算（4）EmptyList（L） 操作前提：線性表L已存在。 操作結(jié)果：如果L為空表則返回真，否則為假。（5）ListLength(L) 操作前提：線性表L已存在。操作結(jié)果：如果L為空表則返回0，否則返回表中元素個數(shù)。（6）Locate(L,e) 操作前提：表L已存在，e為合法元素值。 操作結(jié)果：如果L中存在元素e，則將“當(dāng)前指針”指向元素 e所在位置并返回真，否則返回假。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第9頁。1.線性表的概念及運算（7）GetData（L,i）操作前提：表L存在,且i值合法，即1≤i≤Listlength（L）。 操作結(jié)果：返回線性表L中第i個元素的值。（8）InsList(L,i,e) 操作前提：表L已存在，e為合法元素，且 1≤i≤Listlength(L)+1。操作結(jié)果：在L中第i個位置插入新的數(shù)據(jù)元素e，L的長度 加1。（9）DelList(L,i,&e) 操作前提：表L已存在且非空，1≤i≤Listlength(L)。 操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的 長度減1。}ADTLinearList線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第10頁。02線性表的順序存儲SequenceStorageofLinearListPARTTWO線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第11頁。2.線性表的順序存儲基本概念2.1基本運算2.2優(yōu)缺點分析2.3線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第12頁。2.1基本概念線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表。將順序表歸納為：關(guān)系線性化，結(jié)點順序存。假設(shè)線性表中有n個元素，每個元素占k個單元，第一個元素的地址為loc(a1)，則可通過如下公式計算出第i個元素的地址loc(ai)為：

loc(ai)=loc(a1)+(i-1)×k 其中l(wèi)oc(a1)稱為基地址。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第13頁。2.1基本概念圖2.1順序存儲結(jié)構(gòu)示意圖存儲地址

內(nèi)存空間狀態(tài)

邏輯地址

Loc(a1)a11Loc(a1)+(2-1)ka2

2………loc(a1)+(i-1)kai

i………loc(a1)+(n-1)kan

n...

loc(a1)+(maxlen-1)k空閑線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第14頁。2.1基本概念順序存儲結(jié)構(gòu)的C語言定義#define maxsize=線性表可能達到的最大長度；typedefstruct{ElemTypeelem[maxsize]；/*線性表占用的數(shù)組 空間*/intlast；/*記錄線性表中最后一個元素在數(shù)組 elem[]中的位置（下標(biāo)值），空表置為-1*/}SeqList； 注意區(qū)分元素的序號和數(shù)組的下標(biāo)，如a1的序號為1，而其對應(yīng)的數(shù)組下標(biāo)為0。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第15頁。2.2基本算法查找操作2.2.1插入操作2.2.2刪除操作2.2.3順序表合并算法2.2.4線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第16頁。2.2.1查找操作按序號查找GetData(L,i)：要求查找線性表L中第i個數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]或L->elem[i-1]。按內(nèi)容查找Locate(L,e)：要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第17頁。2.2.1查找操作按內(nèi)容查找：intLocate(SeqListL，ElemTypee){ i=0;/*i為掃描計數(shù)器，初值為0，即從 第一個元素開始比較*/

while((i<=L.last)&&(L.elem[i]!=e)) i++; /*順序掃描表，直到找到值為key 的元素,掃描到表尾而沒找到*/if(i<=L.last)return(i+1);/*若找到值為e的元素，則 返回其序號*/else return(-1);/*若沒找到，則返回空序號*/}圖2.2.查找操作線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第18頁。2.2.2插入操作線性表的插入運算是指在表的第i(1≤i≤n+1)個位置，插入一個新元素e，使長度為n的線性表(e1，…，ei-1，ei，…，en)變成長度為n+1的線性表（e1，…,ei-1，e，ei，…，en）。線性表的插入運算算法已知：線性表(4,9,15,28,30,30,42,51,62)，需在第4個元素之前插入一個元素“21”。則需要將第9個位置到第4個位置的元素依次后移一個位置，然后將“21”插入到第4個位置。要點：將第9個到第4個的元素依次后移一個位置，將“21”插入到第4個位置。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第19頁。2.2.2插入操作序號移動元素插入元素1234567810949152830304251624915283030426251491521283030426251intInsList(SeqList*L,inti,ElemTypee){intk;if((i<1)||(i>L->last+2))/*首先判斷插入位置是否合法*/{printf(“插入位置i值不合法”)；return(ERROR);}if(L->last>=maxsize-1){printf(“表已滿無法插入”)；return(ERROR);}

for(k=L->last;k>=i-1;k--)/*為插入元素而移動位置*/L->elem[k+1]=L->elem[k];L->elem[i-1]=e;/*在C語言中數(shù)組第i個元素的下標(biāo)為i-1*/L->last++;return(OK);}圖2.3插入操作線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第20頁。2.2.3刪除操作線性表的刪除運算是指將表的第i(1≤i≤n)個元素刪去，使長度為n的線性表(e1，…,ei-1，ei，ei+1，…，en)，變成長度為n-1的線性表(e1，…,ei-1，ei+1，…，en)。將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個元素刪除。序號123456781094915212830304262514915213030425162刪除28后圖2.4.刪除操作線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第21頁。2.2.3刪除操作intDelList(SeqList*L,inti,ElemType*e)/*在順序表L中刪除第i個數(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);}序號123456781094915212830304262514915213030425162刪除28后圖2.5刪除操作線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第22頁。2.2.4順序表合并算法已知

：有兩個順序表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個順序表LC，要求LC也是非遞減有序排列。算法思想：設(shè)表LC是一個空表，為使LC也是非遞減有序排列，可設(shè)兩個指針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中，如此進行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第23頁。2.2.4順序表合并算法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長則將表LA余下的元素賦給表LC*/{ LC->elem[k]=LA->elem[i];i++;k++;}while(j<=LB->last)/*當(dāng)表LB長則將表LB余下的元素賦給表LC*/{ LC->elem[k]=LB->elem[j];j++;k++;} LC->last=LA->last+LB->last;}線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第24頁。2.3優(yōu)缺點分析優(yōu)點：1.無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間；2.可方便地隨機存取表中的任一元素。缺點：1.插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結(jié)點，其效率較低；2.由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預(yù)先進行靜態(tài)分配。因此當(dāng)表長變化較大時，難以確定合適的存儲規(guī)模。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第25頁。03線性表的鏈?zhǔn)酱鎯inkedStorageofLinearListPARTTHREE線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第26頁。2.線性表的順序存儲基本概念3.1

單鏈表的基本運算3.2其它鏈表3.3線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第27頁。3.1基本概念結(jié)點：存儲線性表的每個數(shù)據(jù)元素值的信息與元素間邏輯關(guān)系（即后繼結(jié)點地址信息）的兩部分存儲映象。鏈表：采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表。單鏈表：鏈表中的每個結(jié)點只有一個指針域，我們將這種鏈表稱為單鏈表。單鏈表包括兩個域：數(shù)據(jù)域用來存儲結(jié)點的值；指針域用來存儲數(shù)據(jù)元素的直接后繼的地址（或位置）。頭指針：指向鏈表頭結(jié)點的指針。現(xiàn)在我們從兩個角度來討論鏈表：1.從實現(xiàn)角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表；2.從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。圖3.1帶頭結(jié)點的單鏈表線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第28頁。3.1基本概念頭指針H存儲地址數(shù)據(jù)域指針域1D437B1313C119HNULL25F3731A737G1943E25313.2單鏈表的示例圖線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第29頁。3.1基本概念單鏈表的存儲結(jié)構(gòu)描述typedefstructNode/*結(jié)點類型定義*/{ElemTypedata；

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

線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第30頁。3.2基本算法

建立單鏈表3.2.1單鏈表查找3.2.2單鏈表插入3.2.3

單鏈表刪除3.2.4線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第31頁。3.2.1建立單鏈表尾插法建表LinklistCreateFromTail()/*將新增的字符追加到鏈表的末尾*/{LinkListL;Node*r,*s;intflag=1;L=(Node*)malloc(sizeof(Node));/*為頭結(jié)點分配存儲空間*/L->next=NULL;r=L;/*r指針始終動態(tài)指向鏈表的當(dāng)前表尾*/while(flag)/*標(biāo)志，初值為1。輸入“$”時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;}}}圖3.3尾插法建表線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第32頁。3.2.1建立單鏈表頭插法建表LinklistCreateFromHead(){LinkListL;Node

*s;intflag=1; /*設(shè)置一個標(biāo)志，初值為1，當(dāng)輸入“$” 時，flag為0，建表結(jié)束*/L=(Linklist)malloc(sizeof(Node))；/*為頭結(jié)點 分配存儲空間*/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;}}圖3.4頭插法建表線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第33頁。3.2.2單鏈表查找按序號查找

算法描述：設(shè)帶頭結(jié)點的單鏈表的長度為n，要查找表中第i個結(jié)點，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點（L->next）開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點,初值指向頭結(jié)點（pL->next），用j做記數(shù)器，累計當(dāng)前掃描過的結(jié)點數(shù)（初值為0），當(dāng)j=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。/*在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點，若找到(1≤i≤n)，則返回該結(jié)點的存儲位置;否則返回NULL*/Node*Get(LinkListL,inti){Node*p；

p=L；j=0；/*從頭結(jié)點開始掃描*/

while((p->next!=NULL)&&(j<i){p=p->next；j++；/*掃描下一結(jié)點*/}/*已掃描結(jié)點計數(shù)器*/if（i==j）returnp；/*找到了第i個結(jié)點*/elsereturnNULL；/*找不到，i≤0或i>n*/}圖3.5按序號查找線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第34頁。3.2.2單鏈表查找按值查找算法描述：按值查找是指在單鏈表中查找是否有結(jié)點值等于e的結(jié)點，若有的話，則返回首次找到的其值為e的結(jié)點的存儲位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點出發(fā)，順著鏈逐個將結(jié)點的值和給定值e作比較。/*在帶頭結(jié)點的單鏈表L中查找其結(jié)點值等于key的結(jié)點，若找到則返回該結(jié)點的位置p，否則返回NULL*/Node*Locate(LinkListL,ElemTypekey){Node*p;p=L->next;/*從表中第一個結(jié)點比較*/while(p!=NULL)

if(p->data!=key) p=p->next;elsebreak;/*找到結(jié)點key，退出循環(huán)*/returnp;}圖3.6按值查找線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第35頁。3.3.3單鏈表插入插入操作要在帶頭結(jié)點的單鏈表L中第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素e，需要首先在單鏈表中找到第i-1個結(jié)點并由指針pre指示，然后申請一個新的結(jié)點并由指針s指示，其數(shù)據(jù)域的值為e，并修改第i-1個結(jié)點的指針使其指向s，然后使s結(jié)點的指針域指向第i個結(jié)點。voidInsList(LinkListL,inti,ElemTypee){/*在帶頭結(jié)點的單鏈表L中第i個結(jié)點之前插入值為e的新結(jié)點。*/ Node*pre,*s;pre=L;intk=0;while(pre!=NULL&&k<i-1) /*先找到第i-1個數(shù)據(jù)元素的存儲位置,使指針Pre指向它*/ {pre=pre->next; k=k+1;}if(k!=i-1){printf(“插入位置不合理！”)；return;}

s=(Node*)malloc(sizeof(Node));/*為e申請一個新的結(jié)點*/s->data=e;/*將待插入結(jié)點的值e賦給s的數(shù)據(jù)域*/s->next=pre->next;pre->next=s;}3.7單鏈表插入線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第36頁。3.3.4單鏈表刪除刪除操作欲在帶頭結(jié)點的單鏈表L中刪除第i個結(jié)點，則首先要通過計數(shù)方式找到第i-1個結(jié)點并使p指向第i-1個結(jié)點，而后刪除第i個結(jié)點并釋放結(jié)點空間。voidDelList(LinkListL,inti,ElemType*e)/*在帶頭結(jié)點的單鏈表L中刪除第i個元素，并保存其值到變量*e中*/{Node*p,*r;p=L;intk=0;while(p->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點i的前驅(qū)結(jié)點*/{p=p->next;k=k+1;}if(k!=i-1)/*即while循環(huán)是因為p->next=NULL而跳出的*/{printf(“刪除結(jié)點的位置i不合理！”);returnERROR;}r=p->next;p->next=p->next->next/*刪除結(jié)點r*/free(r);/*釋放被刪除的結(jié)點所占的內(nèi)存空間*/}3.8單鏈表刪除線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第37頁。3.3其它鏈表雙向鏈表：在單鏈表的每個結(jié)點里再增加一個指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙(向)鏈表

(DoubleLinkedList)。有時候以倒序掃描鏈表很方便。標(biāo)準(zhǔn)實現(xiàn)方法此時無能為力，然而解決方法卻很簡單。只要在數(shù)據(jù)結(jié)構(gòu)上附加一個域，使它包含指向前一個單元的指針即可。其開銷是一個附加的鏈，它增加了空間的需求，同時也使得插入和刪除的開銷增加一倍，因為有更多的指針需要定位。另一方面，它簡化了刪除操作，因為你不再被迫使用一個指向前驅(qū)元的指針來訪問一個關(guān)鍵字；這個信息是現(xiàn)成的。表示一個雙鏈表。雙向鏈表的結(jié)構(gòu)定義：

typedefstructDnode {ElemTypedata；structDNode*prior，*next；

}DNode,*DoubleList；3.9雙向鏈表線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第38頁。3.3其它鏈表循環(huán)鏈表(CircularLinkedList)是一個首尾相接的鏈表。將單鏈表最后一個結(jié)點的指針域由NULL改為指向頭結(jié)點或線性表中的第一個結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。讓最后的單元反過來直指第一個單元是一種流行的做法。它可以有表頭，也可以沒有表頭（若有表頭，則最后的單元指向它），并且還可以是雙向鏈表（第一個單元的前驅(qū)元指針指向最后的單元）。這無疑會影響某些測試，不過這種結(jié)構(gòu)在某些應(yīng)用程序中卻很流行。顯示了一個無表頭的雙向循環(huán)鏈表。3.10循環(huán)鏈表線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第39頁。04順序表與鏈表的比較ComparisionbetweenthetwoLinearListsPARTFOUR線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第40頁。4.順序表與鏈表的比較簡要概述4.1

實際比較4.2

相關(guān)技術(shù)4.3線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第41頁。4.1簡要概述順序表的特點是邏輯上相鄰的數(shù)據(jù)元素，物理存儲位置也相鄰，并且，順序表的存儲空間需要預(yù)先分配。它的優(yōu)點是：（1）方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。（2）不用為表示節(jié)點間的邏輯關(guān)系而增加額外的存儲開銷。（3）順序表具有按元素序號隨機訪問的特點。缺點：（1）在順序表中做插入、刪除操作時，平均移動表中的一半元素，因此對n較大的順序表效率低。（2）需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第42頁。4.1簡要概述在鏈表中邏輯上相鄰的數(shù)據(jù)元素，物理存儲位置不一定相鄰，它使用指針實現(xiàn)元素之間的邏輯關(guān)系。并且，鏈表的存儲空間是動態(tài)分配的。鏈表的最大特點是：插入、刪除運算方便。缺點：（1）要占用額外的存儲空間存儲元素之間的關(guān)系，存儲密度降低。存儲密度是指一個節(jié)點中數(shù)據(jù)元素所占的存儲單元和整個節(jié)點所占的存儲單元之比。（2）鏈表不是一種隨機存儲結(jié)構(gòu)，不能隨機存取元素。線性表數(shù)據(jù)結(jié)構(gòu)全文共49頁，當(dāng)前為第43頁。4.2.1基于空間的考慮順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對“MaxSize”要有合適的設(shè)定，設(shè)定過大會造成存儲空間的浪費，過小造成溢出。因此，當(dāng)對線性表的長度或存儲規(guī)模難以估計時，不宜采用順序表。然而，鏈表的動態(tài)分配則可以克服這個缺點。鏈表不需要預(yù)留存儲空間，也不需要知道表長如何變化，只要內(nèi)存空間尚有空閑，就可以再程序運行時隨時地動態(tài)分配空間，不需要時還可以動態(tài)回收。因此，當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)較好。存儲密度(StorageDensity)是指結(jié)點數(shù)據(jù)結(jié)構(gòu)本身所占的存儲量和整個結(jié)點結(jié)構(gòu)所占的存儲量之比。一般地，存儲密度越大，存儲空間的利用率就高。顯然，順序表的存儲密度為1，而鏈表的存儲密度小于1。因此，當(dāng)線性表的長度變化不大而且