數(shù)據(jù)結(jié)構(gòu) C++版 教學(xué)課件 楊秀金 第3章 棧和隊列3-大學(xué)課件-

第3數(shù)章?lián)＝Y(jié)和構(gòu)隊列1第3講本章分為（3）講第1講棧棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)棧的鏈表存儲結(jié)構(gòu)及實(shí)現(xiàn)棧的應(yīng)用 3.4.1表達(dá)式計算第2講子程序的嵌套調(diào)用遞歸調(diào)用3.5

隊

列隊列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)第3講隊列的鏈表存儲結(jié)構(gòu)及實(shí)現(xiàn)隊列的應(yīng)用供教師參考23.7隊列的鏈表存儲結(jié)構(gòu)及實(shí)現(xiàn)隊列也可采用鏈表存儲結(jié)構(gòu)。用鏈表表示的隊列簡稱為鏈隊列,如圖所示。一個鏈隊列需兩個指針才能唯一確定,分別稱為頭指針front和尾指針rear。為操作方便使用附加頭結(jié)點(diǎn),并令頭指針指向front附加頭結(jié)點(diǎn),正好指向隊列第一個數(shù)據(jù)結(jié)點(diǎn)的前一位置。尾指針rear指向隊尾數(shù)據(jù)結(jié)點(diǎn)。33.7.1隊列的鏈表存儲結(jié)構(gòu)圖(a)空鏈隊列，滿足條件:front==rear圖(b)進(jìn)隊元素x,僅有一個數(shù)據(jù)元素。圖(c)再進(jìn)隊元素y。圖(d)出隊一個元素的情況。除去空隊情況外，頭指針front總是指向隊頭元素結(jié)點(diǎn)前一位置，隊尾指針rear總是指向隊尾元素結(jié)點(diǎn)自身。4struct

quenode{

ElemType

data;quenode

*next;};quenode

*front,

*rear;5//數(shù)據(jù)元素類型//結(jié)點(diǎn)指針域front和rear分別為隊列的頭指針和尾指針。鏈表隊列的結(jié)點(diǎn)結(jié)構(gòu)為:3.7.2 鏈表隊列類定義隊列采用鏈表存儲結(jié)構(gòu)時,需要兩個指針才能唯一確定,它們分別為頭指針和尾指針。同時,把頭、尾指針作為類的私有成員來處理。鏈隊列的各種操作設(shè)計為類的函數(shù)成員。6class

LsQueue7{

private://頭、尾指針quenode *front,

*rear;public:LsQueue();~LsQueue();int

IsEmpty()void

Display();void

AddQ(ElemType

x);ElemType

DelQ();ElemType

GetFront()};1.鏈表隊列類定義LsQueue::LsQueue(){

quenode

*p;p=new

quenode;p->next=NULL;front=rear=p;}//構(gòu)造函數(shù),初始化空隊int

LsQueue::IsEmpty()

//判隊列是否為空{(diào) if(front==rear)

return

1;

else return

0;}鏈表隊列類的幾個函數(shù)8ElemTypeLsQueue::GetFront()//取隊首元素不出隊{ ElemTypex;quenode*p;if(front==rear){cout<<"\n QueuIsEmpty!"<<endl;x=-1; }else{p=front->next;x=p->data;}returnx;}這里沒有給出析構(gòu)函數(shù)和輸出函數(shù)的實(shí)現(xiàn),請讀者自己思考寫出。鏈表隊列類的幾個函數(shù)9rear->next=s;rear=s;}102.進(jìn)隊操作-算法3.9進(jìn)隊操作在隊尾處進(jìn)行。新數(shù)據(jù)結(jié)點(diǎn)s插在隊尾結(jié)點(diǎn)后，將尾指針rear移至新隊尾結(jié)點(diǎn)s上。voidLsQueue::AddQ(ElemTypex) //x結(jié)點(diǎn)入隊{ quenode*s;s=newquenode;s->data=x;s->next=NULL;//很重要由于是鏈表結(jié)構(gòu),在插入時不用判斷隊列是否為滿。ElemType

LsQueue::DelQ(){

ElemType

x;

quenode

*p;if

(

front==rear)//出隊一個元素{cout<<"\n

隊列為空。"<<endl;

x=-1;}else

{

p=front->next; //p指向第一個數(shù)據(jù)結(jié)點(diǎn)delete

p;}return

x;}3.出隊操作-算法3.10a

∧frontfront->next=p->next;if(p->next==NULL)rear=front;//防止尾指針丟失x=p->data;prear

∧frontrear出隊前后11通過鏈表隊列對象Q調(diào)用進(jìn)隊、出隊和輸出函數(shù)。12int

