C和C++知識精粹匯總

1、一個由c/C+ 編譯的程序占用的內(nèi)存分為以下幾個部分：1.棧區(qū)（stack）由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。2.堆區(qū)（heap） 一般由程序員分配釋放，若程序員不釋放， 程序結(jié)束時可能由OS回收。注意它與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，分配方式倒是類似于鏈表。3.全局區(qū)（靜態(tài)區(qū)） （ static），全局變量和靜態(tài)變量的存儲是放在一塊的，初始化的全局變量和靜態(tài)變量在一塊區(qū)域， 未初始化的全局變量和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域。 - 程序結(jié)束后由系統(tǒng)釋放。4.文字常量區(qū)常量字符串就是放在這里的。程序結(jié)束后由系統(tǒng)釋放。5.程序代碼區(qū)存放函數(shù)體

2、的二進(jìn)制代碼。C 中的內(nèi)存管理：1、內(nèi)存分配方式內(nèi)存分配方式有三種：（ 1）從靜態(tài)存儲區(qū)域分配。內(nèi)存在程序編譯的時候就已經(jīng)分配好，這塊內(nèi)存在程序的整個運行期間都存在。例如全局變量，static變量。（2）在棧上創(chuàng)建。在執(zhí)行函數(shù)時，函數(shù)內(nèi)局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放。棧內(nèi)存分配運算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限。（ 3） 從堆上分配，亦稱動態(tài)內(nèi)存分配。程序在運行的時候用malloc 或 new 申請任意多少的內(nèi)存，程序員自己負(fù)責(zé)在何時用free 或 delete釋放內(nèi)存。動態(tài)內(nèi)存的生存期由我們決定，使用非常靈活，但問題也最多。

3、常用解決辦法是，在使用內(nèi)存之前檢查指針是否為NULL 。如果指針p 是函數(shù)的參數(shù)， 那么在函數(shù)的入口處用assert(p!=NULL) 進(jìn)行檢查。如果是用malloc 或 new 來申請內(nèi)存，應(yīng)該用if(p=NULL)或if(p!=NULL)進(jìn)行防錯處理。注意不要返回指向“棧內(nèi)存”的“指針”或者“引用”，因為該內(nèi)存在函數(shù)體結(jié)束時被自動銷毀。動態(tài)內(nèi)存的申請與釋放必須配對，防止內(nèi)存泄漏。用 free 或 delete 釋放了內(nèi)存之后，立即將指針設(shè)置為NULL ，防止產(chǎn)生“野指針” 。注意當(dāng)數(shù)組作為函數(shù)的參數(shù)進(jìn)行傳遞時，該數(shù)組自動退化為同類型的指針。所以， 指針變量在創(chuàng)建的同時應(yīng)當(dāng)被初始化，要么將指

4、針設(shè)置為NULL ，要么讓它指向合法的內(nèi)存。既然 new/delete 的功能完全覆蓋了 malloc/free ，為什么 C+ 不把 malloc/free 淘汰出局呢？這是因為 C+ 程序經(jīng)常要調(diào)用 C 函數(shù)，而 C 程序只能用 malloc/free 管理動態(tài)內(nèi)存。C+ 語言代碼檢查工具PC-Lint 簡介概述PC-Lint 是一個歷史悠久，功能異常強勁的靜態(tài)代碼檢測工具。它的使用歷史可以追溯到計算機編程的遠(yuǎn)古時代（30 多年以前）。經(jīng)過這么多年的發(fā)展，它不但能夠監(jiān)測出許多語法邏輯上的隱患， 而且也能夠有效地幫你提出許多程序在空間利用、運行效率上的改進(jìn)點，在很多專業(yè)級的軟件公司，比如Mi

