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