數據結構：第2章-線性表

數據結構第2章線性表2.1

線性表及其抽象數據類型2.2線性表的順序存儲結構2.3線性表的鏈式存儲結構2.6一元多項式的表示及相加2.4棧和隊列2.5循環(huán)線性鏈表和雙向鏈表1數據結構第2章線性表2.1線性表及其抽象數據類型

定義：線性表(LinearList)是由n(n≥0)個類型相同的數據元素a1,a2,…，an組成的有限序列，記做（a1,a2,…，ai-1，ai，ai+1，…，an）。數據元素之間是一對一的關系，即每個數據元素最多有一個直接前驅和一個直接后繼。邏輯結構圖：2數據結構第2章線性表特點：①同一性：線性表由同類數據元素組成，每一個ai必須屬于同一數據對象。②有窮性：線性表由有限個數據元素組成，表長度就是表中數據元素的個數。③有序性：線性表中相鄰數據元素之間存在著序偶關系<ai,ai+1>。2.1線性表及其抽象數據類型

3數據結構第2章線性表抽象數據類型定義：ADTLinearList{

數據元素：D={ai|ai∈D0,i=1,2,…，n;n≥0,D0為某一數據對象}

關系：Ｓ=<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝

基本操作：

（1）InitList（L）

操作前提：L為未初始化線性表。操作結果：將L初始化為空表。

（2）DestroyList(L)

操作前提：線性表L已存在。操作結果：將L銷毀。

………p11}ADT

LinearList返回2.1線性表及其抽象數據類型

4數據結構第2章線性表2.2線性表的順序存儲結構定義:采用順序存儲結構的線性表通常稱為順序表。假設線性表中每個元素占k個單元，第一個元素的地址為loc(a1)，則第i個元素的地址為：loc(ai)=loc(a1)+(i-1)×k是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中。5數據結構第2章線性表...loc(a1)+(maxlen-1)knan

loc(a1)+(n-1)k………iai

loc(a1)+(i-1)k………2a2

Loc(a1)+(2-1)k1a1Loc(a1)邏輯地址內存空間狀態(tài)存儲地址順序存儲結構示意圖空閑2.2線性表的順序存儲結構6數據結構第2章線性表C語言定義#definemaxsize

線性表可能達到的最大長度typedef

struct{

ElemType

elem[maxsize]；

intlast；

}SeqList； 2.2線性表的順序存儲結構7數據結構第2章線性表基本運算①查找操作②插入操作③刪除操作2.2線性表的順序存儲結構8數據結構第2章線性表①查找操作按序號查找GetData(L,i)：要求查找線性表L中第i個數據元素，其結果是L.elem[i-1]。按內容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數據元素，其結果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。2.2線性表的順序存儲結構9數據結構第2章線性表按內容查找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線性表的順序存儲結構10數據結構第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個位置。

(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(“表已滿無法插入”)；

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);}

時間復雜度：

O(n)11數據結構第2章線性表③刪除操作是指將表的第i(1≤i≤n)個元素刪去，使長度為n的線性表(e1，…,ei-1，ei，ei+1，…，en)，變成長度為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);}時間復雜度：O(n)2.2線性表的順序存儲結構12數據結構第2章線性表2.2線性表的順序存儲結構例2-1

