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

第三章線性表DS應(yīng)用實踐

線性表的概念

雙向鏈表

循環(huán)鏈表

線性表的順序存儲

單向鏈表

線性結(jié)構(gòu)特點在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼3.1線性表的概念例英文字母表（A,B,C,…..Z)是一個線性表定義：一個線性表是n個數(shù)據(jù)元素的有限序列3.1.1線性表的定義3.1線性表的概念特征：元素個數(shù)n—表長度，n=0空表1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項3.1.1線性表的定義3.1.2線性表的抽象數(shù)據(jù)類型描述ADTList{

數(shù)據(jù)對象：D＝{ai|ai∈ElemType,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：（詳見下頁）}ADTList

基本操作InitList(SqList

*L)//線性表的初始化，即構(gòu)造一個空的線性表LDestroyList(SqList&L)//釋放線性表L占用的內(nèi)存空間ListEmpty(SqListL)//判斷線性表L是否為空表ListLength(SqListL)//求線性表的長度，返回L中元素個數(shù)GetElem(SqListL,inti,DataType

*e)//求線性表L中第i(1≤i≤n)個元素的值

基本操作LocateElem(SqListL,

DataType

e)//返回L中第1個與e滿足關(guān)系的數(shù)據(jù)元素位序ListTraverse(SqList

L)//依次對線性表L的每個元素進行遍歷ClearList(SqList

*L)//將線性表L重置為空表PutElem(SqList

L,inti,DataType

*e)//給線性表L中第i個元素賦值ListInsert(SqList

*L,inti,DataType

e)//在線性表L的第i個元素之前插入新的元素eListDelete(SqList

*L,inti,DataType

*e)//刪除L的第i個元素，并用e返回其值，L的長度減1

基本操作CreateListHead(SqList

*L,intn)//用頭插法建立帶表頭結(jié)點的單鏈線性表LCreateListTail(SqList

*L,intn)//用尾插法建立帶表頭結(jié)點的單鏈線性表L定義：用一組地址連續(xù)的存儲單元存放一個線性表叫~元素地址計算方法LOC(ai+1)=LOC(ai)+d

LOC(ai)=LOC(a1)+(i-1)*dd—一個元素占用的存儲單元個數(shù)LOC(ai)—線性表第i個元素的地址3.2線性表的順序存儲特點：

實現(xiàn)邏輯上相鄰—物理地址相鄰實現(xiàn)隨機存取實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)在C語言中，線性表的順序存儲的類型定義如下：typedef

int

DataType;//DataType類型根據(jù)實際情況而定，這里假設(shè)為int#defineMAXSIZE100//MAXSIZE可根據(jù)實際情況而定typedef

struct{

DataType

data[MAXSIZE];

intlength;}SqList;圖3.1線性表的順序存儲結(jié)構(gòu)

a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1typedef

int

DataType;#defineMAXSIZE100例typedef

struct{

DataType

data[MAXSIZE]

intlength;}SqList;備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組3.2.2順序表的基本運算1.線性表的初始化int

