已閱讀5頁(yè),還剩37頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
C+程序設(shè)計(jì),第7章(3) 堆棧、隊(duì)列結(jié)構(gòu)、二叉樹(shù),主要內(nèi)容,堆棧結(jié)構(gòu)順序棧、鏈棧 順序棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì) 順序棧類(lèi)的應(yīng)用舉例 鏈棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì) 鏈棧類(lèi)的應(yīng)用舉例 隊(duì)列結(jié)構(gòu)順序隊(duì)列、鏈隊(duì)列 順序循環(huán)隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì) 順序循環(huán)隊(duì)列類(lèi)的應(yīng)用舉例 鏈隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì) 鏈隊(duì)列類(lèi)的應(yīng)用舉例 樹(shù)型結(jié)構(gòu)二叉樹(shù) 樹(shù)型結(jié)構(gòu)基于二叉樹(shù)的常用遍歷算法,堆棧結(jié)構(gòu)順序棧、鏈棧,堆棧的邏輯結(jié)構(gòu)是限制插入和刪除操作僅能在一端進(jìn)行的線(xiàn)性結(jié)構(gòu)。 棧頂與棧底:指線(xiàn)性表的兩端。 能進(jìn)行插入和刪除的一端稱(chēng)棧頂(top);而另一端稱(chēng)棧底(bottom)。 在棧頂插入新元素稱(chēng)進(jìn)棧(壓入);刪除元素稱(chēng)出棧(彈出)。 特殊線(xiàn)性表:是后進(jìn)先出(LIFO:Last In First Out)結(jié)構(gòu)的線(xiàn)性表。 進(jìn)棧時(shí):最先進(jìn)棧的在最下面,最后進(jìn)棧的在最上面。 出棧時(shí):最后進(jìn)棧的最先出棧,最先進(jìn)棧的最后出棧。 堆棧的物理結(jié)構(gòu)有連續(xù)、非連續(xù)存儲(chǔ)兩種結(jié)構(gòu),但邏輯功能基本相同。 連續(xù)存儲(chǔ)方式:順序棧。 非連續(xù)存儲(chǔ)方式:鏈棧。 堆棧結(jié)構(gòu)的應(yīng)用堆棧是最常用、最重要的數(shù)據(jù)結(jié)構(gòu)之一。 【例】 局部變量是存放在棧中。 表達(dá)式的優(yōu)先級(jí)處理可由棧來(lái)實(shí)現(xiàn)。 函數(shù)調(diào)用時(shí)參數(shù)的傳遞、函數(shù)值的返回也是由棧來(lái)實(shí)現(xiàn)。,堆棧結(jié)構(gòu)順序棧、鏈棧,順序棧的物理結(jié)構(gòu)連續(xù)存儲(chǔ) 可以隨機(jī)訪(fǎng)問(wèn)順序棧中的元素。 需要先開(kāi)一定量的內(nèi)存空間,使用時(shí)有可能溢出。 順序棧的操作執(zhí)行簡(jiǎn)單,速度快。 鏈棧的物理結(jié)構(gòu)非連續(xù)存儲(chǔ) 只能順序訪(fǎng)問(wèn)鏈棧中的元素。 隨用隨開(kāi)內(nèi)存空間,使用時(shí)不可能溢出。 鏈棧的操作執(zhí)行復(fù)雜(不斷地動(dòng)態(tài)分配),速度慢。,順序棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),順序棧類(lèi)模板 StackSeq 的設(shè)計(jì): 私有成員數(shù)據(jù): int top ; /棧頂指針(對(duì)于順序棧,棧頂位置就是棧頂元素的下標(biāo)) T *elements ; /??臻g首地址(對(duì)于順序棧,??臻g是T類(lèi)型的數(shù)組,開(kāi)在動(dòng)態(tài)存儲(chǔ)區(qū)) int max ; /??臻g中最多容納的元素個(gè)數(shù)(對(duì)順序棧,就是棧空間數(shù)組的長(zhǎng)度),順序棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì), 公有成員函數(shù): StackSeq ( int = 20 ) ; /構(gòu)造函數(shù)(參數(shù)省略時(shí),默認(rèn)棧空間中最多容納20個(gè)元素) StackSeq ( ) ; /析構(gòu)函數(shù)(釋放動(dòng)態(tài)存儲(chǔ)區(qū)的??臻g) void push ( T d ) ; /壓棧(將d元素壓入棧中,本操作 top 將改變) T pop ( ) ; /出棧(彈出棧頂元素并返回,本操作 top 將改變) T get ( int k ) ; /讀取并返回棧內(nèi)第k號(hào)元素(元素編號(hào)為第0top號(hào),本操作 top 不變) int length ( ) ; /求出棧內(nèi)元素的個(gè)數(shù) void print ( ) ; /輸出棧內(nèi)所有元素(將第0top號(hào)的元素依次輸出,本操作 top 不變) void empty ( ) ; /清空棧(使棧內(nèi)無(wú)任何元素,即空棧) bool isEmpty ( ) ; /判斷棧是否為空 bool isFull ( ) ; /判斷棧是否已滿(mǎn),【例】(順序棧類(lèi)模板 StackSeq 的定義,以 “stackseq.h” 為文件名保存。) #include template class StackSeq /順序棧類(lèi)模板 StackSeq 的聲明 int top ; /棧頂指針(對(duì)于順序棧,棧頂位置就是棧頂元素的下標(biāo)) T *elements ; /??臻g首地址(對(duì)于順序棧,棧空間是T類(lèi)型的數(shù)組,開(kāi)在動(dòng)態(tài)存儲(chǔ)區(qū)) int max ; /棧空間中最多容納的元素個(gè)數(shù)(對(duì)于順序棧,就是??臻g數(shù)組的長(zhǎng)度) public: StackSeq ( int = 20 ) ; /構(gòu)造函數(shù)(參數(shù)省略時(shí),默認(rèn)棧空間中最多容納20個(gè)元素) StackSeq ( ) ; /析構(gòu)函數(shù)(釋放動(dòng)態(tài)存儲(chǔ)區(qū)的??臻g) void push ( T d ) ; /壓棧(將d元素壓入棧中,本操作 top 將改變) T pop ( ) ; /出棧(彈出棧頂元素并返回,本操作 top 將改變) T get ( int k ) ; /讀取并返回棧內(nèi)第k號(hào)元素(元素編號(hào)為第0top號(hào),本操作 top 不變) int length ( ) ; /求出棧內(nèi)元素的個(gè)數(shù) void print ( ) ; /輸出棧內(nèi)所有元素(將第0top號(hào)的元素依次輸出,本操作 top 不變) void empty ( ) ; /清空棧(使棧內(nèi)無(wú)任何元素,即空棧) bool isEmpty ( ) ; /判斷棧是否為空 bool isFull ( ) ; /判斷棧是否已滿(mǎn) ;,/構(gòu)造函數(shù) template StackSeq : StackSeq ( int n ) top = -1 ; /棧頂 top 為 -1 時(shí),表示空棧 elements = new T n ; /在堆區(qū)建立??臻g(T類(lèi)型數(shù)組,首地址存放在elements中) max = n ; /??臻g中最多容納的元素個(gè)數(shù)(也就是??臻g數(shù)組的長(zhǎng)度) assert ( elements != 0 ) ; /分配不成功,則結(jié)束程序 /析構(gòu)函數(shù) template StackSeq : StackSeq ( ) delete elements ; /釋放動(dòng)態(tài)存儲(chǔ)區(qū)的棧空間 /壓棧 template void StackSeq : push ( T d ) assert ( ! isFull( ) ) ; /棧滿(mǎn),則結(jié)束程序 elements +top = d ; /棧頂指針先加1,元素d再進(jìn)棧 /出棧 template T StackSeq : pop ( ) assert ( ! isEmpty( ) ) ; /??眨瑒t結(jié)束程序 return elements top- ; /返回棧頂元素,然后棧頂指針減1,/讀取并返回棧內(nèi)第 k 號(hào)元素(棧內(nèi)元素編號(hào)為第 0 top 號(hào)) template T StackSeq : get ( int k ) assert ( k=0 ,順序棧類(lèi)的應(yīng)用舉例,【例】(在文件 s1.txt 中,有若干學(xué)生成績(jī)資料。要求:以Student類(lèi)作為順序棧元素的數(shù)據(jù)類(lèi),對(duì)順序棧類(lèi)模板 StackSeq 中的各成員函數(shù)進(jìn)行測(cè)試。學(xué)生類(lèi) 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 ) ; /定義學(xué)生棧s_SS Student s ; cout s ,在s1.txt 中,學(xué)生資料: 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國(guó) 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,cout “s_SS棧內(nèi)元素個(gè)數(shù)=” s_SS.length( ) endl ; cout “s_SS棧內(nèi)元素有:n” ; s_SS.print( ) ; cout “s_SS棧內(nèi)0號(hào)元素是:n” s_SS.get( 0 ) ; cout “s_SS棧內(nèi)3號(hào)元素是:n” s_SS.get( 3 ) ; cout “s_SS棧內(nèi)元素個(gè)數(shù)=” s_SS.length( ) endl ; cout “依次全部出棧 n” ; while ( !s_SS.isEmpty( ) ) cout s_SS.pop( ) ; cout “s_SS棧內(nèi)元素個(gè)數(shù)=” s_SS.length( ) endl ; cout s_SS.pop( ) ; ,【例】(使用順序棧類(lèi)模板 StackSeq ,建立整數(shù)棧i_SS、字符棧c_SS,隨機(jī)產(chǎn)生6個(gè)范圍在09之間的整數(shù)、6個(gè)范圍在AZ之間的字母,依次進(jìn)各棧,再出各棧。) #include #include #include “stackseq.h” void main ( ) StackSeq i_SS( 6 ) ; StackSeq c_SS( 8 ) ; cout “依次進(jìn)棧 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ù)棧已滿(mǎn)!n” ; else cout“整數(shù)棧未滿(mǎn),可再壓入” 6-i_SS.length() “個(gè)!n”; if ( c_SS.isFull() ) cout “字符棧已滿(mǎn)!n” ; else cout“字符棧未滿(mǎn),可再壓入” 8-c_SS.length() “個(gè)!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” ; ,【例】(棧結(jié)構(gòu)應(yīng)用于表達(dá)式優(yōu)先級(jí)的實(shí)現(xiàn)。若有 + - * / 運(yùn)算符和等號(hào)=組成的算術(shù)表達(dá)式,只有兩個(gè)優(yōu)先級(jí)( 先 */ 后 +- )。設(shè): A+B*C-D/E=; 實(shí)現(xiàn)運(yùn)算符的優(yōu)先級(jí)。) 【算法】定義兩個(gè)棧:操作數(shù)棧 n_S,運(yùn)算符棧 c_S。從左往右掃描算術(shù)表達(dá)式,遇到操作數(shù),則壓入n_S棧;遇到運(yùn)算符,則與c_S棧棧頂運(yùn)算符比較優(yōu)先級(jí),若新運(yùn)算符優(yōu)先級(jí)高,或此時(shí)c_S???,則壓入c_S棧;否則將c_S棧棧頂運(yùn)算符出棧,與n_S棧出棧的兩個(gè)操作數(shù)進(jìn)行運(yùn)算,結(jié)果壓入n_S棧,再將新運(yùn)算符壓入c_S棧。繼續(xù)掃描,直至遇到號(hào),掃描結(jié)束。兩棧的元素繼續(xù)按前面規(guī)則出棧運(yùn)算。,鏈棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),結(jié)點(diǎn)類(lèi)模板 Node 的聲明:前面例子中已出現(xiàn),并以 “node.h” 為文件名保存。 結(jié)點(diǎn)類(lèi)模板 Node 的成員: 私有成員數(shù)據(jù): 數(shù)據(jù)域: T data ; /T類(lèi)型的變量data 鏈域: Node *next ; /next為指向下一個(gè)結(jié)點(diǎn)的指針 公有成員函數(shù): Node ( ) ; /表頭結(jié)點(diǎn)的構(gòu)造 Node ( T d ) ; /普通結(jié)點(diǎn)的構(gòu)造 void set ( T d ) ; /將當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域置為d T get ( ) ; /獲取并返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域 void show ( ) ; /輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域 友元函數(shù)、友元類(lèi): friend class ListLink ; /友元類(lèi),鏈表類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員 friend class StackLink ; /友元類(lèi),鏈棧類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員 friend class QueueLink ; /友元類(lèi),鏈隊(duì)列類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員,鏈棧類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),鏈棧類(lèi)模板 StackLink 的設(shè)計(jì): 私有成員數(shù)據(jù): Node * top ; 公有成員函數(shù): StackLink ( ) ; /構(gòu)造函數(shù)(空棧) StackLink ( ) ; /析構(gòu)函數(shù)(釋放棧內(nèi)各結(jié)點(diǎn)的動(dòng)態(tài)空間) void push ( T d ) ; /壓棧(將d元素壓入棧中,本操作 top 將改變) T pop ( ) ; /出棧(彈出棧頂元素并返回,本操作 top 將改變) T getTop ( ) ; /讀取并返回棧頂元素(本操作 top 不變) int length ( ) ; /求出棧內(nèi)元素的個(gè)數(shù) void print ( ) ; /輸出棧內(nèi)所有元素(本操作 top 不變) void empty ( ) ; /清空棧(使棧內(nèi)無(wú)任何元素,即空棧) bool isEmpty ( ) ; /判斷棧是否為空,【例】(鏈棧類(lèi)模板 StackLink 的定義,以 “stacklink.h” 為文件名保存。) #include template class StackLink /鏈棧類(lèi)模板 StackLink 的聲明 Node * top ; /指向棧頂結(jié)點(diǎn)的指針 public: StackLink ( ) top = NULL ; /構(gòu)造函數(shù)(空棧) StackLink ( ) empty( ) ; /析構(gòu)函數(shù)(釋放棧內(nèi)各結(jié)點(diǎn)的動(dòng)態(tài)空間) void push ( T d ) ; /壓棧(將d元素壓入棧中,本操作 top 將改變) T pop ( ) ; /出棧(彈出棧頂元素并返回,本操作 top 將改變) T getTop ( ) /讀取并返回棧頂元素(本操作 top 不變) assert ( ! isEmpty( ) ) ; return top-data ; int length ( ) ; /求出棧內(nèi)元素的個(gè)數(shù) void print ( ) ; /輸出棧內(nèi)所有元素(本操作 top 不變) void empty ( ) ; /清空棧(使棧內(nèi)無(wú)任何元素,即空棧) 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( ) ) ; /???,則結(jié)束程序 Node *temp = top ; top = top-next ; T da = temp-data ; delete temp ; return da ; ,/求出棧內(nèi)元素的個(gè)數(shù) template int StackLink : length ( ) Node *temp = top ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /輸出棧內(nèi)所有元素(本操作 top 不變) template void StackLink : print ( ) Node *temp = top ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空棧(使棧內(nèi)無(wú)任何元素,即空棧) template void StackLink : empty ( ) Node * temp ; while ( top != NULL ) temp = top ; top = top-next ; delete temp ; ,鏈棧類(lèi)的應(yīng)用舉例,【例】(在文件 s1.txt 中,有若干學(xué)生成績(jī)資料。要求:以Student類(lèi)作為鏈棧結(jié)點(diǎn)的數(shù)據(jù)類(lèi),對(duì)鏈棧類(lèi)模板 StackLink 中的各成員函數(shù)進(jìn)行測(cè)試。學(xué)生類(lèi) 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 ; /定義學(xué)生棧s_SL Student s ; cout s ) s_SL.push( s ) ; inf.close( ) ;,在s1.txt 中,學(xué)生資料: 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國(guó) 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,cout “s_SL棧內(nèi)元素個(gè)數(shù)=” s_SL.length( ) endl ; cout “s_SL棧內(nèi)元素有:n” ; s_SL.print( ) ; cout “s_SL棧頂元素是:n” s_SL.getTop( ) ; cout “s_SL棧內(nèi)元素個(gè)數(shù)=” s_SL.length( ) endl ; cout “依次全部出棧 n” ; while ( !s_SL.isEmpty( ) ) cout s_SL.pop( ) ; cout “s_SL棧內(nèi)元素個(gè)數(shù)=” s_SL.length( ) endl ; cout s_SL.pop( ) ; ,隊(duì)列結(jié)構(gòu)順序隊(duì)列、鏈隊(duì)列,隊(duì)列的邏輯結(jié)構(gòu)是限制插入和刪除操作分別在兩端進(jìn)行的線(xiàn)性結(jié)構(gòu)。 隊(duì)頭與隊(duì)尾:指線(xiàn)性表的兩端。 能進(jìn)行插入的一端稱(chēng)隊(duì)尾(rear);能進(jìn)行刪除的一端稱(chēng)隊(duì)頭(front)。 在隊(duì)尾加入新元素稱(chēng)進(jìn)隊(duì);在隊(duì)頭刪除元素稱(chēng)出隊(duì)。 特殊線(xiàn)性表:是先進(jìn)先出( FIFO: First In First Out)結(jié)構(gòu)的線(xiàn)性表。 進(jìn)隊(duì)時(shí):隨隊(duì)尾加入元素,隊(duì)尾指針(rear)不斷向后移。 出隊(duì)時(shí):隨隊(duì)頭元素的出隊(duì),隊(duì)頭指針(front)也不斷向后移。 即:進(jìn)隊(duì)與出隊(duì)都是隊(duì)尾和隊(duì)頭指針的位置在變。 隊(duì)列的物理結(jié)構(gòu)有連續(xù)、非連續(xù)存儲(chǔ)兩種結(jié)構(gòu),但邏輯功能基本相同。 連續(xù)存儲(chǔ)方式:順序隊(duì)列。 非連續(xù)存儲(chǔ)方式:鏈隊(duì)列。 隊(duì)列結(jié)構(gòu)的應(yīng)用隊(duì)列是最常用、最重要的數(shù)據(jù)結(jié)構(gòu)之一。 【例】在Windows操作系統(tǒng)中,使用了很多消息等待隊(duì)列,以實(shí)現(xiàn)先來(lái)的先服務(wù)。,順序隊(duì)列的物理結(jié)構(gòu)連續(xù)存儲(chǔ) 可以隨機(jī)訪(fǎng)問(wèn)順序隊(duì)列中的元素。 需要先開(kāi)一定量的內(nèi)存空間,使用時(shí)有可能溢出。 順序隊(duì)列的操作執(zhí)行簡(jiǎn)單,速度快。 鏈隊(duì)列的物理結(jié)構(gòu)非連續(xù)存儲(chǔ) 只能順序訪(fǎng)問(wèn)鏈隊(duì)列中的元素。 隨用隨開(kāi)內(nèi)存空間,使用時(shí)不可能溢出。 鏈隊(duì)列的操作執(zhí)行復(fù)雜(不斷地動(dòng)態(tài)分配),速度慢。,隊(duì)列結(jié)構(gòu)順序隊(duì)列、鏈隊(duì)列,順序循環(huán)隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),對(duì)順序隊(duì)列的分析: 空隊(duì)時(shí),隊(duì)頭指針front(下標(biāo))和隊(duì)尾指針rear(下標(biāo))重疊在一起,都為-1。進(jìn)隊(duì)時(shí)隨著隊(duì)尾加入元素,隊(duì)尾指針(rear)不斷加 1 移動(dòng);出隊(duì)時(shí)隨著隊(duì)頭元素的出隊(duì),隊(duì)頭指針(front)也不斷加 1 移動(dòng)。進(jìn)隊(duì)和出隊(duì)都是隊(duì)尾和隊(duì)頭指針的位置在變(若要位置不變,移動(dòng)元素工作量太大) ,最后造成分配給隊(duì)列的存儲(chǔ)空間前端不能再被利用,而后端逐漸產(chǎn)生溢出。,順序循環(huán)隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),順序循環(huán)隊(duì)列:將順序隊(duì)列做成一個(gè)邏輯上的循環(huán)隊(duì)列;而這樣做會(huì)使得:空隊(duì)時(shí)rear = front,滿(mǎn)隊(duì)時(shí) rear = front;為了區(qū)分空隊(duì)與滿(mǎn)隊(duì),在隊(duì)列中少放一個(gè)元素,即隊(duì)列中只剩下一個(gè)空位置時(shí)就算滿(mǎn)隊(duì),以此作為標(biāo)志來(lái)區(qū)分空隊(duì)與滿(mǎn)隊(duì)。,順序循環(huán)隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),順序循環(huán)隊(duì)列類(lèi)模板 QueueSeq 的設(shè)計(jì): 私有成員數(shù)據(jù): int rear, front ; /隊(duì)尾、隊(duì)頭指針(對(duì)于順序隊(duì)列,就是隊(duì)尾、隊(duì)頭位置的下標(biāo)) T *elements ; /隊(duì)列空間的首地址(隊(duì)列空間是T類(lèi)型的數(shù)組,開(kāi)在動(dòng)態(tài)存儲(chǔ)區(qū)) int max ; /隊(duì)列空間最多可容納的元素個(gè)數(shù)+1(也就是隊(duì)列空間數(shù)組的長(zhǎng)度) 公有成員函數(shù): QueueSeq ( int = 20 ) ; /構(gòu)造函數(shù)(參數(shù)省略時(shí),隊(duì)列空間默認(rèn)最多容納19個(gè)元素) QueueSeq ( ) ; /析構(gòu)函數(shù)(釋放動(dòng)態(tài)存儲(chǔ)區(qū)的隊(duì)列空間) void enter ( T d ) ; /新元素d從隊(duì)尾進(jìn)隊(duì)(rear 改變) T leave ( ) ; /隊(duì)頭元素出隊(duì)(front 改變,返回出隊(duì)的元素) T get ( int k ) ; /讀取并返回隊(duì)列中的第k號(hào)元素(隊(duì)頭元素編號(hào)為1。 front 不變) int length ( ) ; /求出隊(duì)列中元素的個(gè)數(shù) void print ( ) ; /輸出隊(duì)列中的所有元素(從隊(duì)頭元素開(kāi)始輸出。front 不變) void empty ( ) ; /清空隊(duì)列(使隊(duì)列中無(wú)任何元素,即空隊(duì)) bool isEmpty ( ) ; /判斷隊(duì)列是否為空 bool isFull ( ) ; /判斷隊(duì)列是否已滿(mǎn),【例】(順序循環(huán)隊(duì)列類(lèi)模板QueueSeq的聲明,以 “queueseq.h” 為文件名保存。) #include template class QueueSeq /順序循環(huán)隊(duì)列類(lèi)模板 QueueSeq 的聲明 int rear, front ; /隊(duì)尾、隊(duì)頭指針(對(duì)于順序隊(duì)列,就是隊(duì)尾、隊(duì)頭位置的下標(biāo)) T *elements ; /隊(duì)列空間的首指針(隊(duì)列空間是T類(lèi)型的數(shù)組,開(kāi)在動(dòng)態(tài)存儲(chǔ)區(qū)) int max ; /隊(duì)列空間最多可容納的元素個(gè)數(shù)+1(也就是隊(duì)列空間數(shù)組的長(zhǎng)度) public: QueueSeq ( int = 20 ) ; /構(gòu)造函數(shù)(參數(shù)省略時(shí),隊(duì)列空間默認(rèn)最多容納19個(gè)元素) QueueSeq ( ) ; /析構(gòu)函數(shù)(釋放動(dòng)態(tài)存儲(chǔ)區(qū)的隊(duì)列空間) void enter ( T d ) ; /新元素d從隊(duì)尾進(jìn)隊(duì)(rear 改變) T leave ( ) ; /隊(duì)頭元素出隊(duì)(front 改變,返回出隊(duì)的元素) T get ( int k ) ; /讀取并返回隊(duì)列中的第k號(hào)元素(隊(duì)頭元素編號(hào)為1號(hào)。 front 不變) int length ( ) ; /求出隊(duì)列中元素的個(gè)數(shù) void print ( ) ; /輸出隊(duì)列中的所有元素(從隊(duì)頭元素開(kāi)始輸出。front 不變) void empty ( ) ; /清空隊(duì)列(使隊(duì)列中無(wú)任何元素,即空隊(duì)) bool isEmpty ( ) ; /判斷隊(duì)列是否為空 bool isFull ( ) ; /判斷隊(duì)列是否已滿(mǎn) ;,/構(gòu)造函數(shù)(參數(shù)省略時(shí),隊(duì)列空間默認(rèn)最多容納19個(gè)元素) template QueueSeq : QueueSeq ( int n ) rear = front = 0 ; /隊(duì)尾rear等于隊(duì)頭front ,表示空棧,初始值都為0 elements = new T n ; /在堆區(qū)建立隊(duì)列空間(是T類(lèi)型數(shù)組,首地址保存在elements中) max = n ; /隊(duì)列空間最多容納元素個(gè)數(shù)+1(對(duì)于順序隊(duì)列,就是隊(duì)列空間數(shù)組的長(zhǎng)度) assert ( elements != 0 ) ; /分配不成功,則結(jié)束程序 /析構(gòu)函數(shù)(釋放動(dòng)態(tài)存儲(chǔ)區(qū)的隊(duì)列空間) template QueueSeq : QueueSeq ( ) delete elements ; /釋放動(dòng)態(tài)存儲(chǔ)區(qū)的隊(duì)列空間 /新元素d從隊(duì)尾進(jìn)隊(duì)(rear 改變) template void QueueSeq : enter ( T d ) assert ( ! isFull() ) ; /隊(duì)列滿(mǎn),則結(jié)束程序 rear = ( rear+1 ) % max ; elements rear = d ; /隊(duì)尾指針先加1,元素再進(jìn)隊(duì) /隊(duì)頭元素出隊(duì)(front 改變,返回出隊(duì)的元素) template T QueueSeq : leave ( ) assert ( ! isEmpty() ) ; /隊(duì)列空,則結(jié)束程序 front = ( front+1 ) % max ; return elements front ; /隊(duì)頭指針先加1,隊(duì)頭元素離隊(duì),/讀取并返回隊(duì)列中的第k號(hào)元素(隊(duì)頭元素編號(hào)為1。 front 不變) template T QueueSeq : get ( int k ) assert ( k=1 ,【例】(在文件s1.txt中,有若干學(xué)生成績(jī)資料。要求:以Student類(lèi)作為順序隊(duì)列元素的數(shù)據(jù)類(lèi),對(duì)順序循環(huán)隊(duì)列類(lèi)模板 QueueSeq 中的各成員函數(shù)進(jìn)行測(cè)試。學(xué)生類(lèi) 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 ) ; /定義學(xué)生隊(duì)列s_QS Student s ; int i = 0 ; cout s ,在s1.txt 中,學(xué)生資料: 61001 方飛飛 96 61002 鞏浩文 72 61003 程可國(guó) 69 61004 麥宏巖 33 61005 文一奇 97 61006 王碧方 99,順序循環(huán)隊(duì)列類(lèi)的應(yīng)用舉例,cout “s_QS隊(duì)列中元素個(gè)數(shù)=” s_QS.length( ) endl ; cout “s_QS隊(duì)列中2號(hào)元素是:n” s_QS.get( 2 ) ; cout “s_QS隊(duì)列中5號(hào)元素是:n” s_QS.get( 5 ) ; cout “s_QS隊(duì)列中元素個(gè)數(shù)=” s_QS.length( ) endl ; cout “現(xiàn)在前3位依次出隊(duì):n” ; for ( i=1; ( i=3 ,鏈隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),結(jié)點(diǎn)類(lèi)模板 Node 的聲明:前面例子中已出現(xiàn),并以 “node.h” 為文件名保存。 結(jié)點(diǎn)類(lèi)模板 Node 的成員: 私有成員數(shù)據(jù): 數(shù)據(jù)域: T data ; /T類(lèi)型的變量data 鏈域: Node *next ; /next為指向下一個(gè)結(jié)點(diǎn)的指針 公有成員函數(shù): Node ( ) ; /表頭結(jié)點(diǎn)的構(gòu)造 Node ( T d ) ; /普通結(jié)點(diǎn)的構(gòu)造 void set ( T d ) ; /將當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域置為d T get ( ) ; /獲取并返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域 void show ( ) ; /輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域 友元函數(shù)、友元類(lèi): friend class ListLink ; /友元類(lèi),鏈表類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員 friend class StackLink ; /友元類(lèi),鏈棧類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員 friend class QueueLink ; /友元類(lèi),鏈隊(duì)列類(lèi)可以訪(fǎng)問(wèn)結(jié)點(diǎn)類(lèi)的私有、保護(hù)成員,鏈隊(duì)列類(lèi)的設(shè)計(jì)采用面向?qū)ο蟪绦蛟O(shè)計(jì),鏈隊(duì)列類(lèi)模板 QueueLink 的設(shè)計(jì): 私有成員數(shù)據(jù): Node *rear , *front ; /指向隊(duì)尾結(jié)點(diǎn)、隊(duì)頭結(jié)點(diǎn)的指針 公有成員函數(shù): QueueLink ( ) ; /構(gòu)造函數(shù)(空隊(duì)列) QueueLink ( ) ; /析構(gòu)函數(shù)(釋放隊(duì)列中各結(jié)點(diǎn)的動(dòng)態(tài)空間) void enter ( T d ) ; /進(jìn)隊(duì)(將d元素加入到隊(duì)尾,本操作 rear 將改變) T leave ( ) ; /出隊(duì)(隊(duì)頭元素離隊(duì),并返回其值,本操作 front 將改變) T getFront ( ) ; /讀取并返回隊(duì)頭元素(本操作 front 不變) int length ( ) ; /求出隊(duì)列中元素的個(gè)數(shù) void print ( ) ; /輸出隊(duì)列中所有元素(本操作 front 、rear 不變) void empty ( ) ; /清空隊(duì)列(使隊(duì)列中無(wú)任何元素,即空隊(duì)列) bool isEmpty ( ) ; /判斷隊(duì)列是否為空,【例】(鏈隊(duì)列類(lèi)模板 QueueLink 的定義,以 “queuelink.h” 為文件名保存。) #include template class QueueLink /鏈隊(duì)列類(lèi)模板 QueueLink 的聲明 Node * rear , *front ; /指向隊(duì)尾結(jié)點(diǎn)、隊(duì)頭結(jié)點(diǎn)的指針 public: QueueLink ( ) rear = front = NULL ; /構(gòu)造函數(shù)(空隊(duì)列) QueueLink ( ) empty( ) ; /析構(gòu)函數(shù)(釋放隊(duì)列中各結(jié)點(diǎn)的動(dòng)態(tài)空間) void enter ( T d ) ; /進(jìn)隊(duì)(將d元素加入到隊(duì)尾,本操作 rear 將改變) T leave ( ) ; /出隊(duì)(隊(duì)頭元素離隊(duì),并返回其值,本操作 front 將改變) T getFront ( ) /讀取并返回隊(duì)頭元素(本操作 front 不變) assert ( ! isEmpty( ) ) ; return front-data ; int length ( ) ; /求出隊(duì)列中元素的個(gè)數(shù) void print ( ) ; /輸出隊(duì)列中所有元素(本操作 front 、rear 不變) void empty ( ) ; /清空隊(duì)列(使隊(duì)列中無(wú)任何元素,即空隊(duì)列) bool isEmpty ( ) return front = NULL ; /判斷隊(duì)列是否為空 ;,/進(jìn)隊(duì)(將d元素加入到隊(duì)尾,本操作 rear 將改變) template void QueueLink : enter ( T d ) Node *pnew = new Node ( d ) ; if ( front = NULL ) front = rear = pnew ; else rear-next = pnew ; rear = pnew ; /出隊(duì)(隊(duì)頭元素離隊(duì),并返回其值,本操作 front 將改變) template T QueueLink : leave ( ) assert ( ! isEmpty( ) ) ; /隊(duì)列空,則結(jié)束程序 Node *temp = front ; front = front-next ; T da = temp-data ; delete temp ; return da ; ,/求出隊(duì)列中元素的個(gè)數(shù) template int QueueLink : length ( ) Node *temp = front ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /輸出隊(duì)列中所有元素(本操作 front 、rear 不變) template void QueueLink : print ( ) Node *temp = front ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空隊(duì)列(使隊(duì)列中無(wú)任何元素,即空隊(duì)列) template void QueueLink : empty ( ) Node * temp ; while ( front != NULL ) temp = front ; front = front -next ; delete temp ; ,鏈隊(duì)列類(lèi)的應(yīng)用舉例,【例】(在文件 s1.txt 中,有若干學(xué)生成績(jī)資料。要求:以Student類(lèi)作為鏈隊(duì)列結(jié)點(diǎn)的數(shù)據(jù)類(lèi),對(duì)鏈隊(duì)列類(lèi)模板 QueueLink 中的各成員函數(shù)進(jìn)行測(cè)試。學(xué)生類(lèi)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 ; /定義學(xué)生隊(duì)列s_QL Student s ; cout s ) s_QL.enter( s )
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《實(shí)驗(yàn)室消毒滅菌》課件
- 《病媒生物控制》課件
- 單位管理制度合并選集人事管理篇
- 《倉(cāng)庫(kù)管理的認(rèn)識(shí)》課件
- 單位管理制度分享合集【人事管理篇】十篇
- 單位管理制度范例匯編【人事管理】十篇
- 做情緒的主人 高一上學(xué)期心理健康教育課
- 2024年農(nóng)業(yè)年終工作總結(jié)
- 2024年協(xié)輔警個(gè)人總結(jié)
- 《山東膠州秧歌》課件
- 有害生物防制員技能競(jìng)賽理論考試題庫(kù)500題(含答案)
- HIV陽(yáng)性孕產(chǎn)婦全程管理專(zhuān)家共識(shí)2024年版解讀
- 小學(xué)體育跨學(xué)科主題學(xué)習(xí)教學(xué)設(shè)計(jì):小小志愿軍
- 附件2:慢病管理中心評(píng)審實(shí)施細(xì)則2024年修訂版
- 《ISO56001-2024創(chuàng)新管理體系 - 要求》之4:“4組織環(huán)境-確定創(chuàng)新管理體系的范圍”解讀和應(yīng)用指導(dǎo)材料(雷澤佳編制-2024)
- 2024-2030年中國(guó)散熱產(chǎn)業(yè)運(yùn)營(yíng)效益及投資前景預(yù)測(cè)報(bào)告
- 和父親斷絕聯(lián)系協(xié)議書(shū)范本
- 2024時(shí)事政治考試題庫(kù)(100題)
- 2024地理知識(shí)競(jìng)賽試題
- 【新教材】統(tǒng)編版(2024)七年級(jí)上冊(cè)語(yǔ)文期末復(fù)習(xí)課件129張
- 欽州市浦北縣2022-2023學(xué)年七年級(jí)上學(xué)期期末語(yǔ)文試題
評(píng)論
0/150
提交評(píng)論