5、crosoft ， PC-Lint檢查無錯誤無警告是代碼首先要過的第一關(guān)，我個人覺得，對于小公司和個人開發(fā)而言，PC-Lint 也非常重要，因為基于開發(fā)成本考慮，小公司和個人往往不能拿出很多很全面的測試，這時候，PC-Lint 的強勁功能可以很好地提高軟件的質(zhì)量。功能1) PC-Lint 是一種靜態(tài)代碼檢測工具，可以說， PC-LINT 是一種更加嚴(yán)格的編譯器，不僅可以象普通編譯器那樣檢查出一般的語法錯誤，還可以檢查出那些雖然完全合乎語法要求，但很可能是潛在的、不易發(fā)現(xiàn)的錯誤。2) PC-lint 不但可以檢測單個文件，也可以從整個項目的角度來檢測問題，因為 C 語言編譯器固有的單個編譯，這些

6、問題在編譯器環(huán)境下很難被檢測，而 PC-Lint 在檢查當(dāng)前文件的同時還會檢查所有與之相關(guān)的文件，可想而知，它會對我們有很大的幫助。3) PC-lint支持幾乎所有流行的編輯環(huán)境和編譯器，比如Borland C+ 從 1.x到5.x 各個版本、 Borland C+ Build 、 GCC、 VC ， VC.net 、watcom C/C+ 、 Source insight、 intel C/C+ 等等，也支持 16/32/64 的平臺環(huán)境。4) 支持Scott Meyes 的名著（Effective C+/More Effective C+）中說描述的各種提高效率和防止錯誤的方法。結(jié)構(gòu)體及成

7、員數(shù)據(jù)對齊：結(jié)構(gòu)的存儲的特殊處理確實提高CPU 存儲變量的速度，但是有時候也帶來了一些麻煩，我們也屏蔽掉變量默認(rèn)的對齊方式，自己可以設(shè)定變量的對齊方式。C 中提供了 #pragma pack(n)來設(shè)定變量以n 字節(jié)對齊方式。 n 字節(jié)對齊就是說變量存放的起始地址的偏移量有兩種情況：第一、如果n 大于等于該變量所占用的字節(jié)數(shù)，那么偏移量必須滿足默認(rèn)的對齊方式，第二、如果n 小于該變量的類型所占用的字節(jié)數(shù)，那么偏移量為n 的倍數(shù)，不用滿足默認(rèn)的對齊方式。結(jié)構(gòu)的總大小也有個約束條件，分下面兩種情況：如果n 大于所有成員變量類型所占用的字節(jié)數(shù)，那么結(jié)構(gòu)的總大小必須為占用空間最大的變量占用的空間數(shù)的倍

8、數(shù)；否則必須為n 的倍數(shù)。下面舉例說明其用法。#pragma pack(push) /保存對齊狀態(tài)#pragma pack(4)/ 設(shè)定為 4 字節(jié)對齊struct testchar m1;double m4;int m3;#pragma pack(pop)/ 恢復(fù)對齊狀態(tài)以上結(jié)構(gòu)的大小為16，下面分析其存儲情況，首先為m1 分配空間，其偏移量為0，滿足我們自己設(shè)定的對齊方式（4 字節(jié)對齊），m1 占用 1 個字節(jié)。接著開始為m4 分配空間，這時其偏移量為1，需要補足3 個字節(jié)，這樣使偏移量滿足為n=4 的倍數(shù)（因為sizeof(double) 大于 n）,m4 占用 8 個字節(jié)。接著為m3

9、分配空間，這時其偏移量為 12，滿足為 4 的倍數(shù)， m3 占用 4 個字節(jié)。這時已經(jīng)為所有成員變量分配了空間，共分配了 16 個字節(jié)， 滿足為 n 的倍數(shù)。 如果把上面的 #pragma pack(4)改為 #pragma pack(16)，那么我們可以得到結(jié)構(gòu)的大小為 24。（請讀者自己分析）二、 #pragma pack(n) 對齊用法詳解什么是對齊，以及為什么要對齊：現(xiàn)代計算機中內(nèi)存空間都是按照byte 劃分的，從理論上講似乎對任何類型的變量的訪問可以從任何地址開始，但實際情況是在訪問特定變量的時候經(jīng)常在特定的內(nèi)存地址訪問，這就需要各類型數(shù)據(jù)按照一定的規(guī)則在空間上排列，而不是順序的一個

