第3章數據結構- 線性表

第三章線性表DS應用實踐

線性表的概念

雙向鏈表

循環(huán)鏈表

線性表的順序存儲

單向鏈表

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

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

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

基本操作InitList(SqList

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

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

基本操作LocateElem(SqListL,

DataType

e)//返回L中第1個與e滿足關系的數據元素位序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)//用頭插法建立帶表頭結點的單鏈線性表LCreateListTail(SqList

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

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

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

int

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

struct{

DataType

data[MAXSIZE];

intlength;}SqList;圖3.1線性表的順序存儲結構

a1a2an01n-112n內存V數組下標元素序號M-1typedef

int

DataType;#defineMAXSIZE100例typedef

struct{

DataType

data[MAXSIZE]

intlength;}SqList;備用空間數據元素不是簡單類型時,可定義結構體數組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);//釋放線性表占據的所有存儲空間}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];//數組中第i-1的單元存儲著線性表中第i個數據元素的內容

returnOK;}3.2.2順序表的基本運算6.返回線性表中第1個與e滿足關系的數據元素位序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;//數組中第i-1的單元存儲著線性表中第i個數據元素的內容

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

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

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

線性表插入前后的狀況內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2aiai+1an01i-1V數組下標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;

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

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

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

圖3.3線性表刪除前后的狀況內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2ai+1V數組下標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;}設Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數的平均次數為：故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低算法評價順序存儲結構的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分表容量難以擴充練習：1.實現在順序表中按值插入元素。2.給定一個順序表L=（a1,a2,a3,...,an),請設計一個算法刪除所有值大于min而且小于max的元素。實現在順序表中按值插入元素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),請設計一個算法刪除所有值大于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單向鏈表順序表的存儲特點是用物理上的相鄰來實現邏輯上的相鄰，它要求用連續(xù)的存儲單元順序存儲線性表中各元素，因此，對順序表插入、刪除時需要通過移動數據元素來實現，影響了運行效率。線性鏈表不需要用地址連續(xù)的存儲單元來實現，而是通過“鏈”建立起數據元素之間的邏輯結構。

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

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

(a1,a2,….,an)的鏈式存儲結構。整個鏈表的存取必須從頭指針開始進行，頭指針指示鏈表中第一個結點（即第一個數據元素的存儲映像）的存儲位置。同時，由于最后一個數據元素沒有直接后繼，則線性鏈表中最后一個結點的指針為空(NULL)。

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

(a)非空表

(b)空表圖3.4

帶頭指針的單鏈表用C語言定義的單鏈表結構如下：typedef

structNode{

DataTypedata;

structNode*next;}Node;typedef

structNode*LinkList;

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

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

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

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

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

L,int

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

L,DataType

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

i,DataType

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

i,DataType*e)//刪除指定位置的數據元素(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指向第一個結點

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)//找到這樣的數據元素

returni;p=p->next;}return0;}算法3.8單鏈表某元素的位序算法評價？pabes在線性表兩個數據元素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個結點

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

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

s->data=e; s->next=p->next; p->next=s; returnOK;}pabc算法評價單鏈表中刪除b，設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結點中的數據給e

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

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)頭插法隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（頭插法）。voidCreateListHead(LinkList&L,intn){

LinkListp;

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

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以內的數字*

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

隨機產生n個元素的值，建立帶表頭結點的單鏈線性表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)結構不需預先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢單鏈表特點1.在下面鏈表中按順序插入結點q，寫出核心程序段1628H4360^52q設計算法2.將單鏈表中所有重復的結點刪除，只保留第一個3.將兩個有序單鏈表合并成一個有序單鏈表，合并后p1為結果鏈表，p2為空。2009年研究生考試真題（15分）已知一個帶有表頭結點的單鏈表，結點結構為假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想（2）描述算法的詳細實現步驟（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C++或JAVA語言實現），關鍵之處請給出簡要注釋datalink（1）基本思想：從頭至尾遍歷單鏈表，并用指針p指向當前結點的前k個結點，當遍歷到鏈表的最后一個結點時，指針p所指向的結點即為所查找的結點（2）詳細步驟：增加兩個指針變量和一個整形變量，從鏈表頭向后遍歷，其中指針p1指向當前遍歷的結點，指針p指向p1所指結點的前k個結點，如果p1之前沒有k個結點，那么p指向表頭結點。用整型變量i表示當前遍歷了多少個結點，當i>k時，指針p隨著每次的遍歷，也向前移動一個結點。當遍歷完成時，p或者指向表頭結點，或者指向鏈表中倒數第k的位置上的結點（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)鏈表是另一種形式的鏈式存儲結構。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)，從表中任何一結點出發(fā)均可找到表中其他結點。

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

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

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

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

struct

DuLNode{DataTypedata;struct

DuLNode*prior;

struct

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