理學(xué)第四章線性表_第1頁(yè)
理學(xué)第四章線性表_第2頁(yè)
理學(xué)第四章線性表_第3頁(yè)
理學(xué)第四章線性表_第4頁(yè)
理學(xué)第四章線性表_第5頁(yè)
已閱讀5頁(yè),還剩66頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論