第二章線性表2課件

邏輯結(jié)構(gòu)存儲結(jié)構(gòu)運(yùn)算建立結(jié)構(gòu)線性表字符串廣義表

樹二叉樹文件圖數(shù)組堆棧和隊(duì)列順序存儲鏈?zhǔn)酱鎯λ饕⒘星宄Y(jié)構(gòu)插入數(shù)據(jù)元素刪除數(shù)據(jù)元素修改數(shù)據(jù)元素排序檢索

數(shù)據(jù)結(jié)構(gòu)的基本問題空間關(guān)于參數(shù)表中的&表示voidFUN2(intn){

n++;}…………voidFUN1(){n=10;FUN2(n);printf(“\n%d”,n);}……………調(diào)用算法調(diào)用算法被調(diào)用FUN2(&n);(*n)++;&n++;FUN2(n);C++表示FUNCTIONFUN2(VAR

n:integer)Pascal:順序存儲結(jié)構(gòu)示意圖

(

a1,a2,a3,......,an-1,an)事先分配給線性表的空間當(dāng)前已經(jīng)占用的空間尚未使用的空間0123…n-2n-1nn+1…MaxSize-1……………a2a1a3an-1ann<MaxSize(1)構(gòu)造原理簡單、直觀，易理解。(2)元素的存儲地址可以通過一個簡單的解析式計(jì)算出來。(1)存儲分配需要事先進(jìn)行。(2)需要一片地址連續(xù)的存儲空間。(3)

由于只需存放數(shù)據(jù)元素本身的信息，而無其他空間開銷，相對鏈?zhǔn)酱鎯Y(jié)構(gòu)而言，存儲空間開銷小(僅此而已!)2.缺點(diǎn)是一種隨機(jī)存儲結(jié)構(gòu),存儲速度快。

順序存儲結(jié)構(gòu)的特點(diǎn)(3)基本操作(如插入、刪除)的時間效率較低。1.優(yōu)點(diǎn)O(n)

LOC(ai)=LOC(a1)+(i1)k

線性表的這種存儲結(jié)構(gòu)稱為

，或者

，其一般形式為：單鏈表線性鏈表a1d1a2d2a3d3a4d4andn…^list一個鏈結(jié)點(diǎn)數(shù)據(jù)域指針域datalinkk個存儲單元求線性表的長度。建立一個線性鏈表。在非空線性鏈表的第一個結(jié)點(diǎn)前插入一個數(shù)據(jù)信息為item的新結(jié)點(diǎn)。在線性鏈表中由指針q指出的結(jié)點(diǎn)之后插入一個數(shù)據(jù)信息為item的鏈結(jié)點(diǎn)。在線性鏈表中第i個結(jié)點(diǎn)后面插入一個數(shù)據(jù)信息為item的鏈結(jié)點(diǎn)。從非空線性鏈表中刪除鏈結(jié)點(diǎn)q(q為指向被刪除鏈結(jié)點(diǎn)的指針)。

2.3.3鏈表的基本操作刪除線性鏈表中滿足某個條件的鏈結(jié)點(diǎn)。線性鏈表的逆轉(zhuǎn)。將兩個線性鏈表合并為一個線性鏈表。檢索線性鏈表中的第i個鏈結(jié)點(diǎn)。

……

1.求線性鏈表的長度……list^p=p->link;pppn++;=NULL鏈表長度p初始：

