理學(xué)第四章線性表

Chapter4線性表、堆棧和隊列

4.1線性表的定義和基本操作

4.2線性表的存儲結(jié)構(gòu)

4.3堆棧和隊列4.1線性表的定義和操作4.1.1線性表的定義

[例1]英文字母表（A,B,C,……,Z)

整數(shù)序列（1,78,9,12,10)[例2]某班學(xué)生健康情況登記表。學(xué)號姓名性別年齡健康情況

01張軍男18一般02陳紅女17良好

03陳軍男19良好

…

…

…

…

…線性表定義：一個線性表是由零個或多個具有相同類型的結(jié)點(diǎn)組成的有序集合。用（a0，a1，…，an-1）來表示一個線性表。當(dāng)n>0時，a0稱為表的始結(jié)點(diǎn)，an-1稱為表的終結(jié)點(diǎn)，當(dāng)n=0時，線性表中有零個結(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)前（或后）

插入一個新結(jié)點(diǎn)x（3）刪除：刪除下標(biāo)為k的結(jié)點(diǎn)。（4）查找：尋覓具有特定域值的結(jié)點(diǎn)。（5）歸并、分拆、復(fù)制、計數(shù)、排序。Chapter4

線性表、堆棧和隊列

4.1線性表的定義和基本操作

4.2線性表的存儲結(jié)構(gòu)

4.2.1順序存儲結(jié)構(gòu)

4.2.2鏈接存儲結(jié)構(gòu)－－單鏈表

4.2.3循環(huán)鏈表

4.2.4雙向循環(huán)鏈表

4.3堆棧和隊列

4.2線性表的存儲結(jié)構(gòu)線性表存儲結(jié)構(gòu)順序存儲非順序存儲——鏈表4.2.1順序存儲結(jié)構(gòu)

●順序存儲：用一組連續(xù)的存儲空間依次存儲線性表的元素。

●特點(diǎn)：其邏輯順序與物理順序相同。 實(shí)現(xiàn)順序存儲的最有效方法是使用一維數(shù)組。[例]：線性表（a0，a1

，a2,a3)。可以使用一個數(shù)組a[n]來存放此線性表。

圖4.1是包含4個結(jié)點(diǎn)的線性表A[4]在內(nèi)存中的表示，其中每個結(jié)點(diǎn)占2個連續(xù)的字節(jié)，第一個結(jié)點(diǎn)A[0]的首地址為302

圖4.1線性表的順序存儲線性表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)：其邏輯順序與物理順序相同。順序存儲，隨機(jī)存取

線性表上實(shí)現(xiàn)的基本運(yùn)算

1、插入

[例]在線性表（12,13,21,24,28,30,42,77） 中下標(biāo)為3的結(jié)點(diǎn)后，插入元素

25。問題：此時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？位置關(guān)系發(fā)生變化長度增1

序號元素230416751213212428304277插入25序號元素230416751213252124283042778在下標(biāo)為k的結(jié)點(diǎn)后插入一個新結(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.).▌時間復(fù)雜性分析插入操作的基本運(yùn)算是：

元素移動Dn中有多少種可能的輸入呢？

n+1種（n+1個位置可以發(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的元素。問題：此時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

位置關(guān)系發(fā)生變化長度減1序號元素230416751213212428304277刪除24序號元素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.)▌

時間復(fù)雜性分析刪除操作的基本運(yùn)算是：元素移動

Dn中有多少種可能的輸入呢？

n種（n個位置可以發(fā)生刪除）設(shè)每種輸入發(fā)生的頻率相等：1/n

則期望復(fù)雜性為：

E(n)=(n-1)/n+……+1/n+0/n=（n-1）/2

●結(jié)論：

優(yōu)點(diǎn)：線性表的順序存儲結(jié)構(gòu)簡單、易于實(shí)現(xiàn)，數(shù)據(jù)的存取操作采用隨機(jī)存取，可以隨機(jī)訪問表中任一元素。