10、接一個的排放，這就是對齊。對齊的作用和原因：各個硬件平臺對存儲空間的處理上有很大的不同。一些平臺對某些特定類型的數(shù)據(jù)只能從某些特定地址開始存取。其他平臺可能沒有這種情況，但是最常見的是如果不按照適合其平臺要求對數(shù)據(jù)存放進(jìn)行對齊， 會在存取效率上帶來損失。比如有些平臺每次讀都是從偶地址開始，如果一個int 型（假設(shè)為 32 位系統(tǒng)） 如果存放在偶地址開始的地方，那么一個讀周期就可以讀出，而如果存放在奇地址開始的地方，就可能會需要2 個讀周期， 并對兩次讀出的結(jié)果的高低字節(jié)進(jìn)行拼湊才能得到該int 數(shù)據(jù)。顯然在讀取效率上下降很多。這也是空間和時間的博弈。對齊的實現(xiàn)通常，我們寫程序的時候，不需要考慮

11、對齊問題。編譯器會替我們選擇時候目標(biāo)平臺的對齊策略。當(dāng)然，我們也可以通知給編譯器傳遞預(yù)編譯指令而改變對指定數(shù)據(jù)的對齊方法。但是，正因為我們一般不需要關(guān)心這個問題，所以因為編輯器對數(shù)據(jù)存放做了對齊， 而我們不了解的話，常常會對一些問題感到迷惑。最常見的就是struct 數(shù)據(jù)結(jié)構(gòu)的sizeof 結(jié)果，出乎意料。為此，我們需要對對齊算法所了解。作用：指定結(jié)構(gòu)體、聯(lián)合以及類成員的packing alignment;語法： #pragma pack( show | push | pop , identifier, n )說明： 1，pack 提供數(shù)據(jù)聲明級別的控制，對定義不起作用；2，調(diào)用 pack 時

12、不指定參數(shù)，n 將被設(shè)成默認(rèn)值； 3，一旦改變數(shù)據(jù)類型的alignment，直接效果就是占用memory 的減少， 但是 performance 會下降；語法具體分析： 1，show：可選參數(shù)；顯示當(dāng)前packing aligment 的字節(jié)數(shù)，以warning message的形式被顯示；2，push：可選參數(shù)；將當(dāng)前指定的packing alignment 數(shù)值進(jìn)行壓棧操作， 這里的棧是the internal compilerstack，同時設(shè)置當(dāng)前的packing alignment 為 n；如果 n 沒有指定，則將當(dāng)前的packing alignment 數(shù)值壓棧；3，pop：可選參

13、數(shù)；從 internal compiler stack 中刪除最頂端的record；如果沒有指定n，則當(dāng)前棧頂record即為新的 packing alignment 數(shù)值；如果指定了n，則 n 將成為新的 packing aligment 數(shù)值；如果指定了 identifier ，則 internal compiler stack 中的 record 都將被 pop 直到 identifier 被找到，然后 pop 出 identitier ，同時設(shè)置 packingalignment 數(shù)值為當(dāng)前棧頂?shù)?record；如果指定的 identifier 并不存在于 internal compi

14、ler stack ，則 pop 操作被忽略；4， identifier ：可選參數(shù)；當(dāng)同push 一起使用時，賦予當(dāng)前被壓入棧中的record一個名稱；當(dāng)同pop一起使用時，從internal compiler stack中 pop 出所有的record 直到identifier被 pop 出，如果identifier沒有被找到，則忽略pop 操作； 5，n：可選參數(shù)；指定packing 的數(shù)值，以字節(jié)為單位；缺省數(shù)值是8，合法的數(shù)值分別是1、 2、4、8、16。重要規(guī)則：1，復(fù)雜類型中各個成員按照它們被聲明的順序在內(nèi)存中順序存儲，第一個成員的地址和整個類型的地址相同；2，每個成員分別對齊，