n=0;intLENGTH(LinkListlist){LinkListp=list;/*p為遍歷鏈表結(jié)點(diǎn)的指針*/

intn=0;/*鏈表的長度置初值0*/

while(p!=NULL){p=p->link;/*p依次指向鏈表的下一結(jié)點(diǎn)*/

n++;

/*對鏈表結(jié)點(diǎn)累計(jì)計(jì)數(shù)*/

}returnn;/*返回鏈表的長度n*/

}算法非遞歸算法時間復(fù)雜度O(n)遞歸算法(a1,a2,a3,…,an–1,an)求nintLENGTH(LinkListlist){if(list!=NULL)return1+LENGTH(list->link);elsereturn0;}遞歸算法……list^遞歸算法的時間效率通常比非遞歸算法要低！為什么申請一個鏈結(jié)點(diǎn)的空間釋放一個鏈結(jié)點(diǎn)的空間(a1,a2,a3,…,an–1,an)p=(LinkList)malloc(sizeof(LNode));C語言free(p);2.建立一個線性鏈表list^a1a2a3an-1an…#include<alloc.h>typedefstructnode{ElemTypedata;structnode*link;}LNode,*LinkList;類型定義(a1,a2,a3,a4,…,an-1,an)a1lista2a3…an-1an^a1a2a3listra4pr->link=p;rr=p；一個結(jié)點(diǎn)的插入過程LinkListCREATE(intn){

/*list是鏈表指針,p指向新申請的結(jié)點(diǎn)，r指向最后一個結(jié)點(diǎn)*/LinkListp,r,list=NULL;

datatypea;

for(i=1;i<=n;i++){

READ(a);

/*取一個數(shù)據(jù)元素*/

p=(LinkList)malloc(sizeof(LNode));

p->data=a;p->link=NULL;

if(list==NULL)list=p;elser->link=p;/*將新結(jié)點(diǎn)鏈接在鏈表尾部*/

r=p;}returnlist;

}算法申請一個新的鏈結(jié)點(diǎn)時間復(fù)雜度O(n)…^listpitem…^itemlistp->link=list；

3.在非空線性鏈表的第一個結(jié)點(diǎn)前插入一個數(shù)據(jù)信息為item的新結(jié)點(diǎn)插入后算法

p=(LinkList)malloc(sizeof(LNode));

申請一個新結(jié)點(diǎn)p->data=item;

/*將item送新結(jié)點(diǎn)數(shù)據(jù)域*/p->link=list;

/*將list送新結(jié)點(diǎn)指針域

*/list=p;

/*修改指針list的指向*/voidINSERTLINK1(LinkList&list,ElemTypeitem){

/*

list指向鏈表第一個鏈結(jié)點(diǎn)*/

}時間復(fù)雜度O(1)…itemlistp……qlistpitemp->link=q->link;q->link=p;

4.在線性鏈表中由指針q指的鏈結(jié)點(diǎn)之后

插入一個數(shù)據(jù)信息為item的鏈結(jié)點(diǎn)插入過程算法p=(LinkList)malloc(sizeof(LNode));p->data=item;/*將item送新結(jié)點(diǎn)數(shù)據(jù)域*/構(gòu)造一個新結(jié)點(diǎn)if(list==NULL){/*若原鏈表為空*/

}else{ /*若原鏈表非空*/}list=p;p->link=NULL;

p->link=q->link;q->link=p;voidINSERTLINK2(LinkList&list,LinkListq,ElemTypeitem){LinkListp;}qp……item時間復(fù)雜度O(1)

5.在線性鏈表中第i(i>0)個結(jié)點(diǎn)后面插入一個數(shù)據(jù)信息為item的新結(jié)點(diǎn)尋找第i個結(jié)點(diǎn)若不存在第i個結(jié)點(diǎn)，則不做插入操作；若存在第i個結(jié)點(diǎn)，則

1.申請一個新結(jié)點(diǎn)；

2.將item送新結(jié)點(diǎn)數(shù)據(jù)域中；

3.將新結(jié)點(diǎn)插入第i個結(jié)點(diǎn)之后。如何找到第i個結(jié)點(diǎn)……pitem…^listqq=q->link;qqqqp->link=q->link;q->link=p;執(zhí)行i-1次第i個結(jié)點(diǎn)q算法voidINSERTLINK3(LinkListlist,inti,ElemTypeitem){LinkListp,q=list;intj;for(j=1;j<=i-1;j++){/*尋找第i個結(jié)點(diǎn)*/q=q->link;if(q==NULL)break;/*不存在第i個結(jié)點(diǎn)*/

}

}p=(LinkList)malloc(sizeof(LNode));p->data=item;/*將item送新結(jié)點(diǎn)數(shù)據(jù)域*/構(gòu)造一個新結(jié)點(diǎn)p->link=q->link;q->link=p;/*將新結(jié)點(diǎn)插入到第i個結(jié)點(diǎn)之后*/時間復(fù)雜度O(n)^…

