數(shù)據(jù)結(jié)構(gòu)--3章棧和隊(duì)-預(yù)覽頁(yè)
【正文】 e)元素 e進(jìn)棧 s。 若 s為空棧 ,發(fā)生 “ 下溢 ” (underflow)； 為空棧時(shí)，表示某項(xiàng)任務(wù)未開始或已完成。 若 s為空棧 ,則 Empty(s)為 true；否則為 false。 A,B,C,D 輸入 輸出 5種 5種 3種 1種 順序棧的基本操作及算法： 順序棧的類型定義如下所示： define SackSize100 typedef struct {Datatype data[SackSize]。 假設(shè)棧空間為 data[0.. SackSize1] (1)頂指針指向頂元素所在位置： top → 棧頂指針 棧頂 棧底 SackSize1 n 1 0 /// /// /// /// /// /// SackSize1 1 0 1 自 由 區(qū) 自 由 區(qū) (a) 非空棧 (b) 空棧 , s→ top==1 若刪除元素，將發(fā)生 “ 下溢 ” /// /// an ... a2 a1 序號(hào) top → 序號(hào) top → 棧頂 棧底 SackSize1 1 0 (c)滿棧 ,s→ top== SackSize1 若插入元素 ,將發(fā)生 “ 上溢 ” “ Overflow” an ... ... ... a2 a1 (1)置空棧：首先建立?？臻g，然后初始化棧頂指針。 return s。 sdata[stop]=x。 /*棧空 */ return (sdata[stop] )。通常?？諘r(shí)常作為一種控制轉(zhuǎn)移的條件。 SeqStack s。s,N%B )。s )。 head,front ▲ 隊(duì)尾 隊(duì)列中只允許插入元素的一端 。 又稱：入隊(duì) 。 (3)EnQueue(q,e) 將 e插入隊(duì)列 q的尾端。 A A B C D 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 ← A進(jìn)隊(duì) f r ← B,C,D進(jìn)隊(duì) f r f r (3)B,C,D進(jìn)隊(duì)后 : 隊(duì)列的順序表示和實(shí)現(xiàn) (1)初始化后 : (2)A進(jìn)隊(duì)后 : 假設(shè)用一維數(shù)組 Q[0..5]表示 順序隊(duì)列 與 “ 假溢出 設(shè) f指向隊(duì)頭元素， r指向隊(duì)尾元素 空隊(duì)列 D E F 0 1 2 3 4 5 D 0 1 2 3 4 5 f r ← E,F 進(jìn)隊(duì) f r ← G進(jìn)隊(duì) ,“假溢出 ” 解決假溢出的辦法之一 :移動(dòng)元素。 b. 少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加 1后是否等于頭指針，相等，隊(duì)滿。 /*數(shù)據(jù)的存儲(chǔ)區(qū) */ int front, rear。 Qcount=0。 //隊(duì)滿上溢 Qcount ++。 if (QueueEmpty (Q)) Error( “Queue undeflow”)。 return temp。 Qrear隊(duì)尾指針，指向隊(duì)尾結(jié)點(diǎn)。amp。 QueueNode *p； //說明變量 p指針 if (QueueEmpty（ Q） ) //若原隊(duì)列為空 Error(“ queue underflow”)； //隊(duì)下溢，退出去 p=Qfront； //P指向隊(duì)頭結(jié)點(diǎn) x=pdata； //取出元素 ,e指向它 Qfront=pnext； //刪除隊(duì)頭結(jié)點(diǎn) if (Qrear==p) //若原隊(duì)列只有 1個(gè)結(jié)點(diǎn) Qrear=NULL； //修改尾指針 free(p)； //釋放被刪除結(jié)點(diǎn)的空間 return x； //返回原隊(duì)頭數(shù)據(jù)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1