15、即每個成員按自己的方式對齊，并最小化長度；規(guī)則就是每個成員按其類型的對齊參數(shù)（通常是這個類型的大?。┖椭付▽R參數(shù)中較小的一個對齊；3，結(jié)構(gòu)、聯(lián)合或者類的數(shù)據(jù)成員，第一個放在偏移為0 的地方；以后每個數(shù)據(jù)成員的對齊，按照 #pragmapack 指定的數(shù)值和這個數(shù)據(jù)成員自身長度兩個中比較小的那個進(jìn)行；也就是說，當(dāng)#pragma pack 指定的值等于或者超過所有數(shù)據(jù)成員長度的時候，這個指定值的大小將不產(chǎn)生任何效果；4，復(fù)雜類型（如結(jié)構(gòu)）整體的對齊<注意是“整體”>是按照結(jié)構(gòu)體中長度最大的數(shù)據(jù)成員和#pragma pack指定值之間較小的那個值進(jìn)行；這樣在成員是復(fù)雜類型時，可以最小化

16、長度；5，結(jié)構(gòu)整體長度的計算必須取所用過的所有對齊參數(shù)的整數(shù)倍，不夠補空字節(jié)； 也就是取所用過的所有對齊參數(shù)中最大的那個值的整數(shù)倍，因為對齊參數(shù)都是2 的 n 次方；這樣在處理數(shù)組時可以保證每一項都邊界對齊；對齊的算法：由于各個平臺和編譯器的不同，現(xiàn)以本人使用的環(huán)境為例（默認(rèn)對齊參數(shù)為4），來討論編譯器對struct 數(shù)據(jù)結(jié)構(gòu)中的各成員如何進(jìn)行對齊的。在相同的對齊方式下，結(jié)構(gòu)體內(nèi)部數(shù)據(jù)定義的順序不同，結(jié)構(gòu)體整體占據(jù)內(nèi)存空間也不同，如下：設(shè)結(jié)構(gòu)體如下定義：struct A int a;char b;short c;結(jié)構(gòu)體A 中包含了4 字節(jié)長度的int一個， 1 字節(jié)長度的char 一個和2 字

17、節(jié)長度的short 型數(shù)據(jù)一個。所以A 用到的空間應(yīng)該是7 字節(jié)。但是因為編譯器要對數(shù)據(jù)成員在空間上進(jìn)行對齊。所以使用sizeof(strcutA) 值為8。 其結(jié)構(gòu)為：1111 1x11abc現(xiàn)在把該結(jié)構(gòu)體調(diào)整成員變量的順序。struct B char b;int a;short c;這時候同樣是總共7 個字節(jié)的變量，但是sizeof(struct B) 的值卻是 12。其結(jié)構(gòu)為1xxx 1111 11xxbac下面我們使用預(yù)編譯指令#progma pack (value)來告訴編譯器，使用我們指定的對齊值來取代缺省的。#progma pack (2) /*指定按2 字節(jié)對齊，等價于#pra

18、gma pack(push,2)*/struct C char b; int a; short c; ;#progma pack () /* 取消指定對齊，恢復(fù)缺省對齊,等價于#pragma pack(pop)*/sizeof(struct C) 值是8。1x 1111 11bac修改對齊值為1：#progma pack (1) /* 指定按 1 字節(jié)對齊 */struct D char b; int a; short c; ;#progma pack () /* 取消指定對齊，恢復(fù)缺省對齊sizeof(struct D) 值為 7。1 1111 1*/bac對于char 型數(shù)據(jù)，其自身對齊值

19、為1，對于short 型為2，對于int,float ，其自身對齊值為4，對于double類型，其自身對齊值為8，單位字節(jié)。這里面有四個概念值：1.數(shù)據(jù)類型自身的對齊值：就是上面交代的基本數(shù)據(jù)類型的自身對齊值。2.指定對齊值：#progma pack (value)時的指定對齊值value。3.結(jié)構(gòu)體或者類的自身對齊值：其數(shù)據(jù)成員中自身對齊值最大的那個值。4.數(shù)據(jù)成員、結(jié)構(gòu)體和類的有效對齊值：自身對齊值和指定對齊值中小的那個值。有了這些值，我們就可以很方便的來討論具體數(shù)據(jù)結(jié)構(gòu)的成員和其自身的對齊方式。有效對齊值N 是最終用來決定數(shù)據(jù)存放地址方式的值，最重要。有效對齊N，就是表示“對齊在N 上”

