數(shù)據(jù)結(jié)構(gòu)習(xí)題解析第4章

PAGEPAGE91第4章棧和隊列一、復(fù)習(xí)要點本章主要討論3種線性結(jié)構(gòu)：棧、隊列與優(yōu)先級隊列。這3種結(jié)構(gòu)都是順序存取的表，而且都是限制存取點的表。棧限定只能在表的一端（棧頂）插入與刪除，其特點是先進(jìn)后出。隊列和優(yōu)先級隊列限定只能在表的一端（隊尾）插入在另一端（隊頭）刪除，不過優(yōu)先級隊列在插入和刪除時需要根據(jù)數(shù)據(jù)對象的優(yōu)先級做適當(dāng)?shù)恼{(diào)整，令優(yōu)先級最高的對象調(diào)整到隊頭，其特點是優(yōu)先級高的先出。而隊列不調(diào)整，其特點是先進(jìn)先出。這幾種結(jié)構(gòu)在開發(fā)各種軟件時非常有用。本章復(fù)習(xí)的要點：1、基本知識點要求理解棧的定義和特點，棧的抽象數(shù)據(jù)類型和在遞歸和表達(dá)式計算中的使用，在棧式鐵路調(diào)車線上當(dāng)進(jìn)棧序列為1,2,3,,n時，可能的出棧序列計數(shù)，棧的順序存儲表示和鏈接存儲表示，特別要注意，鏈?zhǔn)綏５臈ｍ攽?yīng)在鏈頭，插入與刪除都在鏈頭進(jìn)行。另外，需要理解隊列的定義和特點，隊列的抽象數(shù)據(jù)類型和在分層處理中的使用，隊列的順序存儲表示（循環(huán)隊列）和鏈接存儲表示，需要注意的是，鏈?zhǔn)疥犃械年狀^應(yīng)在鏈頭，隊尾應(yīng)在鏈尾。還需要理解優(yōu)先級隊列的定義和特點。優(yōu)先級隊列的最佳存儲表示是堆（heap），本章介紹的表示看懂即可。2、算法設(shè)計 棧的5種操作（進(jìn)棧、退棧、取棧頂元素、判?？铡⒅每諚＃┑脑陧樞虼鎯Ρ硎鞠碌膶崿F(xiàn)，以及在鏈接存儲表示下的實現(xiàn)。 使用棧的后綴表達(dá)式計算算法 雙棧共用一個數(shù)組的進(jìn)棧、退棧、置空棧、判棧空算法及棧滿、?？諚l件 使用兩個棧模擬一個隊列時的進(jìn)隊列和出隊列算法 循環(huán)隊列的進(jìn)隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn) 使用tag區(qū)分隊列空和隊列滿的循環(huán)隊列的進(jìn)隊列和出隊列操作的實現(xiàn) 鏈?zhǔn)疥犃械倪M(jìn)隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn) 使用隊尾指針rear和隊列長度length的鏈?zhǔn)疥犃械倪M(jìn)隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn) 隊列在分層處理中的使用事例（楊輝三角形按層次打印） 雙端隊列的順序存儲表示及其進(jìn)隊列、出隊列算法及隊空、隊滿條件二、難點和重點1、棧：棧的特性、棧的基本運算 棧的數(shù)組實現(xiàn)、棧的鏈表實現(xiàn) 棧滿及?？諚l件、抽象數(shù)據(jù)類型中的先決條件與后置條件 2、棧的應(yīng)用：用后綴表示計算表達(dá)式，中綴表示改后綴表示 3、隊列：隊列的特性、隊列的基本運算 隊列的數(shù)組實現(xiàn)：循環(huán)隊列中隊頭與隊尾指針的表示，隊滿及隊空條件 隊列的鏈表實現(xiàn)：鏈?zhǔn)疥犃兄械年狀^與隊尾指針的表示、4、雙向隊列：雙向隊列的插入與刪除算法5、優(yōu)先級隊列：優(yōu)先級隊列的插入與刪除算法三、教材中習(xí)題的解析4-1改寫順序棧的進(jìn)棧成員函數(shù)Push(x)，要求當(dāng)棧滿時執(zhí)行一個stackFull()操作進(jìn)行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置?！窘獯稹縯emplate<classType>voidstack<Type>::push(constType&item){ if(isFull())stackFull(); //棧滿，做溢出處理elements[++top]=item; //進(jìn)棧 } template<classType>voidstack<Type>::stackFull(){ Type*temp=newType[3*maxSize]; //創(chuàng)建體積大二倍的數(shù)組 for(inti=0;i<=top;i++)temp[i]=elements[i]; //傳送原數(shù)組的數(shù)據(jù) delete[]elements; //刪去原數(shù)組 maxSize*=3; //數(shù)組最大體積增長二倍 elements=temp; //新數(shù)組成為棧的數(shù)組空間 }4-2鐵路進(jìn)行列車調(diào)度時,常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，如右圖所示。試問： (1)設(shè)有編號為1,2,3,4,5,6的六輛列車,順序開入棧式結(jié)構(gòu)的站臺,則可能的出棧序列有多少種? (2)若進(jìn)站的六輛列車順序如上所述,那么是否能夠得到435612,325641,154623和135426的出站序列,如果不能,說明為什么不能;如果能,說明如何得到(即寫出"進(jìn)棧"或"出棧"的序列)?！窘獯稹?(1)可能的不同出棧序列有種。 (2)不能得到435612和154623這樣的出棧序列。因為若在4,3,5,6之后再將1,2出棧，則1,2必須一直在棧中，此時1先進(jìn)棧，2后進(jìn)棧，2應(yīng)壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。356224444111111113323232532532563256432564153441222261113135135413542135421354264-3試證明：若借助?？捎奢斎胄蛄?,2,3,…,n得到一個輸出序列p1,p2,p3,…,pn(它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i<j<k，使得pj<pk<pi。(提示：用反證法)【解答】 充分性：由j<k，pj<pk，則pj必須在pk入棧之前就出棧；而i<j，pj<pi，則意味著pi必須先于pj進(jìn)棧且pj必須先于pi出棧；此外，i<k，則表明pk必須在pi之后出棧，這與pj<pk<pi相矛盾（因為這意味著pj必須在pk之前和pi之后離開，但pi又出現(xiàn)在pk之后）。下面詳細(xì)解釋一下。借助棧由輸入序列1,2,3,…,n，可得到輸出序列p1,p2,p3,…,pn，如果存在下標(biāo)i,j,k，滿足i<j<k，那么在輸出序列中，可能出現(xiàn)如下5種情況：①i進(jìn)棧，i出棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧。此時具有最小值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最大值的排在pk位置，有pi<pj<pk,不可能出現(xiàn)pj<pk<pi的情形；②i進(jìn)棧，i出棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧。此時具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中間值的排在最后pk位置，有pi<pk<pj,不可能出現(xiàn)pj<pk<pi的情形；③i進(jìn)棧，j進(jìn)棧，j出棧，i出棧，k進(jìn)棧，k出棧。此時具有中間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj<pi<pk,不可能出現(xiàn)pj<pk<pi的情形；④i進(jìn)棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧，i出棧。此時具有中間值的排在最前面pi位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk<pi<pj,也不可能出現(xiàn)pj<pk<pi的情形；⑤i進(jìn)棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧，i出棧。此時具有最大值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最小值的排在pk位置，有pk<pj<pi,也不可能出現(xiàn)pj<pk<pi的情形；4-4將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。當(dāng)向第0號棧插入一個新元素時，使top[0]增1得到新的棧頂位置，當(dāng)向第1號棧插入一個新元素時，使top[1]減1得到新的棧頂位置。當(dāng)top[0]+1==top[1]時或top[0]==top[1]-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(DoubleStack)結(jié)構(gòu)的類定義，并實現(xiàn)判?？铡⑴袟M、插入、刪除算法。0m-0m-1bot[0]top[0]top[1]bot[1] 雙棧的類定義如下： #include<assert.h> template<classType>classDblStack{ //雙棧的類定義 private: inttop[2],bot[2]; //雙棧的棧頂指針和棧底指針 Type*elements; //棧數(shù)組 intm; //棧最大可容納元素個數(shù) public: DblStack(intsz=10); //初始化雙棧,總體積m的默認(rèn)值為10 ~DblStack(){delete[]elements;} //析構(gòu)函數(shù) voidDblPush(constType&x,inti); //把x插入到棧i的棧頂 intDblPop(inti); //退掉位于棧i棧頂?shù)脑? Type*DblGetTop(inti); //返回棧i棧頂元素的值 intIsEmpty(inti)const{returntop[i]==bot[i];} //判棧i空否,空返回1,否則返回0 intIsFull()const{returntop[0]+1==top[1];} //判棧滿否,滿則返回1,否則返回0 voidMakeEmpty(inti); //清空棧i的內(nèi)容 } template<classType>DblStack<Type>::DblStack(intsz):m(sz),top[0](-1),bot[0](-1),top[1](sz),bot[1](sz){ //建立一個最大尺寸為sz的空棧,若分配不成功則錯誤處理。 elements=newType[m]; //創(chuàng)建棧的數(shù)組空間 assert(elements!=NULL); //斷言:動態(tài)存儲分配成功與否 } template<classType>voidDblStack<Type>::DblPush(constType&x,inti){ //如果IsFull()，則報錯；否則把x插入到棧i的棧頂 assert(!IsFull()); //斷言:棧滿則出錯處理，停止執(zhí)行 if(i==0)elements[++top[0]]=x; //棧0情形：棧頂指針先加1,然后按此地址進(jìn)棧 elseelements[--top[1]]=x; //棧1情形：棧頂指針先減1,然后按此地址進(jìn)棧} template<classType>intDblStack<Type>::DblPop(inti){ //如果IsEmpty(i)，則不執(zhí)行退棧，返回0；否則退掉位于棧i棧頂?shù)脑兀祷? if(IsEmpty(i))return0; //判?？辗?若棧空則函數(shù)返回0 if(i==0)top[0]--; //棧0情形：棧頂指針減1elsetop[1]++; //棧1情形：棧頂指針加1 return1;} template<classType>Type*DblStack<Type>::DblGetTop(inti){ //若棧不空則函數(shù)返回該棧棧頂元素的地址。 if(IsEmpty(inti))returnNULL; //判棧i空否,若?？談t函數(shù)返回空指針 return&elements[top[i]]; //返回棧頂元素的值 } template<classType>voidMakeEmpty(inti){if(i==0)top[0]=bot[0]=-1;elsetop[1]=bot[1]=m;}4-5寫出下列中綴表達(dá)式的后綴形式： (1)A*B*C (2)-A+B-C+D (3)A*-B+C (4)(A+B)*D+E/(F+A*D)+C (5)A&&B||!(E>F) /*注：按C++的優(yōu)先級*/ (6)!(A&&!((B<C)||(C>D)))||(C<E)【解答】 (1)AB*C* (2)A-B+C-D+ (3)AB-*C+ (4)AB+D*EFAD*+/+C+ (5)AB&&EF>!|| (6)ABC<CD>||!&&!CE<||4-6根據(jù)課文中給出的優(yōu)先級，回答以下問題： (1)在函數(shù)postfix中，如果表達(dá)式e含有n個運算符和分界符，問棧中最多可存入多少個元素？ (2)如果表達(dá)式e含有n個運算符，且括號嵌套的最大深度為6層，問棧中最多可存入多少個元素？【解答】(1)在函數(shù)postfix中，如果表達(dá)式e含有n個運算符和分界符，則可能的運算對象有n+1個。因此在利用后綴表達(dá)式求值時所用到的運算對象棧中最多可存入n+1個元素。(2)同上。4-7設(shè)表達(dá)式的中綴表示為a*x-b/x↑2，試?yán)脳⑺臑楹缶Y表示ax*bx2↑/-。寫出轉(zhuǎn)換過程中棧的變化。【解答】若設(shè)當(dāng)前掃描到的運算符ch的優(yōu)先級為icp(ch)，該運算符進(jìn)棧后的優(yōu)先級為isp(ch)，則可規(guī)定各個算術(shù)運算符的優(yōu)先級如下表所示。運算符;(^*,/,%+,-)isp017538icp086421 isp也叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)，icp也叫做棧外(incomingpriority)優(yōu)先數(shù)。當(dāng)剛掃描到的運算符ch的icp(ch)大于isp(stack)時，則ch進(jìn)棧；當(dāng)剛掃描到的運算符ch的icp(ch)小于isp(stack)時，則位于棧頂?shù)倪\算符退棧并輸出。從表中可知，icp(“(”)最高，但當(dāng)“(”進(jìn)棧后，isp(“(”)變得極低。其它運算符進(jìn)入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級的運算符自左向右計算的要求。運算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對“)”或棧底的“;”號與輸入流最后的“;”號配對時。前者將連續(xù)退出位于棧頂?shù)倪\算符，直到遇到“(”為止。然后將“(”退棧以對消括號，后者將結(jié)束算法。步序掃描項項類型動作棧的變化輸出0';'進(jìn)棧,讀下一符號;1a操作數(shù)直接輸出,讀下一符號;A2*操作符isp(';')<icp('*'),進(jìn)棧,讀下一符號;*A3x操作數(shù)直接輸出,讀下一符號;*ax4-操作符isp('*')>icp('-'),退棧輸出;ax*isp(';')<icp('-'),進(jìn)棧,讀下一符號;-ax*5b操作數(shù)直接輸出,讀下一符號;-ax*b6/操作符isp('-')<icp('/'),進(jìn)棧,讀下一符號;-/ax*b7x操作數(shù)直接輸出,讀下一符號;-/ax*bx8↑操作符isp('/')<icp('↑'),進(jìn)棧,讀下一符號;-/↑ax*bx92操作數(shù)直接輸出,讀下一符號;-/↑ax*bx210;操作符isp('↑')>icp(';'),退棧輸出;-/ax*bx2↑isp('/')>icp(';'),退棧輸出;-ax*bx2↑/isp('-')>icp(';'),退棧輸出;ax*bx2↑/-結(jié)束4-8試?yán)眠\算符優(yōu)先數(shù)法，畫出對如下中綴算術(shù)表達(dá)式求值時運算符棧和運算對象棧的變化。 a+b*(c-d)-e↑f/g【解答】 設(shè)在表達(dá)式計算時各運算符的優(yōu)先規(guī)則如上一題所示。因為直接對中綴算術(shù)表達(dá)式求值時必須使用兩個棧，分別對運算符和運算對象進(jìn)行處理，假設(shè)命名運算符棧為OPTR(operator的縮寫)，運算對象棧為OPND(operand的縮寫)，下面給出對中綴表達(dá)式求值的一般規(guī)則：(1)建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個“;”(2)從頭掃描中綴表達(dá)式，取一字符送入ch。(3)當(dāng)ch不等于“;”時，執(zhí)行以下工作，否則結(jié)束算法。此時在OPND棧的棧頂?shù)玫竭\算結(jié)果。①如果ch是運算對象，進(jìn)OPND棧，從中綴表達(dá)式取下一字符送入ch；②如果ch是運算符，比較ch的優(yōu)先級icp(ch)和OPTR棧頂運算符isp(OPTR)的優(yōu)先級：若icp(ch)>isp(OPTR)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一字符送入ch；若icp(ch)<isp(OPTR)，則從OPND棧退出一個運算符作為第2操作數(shù)a2，再退出一個運算符作為第1操作數(shù)a1，從OPTR棧退出一個運算符θ形成運算指令(a1)θ(a2)，執(zhí)行結(jié)果進(jìn)OPND棧；若icp(ch)==isp(OPTR)且ch==“)”，則從OPTR棧退出棧頂?shù)摹?”，對消括號，然后從中綴表達(dá)式取下一字符送入ch；根據(jù)以上規(guī)則，給出計算a+b*(c-d)-e↑f/g時兩個棧的變化。步序掃描項項類型動作OPND棧OPTR棧0OPTR棧與OPND棧初始化,‘;’進(jìn)OPTR棧,取第一個符號;1a操作數(shù)a進(jìn)OPND棧,取下一符號a;2+操作符icp(‘+’)>isp(‘;’),進(jìn)OPTR棧,取下一符號a;+3b操作數(shù)b進(jìn)OPND棧,取下一符號ab;+4*操作符icp(‘*’)>isp(‘+’),進(jìn)OPTR棧,取下一符號ab;+*5(操作符icp(‘(’)>isp(‘*’),進(jìn)OPTR棧,取下一符號ab;+*(6c操作數(shù)c進(jìn)OPND棧,取下一符號abc;+*(7-操作符icp(‘-’)>isp(‘(’),進(jìn)OPTR棧,取下一符號ab;+*(-8d操作數(shù)d進(jìn)OPND棧,取下一符號abcd;+*(-9)操作符icp(‘)’)<isp(‘-’),退OPND?！甦’,退OPND?！甤’,退OPTR?！?’,計算c–d→s1,結(jié)果進(jìn)OPND棧abs1;+*(10同上同上icp(‘)’)==isp(‘(’),退OPTR棧‘(’,對消括號,取下一符號abs1;+*11-操作符icp(‘-’)<isp(‘*’),退OPND?！畇1’,退OPND棧‘b’,退OPTR?！?’,計算b*s1→s2,結(jié)果進(jìn)OPND棧as2;+12同上同上icp(‘-’)<isp(‘+’),退OPND?！畇2’,退OPND棧‘a(chǎn)’,退OPTR?！?’,計算a*s2→s3,結(jié)果進(jìn)OPND棧s3;13同上同上icp(‘-’)>isp(‘;’),進(jìn)OPTR棧,取下一符號s3;-14e操作數(shù)e進(jìn)OPND棧,取下一符號s3e;-15↑操作符icp(‘↑’)>isp(‘-’),進(jìn)OPTR棧,取下一符號s3e;-↑16f操作數(shù)f進(jìn)OPND棧,取下一符號s3ef;-↑17/操作符icp(‘/’)<isp(‘↑’),退OPND棧‘f’,退OPND?！甧’,退OPTR?！?計算e↑f→s4,結(jié)果進(jìn)OPND棧s3s4;-18同上同上icp(‘/’)>isp(‘-’),進(jìn)OPTR棧,取下一符號s3s4;-/19g操作數(shù)g進(jìn)OPND棧,取下一符號s3s4g;-/20;操作符icp(‘;’)<isp(‘/’),退OPND?！甮’,退OPND?！畇4’,退OPTR?！?’,計算s4/g→s5,結(jié)果進(jìn)OPND棧s3s5;-21同上同上icp(‘;’)<isp(‘-’),退OPND棧‘s5’,退OPND?！畇3’,退OPTR?！?’,計算s3–s5→s6,結(jié)果進(jìn)OPND棧s6;22同上同上icp(‘;’)==isp(‘;’),退OPND?！畇6’,結(jié)束;4-9假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素,同時以rear和length分別指示循環(huán)隊列中的隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件,并寫出相應(yīng)的插入(enqueue)和刪除(dlqueue)元素的操作。【解答】循環(huán)隊列類定義#include<assert.h> template<classType>classQueue{ //循環(huán)隊列的類定義 public: Queue(int=10); ~Queue(){delete[]elements;} voidEnQueue(Type&item); TypeDeQueue(); TypeGetFront(); voidMakeEmpty(){length=0;} //置空隊列 intIsEmpty()const{returnlength==0;} //判隊列空否 intIsFull()const{returnlength==maxSize;} //判隊列滿否 private: intrear,length; //隊尾指針和隊列長度 Type*elements; //存放隊列元素的數(shù)組 intmaxSize; //隊列最大可容納元素個數(shù) } template<classType>Queue<Type>::Queue(intsz):rear(maxSize-1),length(0),maxSize(sz){ //構(gòu)造函數(shù)：建立一個最大具有maxSize個元素的空隊列。 elements=newType[maxSize]; //創(chuàng)建隊列空間 assert(elements!=0); //斷言:動態(tài)存儲分配成功與否 } template<classType>voidQueue<Type>::EnQueue(Type&item){ //插入函數(shù) assert(!IsFull()); //判隊列是否不滿，滿則出錯處理 length++; //長度加1 rear=(rear+1)%maxSize; //隊尾位置進(jìn)1 elements[rear]=item; //進(jìn)隊列 } template<classType>TypeQueue<Type>::DeQueue(){ //刪除函數(shù) assert(!IsEmpty()); //判斷隊列是否不空，空則出錯處理 length--; //隊列長度減1returnelements[(rear-length+maxSize)%maxSize]; //返回原隊頭元素值 } template<classType>TypeQueue<Type>::GetFront(){ //讀取隊頭元素值函數(shù) assert(!IsEmpty());returnelements[(rear-length+1+maxSize)%maxSize]; //返回隊頭元素值 }4-10假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素,同時設(shè)置一個標(biāo)志tag，以tag==0和tag==1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊列類定義#include<assert.h> template<classType>classQueue{ //循環(huán)隊列的類定義 public: Queue(int=10); ~Queue(){delete[]Q;} voidEnQueue(Type&item); TypeDeQueue(); TypeGetFront(); voidMakeEmpty(){front=rear=tag=0;} //置空隊列 intIsEmpty()const{returnfront==rear&&tag==0;} //判隊列空否 intIsFull()const{returnfront==rear&&tag==1;} //判隊列滿否 private: intrear,front,tag; //隊尾指針、隊頭指針和隊滿標(biāo)志 Type*Q; //存放隊列元素的數(shù)組 intm; //隊列最大可容納元素個數(shù) } template<classType>Queue<Type>::Queue(intsz):rear(0),front(0),tag(0),m(sz){ //構(gòu)造函數(shù)：建立一個最大具有m個元素的空隊列。 Q=newType[m]; //創(chuàng)建隊列空間 assert(Q!=0); //斷言:動態(tài)存儲分配成功與否 } template<classType>voidQueue<Type>::EnQueue(Type&item){ //插入函數(shù) assert(!IsFull()); //判隊列是否不滿，滿則出錯處理 rear=(rear+1)%m; //隊尾進(jìn)1,隊尾指針指示實際隊尾位置 Q[rear]=item; //進(jìn)隊列 tag=1; //標(biāo)志改1，表示隊列不空 } template<classType>TypeQueue<Type>::DeQueue(){ //刪除函數(shù) assert(!IsEmpty()); //判斷隊列是否不空，空則出錯處理 front=(front+1)%m; //隊頭進(jìn)1,隊頭指針指示實際隊頭的前一位置tag=0; //標(biāo)志改0,表示棧不滿returnQ[front]; //返回原隊頭元素的值 } template<classType>TypeQueue<Type>::GetFront(){ //讀取隊頭元素函數(shù) assert(!IsEmpty()); //判斷隊列是否不空，空則出錯處理returnQ[(front+1)%m]; //返回隊頭元素的值 }4-11若使用循環(huán)鏈表來表示隊列，p是鏈表中的一個指針。試基于此結(jié)構(gòu)給出隊列的插入(enqueue)和刪除(dequeue)算法，并給出p為何值時隊列空。【解答】 鏈?zhǔn)疥犃械念惗x template<classType>classQueue; //鏈?zhǔn)疥犃蓄惖那耙暥x template<classType>classQueueNode{ //鏈?zhǔn)疥犃薪Y(jié)點類定義 friendclassQueue<Type>; private:Typedata; //數(shù)據(jù)域QueueNode<Type>*link; //鏈域 public:QueueNode(Typed=0,QueueNode*l=NULL):data(d),link(l){} //構(gòu)造函數(shù) }; template<classType>classQueue{ //鏈?zhǔn)疥犃蓄惗x public:Queue():p(NULL){} //構(gòu)造函數(shù) ~Queue(); //析構(gòu)函數(shù) voidEnQueue(constType&item); //將item加入到隊列中 TypeDeQueue(); //刪除并返回隊頭元素 TypeGetFront(); //查看隊頭元素的值 voidMakeEmpty(); //置空隊列，實現(xiàn)與~Queue()相同 intIsEmpty()const{returnp==NULL;} //判隊列空否 private: QueueNode<Type>*p; //隊尾指針（在循環(huán)鏈表中） }; template<classType>Queue<Type>::~Queue(){ //隊列的析構(gòu)函數(shù)QueueNode<Type>*s; while(p!=NULL){s=p;p=p->link;deletes;} //逐個刪除隊列中的結(jié)點 } template<classType>voidQueue<Type>::EnQueue(constType&item){ //隊列的插入函數(shù) if(p==NULL){ //隊列空,新結(jié)點成為第一個結(jié)點p=newQueueNode<Type>(item,NULL);p->link=p; } else{ //隊列不空,新結(jié)點鏈入p之后QueueNode<Type>*s=newQueueNode<Type>(item,NULL);s->link=p->link;p=p->link=s; //結(jié)點p指向新的隊尾 } } 隊列的刪除函數(shù) template<classType>TypeQueue<Type>::DeQueue(){ //隊列的插入函數(shù) if(p==NULL){cout<<"隊列空,不能刪除！"<<endl;return0;} QueueNode<Type>*s=p; //隊頭結(jié)點為p后一個結(jié)點 p->link=s->link; //重新鏈接,將結(jié)點s從鏈中摘下 Typeretvalue=s->data;deletes; //保存原隊頭結(jié)點中的值,釋放原隊頭結(jié)點 returnretvalue; //返回數(shù)據(jù)存放地址 } 隊空條件p==NULL。 4-12若將一個雙端隊列順序表示在一維數(shù)組V[m]中，兩個端點設(shè)為end1和end2，并組織成一個循環(huán)隊列。試寫出雙端隊列所用指針end1和end2的初始化條件及隊空與隊滿條件，并編寫基于此結(jié)構(gòu)的相應(yīng)的插入(enqueue)新元素和刪除(dlqueue)算法?！窘獯稹縠nd1end2 初始化條件end1=end2=0end1end2 隊空條件end1=end2; 隊滿條件(end1+1)%m=end2;//設(shè)end1端順時針進(jìn)棧，end2端逆時針進(jìn)棧循環(huán)隊列類定義#include<assert.h> template<classType>classDoubleQueue{ //循環(huán)隊列的類定義 public: DoubleQueue(int=10); ~DoubleQueue(){delete[]V;} voidEnQueue(Type&item,constintend); TypeDeQueue(constintend); TypeGetFront(constintend); voidMakeEmpty(){end1=end2=0;} //置空隊列 intIsEmpty()const{returnend1==end2;} //判兩隊列空否 intIsFull()const{return(end1+1)%m==end2;} //判兩隊列滿否 private: intend1,end2; //隊列兩端的指針 Type*V; //存放隊列元素的數(shù)組 intm; //隊列最大可容納元素個數(shù) } template<classType>DoubleQueue<Type>::DoubleQueue(intsz):end1(0),end2(0),m(sz){ //構(gòu)造函數(shù)：建立一個最大具有m個元素的空隊列。 V=newType[m]; //創(chuàng)建隊列空間 assert(V!=0); //斷言:動態(tài)存儲分配成功與否 } template<classType>voidDoubleQueue<Type>::EnQueue(Type&item,constintend){ //插入函數(shù) assert(!IsFull()); if(end==1){ end1=(end1+1)%m; //end1端指針先進(jìn)1,再按指針進(jìn)棧 V[end1]=item; //end1指向?qū)嶋H隊頭位置 } else{ V[end2]=item; //end2端先進(jìn)隊列,指針再進(jìn)1 end2=(end2-1+m)%m; //end2指向?qū)嶋H隊頭的下一位置 }} template<classType>TypeDoubleQueue<Type>::DeQueue(constintend){//刪除函數(shù) assert(!IsEmpty()); Typetemp;if(end==1){ temp=V[end1]; //先保存原隊頭元素的值,end1端指針退1end1=(end1+m-1)%m; } else{ end2=(end2+1)%m; temp=V[end2]; //end2端指針先退1。再保存原隊頭元素的值 } returntemp; } template<classType>TypeDoubleQueue<Type>::GetFront(constintend){ //讀取隊頭元素的值 assert(!IsEmpty()); Type&temp;if(end==1)returnV[end1]; //返回隊頭元素的值 elsereturnV[(end2+1)%m]; }4-13設(shè)用鏈表表示一個雙端隊列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿的條件?！窘獯稹?鏈?zhǔn)诫p端隊列的類定義 template<classType>classDoubleQueue; //鏈?zhǔn)诫p端隊列類的前視定義 template<classType>classDoubleQueueNode{ //鏈?zhǔn)诫p端隊列結(jié)點類定義 friendclassDoubleQueue<Type>; private: Typedata; //數(shù)據(jù)域 DoubleQueueNode<Type>*link; //鏈域public:DoubleQueueNode(Typed=0,DoubleQueueNode*l=NULL):data(d),link(l){} //構(gòu)造函數(shù) }; template<classType>classDoubleQueue{ //鏈?zhǔn)诫p端隊列類定義 public: DoubleQueue(); //構(gòu)造函數(shù) ~DoubleQueue(); //析構(gòu)函數(shù) voidEnDoubleQueue1(constType&item); //從隊列end1端插入 voidEnDoubleQueue2(constType&item); //從隊列end2端插入 TypeDeDoubleQueue(); //刪除并返回隊頭end1元素 TypeGetFront(); //查看隊頭end1元素的值 voidMakeEmpty(); //置空隊列 intIsEmpty()const{returnend1==end1->link;} //判隊列空否 private: QueueNode<Type>*end1,*end2; //end1在鏈頭,可插可刪;end2在鏈尾,可插不可刪 }; template<classType>doubleQueue<Type>::doubleQueue(){//隊列的構(gòu)造函數(shù)end1=end2=newDoubleQueueNode<Type>(); //創(chuàng)建循環(huán)鏈表的表頭結(jié)點assert(!end1||!end2);end1->link=end1; } template<classType>Queue<Type>::~Queue(){ //隊列的析構(gòu)函數(shù) QueueNode<Type>*p; //逐個刪除隊列中的結(jié)點,包括表頭結(jié)點 while(end1!=NULL){p=end1;end1=end1->link;deletep;} } template<classType>voidDoubleQueue<Type>::EnDoubleQueue1(constType&item){//隊列的插入：從隊列end1端插入 if(end1==end1->link) //隊列空,新結(jié)點成為第一個結(jié)點end2=end1->link=newDoubleQueueNode<Type>(item,end1); else //隊列不空,新結(jié)點鏈入end1之后 end1->link=newDoubleQueueNode<Type>(item,end1->link); }template<classType>voidDoubleQueue<Type>::EnDoubleQueue2(constType&item){//隊列的插入：從隊列end2端插入 end2=end2->link=newDoubleQueueNode<Type>(item,end1); } template<classType>TypeDoubleQueue<Type>::DeDoubleQueue(){//隊列的刪除函數(shù) if(IsEmpty())return{cout<<"隊列空,不能刪除！"<<endl;return0;} DoubleQueueNode<Type>*p=end1->link; //被刪除結(jié)點 end1->link=p->link; //重新鏈接 Typeretvalue=p->data;deletep; //刪除end1后的結(jié)點p if(IsEmpty())end2=end1;returnretvalue;}template<classType>TypeDoubleQueue<Type>::GetFront(){//讀取隊列end1端元素的內(nèi)容 assert(!IsEmpty()); returnend1->link->data;} template<classType>voidQueue<Type>::MakeEmpty(){ //置空隊列 QueueNode<Type>*p; //逐個刪除隊列中的結(jié)點,包括表頭結(jié)點while(end1!=end1->link){p=end1;end1=end1->link;deletep;} }4-14試建立一個繼承結(jié)構(gòu)，以棧、隊列和優(yōu)先級隊列為派生類，建立它們的抽象基類——Bag類。寫出各個類的聲明。統(tǒng)一命名各派生類的插入操作為Add，刪除操作為Remove，存取操作為Get和Put，初始化操作為MakeEmpty，判空操作為Empty，判滿操作為Full，計數(shù)操作為Length。【解答】 Bag類的定義template<classType>classBag{public:Bag(intsz=DefaultSize); //構(gòu)造函數(shù) virtual~Bag(); //析構(gòu)函數(shù) virtualvoidAdd(constType&item); //插入函數(shù) virtualType*Remove(); //刪除函數(shù) virtualintIsEmpty(){returntop==-1;} //判空函數(shù) virtualintIsFull(){returntop==maxSize-1;} //判滿函數(shù)protecred: virtualvoidEmpty(){cout<<“DataStructureisempty.”<<endl;} virtualvoidFull(){cerr<<“DataStructureisfull.”<<endl;} Type*elements; //存儲數(shù)組 intmaxSize; //數(shù)組的大小 inttop; //數(shù)組當(dāng)前元素個數(shù)}; template<classType>Bag<Type>::Bag(intMaxBagSize):MaxSize(MaxBagSize){//Bag類的構(gòu)造函數(shù) elements=newType[MaxSize]; top=-1;} template<classType>Bag<Type>::~Bag(){//Bag類的析構(gòu)函數(shù)delete[]elements;} template<classType>voidBag<Type>::Add(constType&item){//Bag類的插入函數(shù) if(IsFull())Full(); elseelements[++top]=item; } template<classType>Type*Bag<Type>::Remove(){//Bag類的刪除函數(shù) if(IsEmpty()){Empty();returnNULL;} Type&x=elements[0]; //保存被刪除元素的值 for(inti=0;i<top;i++) //后面元素填補上來 elements[i]=elements[i+1]; top--; return&x;} 棧的類定義template<classType>classStack:publicBag{//棧的類定義（繼承Bag類）public: Stack(intsz=DefaultSize); //構(gòu)造函數(shù) ~Stack(); //析構(gòu)函數(shù) Type*Remove(); //刪除函數(shù)}; template<classType>Stack<Type>::Stack(intsz):Bag(sz){}//棧的構(gòu)造函數(shù)：將調(diào)用Bag的構(gòu)造函數(shù) template<classType>Stack<Type>::~Stack(){}//棧的析構(gòu)函數(shù)：將自動調(diào)用Bag的析構(gòu)函數(shù),以確保數(shù)組elements的釋放 template<classType>Type*Stack<Type>::Remove(){//棧的刪除函數(shù) if(IsEmpty()){Empty();returnNULL;} Typex=elements[top--]; return&x;} 隊列的類定義template<classType>classQueue:publicBag{//隊列的類定義（繼承Bag類）public: Queue(intsz=DefaultSize); //構(gòu)造函數(shù) ~Queue(); //析構(gòu)函數(shù)}; template<classType>Queue<Type>::Queue(intsz):Bag(sz){}//隊列的構(gòu)造函數(shù)：將調(diào)用Bag的構(gòu)造函數(shù) 優(yōu)先級隊列的類定義 template<classType>classPQueue:publicBag{ //優(yōu)先級隊列的類定義（繼承Bag類） public: PQueue(intsz=DefaultSize); //構(gòu)造函數(shù) ~PQueue(){} //析構(gòu)函數(shù) Type*PQRemove(); //刪除函數(shù) } template<classType>PQueue<Type>::PQueue(intsz):Bag(sz){} //優(yōu)先級隊列的構(gòu)造函數(shù)：建立一個最大具有sz個元素的空優(yōu)先級隊列。top=-1。 template<classType>Type*PQueue<Type>::Remove(){ //優(yōu)先級隊列的刪除函數(shù)：若隊列不空則函數(shù)返回該隊列具最大優(yōu)先權(quán)(值最小)元素的值,同時//將該元素刪除。 if(IsEmpty()){Empty();returnNULL;} Typemin=elements[0]; //假設(shè)elements[0]是最小值，繼續(xù)找最小值intminindex=0; for(inti=1;i<=top;i++) if(elements[i]<min){min=elements[i];minindex=i;}elements[minindex]=elements[top]; //用最后一個元素填補要取走的最小值元素 top--; return&min; //返回最小元素的值 }4-15試?yán)脙?yōu)先級隊列實現(xiàn)棧和隊列。【解答】 template<classType>classPQueue; //前視的類定義 template<classType>classPQueueNode{ //優(yōu)先級隊列結(jié)點類的定義 friendclassPQueue<Type>; //PQueue類作為友元類定義 public: PQueueNode(Type&value,intnewpriority,PQueue<Type>*next):data(value),priority(newpriority),link(next){} //構(gòu)造函數(shù) virtualTypeGetData(){returndata;} //取得結(jié)點數(shù)據(jù) virtualintGetPriority(){returnpriority;} //取得結(jié)點優(yōu)先級virtualPQueueNode<Type>*GetLink(){returnlink;} //取得下一結(jié)點地址 virtualvoidSetData(Type&value){data=value;} //修改結(jié)點數(shù)據(jù)virtualvoidSetPriority(intnewpriority){priority=newpriority;} //修改結(jié)點優(yōu)先級virtualvoidSetLink(PQueueNode<Type>*next){link=next;} private: //修改指向下一結(jié)點的指針 Typedata; //數(shù)據(jù)intpriority; //優(yōu)先級 ListNode<Type>*link; //鏈指針 }; template<classType>classPQueue{ //優(yōu)先級隊列的類定義 public: PQueue():front(NULL),rear(NULL){} //構(gòu)造函數(shù) virtual~PQueue(){MakeEmpty();} //析構(gòu)函數(shù)virtualvoidInsert(Type&value,intnewpriority); //插入新元素value到隊尾virtualTypeRemove(); //刪除隊頭元素并返回virtualTypeGet(); //讀取隊頭元素的值virtualvoidMakeEmpty(); //置空隊列virtualintIsEmpty(){returnfront==NULL;} //判隊列空否 private: PQueueNode<Type>*front,*rear; //隊頭指針,隊尾指針 };template<classType>voidPQueue<Type>::MakeEmpty(){//將優(yōu)先級隊列置空 PQueueNode<Type>*q; while(front!=NULL) //鏈不空時,刪去鏈中所有結(jié)點{q=front;front=front->link;deleteq;} //循鏈逐個刪除 rear=NULL; //隊尾指針置空 }template<classType>voidPQueue<Type>::Insert(Type&value,intnewpriority){//插入函數(shù) PQueueNode<Type>*q=newPQueueNode(value,newpriority,NULL); if(IsEmpty())front=rear=q; //隊列空時新結(jié)點為第一個結(jié)點 else{PQueueNode<Type>*p=front,*pr=NULL; //尋找q的插入位置while(p!=NULL&&p->priority>=newpriority) //隊列中按優(yōu)先級從大到小鏈接{pr=p;p=p->link;}if(pr==NULL){q->link=front;front=q;} //插入在隊頭位置else{q->link=p;pr->link=q; //插入在隊列中部或尾部if(pr==rear)rear=q; } } }template<classType>TypePQueue<Type>::Remove(){//刪除隊頭元素并返回 if(IsEmpty())returnNULL;PQueueNode<Type>*q=front;front=front->link; //將隊頭結(jié)點從鏈中摘下 Typeretvalue=q->data;deleteq; if(front==NULL)rear=NULL; returnretvalue; }template<classType>TypePQueue<Type>::Get(){//讀取隊頭元素的值 if(IsEmpty())returnNULL; elsereturnfront->data; } (1)棧的定義與實現(xiàn) template<classType>classStack:publicPQueue{ //棧類定義 public: Stack():front(NULL),rear(NULL){} //構(gòu)造函數(shù)voidInsert(Type&value); //插入新元素value到隊尾 }template<classType>voidStack<Type>::Insert(Type&value){//插入函數(shù) PQueueNode<Type>*q=newPQueueNode(value,0,NULL); if(IsEmpty())front=rear=q; //?？諘r新結(jié)點為第一個結(jié)點else{q->link=front;front=q;} //插入在前端 } (2)隊列的定義與實現(xiàn) template<classType>classQueue:publicPQueue{ //隊列類定義 public: Queue():front(NULL),rear(NULL){} //構(gòu)造函數(shù)voidInsert(Type&value); //插入新元素value到隊尾 }template<classType>voidQueue<Type>::Insert(Type&value){//插入函數(shù) PQueueNode<Type>*q=newPQueueNode(value,0,NULL); if(IsEmpty())front=rear=q; //隊列空時新結(jié)點為第一個結(jié)點elserear=rear->link=q; //插入在隊尾位置 }四、其他練習(xí)題4-16單選題(1)棧的插入和刪除操作在________進(jìn)行。A棧頂 B棧底 C任意位置 D指定位置(2)當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top==n表示?？?，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行________語句修改top指針。Atop++; Btop--; Ctop=0; Dtop;(3)若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)________種情況。A3,2,1 B2,1,3 C3,1,2 D1,3,2(4)在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的________位置。A前一個 B后一個 C當(dāng)前 D后面(5)當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為________。An-2 Bn-1 Cn Dn+1(6)從一個順序存儲的循環(huán)隊列中刪除一個元素時，首先需要________。A隊頭指針加一 B隊頭指針減一C取出隊頭指針?biāo)傅脑? D取出隊尾指針?biāo)傅脑?7)假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r，則判斷隊空的條件為________。Af+1==r Br+1==f Cf==0 Df==r(8)假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為front和rear，則判斷隊空的條件為________。Afront==rear Bfront!=NULL Crear!=NULL Dfront==NULL【解答】(1)A (2)B(3)C(4)A(5)B(6)B(7)D (8)D4-17填空題(1)隊列的插入操作在________進(jìn)行，刪除操作在________進(jìn)行。(2)棧又稱為________的表，隊列又稱為________的表。(3)向一個順序棧插入一個元素時，首先使________后移一個位置，然后把待插入元素________到這個位置上。(4)從一個棧刪除元素時，需要前移一位________。(5)在一個循環(huán)隊列Q中，判斷隊空的條件為________，判斷隊滿的條件為________。(6)在一個順序棧中，若棧頂指針等于________，則為空棧；若棧頂指針等于________，則為滿棧。(7)在一個鏈?zhǔn)綏Ｖ?，若棧頂指針等于NULL則為________；在一個鏈?zhǔn)疥犃兄?，若隊頭指針與隊尾指針的值相同，則表示該隊列為________或該隊列________。(8)向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點時，首先把棧頂指針的值賦給________，然后把新結(jié)點的存儲位置賦給________。(9)向一個循環(huán)隊列中插入元素時，需要首先移動________，然后再向所指位置________新插入的元素。(10)當(dāng)用長度為n的數(shù)組順序存儲一個棧時，若用top==n表示?？眨瑒t表示棧滿的條件為________。(11)向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€新結(jié)點*p時，應(yīng)執(zhí)行________和________操作。(12)從一個棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點并不需要返回棧頂結(jié)點的值和回收結(jié)點時，應(yīng)執(zhí)行________操作。(13)假定front和rear分別為一個鏈?zhǔn)疥犃械年狀^和隊尾指針，則該鏈?zhǔn)疥犃兄兄挥幸粋€結(jié)點的條件為________。(14)中綴表達(dá)式3*(x+2)-5所對應(yīng)的后綴表達(dá)式為________。(15)后綴表達(dá)式“45*32+-”的值為________?！窘獯稹?1)隊尾，隊頭(2)后進(jìn)先出，先進(jìn)先出(3)棧頂指針，寫入(4)棧頂指針(5)Q.front==Q.rear，(Q.rear+1)%MaxSize+1==Q.front(6)–1，MaxSize-1(7)空棧，空，只含有一個結(jié)點(8)新結(jié)點的指針域，棧頂指針(9)隊尾指針，寫入(10)top==0(11)p->link=top，top=p(12)top=top->link(13)front==rear&&front!=NULL或者front==rear&&rear!=NULL(14)3x2+*5-(15)154-18設(shè)有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個元素的出棧順序為s2,s3,s4,