InitList(SqList*L){

L.length=0;//空表，長度為0

returnOK;}3.2.2順序表的基本運算2.釋放線性表voidDestroyList(SqList&L){

if(L->data)

free(L->data);//釋放線性表占據(jù)的所有存儲空間}3.2.2順序表的基本運算3.判斷線性表是否為空表int

ListEmpty(SqListL){

if(L.length==0)

returnTRUE;

if(L.length!=0)

returnFALSE;}3.2.2順序表的基本運算4.求線性表的長度int

ListLength(SqListL){

return(L.length);}3.2.2順序表的基本運算5.求線性表中第i個元素的值int

GetElem(SqList

L,int

i,DataType*e){

if(i<1||i>L.length)

returnERROR;//判斷i值是否合理，若不合理，返回ERROR

*e=L.data[i-1];//數(shù)組中第i-1的單元存儲著線性表中第i個數(shù)據(jù)元素的內(nèi)容

returnOK;}3.2.2順序表的基本運算6.返回線性表中第1個與e滿足關(guān)系的數(shù)據(jù)元素位序int

LocateElem(SqListL,DataTypee){

int

i;

for

(i=1;

i<=L.length;

++i)

{

if

(e

==

L.data[i-1])

return

i;

}

return

FALSE

}

3.2.2順序表的基本運算7.遍歷線性表void

ListTraverse(SqList

L)

{

int

i;

for

(i=i;

i<=L.length;

++i)

printf("%d

",

L.data[i-1]);

}

3.2.2順序表的基本運算8.清空線性表voidClearList(SqList*L){

L->length=0;//將線性表的長度置為0}3.2.2順序表的基本運算9.給線性表中第i個元素賦值int

PutElem(SqList

L,int

i,DataType*e){

if(i<1||i>L.length)

returnERROR;//判斷i值是否合理，若不合理，返回ERROR

L.data[i-1]=*e;//數(shù)組中第i-1的單元存儲著線性表中第i個數(shù)據(jù)元素的內(nèi)容

returnOK;}定義：線性表的插入是指在第i（1in+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表變成長度為n+1的線性表

需將第i至第n共（n-i+1)個元素后移3.2.2順序表的基本運算10.插入數(shù)據(jù)元素ai-1和ai

的邏輯關(guān)系發(fā)生了變化。在線性表的順序存儲結(jié)構(gòu)中，由于邏輯上相鄰的數(shù)據(jù)元素在物理上也是相鄰的，因此，除非i=n+1，否則必須移動元素才能反映這個邏輯關(guān)系的變化。圖3.2

線性表插入前后的狀況內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1an-1xint

ListInsert(SqList*L,int

i,DataTypee){

intk;

if(L->length==MAXSIZE)returnERROR;

if(i<1||i>L->length+1)returnERROR;

if(i<=L->length)

{for(k=L->length-1;k>=i-1;k--)

L->data[k+1]=L->data[k];

}

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

L->length++;

returnOK;

}算法時間復(fù)雜度T(n)設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：11.線性表中數(shù)據(jù)元素的刪除

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

需將第i+1至第n共（n-i)個元素前移定義：線性表的刪除是指將第i（1in）個元素刪除，使長度為n的線性表

圖3.3線性表刪除前后的狀況內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號i+1n-1nanai+2int

ListDelete(SqList*L,int

i,DataType*e){

intk;if(L->length==0)returnERROR;if(i<1||i>L->length)returnERROR;*e=L->data[i-1];if(i<L->length){

for(k=i;k<L->length;k++) L->data[k-1]=L->data[k];}L->length--;returnOK;}設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當(dāng)n很大時，效率很低算法評價順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充練習(xí)：1.實現(xiàn)在順序表中按值插入元素。2.給定一個順序表L=（a1,a2,a3,...,an),請設(shè)計一個算法刪除所有值大于min而且小于max的元素。實現(xiàn)在順序表中按值插入元素int

ListInsert(SqList*L,DataTypee){

intk; if(L->length==MAXSIZE)returnERROR;

for(k=L->length;k>=1;k--) {if(L->data[k-1]>e) {L->data[k]=L->data[k-1]; } else {break;} } L->data[k]=e; L->length++; returnOK;}給定一個順序表L=（a1,a2,a3,...,an),請設(shè)計一個算法刪除所有值大于min而且小于max的元素int

ListDelete(SqList*L,int

min,intmax){

int

k,i;if(L->length==0)returnERROR;

for(k=1;k<=L->length;k++) {if(L->data[k-1]>min&&L->data[k-1]<max) {for(i=k;i<L->length;i++) {L->data[i-1]=L->data[i];} L->length--; k--; }}returnOK;}3.3單向鏈表順序表的存儲特點是用物理上的相鄰來實現(xiàn)邏輯上的相鄰，它要求用連續(xù)的存儲單元順序存儲線性表中各元素，因此，對順序表插入、刪除時需要通過移動數(shù)據(jù)元素來實現(xiàn)，影響了運行效率。線性鏈表不需要用地址連續(xù)的存儲單元來實現(xiàn)，而是通過“鏈”建立起數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。

