中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法第3章棧和隊(duì)列課后作業(yè)答案匯總(更新版)
【正文】 pnext=Qrearnext?！ rear = Qrearnext?！ 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素站點(diǎn)(注意不設(shè)頭指針) ，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空 、入隊(duì)和出隊(duì)等算法。//保存元素值 Qfront= ( Qfront+1 ) %QueueSize。 }CirQueue。 算法設(shè)計(jì)如下:amp。 //因?yàn)檫@個(gè)棧是以另一端為底的，所以指針值加1。 } int FullStack( DblStack *S) { //判棧滿,滿時(shí)肯定兩頭相遇 return (Stop0 == Stop11)。 }DblStack void InitStack( DblStack *S ) { //初始化雙向?！ top0 = 1?！ f (!StackEmpty(S))//棧不為空時(shí)，將棧頂元素出棧 Pop(amp。 ) Push(amp?！ eqStack S。(39?！ ++。 因?yàn)橐每盏氖菞，如果不用指針來做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對(duì)原來的棧產(chǎn)生影響，系統(tǒng)將會(huì)在內(nèi)存中開辟另外的單元來對(duì)形參進(jìn)行函數(shù)操作。 return 0 。 //求向量長(zhǎng)度 for ( i=0。 }SeqStack?！ ?4)程序段的功能是將一個(gè)循環(huán)隊(duì)列Q經(jīng)過S棧的處理，反向排列，原來的隊(duì)頭變成隊(duì)尾，原來的隊(duì)尾變成隊(duì)頭。Q1, x) 。 n++。} }// Demo3(5) CirQueue Q1, Q2。S)。T,i)?！ ush( amp?！ ush(amp?！ hile ( StackEmpty(S)) arr[n++]=Pop(S)。 設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢?因?yàn)橐玫?4的出棧序列，則應(yīng)做Push(1),Pop(),Push(2),Push (2)能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。 (3),Push(4),Pop()。 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿?因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈兀猿鲫?duì)時(shí)不需要遍歷整個(gè)隊(duì)列?！ //Demo1(2) SeqStack S1, S2, tmp。tmp) ) { x=Pop( amp。 { // 設(shè)DataType 為int 型 SeqStack T。T)。S,x)。Q1) ) i++)}試寫一個(gè)算法判定給定的字符向量是否為回文?！ nt i , len。s, t[i])?！ eturn 1 。 利用棧的基本操作， 寫一個(gè)返回S中結(jié)點(diǎn)個(gè)數(shù)的算法 int StackSize( SeqStack S),并說明S為何不作為指針參數(shù)?并不能改變棧的結(jié)構(gòu)。就退掉棧頂?shù)?9?！ or (i=0。(39。//不匹配，返回0 } if EmptyStack(amp。 DataType Data[StackSize] int EmptyStack( DblStack *S, int i ) { //判棧空(棧號(hào) i) return (i == 0 amp。 //棧0入?！ f ( i == 1) SData[ Stop1]= x?！ 々?n+1 當(dāng)m=0時(shí)amp?！ypedef char Datatype 。 } (2)判隊(duì)空 int EmptyQueue( CirQueue *Q) { //判隊(duì)空 return Qfront==Qrear?！ Data[Qrear]=x?！ truct queuenode *next?！ ree(s)?！ rear=p。} else解： 根據(jù)題意，可定義該循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)： define QueueSize 100 循環(huán)隊(duì)列的隊(duì)滿條件是：Qquelen==QueueSize 知道了尾指針和元素個(gè)數(shù)，當(dāng)然就能計(jì)算出隊(duì)頭元素的位置。 //設(shè)一個(gè)臨時(shí)隊(duì)頭指針 tmpfront=(QueueSize+Qrear Qquelen+1)%QueueSize。拼一個(gè)春夏秋冬！贏一個(gè)無悔人生！早安！—————獻(xiàn)給所有努力的人.學(xué)習(xí)參考
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1