：有兩個順序表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個順序表LC，要求LC也是非遞減有序排列。算法思想：設表LC是一個空表，為使LC也是非遞減有序排列，可設兩個指針i、j分別指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，則當前先將LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j]，當前先將LA.elem[i]插入到表LC中，如此進行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表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數據結構第2章線性表優(yōu)點：②可方便地隨機存取表中的任一元素。缺點：①插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結點，其效率較低；①無須為表示結點間的邏輯關系而增加額外的存儲空間；②由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預先進行靜態(tài)分配。因此當表長變化較大時，難以確定合適的存儲規(guī)模。返回2.2線性表的順序存儲結構14數據結構第2章線性表2.3線性表的鏈式存儲結構定義:采用鏈式存儲結構的線性表稱為鏈表。動態(tài)鏈表靜態(tài)鏈表單鏈表雙鏈表循環(huán)鏈表實現角度鏈接方式15數據結構第2章線性表單鏈表：鏈表中的每個結點只有一個指針域結點（Node）：單鏈表包括兩個域數據域：指針域：用來存儲結點的數據值用來存儲數據元素的直接后繼的地址（或位置）頭指針：指向鏈表頭結點的指針。為了正確地表示結點間的邏輯關系，必須在存儲線性表的每個數據元素值的同時，存儲指示其后繼結點的地址（或位置）信息，這兩部分信息組成的存儲映象叫做結點。2.3線性表的鏈式存儲結構16數據結構第2章線性表單鏈表頭指針H存儲地址數據域指針域1D437B1313C119HNULL25F3731A737G1943E2531AHBCDEFGH∧2.3線性表的鏈式存儲結構17數據結構第2章線性表單鏈表頭結點H∧帶頭結點的空單鏈表帶頭結點的單鏈表EFGH∧H2.3線性表的鏈式存儲結構18數據結構第2章線性表單鏈表存儲結構描述typedef

structNode{

ElemTypedata；

structNode*next；}Node,*LinkList；2.3線性表的鏈式存儲結構19數據結構第2章線性表單鏈表的基本運算①建立單鏈表②單鏈表查找③單鏈表插入操作④單鏈表刪除⑤求單鏈表的長度2.3線性表的鏈式存儲結構20數據結構第2章線性表①建立單鏈表頭插法建表sA∧s指向新申請的結點s->data=A;H∧sA∧插入第一個結點：插入某一個結點：H∧A∧sB∧從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭結點之后，直至讀入結束標志為止?！立賡->next=H->next;②H->next=s;順序可以顛倒嗎？H∧初始化空表2.3線性表的鏈式存儲結構21數據結構第2章線性表2.3線性表的鏈式存儲①建立單鏈表頭插法建表算法

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數據結構第2章線性表①建立單鏈表尾插法建表sA∧s指向新申請的結點s->data=A;H∧sA∧插入第一個結點：插入某一個結點：sB∧將新結點插到當前單鏈表的表尾上。增加一個尾指針r，使之指向當前單鏈表的表尾。r->next=s;r=s;順序可以顛倒嗎？H∧初始化空表rrH∧A∧rr2.3線性表的鏈式存儲結構23數據結構第2章線性表2.3線性表的鏈式存儲②建立單鏈表尾插法建表算法

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數據結構第2章線性表②單鏈表查找按序號查找設帶頭結點的單鏈表的長度為n，要查找表中第i個結點，則需要從單鏈表的頭指針L出發(fā)，從第一個結點（L->next）開始順著鏈域掃描。用指針p指向當前掃描到的結點,初值指向第一個結點（p=L->next），用j做記數器，累計當前掃描過的結點數（初值為0），當j=i時，指針p所指的結點就是要找的第i個結點。

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線性表的鏈式存儲結構25數據結構第2章線性表③單鏈表查找按值查找指在單鏈表中查找是否有結點值等于e的結點，若有的話，則返回首次找到的其值為e的結點的存儲位置，否則返回NULL。

查找過程從單鏈表的頭指針指向的第一個結點出發(fā)，順著鏈逐個將結點的值和給定值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線性表的鏈式存儲結構26數據結構第2章線性表③單鏈表插入要在帶頭結點的單鏈表L中第i個數據元素之前插入一個數據元素e，需要首先在單鏈表中找到第i-1個結點并由指針pre指示，然后申請一個新的結點并由指針s指示，其數據域的值為e，并修改第i-1個結點的指針使其指向s，然后使s結點的指針域指向第i個結點。se∧×①s->next=pre->next;②pre->next=s;順序可以顛倒嗎？a1a2ai-1aian∧……preL2.3線性表的鏈式存儲結構27算法實現數據結構第2章線性表2.3線性表的鏈式存儲④單鏈表插入

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數據結構第2章線性表④單鏈表刪除欲在帶頭結點的單鏈表L中刪除第i個結點，則首先要通過計數方式找到第i-1個結點并使pre指向第i-1個結點，而后刪除第i個結點并釋放結點空間?！痢羛re->next=pre->next->next;a1a2ai-1aian∧……preai+1rL