3.3單向鏈表特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素的存儲映像，稱為結(jié)點。由于上述鏈表的每個結(jié)一個點只有一個指示其直接相繼的信息，故將這種鏈表稱為單向鏈表，簡稱為單鏈表。結(jié)點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點n個結(jié)點（ai(1≤i≤n)的存儲映像）鏈結(jié)成一個鏈表，即為線性表

(a1,a2,….,an)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。整個鏈表的存取必須從頭指針開始進行，頭指針指示鏈表中第一個結(jié)點（即第一個數(shù)據(jù)元素的存儲映像）的存儲位置。同時，由于最后一個數(shù)據(jù)元素沒有直接后繼，則線性鏈表中最后一個結(jié)點的指針為空(NULL)。

L為單鏈表的頭指針，它指向表中第一個結(jié)點。若L為空(NULL)，則所表示的線性表為“空”表，其長度n為“零”。在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱之為“頭結(jié)點”。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，指針域存儲指向第一個結(jié)點的指針（即第一個元素結(jié)點的存儲位置）。單鏈表的頭指針指向頭結(jié)點。若線性表為空表，則頭結(jié)點的指針域為“空”。

(a)非空表

(b)空表圖3.4

帶頭指針的單鏈表用C語言定義的單鏈表結(jié)構(gòu)如下：typedef

structNode{

DataTypedata;

structNode*next;}Node;typedef

structNode*LinkList;

ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針(1)InitList(LinkList*L)//初始化單鏈表(2)ListEmpty(LinkList

L)//判斷單鏈表是否為空(3)ClearList(LinkList*L)//單鏈表的置空(4)CreateListTail(LinkList*L,int

n)//從尾創(chuàng)建添加結(jié)點(5)CreateListHead(LinkList*L,int

n)//從頭創(chuàng)建添加結(jié)點(6)ListLength(LinkList

L)//獲取鏈表結(jié)點數(shù)量(表長)(7)GetElem(LinkList

L,int

i,DataType*e)//獲取指定位置結(jié)點(8)LocateElem(LinkList

L,DataType

e)//獲取指定數(shù)據(jù)元素的位序(9)ListInsert(LinkList*L,int

i,DataType

e)//插入指定位置的數(shù)據(jù)元素(10)ListDelete(LinkList*L,int

i,DataType*e)//刪除指定位置的數(shù)據(jù)元素(11)ListTraverse(LinkList

L)//單鏈表的遍歷3.3.3單向鏈表的基本操作(1)初始化單向鏈表int

InitList(LinkList&L){L=(LinkList)malloc(sizeof(Node));

if(!L)returnERROR;L->next=NULL;returnOK;}算法3.3初始化單鏈表(2)判斷是否為空若L為空表，則返回TRUE，否則返回FALSE。int

ListEmpty(LinkListL){

if(L->next)returnFALSE;elsereturnTRUE;}算法3.4判斷單鏈表是否為空(3)置空int

ClearList(LinkList&L){LinkList

p,q; p=L->next;//p指向第一個結(jié)點

while(p)//沒到表尾

{ q=p->next;

free(p); p=q; } L->next=NULL; returnOK;}算法3.5單鏈表的置空(4)求表長int

ListLength(LinkListL){

inti=0;

LinkListp=L->next;

while(p){i++;p=p->next;}returni;}算法3.6單鏈表的表長(5)取值intGetElem(LinkListL,inti,DataType*e){intj;

LinkListp; p=L->next; j=1; while(p&&j<i)

{p=p->next;++j;} if(!p||j>i)returnERROR; *e=p->data; returnOK;}(6)求位序(查找)int

