【正文】 5 2 0 2 void conversion( ) { initstack(s)。 scanf (“ %” ,n)。 while(n){ push(s,n%8)。 n=n/8。 } while(! Stackempty(s)){ pop(s,e)。 printf(“ %d” ,e)。 } } 括號(hào)匹配的檢驗(yàn) 假設(shè)表達(dá)式中充許括號(hào)嵌套 ,則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。例： （（）（） （（））） 行編輯程序 在編輯程序中，設(shè)立一個(gè)輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯(cuò)誤，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。 行編輯程序算法如下 : void lineedit( ){ initstack(s)。 ch=gether( )。 while(ch!=eof){ while(ch!=eof ch!=‘ \n’ ){ switch(ch){ case ‘ ’ : pop(s,c)。 case ‘ ’ : clearstack(s)。 default : push(s,ch)。 } ch=getchar( )。 } clearstack(s)。 if(ch!=eof) ch=gethar( )。 } destroystack(s)。 } 迷宮求解 入口 出口 隊(duì)列 抽象數(shù)據(jù)類型隊(duì)列的定義 隊(duì)列 (Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭 (front)，允許插入的一端稱為隊(duì)尾 (rear)。 例如：排隊(duì)購(gòu)物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。因此隊(duì)列亦稱作先進(jìn)先出 (First In First Out)的線性表，簡(jiǎn)稱 FIFO表。 當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素 a1,a2,?a n之后， a1是隊(duì)頭元素， an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是 a1,a2,?a n ，也就是說隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。 下圖是隊(duì)列的示意圖： a1 a2 ? an 出隊(duì) 入隊(duì) 隊(duì)頭 隊(duì)尾 隊(duì)列的抽象數(shù)據(jù)定義見書Ｐ 59 循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣，順序隊(duì)列也是必須用一個(gè)向量空間來(lái)存放當(dāng)前隊(duì) 列中的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素在隊(duì)列中的位置，它們的初始值地隊(duì)列初始化時(shí)均應(yīng)置為０。入隊(duì)時(shí)將新元素插入所指的位置，然后將加１。出隊(duì)時(shí)，刪去所指的元素，然后將加１并返回被刪元素。由此可見，當(dāng)頭尾指針相等時(shí)隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。 ０ １ ２ ３ 0 1 2 3 Front rear a b c Front rear (a)隊(duì)列初始為空 （ b） A,B,C入隊(duì) ０ １ ２ ３ ０ １ ２ ３ b c front rear front rear （ c) a出隊(duì) (d) b,c出隊(duì)，隊(duì)為空 和棧類似，隊(duì)列中亦有上溢和下溢現(xiàn)象。此外，順序隊(duì)列中還存在“假上溢”現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無(wú)法重新利用。因此，盡管隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。 為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（ Circular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加 1，朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界（ QueueSize1）時(shí)，其加 1操作的結(jié)果是指向向量的下界 0。 這種循環(huán)意義下的加 1操作可以描述為： if(I+1==QueueSize) i=0。 else i++。 利用模運(yùn)算可簡(jiǎn)化為 ： i=(i+1)%QueueSize 顯然，因?yàn)檠h(huán)隊(duì)列元素的空間可以被利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，除一些簡(jiǎn)單的應(yīng)用外，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。 如圖所示：由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無(wú)法通過 front=rear來(lái)判斷隊(duì)列“空”還是“滿”。 解決此問題的方法至少有三種： 其一是另設(shè)一個(gè)布爾變量以匹別隊(duì)列的空和滿；其二是少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加 1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意： rear所指的單元始終為空）； 其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長(zhǎng)度）。下面我們用第三種方法實(shí)現(xiàn)循環(huán)隊(duì)列上的六種基本操作，為此先給出循環(huán)隊(duì)列的類型定義。 ? define QueueSize 100 ? typedef char DataType。 ? typedef Struct{ ? int front。 ? int rear。 ? int count。 ? datatype data[queuesize] ? }cirqueue。 （ 1）置空隊(duì) void initqueue(cirqueue *q){ q–front=q–rear=0。 q–count=0。 } （ 2）判斷隊(duì)空 int queueempty(cirqueue *q) { return q–count==0。 } （ 3）判斷隊(duì)滿 int queuefull(cirqueue *q){ return q–count==queuesize。 } （ 4）入隊(duì) void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(“ queue overflow” )。 q–count++。 q–data[q–rear]=x。 q–rear=(q–rear+1)%queuesize。 } （ 5）出隊(duì) datatype dequeue(cirqueue *q) { datatype temp。 if(queueempty(q)) error(“ queue underflow” )。 temp=q–data[q–front]。 q–count。 q–front=(q–front+1)%queuesize。 return temp。 } （ 6）取頭指針 datatype queuefront(cirqueue *q) { if(queueempty(q)) error(“ queue is empty.” )。 return q–data[q–front]。 } ? 鏈隊(duì)列 ? 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個(gè)尾指針，指向鏈表的最后一個(gè)結(jié)點(diǎn)。于是，一個(gè)鏈隊(duì)列由一個(gè)頭指針唯一確定。和順序隊(duì)列類似，我們也是將這兩個(gè)指針封裝在一起，將鏈隊(duì)列的類型 LinkQueue定義為一個(gè)結(jié)構(gòu)類型： ? typedef struct queuenode{ ? datatype data。 ? struct queuenode *next。 ? }queuenode。 typedef struct{ queuenode *front。 queuenode *rear。 }linkqueue。 下面給出鏈隊(duì)列上實(shí)現(xiàn)的基本運(yùn)算： void initqueue(linkqueue *q) { q–front=q–rear=null。 } int queueempty(linkqueue *q) { return q–front==null q–rear==null。 } void enqueue(linkqueue *q,datatype x) { queuenode *p p=(queuenode * )malloc(sizeof(queuenode))。 p–data=x。 p–next=null。 if(queueempty(q)) q–front=q–rear=p。 else{ q–rear–next=p。 q–rear=p。 } } Datatype dequeue(linkqueue *q) { datatype x。 queuenode *p if(queueempty(q)) error(“ queue underflow” )。 p=q–front。 x=p–data。 q–front=p–next。 if(q–rear==p) q–rear=null。 free(p)。 return x。 } datatype queuefront(linkqueue *q) { if(queueempty(q)) error(“ queue is empty.” )。 return q–front–data。 } 注意：在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。 習(xí)題 設(shè)將整數(shù)以萬(wàn)計(jì)、 4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下有問題： （ 1）若入棧次序?yàn)?push(1)， pop()， push(