




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
Chapter4線性表、堆棧和隊(duì)列
4.1線性表的定義和基本操作
4.2線性表的存儲(chǔ)結(jié)構(gòu)
4.3堆棧和隊(duì)列4.1線性表的定義和操作4.1.1線性表的定義
[例1]英文字母表(A,B,C,……,Z)
整數(shù)序列(1,78,9,12,10)[例2]某班學(xué)生健康情況登記表。學(xué)號(hào)姓名性別年齡健康情況
01張軍男18一般02陳紅女17良好
03陳軍男19良好
…
…
…
…
…線性表定義:一個(gè)線性表是由零個(gè)或多個(gè)具有相同類型的結(jié)點(diǎn)組成的有序集合。用(a0,a1,…,an-1)來(lái)表示一個(gè)線性表。當(dāng)n>0時(shí),a0稱為表的始結(jié)點(diǎn),an-1稱為表的終結(jié)點(diǎn),當(dāng)n=0時(shí),線性表中有零個(gè)結(jié)點(diǎn),稱為空表。
線性表的邏輯結(jié)構(gòu):線性結(jié)構(gòu)線性表記為(a0,a1,…,an-1)n≠0()n=0線性表的操作(1)隨機(jī)存?。捍嫒∠聵?biāo)為k的結(jié)點(diǎn)(2)插入:在下標(biāo)為k的結(jié)點(diǎn)前(或后)
插入一個(gè)新結(jié)點(diǎn)x(3)刪除:刪除下標(biāo)為k的結(jié)點(diǎn)。(4)查找:尋覓具有特定域值的結(jié)點(diǎn)。(5)歸并、分拆、復(fù)制、計(jì)數(shù)、排序。Chapter4
線性表、堆棧和隊(duì)列
4.1線性表的定義和基本操作
4.2線性表的存儲(chǔ)結(jié)構(gòu)
4.2.1順序存儲(chǔ)結(jié)構(gòu)
4.2.2鏈接存儲(chǔ)結(jié)構(gòu)--單鏈表
4.2.3循環(huán)鏈表
4.2.4雙向循環(huán)鏈表
4.3堆棧和隊(duì)列
4.2線性表的存儲(chǔ)結(jié)構(gòu)線性表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)非順序存儲(chǔ)——鏈表4.2.1順序存儲(chǔ)結(jié)構(gòu)
●順序存儲(chǔ):用一組連續(xù)的存儲(chǔ)空間依次存儲(chǔ)線性表的元素。
●特點(diǎn):其邏輯順序與物理順序相同。 實(shí)現(xiàn)順序存儲(chǔ)的最有效方法是使用一維數(shù)組。[例]:線性表(a0,a1
,a2,a3)??梢允褂靡粋€(gè)數(shù)組a[n]來(lái)存放此線性表。
圖4.1是包含4個(gè)結(jié)點(diǎn)的線性表A[4]在內(nèi)存中的表示,其中每個(gè)結(jié)點(diǎn)占2個(gè)連續(xù)的字節(jié),第一個(gè)結(jié)點(diǎn)A[0]的首地址為302
圖4.1線性表的順序存儲(chǔ)線性表A[2]308306304302A[0]A[1]A[3]
Loc(a[k])=Loc(a[0])+k*ca0a1an-1akb+cb+k*cbb+(n-1)*c……01n-1k空閑區(qū)
特點(diǎn):其邏輯順序與物理順序相同。順序存儲(chǔ),隨機(jī)存取
線性表上實(shí)現(xiàn)的基本運(yùn)算
1、插入
[例]在線性表(12,13,21,24,28,30,42,77) 中下標(biāo)為3的結(jié)點(diǎn)后,插入元素
25。問(wèn)題:此時(shí),線性表的邏輯結(jié)構(gòu)發(fā)生什么變化?位置關(guān)系發(fā)生變化長(zhǎng)度增1
序號(hào)元素230416751213212428304277插入25序號(hào)元素230416751213252124283042778在下標(biāo)為k的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)//ADL描述算法Insert(A,k,x)Insert1[k是否合法]IF(k<0ORk>n)THENPRINT(“overflow”)ELSE(FORi=nTOk+1STEP-1DO
A[i+1]
A[i].A[i]
x.n
n+1.).▌時(shí)間復(fù)雜性分析插入操作的基本運(yùn)算是:
元素移動(dòng)Dn中有多少種可能的輸入呢?
n+1種(n+1個(gè)位置可以發(fā)生插入)設(shè)每種輸入發(fā)生的頻率相等:1/(n+1)則期望復(fù)雜性為:E(n)=(n+(n-1)+……+1+0)/(n+1)=n/22、刪除
[例]在線性表(12,13,21,24,28,30,42,77) 中刪除下標(biāo)為3的元素。問(wèn)題:此時(shí),線性表的邏輯結(jié)構(gòu)發(fā)生什么變化?
位置關(guān)系發(fā)生變化長(zhǎng)度減1序號(hào)元素230416751213212428304277刪除24序號(hào)元素230416512132128304277刪除下標(biāo)為k的結(jié)點(diǎn)//ADL描述算法Delete(A,k)Delete1[檢查k是否合法]IF(k<1ORk>n)THENPRINT(“error”)ELSE(FORi=k+1TOnDO
A[i-1]
A[i].
nn-1.)▌
時(shí)間復(fù)雜性分析刪除操作的基本運(yùn)算是:元素移動(dòng)
Dn中有多少種可能的輸入呢?
n種(n個(gè)位置可以發(fā)生刪除)設(shè)每種輸入發(fā)生的頻率相等:1/n
則期望復(fù)雜性為:
E(n)=(n-1)/n+……+1/n+0/n=(n-1)/2
●結(jié)論:
優(yōu)點(diǎn):線性表的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn),數(shù)據(jù)的存取操作采用隨機(jī)存取,可以隨機(jī)訪問(wèn)表中任一元素。
缺點(diǎn):線性表的容量不容易擴(kuò)充,不利于數(shù)據(jù)的合并與分離;插入、刪除操作需要移動(dòng)大量元素。問(wèn)題:由于線性表中元素的數(shù)目可以改變,定義數(shù)組時(shí)要做如何的考慮呢?
定義足夠大的數(shù)組
4.2.2鏈接存儲(chǔ)結(jié)構(gòu)
————單鏈表
1、單鏈表的定義
●鏈?zhǔn)酱鎯?chǔ):用一組任意存儲(chǔ)單元存儲(chǔ)線性 表的數(shù)據(jù)元素。
單鏈表的結(jié)點(diǎn)結(jié)構(gòu):
鏈表的第一個(gè)結(jié)點(diǎn)被稱為頭結(jié)點(diǎn),指向頭結(jié)點(diǎn)
的指針被稱為頭指針。鏈表的最后一個(gè)結(jié)點(diǎn)被
稱為尾結(jié)點(diǎn)。
●單鏈表的定義:每個(gè)結(jié)點(diǎn)只含有一個(gè)指針域的 鏈表叫單鏈表。datanext單鏈表的存儲(chǔ)映像●特點(diǎn):邏輯順序與物理順序可以相同也可 以不同。
優(yōu)點(diǎn):①插入、刪除操作方便。 ②數(shù)據(jù)的合并與分離容易。結(jié)點(diǎn)可以不連續(xù)存儲(chǔ)線性表可擴(kuò)充[例]將線性表(a3,a4,a5),以鏈表的形式存儲(chǔ) 在內(nèi)存中。a5500a3100002a4002500∧●單鏈表的特性:
①在鏈表中,利用指針域表示線性表的邏輯結(jié)
構(gòu)。②鏈表有頭節(jié)點(diǎn)、尾節(jié)點(diǎn)、頭指針。a5a3a4∧2.單鏈表插入、刪除操作舉例●插入:
…FATHAT…pGATssnext=pnext;pnext=s;×插入操作演示2.單鏈表插入、刪除操作舉例●刪除:
刪除操作演示
q=pnext;×…FATHAT…pGATqpnext=qnext;鏈表結(jié)點(diǎn)類Node的ADT描述:ADTNodeisDatadata用來(lái)保存結(jié)點(diǎn)信息的域
next用來(lái)存放后繼結(jié)點(diǎn)地址信息的域,即存放指
向后繼結(jié)點(diǎn)的指針
OperationsConstructorInitialvalue: 給出當(dāng)前結(jié)點(diǎn)的data域值和next域值
Process: 對(duì)data域和next域進(jìn)行初始化
NextNode:
Input: 無(wú)
Precondition: 無(wú)
Process: 取next域值
Output: 返回next域值
Postcondition: 無(wú)
InsertAfterInput: 指向被插入結(jié)點(diǎn)的指針
Precondition: 無(wú)
Process:在當(dāng)前結(jié)點(diǎn)之后插入結(jié)點(diǎn)。
1.將當(dāng)前結(jié)點(diǎn)的next域值賦給新插入結(jié)點(diǎn)的next域
2.將當(dāng)前結(jié)點(diǎn)的next域值更新為新插入結(jié)點(diǎn)的地址
Output: 無(wú)
Postcondition:當(dāng)前結(jié)點(diǎn)的next域存放新插入結(jié)點(diǎn)的地址
DeleteAfterInput: 無(wú)
Precondition:無(wú)
Process: 刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)。
將當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)的next域值賦給當(dāng)前結(jié)點(diǎn)的next域
Output: 指向被刪除結(jié)點(diǎn)的指針
Postcondition: 當(dāng)前結(jié)點(diǎn)的next域值被更新
EndADTNode3.單鏈表基本操作算法
(1)Node類聲明:
template<classT>classNode{private:Node<T>*next;public:Tdata;
//
構(gòu)造函數(shù)Node(constT&item,Node<T>*ptrnext=NULL);//
在當(dāng)前結(jié)點(diǎn)之后插入指針p所指結(jié)點(diǎn)voidInsertAfter(Node<T>*p);//
刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)Node<T>*DeleteAfter(void);//
返回指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針Node<T>*NextNode(void)const;};
(2)Node類的實(shí)現(xiàn)①構(gòu)造函數(shù)
template<classT>Node<T>::Node(constT&item,Node<T>*ptrnext):
data(item),next(ptrnext){}
②返回當(dāng)前結(jié)點(diǎn)的next域的值
C++:
template<classT>
Node<T>*Node<T>::
nextNode(void)const{returnnext;} ADL:算法NextNode(this.p) NextNode1[取當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)] pnext(this).▌
③在當(dāng)前結(jié)點(diǎn)之后插入結(jié)點(diǎn)p
//ADL描述算法InsertAfter(this,p)
IA1[將當(dāng)前結(jié)點(diǎn)的next域值賦給P的next域]
next(p)
next(this).IA2[將P賦給當(dāng)前結(jié)點(diǎn)的next域]
next(this)
p.▌
…FATHAT…thisGATp×
④刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)
//ADL描述算法DeleteAfter(this.tempptr)
DA1[this的next域值=NULL?]IFnext(this)=NULL THENtempptr
NULLELSE(tempptr
next(this). next(this)
next(tempptr)).▌
×…FATHAT…thisGATtempptr
(3)構(gòu)造鏈表
//ADL描述①創(chuàng)建一個(gè)data域值為item,next域值為 nextptr的結(jié)點(diǎn)。算法GetNode(item,nextptr.newNode)
GN1[為新結(jié)點(diǎn)申請(qǐng)空間]
newNode
AVAIL.GN2[為結(jié)點(diǎn)諸域賦值]
data(newNode)
item.next(newNode)
nextptr.▌itemNewNodenextptr
②在頭指針為head的鏈表中,插入一個(gè)data域?yàn)閕tem的新結(jié)點(diǎn)作為該鏈表的表頭結(jié)點(diǎn)。
算法InsertFront(head,item)
IF1[調(diào)用函數(shù)GetNode]
GetNode(item,head.newNode).
IF2[head指向新結(jié)點(diǎn)]
head
newNode.▌
表頭插入結(jié)點(diǎn)演示HATheadGAT∧itemnewNodehead
head
(4)遍歷鏈表
遍歷鏈表演示算法
PrintList(head)//輸出頭指針為head的鏈表,每輸出5個(gè)元素?fù)Q行PL1[取表頭,計(jì)數(shù)器初始化]currptr
head.count
0.acbheadcurrptr∧PL2[遍歷并輸出鏈表結(jié)點(diǎn)的data值]
WHILE(currptr≠NULL)DO(PRINT(data(currptr)).count
count+1.IF(MOD(count,5)=0)THENPRINT.
currptr
next(currptr).
)▌acbheadcurrptrcurrptrcurrptrcurrptr∧(5)表尾插入結(jié)點(diǎn)
表尾插入結(jié)點(diǎn)演示算法InsertRear(head,item)//在頭指針為head的鏈表尾部插入data域值//為item的結(jié)點(diǎn);IR1[取頭指針]currptr
head.acbheadcurrptr∧
IR2[currptr=NULL?]IFcurrptr=NULLTHEN
InsertFront(head,item)
head=NULLcurrptr=NULLheaditemheadNULL
IR2[currptr=NULL?]IFcurrptr=NULLTHEN
InsertFront(head,item)
ELSE
(WHILE(next(currptr)≠NULL)DOcurrptr
next(currptr).
GetNote(item,NULL.newNode).InsertAfter(currptr,newNode).)▌acbheadcurrptrcurrptrnewNodeitemNULL∧
定義一種鏈表類,將鏈表的基本操作視為鏈表類的成員函數(shù),即將其封裝在類中。
6.鏈表類LinkedList
在鏈表類的定義中,有一個(gè)當(dāng)前指針,稱當(dāng)前指針?biāo)附Y(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn),用Node(currptr)記。類LinkedList的數(shù)據(jù)成員:頭指針:front
尾指針:rear
當(dāng)前指針:currptr
當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針:prevptr
鏈表中結(jié)點(diǎn)個(gè)數(shù):size
當(dāng)前結(jié)點(diǎn)在鏈表中的位置:position//令當(dāng)前指針指向表頭voidReset(intpos=0);
//令當(dāng)前指針指向原當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)voidNext(void);
//判斷當(dāng)前指針是否指向表尾結(jié)點(diǎn)intEndOfList(void)const;
//插入一個(gè)data域值為item的結(jié)點(diǎn)voidInsertFront(constT&item); //表頭插入voidInsertRear(constT&item); //表尾插入//返回當(dāng)前結(jié)點(diǎn)的data域值T&Data(void); 例4.1按表L1在前,表L2在后的次序,實(shí)現(xiàn)兩者的連接。template<classT>鏈表連接演示voidJointLists(LinkedList<T>&L1,LinkedList<T>&L2){//為操作無(wú)誤,先令兩個(gè)表當(dāng)前指針指向
//各自表頭結(jié)點(diǎn)
L1.Reset(); L2.Reset(); while(!L2.EndOfList())
{ L1.InsertRear(L2.Data());L2.Next(); }}缺點(diǎn):(1)單鏈表雖然克服了順序存儲(chǔ)的缺點(diǎn),但卻不能進(jìn)行隨機(jī)訪問(wèn),數(shù)據(jù)存取只能采用順序存取方式。(2)內(nèi)存空間占用較多。問(wèn)題:從單鏈表中某一個(gè)結(jié)點(diǎn)出發(fā),能訪問(wèn)到它前面的結(jié)點(diǎn)嗎?不能,只能訪問(wèn)到它后面的結(jié)點(diǎn)。對(duì)單鏈表來(lái)說(shuō),只有從頭結(jié)點(diǎn)開(kāi)始才能掃描表中全部結(jié)點(diǎn).作業(yè)68頁(yè)4-14.2.3循環(huán)鏈表
1.循環(huán)鏈表的定義和結(jié)構(gòu)
循環(huán)鏈表的定義:在單鏈表中,使其表尾結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn),這樣的鏈表叫循環(huán)鏈表。循環(huán)鏈表演示
xnx1…L單鏈表表頭結(jié)點(diǎn):第一個(gè)節(jié)點(diǎn)循環(huán)鏈表表頭結(jié)點(diǎn):哨位節(jié)點(diǎn)
●注意:判斷表尾的條件:?jiǎn)捂湵恚簆
next==NULL循環(huán)鏈表:p
next==header
xnx1…pheader
判斷空表的的條件:
單鏈表:head==NULL
循環(huán)鏈表:header
next==header
header
2.循環(huán)鏈表結(jié)點(diǎn)類CNode的定義聲明
template<classT>classCNode
{private:
CNode<T>*next;public:Tdata;
CNode(void);//生成哨位結(jié)點(diǎn)
CNode(constT&item):data(item),next(this){}voidInsertAfter(CNode<T>*p);CNode<T>*DeleteAfter(void);CNode<T>*NextNode(void)const;};s,s.InsertAfter(…),…實(shí)現(xiàn)
//刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)
ADL描述:算法DeleteAfter(this.tempptr)DA1[鏈表為空?]IFnext(this)=thisTHEN
tempptr
NULL
DeleteAfter函數(shù)的演示
ELSE(IFnext(this)=headerTHEN (tempptrnext(header). next(header)next(tempptr).) ELSE (tempptr
next(this).
next(this)
next(tempptr).))▌xnx1…h(huán)eaderthisx1headerthis4.2.4雙向循環(huán)鏈表
1.問(wèn)題的提出在循環(huán)鏈表中訪問(wèn)當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)tempptrnext(p).WHILEnext(tempptr)≠pDOtempptrnext(tempptr).xnx1…h(huán)eaderp2雙向循環(huán)鏈表的結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):
鏈表的結(jié)構(gòu):
。。。L★★leftdataright
headerleft==headerright==header
prightleft=pleftright=p
雙向循環(huán)鏈表判空的條件:★雙鏈表的對(duì)稱性:★header
3循環(huán)雙鏈表結(jié)點(diǎn)類DNode定義聲明
template<classT>classDNode{private:
DNode<T>*left;
DNode<T>*right;
public:Tdata;
DNode(void);//生成哨位節(jié)點(diǎn)
DNode(constT&item);voidInsertRight(DNode<T>*p);voidInsertLeft(DNode<T>*p);DNode<T>*
DeleteNode(void);DNode<T>*NextNodeLeft(void)const;DNode<T>*NextNodeRight(void)const;};實(shí)現(xiàn)①
構(gòu)造函數(shù)
tamplate<classT>Node<T>::DNode(constT&item):
data(item),left(this),right(this){}
thisitem
在當(dāng)前結(jié)點(diǎn)(this)之后插入結(jié)點(diǎn)p
left(right(this))
P.right(P)
right(this).
left(P)
this.
right(this)
Pp4321this×②
在當(dāng)前結(jié)點(diǎn)(this)之后插入結(jié)點(diǎn)p算法InsertRight(this,P)//在當(dāng)前結(jié)點(diǎn)Node(this)的右邊插入結(jié)點(diǎn)Node(P)IR1[令當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)的左指針指向Node(P)]left(right(this))
P.IR2[令Node(P)的右指針指向當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)]right(P)
right(this).IR3[令Node(P)的左指針指向當(dāng)前結(jié)點(diǎn)]left(P)
this.IR4[令當(dāng)前結(jié)點(diǎn)的右指針指向Node(P)]right(this)
P▌?dòng)也迦胙菔劲趐2134×在當(dāng)前
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- GB/T 45299-2025干蒔蘿
- 灌溉系統(tǒng)的運(yùn)行與維護(hù)試題及答案
- 婦幼保健員考試課本知識(shí)試題及答案
- 個(gè)人與社會(huì)健康的試題及答案
- 人力資源管理中的道德問(wèn)題試題及答案
- 2025股東股權(quán)協(xié)議:衛(wèi)星通信網(wǎng)絡(luò)建設(shè)與運(yùn)營(yíng)
- 二零二五年度民法典金融借款合同新能源產(chǎn)業(yè)貸款合同
- 2025年度電子商務(wù)企業(yè)員工正式入職運(yùn)營(yíng)合同
- 二零二五年度房地產(chǎn)租賃委托代理協(xié)議書(shū)范本與風(fēng)險(xiǎn)規(guī)避
- 智慧備考2024人力資源管理師試題及答案
- 沙袋土圍堰施工方案
- 灌漿技術(shù)在水利工程中的應(yīng)用
- 消毒隔離知識(shí)培訓(xùn)資料培訓(xùn)課件
- 《影子的形成》(課件)四年級(jí)下冊(cè)科學(xué)大象版
- GB/T 41953-2022色漆和清漆涂料中水分含量的測(cè)定氣相色譜法
- 國(guó)家中醫(yī)藥管理局第3批24個(gè)專業(yè)104個(gè)病種中醫(yī)診療方案
- LY/T 2697-2016馬尾松撫育經(jīng)營(yíng)技術(shù)規(guī)程
- GB/T 41811-2022魔芋凝膠食品質(zhì)量通則
- GB/T 32854.3-2020自動(dòng)化系統(tǒng)與集成制造系統(tǒng)先進(jìn)控制與優(yōu)化軟件集成第3部分:活動(dòng)模型和工作流
- 豪邁CutRite V9板材優(yōu)化軟件學(xué)習(xí)教材
- 建設(shè)工程合同糾紛-審判實(shí)務(wù)分析課件
評(píng)論
0/150
提交評(píng)論