【文章內容簡介】 隊列的元素類型均為int）：（1）void proc_1(Stack S){ int i, n, A[255]。 n=0。 while(!EmptyStack(S)) {n++。 Pop(amp。S, amp。A[n])。} for(i=1。 i=n。 i++) Push(amp。S, A[i])。 }將棧S逆序。（2）void proc_2(Stack S, int e){ Stack T。 int d。InitStack(amp。T)。 while(!EmptyStack(S)) { Pop(amp。S, amp。d)。 if (d!=e) Push( amp。T, d)。 } while(!EmptyStack(T)) { Pop(amp。T, amp。d)。 Push( amp。S, d)。 }}刪除棧S中所有等于e的元素。（3）void proc_3(Queue *Q){ Stack S。 int d。InitStack(amp。S)。 while(!EmptyQueue(*Q)) {DeleteQueue(Q, amp。d)。Push( amp。S, d)。 } while(!EmptyStack(S)) { Pop(amp。S, amp。d)。 EnterQueue(Q，d) } }將隊列Q逆序。實習題1． 回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫一個算法，判斷依次讀入的一個以@為結束符的字母序列，是否為形如‘序列1　amp。序列2’模式的字符序列。其中序列1和序列2　中都不含字符‘amp?！?，且序列2　是序列1的逆序列。例如，‘a+bamp。b+a’是屬該模式的字符序列，而‘１+３amp。３－１’則不是。2． 停車場管理。設停車場是一個可停放n輛車的狹長通道，且只有一個大門可供汽車進出。在停車場內，汽車按到達的先后次序，由北向南依次排列（假設大門在最南端）。若車場內已停滿n輛車，則后來的汽車需在門外的便道上等候，當有車開走時，便道上的第一輛車即可開入。當停車場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場。每輛車離開停車場時，應按其停留時間的長短交費（在便道上停留的時間不收費）。試編寫程序，模擬上述管理過程。要求以順序棧模擬停車場，以鏈隊列模擬便道。從終端讀入汽車到達或離去的數據，每組數據包括三項：①是“到達”還是“離去”；②汽車牌照號碼；③“到達”或“離去”的時刻。與每組輸入信息相應的輸出信息為：如果是到達的車輛，則輸出其在停車場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應交的費用。（提示：需另設一個棧，臨時停放為讓路而從車場退出的車。）車庫便道暫時退車道3． 商品貨架管理。商品貨架可以看成一個棧，棧頂商品的生產日期最早，棧底商品的生產日期最近。上貨時，需要倒貨架，以保證生產日期較近的商品在較下的位置。用隊列和棧作為周轉，實現上述管理過程。第三章答案(b)所示鐵道（兩側鐵道均為單向行駛道）進行車廂調度，回答：（1） 如進站的車廂序列為123，則可能得到的出站車廂序列是什么？（2） 如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因（即寫出以“S”表示進棧、“X”表示出棧的棧序列操作）?！窘獯稹浚?）可能得到的出站車廂序列是：12132123321。(2)不能得到435612的出站序列。因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此時按照“后進先出”的原則，出棧的順序必須為X(2)X(1)。能得到135426的出站序列。因為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。，在這兩種棧的存儲結構中如何判別?？张c棧滿？【解答】（1）順序棧 （top用來存放棧頂元素的下標）判斷棧S空：如果Stop==1表示?？?。判斷棧S滿：如果Stop==Stack_Size1表示棧滿。(2) 鏈棧（top為棧頂指針，指向當前棧頂元素前面的頭結點）判斷?？眨喝绻鹴opnext==NULL表示?？?。判斷棧滿：當系統(tǒng)沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。 3． 4照四則運算加、減、乘、除和冪運算的優(yōu)先慣例，畫出對下列表達式求值時操作數棧和運算符棧的變化過程：AB*C/D+E↑F【解答】3． 5寫一個算法，判斷依次讀入的一個以@為結束符的字母序列，是否形如‘序列1amp。序列2’的字符序列。序列1和序列2中都不含‘amp?！?，且序列2是序列1 的逆序列。例如，’a+bamp。b+a’是屬于該模式的字符序列，而’1+3amp。31’則不是?！窘獯稹克惴ㄈ缦拢? int IsHuiWen() { Stack *S。 Char ch,temp。 InitStack(amp。S)。 Printf(“\n請輸入字符序列：”)。 Ch=getchar()。While( ch!=amp。) /*序列1入棧*/{ Push(amp。S,ch)。 ch=getchar()。}do /*判斷序列2是否是序列1的逆序列*/{ ch=getchar()。 Pop(amp。S,amp。temp)。 if(ch!= temp) /*序列2不是序列1的逆序列*/{ return(FALSE)。 printf(“\nNO”)。} } while(ch!=@ amp。amp。 !IsEmpty(amp。S))if(ch = = @ amp。amp。 IsEmpty(amp。S)) { return(TRUE)。 printf(“\nYES”)。} /*序列2是序列1的逆序列*/else {return(FALSE)。 printf(“\nNO”)。} }/*IsHuiWen()*/ 要求循環(huán)隊列不損失一個空間全部都能得到利用，設置一個標志tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應的入隊與出隊算法?！窘獯稹咳腙犓惴ǎ篿nt EnterQueue(SeqQueue *Q, QueueElementType x){ /*將元素x入隊*/ if(Qfront==Qfront amp。amp。 tag==1) /*隊滿*/ return(FALSE)。 if(Qfront==Qfront amp。amp。 tag==0) /*x入隊前隊空，x入隊后重新設置標志*/ tag=1。Qelememt[Qrear]=x。Qrear=(Qrear+1)%MAXSIZE。 /*設置隊尾指針*/Return(TRUE)。 }出隊算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*刪除隊頭元素，用x返回其值*/if(Qfront==Qrear amp。amp。 tag==0) /*隊空*/ return(FALSE)。*x=Qelement[Qfront]。Qfront=(Qfront+1)%MAXSIZE。 /*重新設置隊頭指針*/if(Qfront==Qrear) tag=0。 /*隊頭元素出隊后隊列為空，重新設置標志域*/Return(TUUE)。 } 編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調用過程。【解答】算法： void hanoi (int n ,char x, char y, char z) { /*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/ if(n = =1) move(x,1,z)。 else { Hanoi(n1,x,z,y)。 move(x, n, z)。 Hanoi(n1, y,x,z)。 }}Hanoi(3,A,B,C)的遞歸調用過程： Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(AC) 1號搬到C Move(AB) 2號搬到B Hanoi(1,C,A,B) move(CB) 1號搬到B Move(AC) 3號搬到CHanoi(2,B,A,C) Hanoi(1,B,C,A) move(BA) 1號搬到A Move(BC) 2號搬到C Hanoi(1,A,B,C) move(AC) 1號搬到C第4章 串習題1. 設s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。給出下列操作的結果：StrLength(s)。 SubString(sub1,s,1,7)。 SubString(sub2,s,7,1)。StrIndex(s,’A’,4)。 StrReplace(s,’STUDENT’,q)。 StrCat(StrCat(sub1,t), StrCat(sub2,q))。[參考答案]StrLength(s)=14。 sub1= ’I AM A_’。 sub2= ’_’。 StrIndex(s,’A’,4)=6。 StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’。 StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’。2. 編寫算法，實現串的基本操作StrReplace(S,T,V)。3. 假設以塊鏈結構表示串，塊的大小為1，且附設頭結點。試編寫算法，實現串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。[說明]：用單鏈表實現。4． 敘述以下每對術語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。5． 已知：S=”(xyz)*”,T=”(x+z)*y”。試利用聯(lián)接、求子串和置換等操作，將S轉換為T.6． S和T是用結點大小為1的單鏈表存儲的兩個串，設計一個算法將串S中首次與T匹配的子串逆置。7． S是用結點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及從第k個字符刪除len個字符。以下算法用定長順序串：8． 寫下列算法：（1） 將順序串r中所有值為ch1的字符換成ch2的字符。（2） 將順序串r中所有字符按照相反的次序仍存放在r中。（3） 從順序串r中刪除其值等于ch的所有字符。（4） 從順序串r1中第index 個字符起求出首次與串r2相同的子串的起始位置。（5） 從順序串r中刪除所有與串r1相同的子串。9． 寫一個函數將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換。[提示]：（1）用靜態(tài)順序串 （2）先移位，后復制10． 寫算法，實現順序串的基本操作StrCompare(s,t)。11． 寫算法，實現順序串的基本操作StrReplace(amp。s,t,v)。[提示]：（1） 被替換子串定位（相當于第9題中i）（2） 被替換子串后面的字符左移或右移（為替換子串準備房間）（3） 替換子串入住（復制）（4） 重復上述，直到……第四章答案 設s=’I AM A STUDENT’，t=’GOOD’， q=’WORKER’。給出下列操作的結果：【解答】StrLength(s)=14。SubString(sub1,s,1,7) sub1=’I AM A ’。SubString(sub2,s,7,1) sub2=’ ’。StrIndex(s,4,’A’)=6。StrReplace(s,’STUDENT’,q)。 s=’I AM A WORKER’。StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=’I AM A GOOD WORKER’。 ，實現串的基本操作StrReplace(S,T,V)。 【解答】算法如下：int strReplace(SString S,SString T, SString V){/*用串V替換S中的所有子串T */ int pos,i。 pos=strIndex(S,1,T)。 /*求S中子串T第一次出現的位置*/ if(pos = = 0) return(0)。 while(pos!=0) /*用串V替換S中的所有子串T */ { switch() { case 0: /*串T的長度等于串V的長度*/ for(i=0。i=。i++) /*用