20、，也就是說該數(shù)據(jù)的" 存放起始地址 %N=0". 而數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)變量都是按定義的先后順序來排放的。第一個數(shù)據(jù)變量的起始地址就是數(shù)據(jù)結(jié)構(gòu)的起始地址。結(jié)構(gòu)體的成員變量要對齊排放，結(jié)構(gòu)體本身也要根據(jù)自身的有效對齊值圓整 ( 就是結(jié)構(gòu)體成員變量占用總長度需要是對結(jié)構(gòu)體有效對齊值的整數(shù)倍，結(jié)合下面例子理解)。這樣就不能理解上面的幾個例子的值了。例子分析：分析例子 B；struct B char b;int a;short c;假設(shè) B 從地址空間0x0000 開始排放。該例子中沒有定義指定對齊值，在筆者環(huán)境下，該值默認(rèn)為 4。第一個成員變量b 的自身對齊值是1，比指定或者默認(rèn)指定

21、對齊值4 小，所以其有效對齊值為1，所以其存放地址0x0000符合0x0000%1=0.第二個成員變量a，其自身對齊值為4，所以有效對齊值也為4，所以只能存放在起始地址為0x0004到 0x0007 這四個連續(xù)的字節(jié)空間中，符合0x0004%4=0, 且緊靠第一個變量。第三個變量c,自身對齊值為2，所以有效對齊值也是2，可以存放在0x0008 到 0x0009 這兩個字節(jié)空間中，符合 0x0008%2=0 。所以從 0x0000 到 0x0009 存放的都是B 內(nèi)容。再看數(shù)據(jù)結(jié)構(gòu)B 的自身對齊值為其變量中最大對齊值(這里是 b）所以就是4，所以結(jié)構(gòu)體的有效對齊值也是 4。根據(jù)結(jié)構(gòu)體圓整的要求，

22、0x0009 到 0x0000=10 字節(jié)，（ 10 2）40。所以 0x0000A 到 0x000B也為結(jié)構(gòu)體B 所占用。故B 從0x0000 到 0x000B 共有12 個字節(jié),sizeof(struct B)=12;同理 ,分析上面例子C：#progma pack (2) /* 指定按2 字節(jié)對齊*/struct C char b;int a;short c; ;#progma pack () /* 取消指定對齊，恢復(fù)缺省對齊第一個變量b 的自身對齊值為1，指定對齊值為*/2，所以，其有效對齊值為1，假設(shè)C 從 0x0000 開始，那么b 存放在0x0000 ，符合0x0000%1=0;

23、第二個變量，自身對齊值為4，指定對齊值為2，所以有效對齊值為2，所以順序存放在0x0002 、0x0003 、0x0004、 0x0005 四個連續(xù)字節(jié)中，符合第三個變量c 的自身對齊值為0x0002%2=0 。2，所以有效對齊值為2，順序存放在0x0006 、 0x0007中，符合0x0006%2=0 。所以從0x0000 到 0x00007 共八字節(jié)存放的是C 的變量。又 C 的自身對齊值為4，所以C 的有效對齊值為2。又 8%2=0,C只占用0x0000 到 0x0007 的八個字節(jié)。所以sizeof(struct C)=8.C+ 中棧和隊列實現(xiàn)：棧1、棧的相關(guān)概念棧是限定只能在表的一端

24、進(jìn)行操作的線性表。在表中允許插入和刪除的一端叫做棧頂（ top ）, 而不允許插入和刪除的另一端叫做棧底，向棧頂插入一個元素的操作叫做入棧（ push）操作，從棧頂取出一個元素的操作叫做出棧（ pop）操作。棧一經(jīng)確定，則棧底便固定不變，而棧頂隨入棧、出棧操作的執(zhí)行不斷地變化。2、 棧的特點先進(jìn)后出或者 后進(jìn)先出3、 順序棧的定義和實現(xiàn)SeqStack.htemplate <typename Type> class SeqStack public:SeqStack(intsz):m_ntop(-1),m_nMaxSize(sz)m_pelements=new Typesz;if(m

25、_pelements=NULL)cout<< "Application Error!"<<endl;exit(1);SeqStack()delete m_pelements;public:voidPush(constType item);/push dataType Pop();/pop dataType GetTop()const;/get datavoidPrint();/print the stackvoidMakeEmpty()/make the stack emptym_ntop=-1;boolIsEmpty()constreturnm_n

26、top=-1;boolIsFull()constreturnm_ntop=m_nMaxSize-1;private:intm_ntop;Type *m_pelements;intm_nMaxSize;template<typenameType> voidSeqStack<Type>:Push(const Type item)if (IsFull()cout<<"The stack is full!"<<endl;return;m_pelements+m_ntop=item;template<typenameType>

27、; Type SeqStack<Type>:Pop()if(IsEmpty()cout<<"There is no element!"<<endl;exit(1);returnm_pelementsm_ntop-;template<typenameType> TypeSeqStack<Type>:GetTop()constif(IsEmpty()cout<<"There is no element!"<<endl;exit(1);returnm_pelementsm_nt

28、op;template<typenameType>voidSeqStack<Type>:Print()cout<<"bottom"for( inti=0;i<=m_ntop;i+)cout<<"->"<<m_pelementsi;cout<<"->top"<<endl<<endl<<endl;Test.cpp#include<iostream>usingnamespacestd;#include&q

29、uot;SeqStack.h"intmain()SeqStack<int> stack(10);intinit10=1,2,6,9,0,3,8,7,5,4;for ( inti=0;i<10;i+)stack.Push(initi);stack.Print();stack.Push(88);cout<<stack.Pop()<<endl;stack.Print();stack.MakeEmpty();stack.Print();stack.Pop();return0;4、 鏈?zhǔn)綏５亩x和實現(xiàn)LinkStack.h#include"S

30、tackNode.h"template <typename Type> class LinkStack public:LinkStack():m_ptop(NULL)LinkStack()MakeEmpty();public:void MakeEmpty(); void Push( const Type Pop();Type item);/makethestack/push the data/pop the dataemptyType GetTop()voidPrint();const;/get the data/print the stackboolIsEmpty()c

31、onstreturnm_ptop=NULL;private:StackNode<Type> *m_ptop;template<typenameType>voidLinkStack<Type>:MakeEmpty()StackNode<Type> *pmove;while(m_ptop!=NULL)pmove=m_ptop;m_ptop=m_ptop->m_pnext;deletepmove;template <typename LinkStack<Type>:Push(Type>void constType item

32、)m_ptop= new StackNode<Type>(item,m_ptop);template<typenameType> TypeLinkStack<Type>:GetTop()constif (IsEmpty()cout<<"There is no elements!"<<endl;exit(1);returnm_ptop->m_data;template<typenameType> Type LinkStack<Type>:Pop()if(IsEmpty()cout<

33、<"There is no elements!"<<endl;exit(1);StackNode<Type> *pdel=m_ptop;m_ptop=m_ptop->m_pnext;Type temp=pdel->m_data;deletepdel;returntemp;template<typenameType>voidLinkStack<Type>:Print()StackNode<Type> *pmove=m_ptop;cout<<"buttom"while(

34、pmove!=NULL)cout<< "->"<<pmove->m_data;pmove=pmove->m_pnext;cout<<"->top"<<endl<<endl<<endl;Test.cpp#include<iostream>usingnamespacestd;#include"LinkStack.h"intmain()LinkStack<int> stack;intinit10=1,3,5,7,4,2,8

35、,0,6,9;for ( inti=0;i<10;i+)stack.Push(initi);stack.Print();cout<<stack.Pop()<<endl;stack.Print();cout<<stack.GetTop()<<endl;stack.Print();cout<<stack.Pop()<<endl;stack.Print();stack.MakeEmpty();stack.Print();stack.Pop();return0;5、 棧操作的注意事項在進(jìn)行入棧（ push）操作和出棧（ po

36、p）操作時，一定要進(jìn)行棧的判滿和判空操作。隊列1、隊列的相關(guān)概念隊列是限定只能在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表，在表中允許插入的一端叫做對尾 （ rear ）, 允許刪除的一端叫做對頭 （front ），向?qū)ξ膊迦胍粋€元素的操作叫做入隊（ enque）操作，從對頭取出一個元素的操作叫做出對（ dlque ）操作。隨著入隊、出對操作的執(zhí)行，隊列的對頭，對尾也不斷地隨之改變。2、 隊列的特點先進(jìn)先出3、 順序隊列的定義和實現(xiàn)LinkStack.h#include"StackNode.h"template<typenameType>classLink

37、Stackpublic:LinkStack():m_ptop(NULL)LinkStack()MakeEmpty();public:voidMakeEmpty();voidPush(constType item);Type Pop();Type GetTop()const;voidPrint();boolIsEmpty()const/makethestack/push the data/pop the data/get the data/print the stackemptyreturnm_ptop=NULL;private:StackNode<Type> *m_ptop;tem

38、plate<typenameType>voidLinkStack<Type>:MakeEmpty()StackNode<Type> *pmove;while(m_ptop!=NULL)pmove=m_ptop;m_ptop=m_ptop->m_pnext;deletepmove;template <typename LinkStack<Type>:Push(Type>void constType item)m_ptop= new StackNode<Type>(item,m_ptop);template<typ

39、enameType> TypeLinkStack<Type>:GetTop()constif (IsEmpty()cout<< "There is no elements!"<<endl;exit(1);returnm_ptop->m_data;template<typenameType> Type LinkStack<Type>:Pop()if (IsEmpty()cout<<"There is no elements!"<<endl;exit(1);Sta

40、ckNode<Type> *pdel=m_ptop;m_ptop=m_ptop->m_pnext;Type temp=pdel->m_data;deletepdel;returntemp;template<typenameType>voidLinkStack<Type>:Print()StackNode<Type> *pmove=m_ptop;cout<<"buttom"while(pmove!=NULL)cout<< "->"<<pmove->m

41、_data;pmove=pmove->m_pnext;cout<<"->top"<<endl<<endl<<endl;Test.cpp#include<iostream>usingnamespacestd;#include"LinkStack.h"intmain()LinkStack<int> stack;intinit10=1,3,5,7,4,2,8,0,6,9;for ( inti=0;i<10;i+)stack.Push(initi);stack.Print(

42、);cout<<stack.Pop()<<endl;stack.Print();cout<<stack.GetTop()<<endl;stack.Print();cout<<stack.Pop()<<endl;stack.Print();stack.MakeEmpty();stack.Print();stack.Pop();return0;4、鏈?zhǔn)疥犃械亩x和實現(xiàn)QueueNode.htemplate<typenameType>classLinkQueue;template<typenameType>

43、;classQueueNodeprivate:friendclassLinkQueue<Type>QueueNode( constType item,QueueNode<Type>*next=NULL):m_data(item),m_pnext(next)private:Type m_data;QueueNode<Type> *m_pnext;LinkQueue.h#include"QueueNode.h"template <typename Type> class LinkQueue public:LinkQueue():m

44、_prear(NULL),m_pfront(NULL)LinkQueue()MakeEmpty();voidAppend(constType item);/insert dataType Delete();/delete dataType GetFront();/get datavoidMakeEmpty();/make the queue emptyvoidPrint();/print the queueboolIsEmpty()constreturn m_pfront=NULL;private:QueueNode<Type> *m_prear,*m_pfront;templat

45、e<typenameType>voidLinkQueue<Type>:MakeEmpty()QueueNode<Type> *pdel;while(m_pfront)pdel=m_pfront;m_pfront=m_pfront->m_pnext;deletepdel;template<typenameType>voidLinkQueue<Type>:Append(constType item)if (m_pfront=NULL)m_pfront=m_prear=new QueueNode<Type>(item);E

46、lsem_prear=m_prear->m_pnext=new QueueNode<Type>(item);template<typenameType> TypeLinkQueue<Type>:Delete()if (IsEmpty()cout<< "There is no element!" <<endl; exit(1);QueueNode<Type> *pdel=m_pfront;Type temp=m_pfront->m_data;m_pfront=m_pfront->m_pnext;deletepdel;returntemp;template<typenameType> TypeLinkQueue<Type>:GetFront()if (IsEmpty()co