【正文】 case 39。 //結果壓棧 case 39。 switch(Opr){ case 39。} 棧與應用 void Calculator::Compute(char Opr){ int Num1,Num2。} void Calculator::GetTwoNum(int amp。 void Clear(void)。 //計算器運算程序 void GetTwoNum(int amp。 簡易計算器類定義： class Calculator{ Stackint Nstack。棧中數據繼續(xù)按前面規(guī)則出棧。數棧暫存操作數，運算符棧暫存運算符。 鏈棧內存空間隨用隨開，不會溢出，但執(zhí)行復雜（不斷地動態(tài)分配），速度慢。 } //返回棧頂數據 templatetypename T T StackT::GetTop(){ assert(!IsEmpty())。 T data=tempinfo。} } 棧與應用 templatetypename T void StackT::Push(const T amp。} templatetypename Tvoid StackT::MakeEmpty(){ NodeT *temp。 //取棧頂元素 void MakeEmpty()。 void Push(const T amp。 }。 NodeT *link。 //超出棧有效數據則錯，退出程序 return elements[i]。 //棧已空則不能退棧，退出程序 return elements[top]。} templatetypename T void StackT::Push(const T amp。i=top。 top=1。} //判?？? bool IsFull() const{return top==maxSize1。 //壓棧 T Pop()。 //棧最大容納的元素個數 public: Stack(int=20)。通常只有棧頂與操作有關。所以棧又稱作 后進先出（ LIFO： Last In First Out）的線性表 。 棧中沒有任何元素時，稱為空棧。 p llink rlink rlink llink rlink 前驅結點 llink 本結點 后繼結點 間接訪問符的使用 在 VC++平臺上演示 例 。雙向鏈表的 結點有三個域 ： 左鏈接指針（ llink)， 數據域（ info)， 右鏈接指針域 (rlink)。 在本例中程序只需調用類模板中的成員函數就可以完成所有鏈表操作。 } //本函數所用方法可省一個工作指針，與 InsertOrder比較 單鏈表類型模板 單鏈表類型模板 【 例 】 由鍵盤輸入 16個整數 ， 以這些整數作為結點數據 ， 生成兩個鏈表 ， 一個向前生成 ， 一個向后生成 ， 輸出兩個表 。amp。 } tempQInsertAfter(p)。} templatetypename Tvoid ListT::InsertOrder(NodeT *p){ NodeT *tempP=headlink,*tempQ=head。taillink=p。} templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。 while(tempP!=NULL){ couttempPinfo39。 while(tempP!=NULL){ tempP=tempPlink。tempPinfo!=data) tempP=tempPlink。 } //刪除 (釋放 )脫離下來的結點 tail=head。} templatetypename Tvoid ListT::MakeEmpty(){ NodeT *tempP。 //刪除指定結點 }。 //可用來向前生成鏈表 void InsertRear(NodeT* p)。 //清空一個鏈表，只余表頭結點 NodeT* Find(T data)。 } 再定義鏈表類，操作包括建立有序鏈表、搜索遍歷、插入、刪除、取數據等 : templatetypename Tclass List{ NodeT *head,*tail。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 data){ info=data。 //刪除當前結點的后繼結點 friend class ListT。 //生成頭結點的構造函數 Node(const T amp。 首先看結點組織，采用結點類，凡與結點數據和指針操作有關函數作為成員函數 : templatetypename Tclass List。 plink=qlink。 qlink=plink。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結點 。 //頭結點放新結點之前 } return head。 while(cindata){ //建立的總是第一個結點 p=new node。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法 node *createup(){ node *head,*p。 //添入數據 p0link= p1。 head=new node。 即： newnode→ link=head； //注意：鏈表操作次序非常重要 head=newnode； 單鏈表基本算法 infox infoi1 infoi p ｑ newnode 插在中間 首先用工作指針 p找到指定結點 ， 而讓指針 q指向緊跟其后的結點 ， 令 infoi1所在結點的 link指針指向新結點 ， 而后讓新結點的 link指向 infoi所在結點 。 單鏈表的插入與刪除： 只要改變鏈中結點指針的值，無需移動表中的元素，就能實現插入和刪除操作。 node *link。 每個數據元素占用一個節(jié)點 （ Node） 。對象的拷貝就是深拷貝了 。 return *this。 delete[] pName。 delete[] pName。 coutpNameendl。} 拷貝構造函數： student::student(student amp。cout缺省 endl。s)。s)。 學生類定義： class student{ char *pName?！闭Z句，則如果先析構函數 obj1時，堆對象已經釋放，以后再析構 obj2時出現了二次釋放的問題。 這稱為 淺拷貝。 delete []pc2。 cinn。 CGoods *pc,*pc1,*pc2。 Amount=amount。 public: CGoods(){}。見下例類說明： 堆對象與構造函數 class CGoods{ char Name[21]。 //先析構 ，然后將內存空間返回給堆； 堆對象的生命期并不依賴于建立它的作用域，所以除非程序結束，堆對象（無名對象）的生命期不會到期，并且需要顯式地用 delete語句析構堆對象，上面的堆對象在執(zhí)行 delete語句時， C++自動調用其析構函數。 堆對象與構造函數 通過 new建立的對象要調用構造函數，通過 deletee刪除對象也要調用析構函數。 ４．動態(tài)分配的變量或對象的生命期。） 實際意思是刪除了 p所指的目標（變量或對象等），釋放了它所占的堆空間，而不是刪除ｐ本身，釋放堆空間后，ｐ成了 空懸指針 。 指針使用的幾個問題： １．動態(tài)分配失敗。im。//初始化數組元素 display(data)。im。j++){ data[j] = new double[n]。 //設置行 if ((data ) == 0){ cout Couuld not allocate. Bye ...。 const int m=4。刪除這兩個動態(tài)數組可用下式： delete [] cp。 //三級指針； float (*bp) [20]。 //指向一個 30行 20列數組的指針 cp=new float [15] [30] [20]。盡管 C++不對數組作邊界檢查，但在堆空間分配時，對數組分配空間大小是紀錄在案的 。 delete []pc。 cinn。 請注意 “下標表達式”不是常量表達式 ，即它的值不必在編譯時確定， 可以在運行時確定 。 delete [ ] 指向該數組的指針變量名 。 堆內存的分配與釋放 堆 ０ Ｐ i 下面看演示： １．用初始化式 (initializer)來顯式初始化 int *pi=new int(0)。 它與下列代碼序列 大體 等價： int ival=0。堆區(qū)是不會自動在分配時做初始化的（包括清零），所以必須用初始化式 (initializer)來顯式初始化。 在 C++中 ， 申請和釋放堆中分配的存貯空間 ， 分別使用new和 delete的兩個運算符來完成 ， 其使用的格式如下： 指針變量名 =new 類型名 (初始化式 )； delete 指針名 。這種內存分配稱為 靜態(tài)存儲分配 有些操作對象只有在程序運行時才能確定，這樣編譯器在編譯時就無法為他們預定存儲空間，只能在程序運行時，系統(tǒng)根據運行時的要求進行內存分配，這種方法稱為 動態(tài)存儲分配 。模板 是標準 C++實現代碼復用的有力工具，特別是有關數據結構的算法。第七章 動態(tài)內存分配 本章首先介紹程序運行時 動態(tài)內存分配 （ dynamic memory allocation）的概念與方法。本章將進一步討論拷貝構造函數；還要學習更多有關 數據結構的基本知識，包括 棧 ， 隊 ， 二叉樹 等的基本算法和應用。 通常定義變量（或對象），編譯器在編譯時都可以根據該變量（或對象）的類型知道所需內存空間的大小，從而系統(tǒng)在適當的時候為他們分配確定的存儲空間。 當不再使用該變量或對象時 ， 也就是它的生命結束時 ， 要 顯式釋放 它所占用的存貯空間 ， 這樣系統(tǒng)就能對該堆空間進行再次分配 ， 做到重復使用有限的資源 。 堆內存的分配與釋放 一般定義變量和對象時要用標識符命名，稱 命名對象 ，而動態(tài)的稱 無名對象 (請注意與棧區(qū)中的臨時對象的區(qū)別，兩者完全不同：生命期不同，操作方法不同，臨時變量對程序員是透明的 )。例如： int *pi=new int(0)。 只是 pi現在所指向的變量是由庫操作符 new()分配的，位于程序的堆區(qū)中，并且該 對象未命名 。 堆內存的分配與釋放 對于數組進行動態(tài)分配的格式為： 指針變量名 =new 類型名 [下標表達式 ]。即使寫了，編譯器也忽略。 cout請輸入動態(tài)數組的元素個數 endl。 coutpcendl。 delete []pc是將 n個字符的空間釋放，而用 delete pc則只釋放了一個字符的空間； 2. 如果有一個 char *pc1，令 pc1=p，同樣可用 delete [] pc1來釋放該空間。 建立一個動態(tài)三維數組 float (*cp)[30][20] 。 堆內存的分配與釋放 比較： float(*cp) [30] [20]。 兩個數組都是由 600個浮點數組成，前者是只有一個元素的三維數組 ，每個元素為 30行 20列的二維數組，而另一個是有 30個元素的二維數組 ，每個元素為 20個元素的一維數組。采用 指針數組方式 來完成二維數組的動態(tài)創(chuàng)建。 data = new double*[m]。jm。} } for (int i=0。j++) data[i][j]=i*n+j。 } 堆內存的分配與釋放 再 看二維數組的撤銷與內存釋放： void de_allocate(double **data){ for (int i=0。 } 在 VC++平臺上演示本例