第三章-棧和隊列作業(yè)答案

1、 3.1 3.1 鏈棧中為何不設(shè)置頭結(jié)點鏈棧中為何不設(shè)置頭結(jié)點? ? 鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進行操作的，鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進行操作的， 如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進行操作，反而使算如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進行操作，反而使算 法更復(fù)雜，所以只要有鏈表的頭指針就可以了。法更復(fù)雜，所以只要有鏈表的頭指針就可以了。 3.2 3.2 循環(huán)隊列的優(yōu)點是什么循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿如何判別它的空和滿? 循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的“假上溢假上溢”現(xiàn)象，現(xiàn)象， 能夠使

2、存儲隊列的向量空間得到充分的利用。能夠使存儲隊列的向量空間得到充分的利用。 判別循環(huán)隊列的判別循環(huán)隊列的空空或或滿滿不能以頭尾指針是否相等來確定，不能以頭尾指針是否相等來確定， 一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊列的空和一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊列的空和 滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是 否會重合，如果會重合就認為隊列已滿。三是設(shè)置一計數(shù)器記錄隊否會重合，如果會重合就認為隊列已滿。三是設(shè)置一計數(shù)器記錄隊 列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。列中元素

3、總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。 3.3 設(shè)長度為設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指 針，則入隊、出隊操作的時間為何針，則入隊、出隊操作的時間為何? 若只設(shè)尾指針呢若只設(shè)尾指針呢? 當只設(shè)頭指針時，出隊的時間為當只設(shè)頭指針時，出隊的時間為1，而入隊的時，而入隊的時 間需要間需要n，因為每次入隊均需從頭指針開始查找，找，因為每次入隊均需從頭指針開始查找，找 到最后一個元素時方可進行入隊操作。到最后一個元素時方可進行入隊操作。 若只設(shè)尾指針，則出、入隊時間均為若只設(shè)尾指針，則出、入隊時間均為1。因為是。因為是 循環(huán)鏈表，尾指針所指的下一個

4、元素就是頭指針所指循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指 元素，所以出隊時不需要遍歷整個隊列。元素，所以出隊時不需要遍歷整個隊列。 提示：提示： 對表達式進行掃描，凡遇到對表達式進行掃描，凡遇到( (就進棧，遇就進棧，遇) )就退掉棧頂?shù)木屯说魲ｍ數(shù)? (， 表達式被掃描完畢，棧應(yīng)為空。表達式被掃描完畢，棧應(yīng)為空。 根據(jù)提示，可以設(shè)計算法如下：根據(jù)提示，可以設(shè)計算法如下： #include #include #include stack.h#include stack.h int PairBracket( char int PairBracket( char * *S)S) / /檢查表達式中括號是否配對檢查表達式中括號是否配對 int i;int i; SeqStack T; /SeqStack T; /定義一個棧定義一個棧 InitStack (InitStack ( for (i=0; istrlen(S) ; i+)for (i=0; istrlen(S) ; i+) if ( Si= =( ) Push( /if ( Si= =( ) Push( /遇遇( (時進棧時進棧 if ( Si= =) ) Pop( /if ( Si= =) ) Pop( /遇遇)