…listq情況1：刪除鏈表的第一個結(jié)點(diǎn)list=q->link;情況2：刪除鏈表中非第一個結(jié)點(diǎn)^……listqrr->link=q->link;

6.

從非空線性鏈表中刪除q指的鏈結(jié)點(diǎn),設(shè)q的直接前驅(qū)結(jié)點(diǎn)由r指出voidDELETELINK1(LinkList&list,LinkListr,LinkListq){if(q==list)list=q->link;/*刪除鏈表的第一個鏈結(jié)點(diǎn)*/

elser->link=q->link;/*刪除q指的鏈結(jié)點(diǎn)*/free(q);/*釋放被刪除的結(jié)點(diǎn)空間*/}

算法時間復(fù)雜度O(1)…listq(情況1)q……(情況2)r^……listqr^……listqrr=r->link;rr=list;while(r->link!=q)r=r->link;

6.

從非空線性鏈表中刪除q指的鏈結(jié)點(diǎn),設(shè)q的直接前驅(qū)結(jié)點(diǎn)由r指出voidDELETELINK2(LinkList&list,LinkListq){LinkListr;if(q==list){/*當(dāng)刪除鏈表第一個結(jié)點(diǎn)*/

list=list->link;free(q);/*釋放被刪除結(jié)點(diǎn)的空間*/}else{r=list;while(r->link!=q&&r->link!=NULL)r=r->link;/*移向下一個鏈結(jié)點(diǎn)*/if(r->link!=NULL){r->link=q->link;free(q);}}

}尋找q結(jié)點(diǎn)的直接前驅(qū)r算法時間復(fù)雜度O(n)(1)存儲空間動態(tài)分配，可以根據(jù)實(shí)際需要使用。(3)插入/刪除操作只須通過修改指針實(shí)現(xiàn),不必移動數(shù)據(jù)元素，操作的時間效率較高。(1)每個鏈結(jié)點(diǎn)需要設(shè)置指針域(存儲密度小)。(2)是一種非隨機(jī)存儲結(jié)構(gòu)，查找、定位等操作要通過順序掃描鏈表實(shí)現(xiàn)，時間效率較低。1.優(yōu)點(diǎn)2.缺點(diǎn)(2)不需要地址連續(xù)的存儲空間。無論位于鏈表何處，無論鏈表的長度如何，插入和刪除操作的時間都是(1)。時間為(n)

2.3.4鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)思考題

1.線性表可以采用順序存儲結(jié)構(gòu)，也可以采用鏈存儲結(jié)構(gòu)，在實(shí)際問題中，應(yīng)該根據(jù)什么原則來選擇其中最合適的一種存儲結(jié)構(gòu)