LocateElem(LinkList

L,DataTypee){inti=0;

LinkListp=L->next;

while(p){i++;

if(p->data==e)//找到這樣的數(shù)據(jù)元素

returni;p=p->next;}return0;}算法3.8單鏈表某元素的位序算法評價？pabes在線性表兩個數(shù)據(jù)元素a和b間插入e，已知p指向as->next=p->next;p->next=s;算法評價(7)單鏈表的插入(7)單鏈表的插入int

ListInsert(LinkList&L,int

i,DataTypee){ intj;

LinkList

p,s; p=L; j=1; while(p&&j<i)//尋找第i個結(jié)點

{ p=p->next; ++j; } if(!p||j>i)returnERROR;

(7)單鏈表的插入 s=(LinkList)malloc(sizeof(Node));//生成新結(jié)點

s->data=e; s->next=p->next; p->next=s; returnOK;}pabc算法評價單鏈表中刪除b，設(shè)p指向ap->next=p->next->next;(8)單鏈表的刪除q=p->next;p->next=q->next;q(8)單鏈表的刪除int

ListDelete(LinkList&L,int

i,DataType*e){

intj;

LinkList

p,q; p=L; j=1; while(p->next&&j<i) {p=p->next;++j; } if(!(p->next)||j>i)returnERROR;

(8)單鏈表的刪除 q=p->next; p->next=q->next; *e=q->data;//將q結(jié)點中的數(shù)據(jù)給e

free(q);//系統(tǒng)回收此結(jié)點，釋放內(nèi)存

returnOK;}(9)單鏈表的遍歷int

ListTraverse(LinkListL){intcount=0;

LinkListp=L->next;

while(p){

printf("%d",p->data);p=p->next;count++;}

printf("\n");return(count);}(10)頭插法隨機產(chǎn)生n個元素的值，建立帶表頭結(jié)點的單鏈線性表L（頭插法）。voidCreateListHead(LinkList&L,intn){

LinkListp;

inti; srand(time(0));//初始化隨機數(shù)種子

L=(LinkList)malloc(sizeof(Node)); L->next=NULL;

(10)頭插法

for(i=0;i<n;i++) { p=(LinkList)malloc(sizeof(Node)); p->data=rand()%100+1;//隨機生成100以內(nèi)的數(shù)字*

p->next=L->next; L->next=p; }}(11)尾插法

隨機產(chǎn)生n個元素的值，建立帶表頭結(jié)點的單鏈線性表L（尾插法）。voidCreateListTail(LinkList&L,intn){

LinkList

p,r;

inti; srand(time(0)); L=(LinkList)malloc(sizeof(Node)); r=L;

(11)尾插法 for(i=0;i<n;i++) { p=(Node*)malloc(sizeof(Node)); p->data=rand()%100+1; r->next=p; r=p; } r->next=NULL;}它是一種動態(tài)結(jié)構(gòu)不需預(yù)先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢單鏈表特點1.在下面鏈表中按順序插入結(jié)點q，寫出核心程序段1628H4360^52q設(shè)計算法2.將單鏈表中所有重復(fù)的結(jié)點刪除，只保留第一個3.將兩個有序單鏈表合并成一個有序單鏈表，合并后p1為結(jié)果鏈表，p2為空。2009年研究生考試真題（15分）已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計思想（2）描述算法的詳細實現(xiàn)步驟（3）根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法（使用C或C++或JAVA語言實現(xiàn)），關(guān)鍵之處請給出簡要注釋datalink（1）基本思想：從頭至尾遍歷單鏈表，并用指針p指向當(dāng)前結(jié)點的前k個結(jié)點，當(dāng)遍歷到鏈表的最后一個結(jié)點時，指針p所指向的結(jié)點即為所查找的結(jié)點（2）詳細步驟：增加兩個指針變量和一個整形變量，從鏈表頭向后遍歷，其中指針p1指向當(dāng)前遍歷的結(jié)點，指針p指向p1所指結(jié)點的前k個結(jié)點，如果p1之前沒有k個結(jié)點，那么p指向表頭結(jié)點。用整型變量i表示當(dāng)前遍歷了多少個結(jié)點，當(dāng)i>k時，指針p隨著每次的遍歷，也向前移動一個結(jié)點。當(dāng)遍歷完成時，p或者指向表頭結(jié)點，或者指向鏈表中倒數(shù)第k的位置上的結(jié)點（3）int