缺點(diǎn)：線性表的容量不容易擴(kuò)充，不利于數(shù)據(jù)的合并與分離；插入、刪除操作需要移動大量元素。問題：由于線性表中元素的數(shù)目可以改變，定義數(shù)組時要做如何的考慮呢？

定義足夠大的數(shù)組

4.2.2鏈接存儲結(jié)構(gòu)

————單鏈表

1、單鏈表的定義

●鏈?zhǔn)酱鎯Γ河靡唤M任意存儲單元存儲線性 表的數(shù)據(jù)元素。

單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：

鏈表的第一個結(jié)點(diǎn)被稱為頭結(jié)點(diǎn)，指向頭結(jié)點(diǎn)

的指針被稱為頭指針。鏈表的最后一個結(jié)點(diǎn)被

稱為尾結(jié)點(diǎn)。

●單鏈表的定義：每個結(jié)點(diǎn)只含有一個指針域的 鏈表叫單鏈表。datanext單鏈表的存儲映像●特點(diǎn)：邏輯順序與物理順序可以相同也可 以不同。

優(yōu)點(diǎn)：①插入、刪除操作方便。 ②數(shù)據(jù)的合并與分離容易。結(jié)點(diǎn)可以不連續(xù)存儲線性表可擴(kuò)充[例]將線性表（a3，a4，a5),以鏈表的形式存儲 在內(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用來保存結(jié)點(diǎn)信息的域

next用來存放后繼結(jié)點(diǎn)地址信息的域，即存放指

向后繼結(jié)點(diǎn)的指針

OperationsConstructorInitialvalue: 給出當(dāng)前結(jié)點(diǎn)的data域值和next域值

Process: 對data域和next域進(jìn)行初始化

NextNode:

Input: 無

Precondition: 無

Process: 取next域值

Output: 返回next域值

Postcondition: 無

InsertAfterInput: 指向被插入結(jié)點(diǎn)的指針

Precondition: 無

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: 無

Postcondition:當(dāng)前結(jié)點(diǎn)的next域存放新插入結(jié)點(diǎn)的地址

DeleteAfterInput: 無

Precondition:無

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)的下一個結(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)建一個data域值為item,next域值為 nextptr的結(jié)點(diǎn)。算法GetNode（item，nextptr.newNode）

GN1[為新結(jié)點(diǎn)申請空間]

newNode

AVAIL.GN2[為結(jié)點(diǎn)諸域賦值]

data（newNode）

item.next（newNode）

nextptr.▌itemNewNodenextptr

②在頭指針為head的鏈表中，插入一個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個元素?fù)Q行PL1[取表頭，計數(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

在鏈表類的定義中，有一個當(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)個數(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;

//插入一個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）{//為操作無誤，先令兩個表當(dāng)前指針指向

//各自表頭結(jié)點(diǎn)

L1.Reset（）; L2.Reset（）; while（!L2.EndOfList（））

{ L1.InsertRear（L2.Data（））;L2.Next（）; }}缺點(diǎn)：（1）單鏈表雖然克服了順序存儲的缺點(diǎn)，但卻不能進(jìn)行隨機(jī)訪問，數(shù)據(jù)存取只能采用順序存取方式。（2）內(nèi)存空間占用較多。問題：從單鏈表中某一個結(jié)點(diǎn)出發(fā)，能訪問到它前面的結(jié)點(diǎn)嗎？不能，只能訪問到它后面的結(jié)點(diǎn)。對單鏈表來說，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn).作業(yè)68頁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)：第一個節(jié)點(diǎn)循環(huán)鏈表表頭結(jié)點(diǎn)：哨位節(jié)點(diǎn)

●注意：判斷表尾的條件：單鏈表：p

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.問題的提出在循環(huá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)鏈表判空的條件：★雙鏈表的對稱性：★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▌右插入演示②p2134×在當(dāng)前