2.你知道內(nèi)存的堆空間和?？臻g嗎？請說明malloc分配的內(nèi)容是在堆上分配的，還是在棧上分配的，有什么不同？請?jiān)诰W(wǎng)絡(luò)上查閱一下相關(guān)內(nèi)容。…list線性鏈表…list循環(huán)鏈表pp2.4循環(huán)鏈表是指鏈表中最后那個鏈結(jié)點(diǎn)的指針域存放指向鏈表最前面那個結(jié)點(diǎn)的指針，整個鏈表形成一個環(huán)。循環(huán)鏈表頭結(jié)點(diǎn)…list循環(huán)鏈表頭結(jié)點(diǎn)list帶頭結(jié)點(diǎn)的循環(huán)鏈表…list線性鏈表…list循環(huán)鏈表…list帶有頭結(jié)點(diǎn)的循環(huán)鏈表1.頭結(jié)點(diǎn)的設(shè)置要根據(jù)實(shí)際需要確定；2.對于采用循環(huán)鏈表作為存儲結(jié)構(gòu)的線性表，若鏈表設(shè)置了頭結(jié)點(diǎn)，則判斷空表的條件是頭結(jié)點(diǎn)list說明3.對于循環(huán)鏈表，如何判斷是否遍歷了鏈表一周？list->link=list…list線性鏈表…list循環(huán)鏈表ppppp=p=NULLp=ppp=list例如p=p->link;有用的語句：pintLENGTH(LinkListlist){LinkListp=list;intn=0;/*鏈表的長度置初值0

*/

while(p!=NULL){p=p->link;n++;}returnn;/*返回鏈表的長度n*/

}非循環(huán)鏈表intLENGTH(LinkListlist){LinkListp=list;intn=0;/*鏈表的長度置初值0

*/

do{p=p->link;n++;}while(p!=list);returnn;/*返回鏈表的長度n*/

}循環(huán)鏈表求非空線性鏈表的長度已知n個人(不妨分別以編號1,2,3,…,n代表）圍坐在一張圓桌周圍，編號為k的人從1開始報(bào)數(shù),數(shù)到m的那個人出列，他的下一個人又從1開始繼續(xù)報(bào)數(shù),數(shù)到m的那個人出列,…,依此重復(fù)下去，直到圓桌周圍的人全部出列。圓桌問題約瑟夫(JOSEPHU)問題例直到圓桌周圍只剩一個人。123n45···n-1

若假設(shè)

k=3,m=4n:鏈表中鏈結(jié)點(diǎn)的個數(shù)；k：第一個出發(fā)點(diǎn)；m：報(bào)數(shù)。利用一個不帶頭結(jié)點(diǎn)的循環(huán)鏈表…list需要做的工作：1.建立一個不帶頭結(jié)點(diǎn)的循環(huán)鏈表；…listvoidCREATE(intn,LinkList&list){LinkListp,r;list=NULL;/*創(chuàng)建一個空鏈表*/

datatypea;

for(i=1;i<=n;i++){READ(a);/*取一個數(shù)據(jù)元素*/

p=(LinkList)malloc(sizeof(LNode));

p->data=a;p->link=NULL;if(list==NULL)list=p;elser->link=p;/*將新結(jié)點(diǎn)鏈接在鏈表尾部*/

r=p;}

}p->link=list;建立一個無頭結(jié)點(diǎn)的非循環(huán)鏈表1.建立一個不帶頭結(jié)點(diǎn)的循環(huán)鏈表；…list需要做的工作：1.建立一個不帶頭結(jié)點(diǎn)的循環(huán)鏈表；2.找到第一個出發(fā)點(diǎn)；3.

反復(fù)刪除第m個鏈結(jié)點(diǎn)。

若假設(shè)

k=3,m=4p=p->link;k-1次m-1次算法voidJOSEPHU(intn,intk,intm){LinkListlist,p,r;inti;

list=NULL;for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));p->data=i;if(list==NULL)list=p;elser->link=p;r=p;}

p->link=list;/*建立循環(huán)鏈表

*/p=list;for(i=1;i<=k-1;i++){r=p;p=p->link;}/*找到第一個點(diǎn)*/

while(p->link!=p){for(i=1;i<=m-1;i++){r=p;p=p->link;}r->link=p->link;printf(“%3d”,p->data);free(p);p=r->link;}printf(“%3d”,p->data);}……pr當(dāng)k1,m=1時反復(fù)尋找并刪除結(jié)點(diǎn)

#include<alloc.h>

