━━堆棧、隊列結構、二叉樹.ppt

C+程序設計,第7章(3) 堆棧、隊列結構、二叉樹,主要內容,堆棧結構順序棧、鏈棧 順序棧類的設計采用面向對象程序設計 順序棧類的應用舉例 鏈棧類的設計采用面向對象程序設計 鏈棧類的應用舉例 隊列結構順序隊列、鏈隊列 順序循環(huán)隊列類的設計采用面向對象程序設計 順序循環(huán)隊列類的應用舉例 鏈隊列類的設計采用面向對象程序設計 鏈隊列類的應用舉例 樹型結構二叉樹 樹型結構基于二叉樹的常用遍歷算法,堆棧結構順序棧、鏈棧,堆棧的邏輯結構是限制插入和刪除操作僅能在一端進行的線性結構。 棧頂與棧底：指線性表的兩端。 能進行插入和刪除的一端稱棧頂（top）；而另一端稱棧底（bottom）。 在棧頂插入新元素稱進棧（壓入）；刪除元素稱出棧（彈出）。 特殊線性表：是后進先出（LIFO：Last In First Out）結構的線性表。 進棧時：最先進棧的在最下面，最后進棧的在最上面。 出棧時：最后進棧的最先出棧，最先進棧的最后出棧。 堆棧的物理結構有連續(xù)、非連續(xù)存儲兩種結構，但邏輯功能基本相同。 連續(xù)存儲方式：順序棧。 非連續(xù)存儲方式：鏈棧。 堆棧結構的應用堆棧是最常用、最重要的數(shù)據結構之一。 【例】 局部變量是存放在棧中。 表達式的優(yōu)先級處理可由棧來實現(xiàn)。 函數(shù)調用時參數(shù)的傳遞、函數(shù)值的返回也是由棧來實現(xiàn)。,堆棧結構順序棧、鏈棧,順序棧的物理結構連續(xù)存儲 可以隨機訪問順序棧中的元素。 需要先開一定量的內存空間，使用時有可能溢出。 順序棧的操作執(zhí)行簡單，速度快。 鏈棧的物理結構非連續(xù)存儲 只能順序訪問鏈棧中的元素。 隨用隨開內存空間，使用時不可能溢出。 鏈棧的操作執(zhí)行復雜（不斷地動態(tài)分配），速度慢。,順序棧類的設計采用面向對象程序設計,順序棧類模板 StackSeq 的設計： 私有成員數(shù)據： int top ; /棧頂指針（對于順序棧，棧頂位置就是棧頂元素的下標） T *elements ; /棧空間首地址（對于順序棧，?？臻g是T類型的數(shù)組，開在動態(tài)存儲區(qū)） int max ; /棧空間中最多容納的元素個數(shù)（對順序棧，就是?？臻g數(shù)組的長度）,順序棧類的設計采用面向對象程序設計, 公有成員函數(shù)： StackSeq ( int = 20 ) ; /構造函數(shù)（參數(shù)省略時，默認?？臻g中最多容納20個元素） StackSeq ( ) ; /析構函數(shù)（釋放動態(tài)存儲區(qū)的?？臻g） void push ( T d ) ; /壓棧（將d元素壓入棧中，本操作 top 將改變） T pop ( ) ; /出棧（彈出棧頂元素并返回，本操作 top 將改變） T get ( int k ) ; /讀取并返回棧內第k號元素（元素編號為第0top號，本操作 top 不變） int length ( ) ; /求出棧內元素的個數(shù) void print ( ) ; /輸出棧內所有元素（將第0top號的元素依次輸出，本操作 top 不變） void empty ( ) ; /清空棧（使棧內無任何元素，即空棧） bool isEmpty ( ) ; /判斷棧是否為空 bool isFull ( ) ; /判斷棧是否已滿,【例】（順序棧類模板 StackSeq 的定義，以 “stackseq.h” 為文件名保存。） #include template class StackSeq /順序棧類模板 StackSeq 的聲明 int top ; /棧頂指針（對于順序棧，棧頂位置就是棧頂元素的下標） T *elements ; /?？臻g首地址（對于順序棧，棧空間是T類型的數(shù)組，開在動態(tài)存儲區(qū)） int max ; /棧空間中最多容納的元素個數(shù)（對于順序棧，就是?？臻g數(shù)組的長度） public: StackSeq ( int = 20 ) ; /構造函數(shù)（參數(shù)省略時，默認?？臻g中最多容納20個元素） StackSeq ( ) ; /析構函數(shù)（釋放動態(tài)存儲區(qū)的?？臻g） void push ( T d ) ; /壓棧（將d元素壓入棧中，本操作 top 將改變） T pop ( ) ; /出棧（彈出棧頂元素并返回，本操作 top 將改變） T get ( int k ) ; /讀取并返回棧內第k號元素（元素編號為第0top號，本操作 top 不變） int length ( ) ; /求出棧內元素的個數(shù) void print ( ) ; /輸出棧內所有元素（將第0top號的元素依次輸出，本操作 top 不變） void empty ( ) ; /清空棧（使棧內無任何元素，即空棧） bool isEmpty ( ) ; /判斷棧是否為空 bool isFull ( ) ; /判斷棧是否已滿 ;,/構造函數(shù) template StackSeq : StackSeq ( int n ) top = -1 ; /棧頂 top 為 -1 時，表示空棧 elements = new T n ; /在堆區(qū)建立?？臻g（T類型數(shù)組，首地址存放在elements中） max = n ; /?？臻g中最多容納的元素個數(shù)（也就是棧空間數(shù)組的長度） assert ( elements != 0 ) ; /分配不成功，則結束程序 /析構函數(shù) template StackSeq : StackSeq ( ) delete elements ; /釋放動態(tài)存儲區(qū)的棧空間 /壓棧 template void StackSeq : push ( T d ) assert ( ! isFull( ) ) ; /棧滿，則結束程序 elements +top = d ; /棧頂指針先加1，元素d再進棧 /出棧 template T StackSeq : pop ( ) assert ( ! isEmpty( ) ) ; /棧空，則結束程序 return elements top- ; /返回棧頂元素，然后棧頂指針減1,/讀取并返回棧內第 k 號元素（棧內元素編號為第 0 top 號） template T StackSeq : get ( int k ) assert ( k=0 ,順序棧類的應用舉例,【例】（在文件 s1.txt 中，有若干學生成績資料。要求：以Student類作為順序棧元素的數(shù)據類，對順序棧類模板 StackSeq 中的各成員函數(shù)進行測試。學生類 Student 的聲明 ，前面例子中已出現(xiàn)，并以 “student.h” 為文件名保存。 ） #include #include #include “stackseq.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_SS( 10 ) ; /定義學生棧s_SS Student s ; cout s ,在s1.txt 中，學生資料： 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,cout “s_SS棧內元素個數(shù)=” s_SS.length( ) endl ; cout “s_SS棧內元素有：n” ; s_SS.print( ) ; cout “s_SS棧內0號元素是：n” s_SS.get( 0 ) ; cout “s_SS棧內3號元素是：n” s_SS.get( 3 ) ; cout “s_SS棧內元素個數(shù)=” s_SS.length( ) endl ; cout “依次全部出棧 n” ; while ( !s_SS.isEmpty( ) ) cout s_SS.pop( ) ; cout “s_SS棧內元素個數(shù)=” s_SS.length( ) endl ; cout s_SS.pop( ) ; ,【例】（使用順序棧類模板 StackSeq ，建立整數(shù)棧i_SS、字符棧c_SS，隨機產生6個范圍在09之間的整數(shù)、6個范圍在AZ之間的字母，依次進各棧，再出各棧。） #include #include #include “stackseq.h” void main ( ) StackSeq i_SS( 6 ) ; StackSeq c_SS( 8 ) ; cout “依次進棧 n” ; cout “整數(shù)棧：t字符棧：n” ; for ( int i=0; i6; i+ ) i_SS.push( rand()%10 ) ; c_SS.push( rand()%26+65 ) ; cout i_SS.get( i ) “tt” c_SS.get( i ) endl ; ,if ( i_SS.isFull( ) ) cout “整數(shù)棧已滿!n” ; else cout“整數(shù)棧未滿，可再壓入” 6-i_SS.length() “個!n”; if ( c_SS.isFull() ) cout “字符棧已滿!n” ; else cout“字符棧未滿，可再壓入” 8-c_SS.length() “個!n”; cout “依次出棧 n” ; cout “整數(shù)棧：t字符棧：n” ; for ( i=0; i6; i+ ) cout i_SS.pop( ) “tt” c_SS.pop( ) endl ; if ( i_SS.isEmpty( ) ) cout “整數(shù)棧已空!n” ; if ( c_SS.isEmpty( ) ) cout “字符棧已空!n” ; ,【例】（棧結構應用于表達式優(yōu)先級的實現(xiàn)。若有 + - * / 運算符和等號=組成的算術表達式，只有兩個優(yōu)先級( 先 */ 后 +- )。設： A+B*C-D/E=； 實現(xiàn)運算符的優(yōu)先級。） 【算法】定義兩個棧：操作數(shù)棧 n_S，運算符棧 c_S。從左往右掃描算術表達式，遇到操作數(shù)，則壓入n_S棧；遇到運算符，則與c_S棧棧頂運算符比較優(yōu)先級，若新運算符優(yōu)先級高，或此時c_S?？眨瑒t壓入c_S棧；否則將c_S棧棧頂運算符出棧，與n_S棧出棧的兩個操作數(shù)進行運算，結果壓入n_S棧，再將新運算符壓入c_S棧。繼續(xù)掃描，直至遇到號，掃描結束。兩棧的元素繼續(xù)按前面規(guī)則出棧運算。,鏈棧類的設計采用面向對象程序設計,結點類模板 Node 的聲明：前面例子中已出現(xiàn)，并以 “node.h” 為文件名保存。 結點類模板 Node 的成員： 私有成員數(shù)據： 數(shù)據域： T data ; /T類型的變量data 鏈域： Node *next ; /next為指向下一個結點的指針 公有成員函數(shù)： Node ( ) ; /表頭結點的構造 Node ( T d ) ; /普通結點的構造 void set ( T d ) ; /將當前結點的數(shù)據域置為d T get ( ) ; /獲取并返回當前結點的數(shù)據域 void show ( ) ; /輸出當前結點的數(shù)據域 友元函數(shù)、友元類： friend class ListLink ; /友元類，鏈表類可以訪問結點類的私有、保護成員 friend class StackLink ; /友元類，鏈棧類可以訪問結點類的私有、保護成員 friend class QueueLink ; /友元類，鏈隊列類可以訪問結點類的私有、保護成員,鏈棧類的設計采用面向對象程序設計,鏈棧類模板 StackLink 的設計： 私有成員數(shù)據： Node * top ; 公有成員函數(shù)： StackLink ( ) ; /構造函數(shù)（空棧） StackLink ( ) ; /析構函數(shù)（釋放棧內各結點的動態(tài)空間） void push ( T d ) ; /壓棧（將d元素壓入棧中，本操作 top 將改變） T pop ( ) ; /出棧（彈出棧頂元素并返回，本操作 top 將改變） T getTop ( ) ; /讀取并返回棧頂元素（本操作 top 不變） int length ( ) ; /求出棧內元素的個數(shù) void print ( ) ; /輸出棧內所有元素（本操作 top 不變） void empty ( ) ; /清空棧（使棧內無任何元素，即空棧） bool isEmpty ( ) ; /判斷棧是否為空,【例】（鏈棧類模板 StackLink 的定義，以 “stacklink.h” 為文件名保存。） #include template class StackLink /鏈棧類模板 StackLink 的聲明 Node * top ; /指向棧頂結點的指針 public: StackLink ( ) top = NULL ; /構造函數(shù)（空棧） StackLink ( ) empty( ) ; /析構函數(shù)（釋放棧內各結點的動態(tài)空間） void push ( T d ) ; /壓棧（將d元素壓入棧中，本操作 top 將改變） T pop ( ) ; /出棧（彈出棧頂元素并返回，本操作 top 將改變） T getTop ( ) /讀取并返回棧頂元素（本操作 top 不變） assert ( ! isEmpty( ) ) ; return top-data ; int length ( ) ; /求出棧內元素的個數(shù) void print ( ) ; /輸出棧內所有元素（本操作 top 不變） void empty ( ) ; /清空棧（使棧內無任何元素，即空棧） bool isEmpty ( ) return top = NULL ; /判斷棧是否為空 ;,/壓棧（將d元素壓入棧中，本操作 top 將改變） template void StackLink : push ( T d ) Node *pnew = new Node ( d ) ; pnew-next = top ; top = pnew ; /出棧（彈出棧頂元素并返回，本操作 top 將改變） template T StackLink : pop ( ) assert ( ! isEmpty( ) ) ; /?？?，則結束程序 Node *temp = top ; top = top-next ; T da = temp-data ; delete temp ; return da ; ,/求出棧內元素的個數(shù) template int StackLink : length ( ) Node *temp = top ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /輸出棧內所有元素（本操作 top 不變） template void StackLink : print ( ) Node *temp = top ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空棧（使棧內無任何元素，即空棧） template void StackLink : empty ( ) Node * temp ; while ( top != NULL ) temp = top ; top = top-next ; delete temp ; ,鏈棧類的應用舉例,【例】（在文件 s1.txt 中，有若干學生成績資料。要求：以Student類作為鏈棧結點的數(shù)據類，對鏈棧類模板 StackLink 中的各成員函數(shù)進行測試。學生類 Student 的聲明 ，前面例子中已出現(xiàn)，并以 “student.h” 為文件名保存。 ） #include #include #include “node.h” #include “stacklink.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_SL ; /定義學生棧s_SL Student s ; cout s ) s_SL.push( s ) ; inf.close( ) ;,在s1.txt 中，學生資料： 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,cout “s_SL棧內元素個數(shù)=” s_SL.length( ) endl ; cout “s_SL棧內元素有：n” ; s_SL.print( ) ; cout “s_SL棧頂元素是：n” s_SL.getTop( ) ; cout “s_SL棧內元素個數(shù)=” s_SL.length( ) endl ; cout “依次全部出棧 n” ; while ( !s_SL.isEmpty( ) ) cout s_SL.pop( ) ; cout “s_SL棧內元素個數(shù)=” s_SL.length( ) endl ; cout s_SL.pop( ) ; ,隊列結構順序隊列、鏈隊列,隊列的邏輯結構是限制插入和刪除操作分別在兩端進行的線性結構。 隊頭與隊尾：指線性表的兩端。 能進行插入的一端稱隊尾（rear）；能進行刪除的一端稱隊頭（front）。 在隊尾加入新元素稱進隊；在隊頭刪除元素稱出隊。 特殊線性表：是先進先出（ FIFO： First In First Out）結構的線性表。 進隊時：隨隊尾加入元素，隊尾指針（rear）不斷向后移。 出隊時：隨隊頭元素的出隊，隊頭指針（front）也不斷向后移。 即：進隊與出隊都是隊尾和隊頭指針的位置在變。 隊列的物理結構有連續(xù)、非連續(xù)存儲兩種結構，但邏輯功能基本相同。 連續(xù)存儲方式：順序隊列。 非連續(xù)存儲方式：鏈隊列。 隊列結構的應用隊列是最常用、最重要的數(shù)據結構之一。 【例】在Windows操作系統(tǒng)中，使用了很多消息等待隊列，以實現(xiàn)先來的先服務。,順序隊列的物理結構連續(xù)存儲 可以隨機訪問順序隊列中的元素。 需要先開一定量的內存空間，使用時有可能溢出。 順序隊列的操作執(zhí)行簡單，速度快。 鏈隊列的物理結構非連續(xù)存儲 只能順序訪問鏈隊列中的元素。 隨用隨開內存空間，使用時不可能溢出。 鏈隊列的操作執(zhí)行復雜（不斷地動態(tài)分配），速度慢。,隊列結構順序隊列、鏈隊列,順序循環(huán)隊列類的設計采用面向對象程序設計,對順序隊列的分析： 空隊時，隊頭指針front（下標）和隊尾指針rear（下標）重疊在一起，都為-1。進隊時隨著隊尾加入元素，隊尾指針（rear）不斷加 1 移動；出隊時隨著隊頭元素的出隊，隊頭指針（front）也不斷加 1 移動。進隊和出隊都是隊尾和隊頭指針的位置在變（若要位置不變，移動元素工作量太大） ，最后造成分配給隊列的存儲空間前端不能再被利用，而后端逐漸產生溢出。,順序循環(huán)隊列類的設計采用面向對象程序設計,順序循環(huán)隊列：將順序隊列做成一個邏輯上的循環(huán)隊列；而這樣做會使得：空隊時rear = front，滿隊時 rear = front；為了區(qū)分空隊與滿隊，在隊列中少放一個元素，即隊列中只剩下一個空位置時就算滿隊，以此作為標志來區(qū)分空隊與滿隊。,順序循環(huán)隊列類的設計采用面向對象程序設計,順序循環(huán)隊列類模板 QueueSeq 的設計： 私有成員數(shù)據： int rear, front ; /隊尾、隊頭指針（對于順序隊列，就是隊尾、隊頭位置的下標） T *elements ; /隊列空間的首地址（隊列空間是T類型的數(shù)組，開在動態(tài)存儲區(qū)） int max ; /隊列空間最多可容納的元素個數(shù)+1（也就是隊列空間數(shù)組的長度） 公有成員函數(shù)： QueueSeq ( int = 20 ) ; /構造函數(shù)（參數(shù)省略時，隊列空間默認最多容納19個元素） QueueSeq ( ) ; /析構函數(shù)（釋放動態(tài)存儲區(qū)的隊列空間） void enter ( T d ) ; /新元素d從隊尾進隊（rear 改變） T leave ( ) ; /隊頭元素出隊（front 改變，返回出隊的元素） T get ( int k ) ; /讀取并返回隊列中的第k號元素（隊頭元素編號為1。 front 不變） int length ( ) ; /求出隊列中元素的個數(shù) void print ( ) ; /輸出隊列中的所有元素（從隊頭元素開始輸出。front 不變） void empty ( ) ; /清空隊列（使隊列中無任何元素，即空隊） bool isEmpty ( ) ; /判斷隊列是否為空 bool isFull ( ) ; /判斷隊列是否已滿,【例】（順序循環(huán)隊列類模板QueueSeq的聲明，以 “queueseq.h” 為文件名保存。） #include template class QueueSeq /順序循環(huán)隊列類模板 QueueSeq 的聲明 int rear, front ; /隊尾、隊頭指針（對于順序隊列，就是隊尾、隊頭位置的下標） T *elements ; /隊列空間的首指針（隊列空間是T類型的數(shù)組，開在動態(tài)存儲區(qū)） int max ; /隊列空間最多可容納的元素個數(shù)+1（也就是隊列空間數(shù)組的長度） public: QueueSeq ( int = 20 ) ; /構造函數(shù)（參數(shù)省略時，隊列空間默認最多容納19個元素） QueueSeq ( ) ; /析構函數(shù)（釋放動態(tài)存儲區(qū)的隊列空間） void enter ( T d ) ; /新元素d從隊尾進隊（rear 改變） T leave ( ) ; /隊頭元素出隊（front 改變，返回出隊的元素） T get ( int k ) ; /讀取并返回隊列中的第k號元素（隊頭元素編號為1號。 front 不變） int length ( ) ; /求出隊列中元素的個數(shù) void print ( ) ; /輸出隊列中的所有元素（從隊頭元素開始輸出。front 不變） void empty ( ) ; /清空隊列（使隊列中無任何元素，即空隊） bool isEmpty ( ) ; /判斷隊列是否為空 bool isFull ( ) ; /判斷隊列是否已滿 ;,/構造函數(shù)（參數(shù)省略時，隊列空間默認最多容納19個元素） template QueueSeq : QueueSeq ( int n ) rear = front = 0 ; /隊尾rear等于隊頭front ，表示空棧，初始值都為0 elements = new T n ; /在堆區(qū)建立隊列空間（是T類型數(shù)組，首地址保存在elements中） max = n ; /隊列空間最多容納元素個數(shù)+1（對于順序隊列，就是隊列空間數(shù)組的長度） assert ( elements != 0 ) ; /分配不成功，則結束程序 /析構函數(shù)（釋放動態(tài)存儲區(qū)的隊列空間） template QueueSeq : QueueSeq ( ) delete elements ; /釋放動態(tài)存儲區(qū)的隊列空間 /新元素d從隊尾進隊（rear 改變） template void QueueSeq : enter ( T d ) assert ( ! isFull() ) ; /隊列滿，則結束程序 rear = ( rear+1 ) % max ; elements rear = d ; /隊尾指針先加1，元素再進隊 /隊頭元素出隊（front 改變，返回出隊的元素） template T QueueSeq : leave ( ) assert ( ! isEmpty() ) ; /隊列空，則結束程序 front = ( front+1 ) % max ; return elements front ; /隊頭指針先加1，隊頭元素離隊,/讀取并返回隊列中的第k號元素（隊頭元素編號為1。 front 不變） template T QueueSeq : get ( int k ) assert ( k=1 ,【例】（在文件s1.txt中，有若干學生成績資料。要求：以Student類作為順序隊列元素的數(shù)據類，對順序循環(huán)隊列類模板 QueueSeq 中的各成員函數(shù)進行測試。學生類 Student 的聲明 ，前面例子中已出現(xiàn)，并以 “student.h” 為文件名保存。 ） #include #include #include “queueseq.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_QS( 10 ) ; /定義學生隊列s_QS Student s ; int i = 0 ; cout s ,在s1.txt 中，學生資料： 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,順序循環(huán)隊列類的應用舉例,cout “s_QS隊列中元素個數(shù)=” s_QS.length( ) endl ; cout “s_QS隊列中2號元素是：n” s_QS.get( 2 ) ; cout “s_QS隊列中5號元素是：n” s_QS.get( 5 ) ; cout “s_QS隊列中元素個數(shù)=” s_QS.length( ) endl ; cout “現(xiàn)在前3位依次出隊：n” ; for ( i=1; ( i=3 ,鏈隊列類的設計采用面向對象程序設計,結點類模板 Node 的聲明：前面例子中已出現(xiàn)，并以 “node.h” 為文件名保存。 結點類模板 Node 的成員： 私有成員數(shù)據： 數(shù)據域： T data ; /T類型的變量data 鏈域： Node *next ; /next為指向下一個結點的指針 公有成員函數(shù)： Node ( ) ; /表頭結點的構造 Node ( T d ) ; /普通結點的構造 void set ( T d ) ; /將當前結點的數(shù)據域置為d T get ( ) ; /獲取并返回當前結點的數(shù)據域 void show ( ) ; /輸出當前結點的數(shù)據域 友元函數(shù)、友元類： friend class ListLink ; /友元類，鏈表類可以訪問結點類的私有、保護成員 friend class StackLink ; /友元類，鏈棧類可以訪問結點類的私有、保護成員 friend class QueueLink ; /友元類，鏈隊列類可以訪問結點類的私有、保護成員,鏈隊列類的設計采用面向對象程序設計,鏈隊列類模板 QueueLink 的設計： 私有成員數(shù)據： Node *rear , *front ; /指向隊尾結點、隊頭結點的指針 公有成員函數(shù)： QueueLink ( ) ; /構造函數(shù)（空隊列） QueueLink ( ) ; /析構函數(shù)（釋放隊列中各結點的動態(tài)空間） void enter ( T d ) ; /進隊（將d元素加入到隊尾，本操作 rear 將改變） T leave ( ) ; /出隊（隊頭元素離隊，并返回其值，本操作 front 將改變） T getFront ( ) ; /讀取并返回隊頭元素（本操作 front 不變） int length ( ) ; /求出隊列中元素的個數(shù) void print ( ) ; /輸出隊列中所有元素（本操作 front 、rear 不變） void empty ( ) ; /清空隊列（使隊列中無任何元素，即空隊列） bool isEmpty ( ) ; /判斷隊列是否為空,【例】（鏈隊列類模板 QueueLink 的定義，以 “queuelink.h” 為文件名保存。） #include template class QueueLink /鏈隊列類模板 QueueLink 的聲明 Node * rear , *front ; /指向隊尾結點、隊頭結點的指針 public: QueueLink ( ) rear = front = NULL ; /構造函數(shù)（空隊列） QueueLink ( ) empty( ) ; /析構函數(shù)（釋放隊列中各結點的動態(tài)空間） void enter ( T d ) ; /進隊（將d元素加入到隊尾，本操作 rear 將改變） T leave ( ) ; /出隊（隊頭元素離隊，并返回其值，本操作 front 將改變） T getFront ( ) /讀取并返回隊頭元素（本操作 front 不變） assert ( ! isEmpty( ) ) ; return front-data ; int length ( ) ; /求出隊列中元素的個數(shù) void print ( ) ; /輸出隊列中所有元素（本操作 front 、rear 不變） void empty ( ) ; /清空隊列（使隊列中無任何元素，即空隊列） bool isEmpty ( ) return front = NULL ; /判斷隊列是否為空 ;,/進隊（將d元素加入到隊尾，本操作 rear 將改變） template void QueueLink : enter ( T d ) Node *pnew = new Node ( d ) ; if ( front = NULL ) front = rear = pnew ; else rear-next = pnew ; rear = pnew ; /出隊（隊頭元素離隊，并返回其值，本操作 front 將改變） template T QueueLink : leave ( ) assert ( ! isEmpty( ) ) ; /隊列空，則結束程序 Node *temp = front ; front = front-next ; T da = temp-data ; delete temp ; return da ; ,/求出隊列中元素的個數(shù) template int QueueLink : length ( ) Node *temp = front ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /輸出隊列中所有元素（本操作 front 、rear 不變） template void QueueLink : print ( ) Node *temp = front ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空隊列（使隊列中無任何元素，即空隊列） template void QueueLink : empty ( ) Node * temp ; while ( front != NULL ) temp = front ; front = front -next ; delete temp ; ,鏈隊列類的應用舉例,【例】（在文件 s1.txt 中，有若干學生成績資料。要求：以Student類作為鏈隊列結點的數(shù)據類，對鏈隊列類模板 QueueLink 中的各成員函數(shù)進行測試。學生類Student的聲明 ，前面例子中已出現(xiàn)，并以 “student.h” 為文件名保存。 ） #include #include #include “node.h” #include “queuelink.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_QL ; /定義學生隊列s_QL Student s ; cout s ) s_QL.enter( s )