LocateElement(Linklist

list,intk){p1=list->link;p=list;i=1;while(p1){p1=p1->link;i++;

if(i>k)p=p->link;}

if(p==list)return0;else{printf(“%d\n”,p->data);return1;}}3.4循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，從表中任何一結(jié)點出發(fā)均可找到表中其他結(jié)點。

(a)非空表(b)空表圖3.5單循環(huán)鏈表循環(huán)鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是在于它們是否等于頭指針。3.5雙向鏈表(doublelinkedlist)對單鏈表進行改進的另一種方法是構(gòu)成雙向鏈表。雙向鏈表中每個結(jié)點除了有向后的指針(next)外，還有一個指向前一個結(jié)點的指針(prior)，這樣形成的鏈表中有兩條不同方向的鏈，因此，從某一個結(jié)點均可向兩個方向訪問。這樣構(gòu)成的鏈表有兩個方向不同的鏈，簡稱為雙向鏈表。3.5雙向鏈表(doublelinkedlist)圖3.7雙向循環(huán)鏈表結(jié)點結(jié)構(gòu)其中鏈域prior和next分別指向本結(jié)點的直接前趨結(jié)點和直接后繼結(jié)點。數(shù)據(jù)域指針域指針域結(jié)點存儲數(shù)據(jù)元素data存儲后繼結(jié)點的地址next存儲前趨結(jié)點的地址prior如果循環(huán)鏈表的結(jié)點再采用雙向指針，就成為雙向循環(huán)鏈表也成為雙鏈表。圖3.8是一個具有空表頭結(jié)點的雙向循環(huán)鏈表，其表尾結(jié)點的向右指針指向空表頭結(jié)點，空表頭結(jié)點的向左指針指向表尾結(jié)點。

圖3.8雙向循環(huán)鏈表

L空雙向循環(huán)鏈表：雙鏈表較單鏈表雖然要多占用一些存儲單元，但對其插入和刪除操作以及查找結(jié)點的前趨和后繼都非常方便。在鏈表較長，插入、刪除較頻繁或需要經(jīng)常查找結(jié)點的前趨和后繼的情況下使用雙鏈表比較合適。雙鏈表結(jié)構(gòu)是一種對稱結(jié)構(gòu)，設(shè)指針p指向雙鏈表的某一結(jié)點，則雙鏈表的對稱性可用下式來表示：

p=(p->next)->prior=(p->prior)->next亦即結(jié)點*p的地址既存放在其前趨結(jié)點*(p->prior)的后繼指針域中，又存放在它的后繼結(jié)點*(p->next)的前趨指針域中。3.5.2雙向鏈表的基本操作與單鏈表相比較，雙向鏈表只是增加了直接前繼的指針域，故其存儲結(jié)構(gòu)可表示為：typedef

struct

DuLNode{DataTypedata;struct

DuLNode*prior;

struct

DuLNode*next;}DuLNode,*DuLink;在雙向鏈表上進行操作基本上和單向鏈表相同，例如，查找結(jié)點也是要從頭指針指示的頭結(jié)點開始，但插入和刪除時必須同時修改兩個方向上的指針。(1)雙向鏈表的插入在帶頭結(jié)點的雙向鏈表L中結(jié)