main(){intn,k,m;printf(“\nInputn,k,m:”);scanf(“%d%d%d”,&n,&k,&m);

JOSEPHU(n,k,m);}主函數(shù)輸入鏈結(jié)點(diǎn)總數(shù)n、報(bào)數(shù)的起始位置k與報(bào)數(shù)m。調(diào)用約瑟夫函數(shù)…^list線性鏈表(單鏈表)…list循環(huán)鏈表…^list帶頭結(jié)點(diǎn)的線性鏈表…list帶頭結(jié)點(diǎn)的循環(huán)鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.5雙向鏈表及其操作本節(jié)主要內(nèi)容1.雙向鏈表的構(gòu)造2.雙向鏈表的插入與刪除

2.5.1雙向鏈表的構(gòu)造其中，data

為數(shù)據(jù)域

rlink,llink

分別為指向該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)與直接前驅(qū)結(jié)點(diǎn)的指針域llinkdatarlink（右指針域）（左指針域）

所謂是指鏈表的每一個結(jié)點(diǎn)中除了數(shù)據(jù)域以外設(shè)置兩個指針域，其中之一指向結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，另外一個指向結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。鏈結(jié)點(diǎn)的實(shí)際構(gòu)造可以形象地描述如下：雙向鏈表分別稱為右指針和左指針…^^list無頭結(jié)點(diǎn)的雙向鏈表…list無頭結(jié)點(diǎn)的雙向循環(huán)鏈表…list帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表雙向鏈表的幾種形式typedefstructnode{ElemTypedata;structnode*rlink,*llink;}DNode,*DLinkList;類型定義功能在帶有頭結(jié)點(diǎn)的非空雙向循環(huán)鏈表中第一個數(shù)據(jù)域的內(nèi)容為x的鏈結(jié)點(diǎn)右邊插入一個數(shù)據(jù)信息為item的新結(jié)點(diǎn)?！璴ist需要做的工作:1.找到滿足條件的結(jié)點(diǎn)；2.若找到，構(gòu)造一個新的鏈結(jié)點(diǎn)；3.將新結(jié)點(diǎn)插到滿足條件的結(jié)點(diǎn)后面。

2.5.2雙向鏈表的插入…list插入前pitemxq……插入p->llink=q;p->rlink=q->rlink;q->rlink->llink=p;q->rlink=p;xq……插入后itemplist

q=list->rlink;/*q初始指向頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)*/

while(q!=list&&q->data!=x)/*尋找滿足條件的鏈結(jié)點(diǎn)*/q=q->rlink;

if(q==list)return-1;/*沒有找到滿足條件的結(jié)點(diǎn)*/intINSERTD(DLinkListlist,ElemTypex,ElemTypeitem){intDLinkListp,q;}p=(DLinkList)malloc(sizeof(DNode));/*申請一個新的結(jié)點(diǎn)*/

p->data=item;

p->llink=q;p->rlink=q->rlink;

q->rlink->llink=p;q->rlink=p;return1;

/*插入成功*/尋找滿足條件的結(jié)點(diǎn)時間復(fù)雜度O(n)算法……xitemqpO(1)功能刪除帶有頭結(jié)點(diǎn)的非空雙向循環(huán)鏈表中第一個數(shù)據(jù)域的內(nèi)容為x的鏈結(jié)點(diǎn)。…list需要做的工作:1.找到滿足條件的結(jié)點(diǎn)；2.若找到，刪除(并釋放)滿足條件的結(jié)點(diǎn)。

2.5.3雙向鏈表的刪除…list刪除前xq……刪除q->llink->rlink=q->rlink;q->rlink->llink=q->llink;…list刪除后…

q=list->rlink;/*

q初始指向頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)

*/

while(q!=list&&q->data!=x)/*

找滿足條件的鏈結(jié)點(diǎn)

*/q=q->rlink；if(q==list)return-1;/*

沒有找到滿足條件的結(jié)點(diǎn)*/

q->llink->rlink=q->rlink;

q->rlink->llink=q->llink;free(q);/*

釋放被刪除的結(jié)點(diǎn)的存儲空間

*/intDELETED(DLinkListlist,Ele