free(r);2.3線性表的鏈式存儲結構29算法實現數據結構第2章線性表2.3線性表的鏈式存儲⑤單鏈表刪除

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(“刪除結點的位置i不合理！”);returnERROR;}

r=pre->next;pre->next=pre->next->next;free(r);returnOK;}30數據結構第2章線性表⑤求單鏈表的長度可以采用“數”結點的方法來求出單鏈表的長度，用指針p依次指向各個結點,從第一個元素開始“數”，一直“數”到最后一個結點（p->next=NULL）。算法實現

int

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

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數據結構第2章線性表循環(huán)鏈表(CircularLinkedList)：是一個首尾相接的鏈表。特點：將單鏈表最后一個結點的指針域由NULL改為指向頭結點或線性表中的第一個結點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結點被鏈在一個環(huán)上。L帶頭結點的空循環(huán)鏈表a1a2ai-1aian……L帶頭結點的循環(huán)單鏈表a1a2ai-1aian……采用尾指針的循環(huán)單鏈表rear2.5循環(huán)線性鏈表和雙向鏈表33數據結構第2章線性表循環(huán)鏈表(CircularLinkedList)例2-3有兩個帶頭結點的循環(huán)單鏈表LA、LB，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為LA。先找到兩個鏈表的尾，并分別由指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結點鏈接起來，并修改第二個表的尾q，使它的鏈域指向第一個表的頭結點。a1a2ai-1aian……LAb1b2bi-1bibn……LBpq

p->next=LB->next;q->next=LA;free(LB);2.5循環(huán)線性鏈表和雙向鏈表34數據結構第2章線性表循環(huán)鏈表(CircularLinkedList)算法實現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);}時間復雜度為

O(n)2.5循環(huán)線性鏈表和雙向鏈表35數據結構第2章線性表循環(huán)鏈表(CircularLinkedList)例2-3有兩個帶頭結點的循環(huán)單鏈表LA、LB，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為LA。采用帶尾指針的循環(huán)鏈表，執(zhí)行時間可降低為O(1)。a1a2ai-1aian……RAb1b2bi-1bibn……RBpRA->next=RB->next->next;RB->next=p;free(RB->next);2.5循環(huán)線性鏈表和雙向鏈表36數據結構第2章線性表循環(huán)鏈表(CircularLinkedList)算法實現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數據結構第2章線性表雙向鏈表(DoubleLinkedList)在單鏈表的每個結點里再增加一個指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙(向)鏈表。結構定義：typedef

struct

Dnode{

ElemTypedata；

struct

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

p->prior->next=s;②②s->prior=p->prior;順序可以顛倒嗎？×③③p->prior=s;④④s->next=p;順序可以顛倒嗎？順序可以顛倒嗎？2.5循環(huán)線性鏈表和雙向鏈表40數據結構第2章線性表2.3線性表的鏈式存儲雙向鏈表(DoubleLinkedList)前插操作算法實現：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數據結構第2章線性表2.5循環(huán)線性鏈表和雙向鏈表雙向鏈表(DoubleLinkedList)刪除操作：abc……p×①p->prior->next=p->next;①×②②p->next->prior=p->prior;free(p);42數據結構第2章線性表2.5循環(huán)線性鏈表和雙向鏈表雙向鏈表(DoubleLinkedList)刪除操作算法實現：int

DlinkDel(DoubleList

L,inti){

DNode*p;

p=search(L,i);

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