main(){

ElemType

e;

int

j;LsQueue

Q;cout<<"\n隊列鏈?zhǔn)酱鎯Y(jié)構(gòu)演示";cout<<"進(jìn)隊data=?";cin>>e;Q.AddQ(e);Q.Display();e=Q.DelQ();Q.Display();return

0;}3.8隊列的應(yīng)用13隊列有著廣泛的應(yīng)用。本節(jié)通過“報數(shù)問題”的求解介紹隊列在程序設(shè)計中的應(yīng)用。所謂報數(shù)問題，設(shè)有n個人站成一排，從左到右的編號分別為1～n，從左到右報數(shù)“1，2，3，1，2，3”數(shù)到“1”和“2”的人出列，數(shù)到“3”的人立即站到隊伍的最右端。報數(shù)過程反復(fù)進(jìn)行，直到n個人都出列為止。要求輸出數(shù)據(jù)出列的順序。例如，當(dāng)n=10時，初始序列為1 2 3 45 6 7 8 9 10則出列順序為:2 4 5 7 8 10 3 6 9算法思想14先將n個人的編號進(jìn)隊，然后反復(fù)執(zhí)行如下操作:出隊一個元素，輸出其編號；再出隊一個元素，輸出其編號；若隊列不空，則出隊一個元素，然后將該元素再進(jìn)隊，直到隊列為空。本算法采用鏈表隊列類LsQueueQ，假設(shè)ElemType代表整型，算法如下:void

number(int

n)15{

int

i;

ElemType

e;

LiQueue

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

Q.AddQ(i);報數(shù)問題的算法//構(gòu)建初始序列cout<<"\n 報數(shù)出列順序:"；while(!Q.IsEmpty()){e=Q.delQ();cout<<""<<e;e=Q.delQ();cout<<""<<e;if(!Q.IsEmpty()){e=Q.delQ();//出列一個元素且輸出//再出列一個元素且輸出//出列一個元素Q.AddQ(e); //將該元素進(jìn)隊,排在隊尾}}//while}小

結(jié)16棧是操作受限的線性表,插入和刪除操作只能在表一端進(jìn)行。棧是一個后進(jìn)先出（LastInFirstOut,LIFO）的線性表。棧的順序存儲結(jié)構(gòu)稱為順序棧,本質(zhì)上是順序表的簡化。通常把數(shù)組中下標(biāo)為0的一端作為棧底,同時設(shè)指針top指示棧頂元素的位置。順序棧基本操作的算法的時間復(fù)雜度均為O(1)。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧,鏈棧的插入和刪除操作僅在棧頂進(jìn)行,其時間復(fù)雜度均為O(1)。小

結(jié)17隊列也是操作受限的線性表。限定在隊尾處插入，而在隊頭處刪除。隊列是先進(jìn)先出（FirstInFirstOout，F(xiàn)IFO）的線性表。約定隊列的頭指針front指向隊列頭元素前一位置，而為指針rear指向隊尾元素自身。循環(huán)隊列是重要數(shù)據(jù)結(jié)構(gòu)，即指隊列的順序存儲結(jié)構(gòu)。凡涉及隊頭或隊尾指針的修改都要對MAXSIZE求模:front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;循環(huán)隊列，隊空的判定條件:rear==front循環(huán)隊列，隊滿的的判定條件是:(rear+1)%MAXSIZE==front小

結(jié)18隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列。通常設(shè)附加頭結(jié)點(diǎn)，并設(shè)隊頭指針指向頭結(jié)點(diǎn)，即指向第一個數(shù)據(jù)結(jié)點(diǎn)的前一位置。隊列的尾指針指向終端結(jié)點(diǎn)。鏈隊列的基本操作，也是單鏈表操作的簡化，插入只考慮在鏈隊列的尾部進(jìn)行，刪除只考慮在鏈隊列的頭部進(jìn)行，其時間復(fù)雜度均為O(1)。鏈隊列，隊空的判定條件:rear==front鏈隊列一般不作隊滿的的判。本章的重點(diǎn)是棧和隊列的基本概念，以及在不同存儲結(jié)構(gòu)前提下的進(jìn)棧、出棧、進(jìn)隊、出隊算法。寫給任課教師19為了逐步培養(yǎng)在實(shí)際中應(yīng)用棧和隊列的能力。結(jié)合布置的上機(jī)作業(yè),因C++實(shí)驗存在一定難度,教師在實(shí)驗室也要有實(shí)驗課件,適當(dāng)講解,對學(xué)生加以指導(dǎo)和引導(dǎo)。結(jié)合將要布置的課后書寫作業(yè),教師在講課過程中要增加與作業(yè)相關(guān)的引導(dǎo)示范內(nèi)容。后面（下一片）的“對比復(fù)習(xí)”內(nèi)容,僅供教師參考,僅有標(biāo)題?？刹徊杉{,也可根據(jù)自己理解完成。棧和隊列與線性表對比復(fù)習(xí)20一、存儲結(jié)構(gòu)的復(fù)習(xí)二、類設(shè)計的復(fù)習(xí)三、重要算法的前提條件一、存儲結(jié)構(gòu)的復(fù)習(xí)21順序結(jié)構(gòu)類的私有數(shù)據(jù)成員:ElemType

elem[MAXSIZE];//三者相同int

length;int

top

;//線性表長,用于順序表//棧頂指針,用于順序棧intfront,rear;//隊頭、隊尾指針，用于循環(huán)隊列鏈表結(jié)構(gòu)類的私有數(shù)據(jù)成員:Head;top;//