【正文】 算符壓棧。數(shù)棧暫存操作數(shù)，運(yùn)算符棧暫存運(yùn)算符?，F(xiàn)考慮最簡(jiǎn)單的 +、 、 *、 /四個(gè)運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有 兩個(gè)優(yōu)先級(jí) ，先 */，后 +。 鏈棧內(nèi)存空間隨用隨開，不會(huì)溢出，但執(zhí)行復(fù)雜（不斷地動(dòng)態(tài)分配），速度慢。} 棧與應(yīng)用 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個(gè)棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)?順序棧可以隨機(jī)訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同） 。 } //返回棧頂數(shù)據(jù) templatetypename T T StackT::GetTop(){ assert(!IsEmpty())。 //丟棄棧頂結(jié)點(diǎn) delete temp。 T data=tempinfo。 } //鏈棧向前生成，新結(jié)點(diǎn)在鏈棧頭 templatetypename T T StackT::Pop(){ assert(!IsEmpty())。} } 棧與應(yīng)用 templatetypename T void StackT::Push(const T amp。top=toplink。} templatetypename Tvoid StackT::MakeEmpty(){ NodeT *temp。} }。 //取棧頂元素 void MakeEmpty()。 //壓棧 T Pop()。 void Push(const T amp。 //棧頂指針 public: Stack(){top=NULL。 }。 link=next。 NodeT *link。 棧與應(yīng)用 鏈棧的類模板 : templatetypename Tclass Stack。 //超出棧有效數(shù)據(jù)則錯(cuò)，退出程序 return elements[i]。amp。 //棧已空則不能退棧，退出程序 return elements[top]。 //棧滿則退出程序 elements[++top]=data。} templatetypename T void StackT::Push(const T amp。\t39。i=top。 //建立?？臻g assert(elements!=0)。 top=1。 //輸出棧內(nèi)所有數(shù)據(jù) }。} //判棧空 bool IsFull() const{return top==maxSize1。 //取數(shù)據(jù)， top不變 void MakeEmpty(){top= 1。 //壓棧 T Pop()。} void Push(const T amp。 //棧最大容納的元素個(gè)數(shù) public: Stack(int=20)。 //棧頂指針（下標(biāo)） T *elements。通常只有棧頂與操作有關(guān)。 a0 an2 …… a1 an1 bottom 進(jìn)棧 top top top top top 出棧 圖示為順序棧。所以棧又稱作 后進(jìn)先出（ LIFO： Last In First Out）的線性表 。進(jìn)棧時(shí)最先進(jìn)棧的 a0在最下面， an1在最上面，后來居上。 棧中沒有任何元素時(shí)，稱為空棧。 7. 3. 1 棧 與 應(yīng) 用 7. 3. 2 隊(duì) 列 棧與應(yīng)用 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。 p llink rlink rlink llink rlink 前驅(qū)結(jié)點(diǎn) llink 本結(jié)點(diǎn) 后繼結(jié)點(diǎn) 間接訪問符的使用 在 VC++平臺(tái)上演示 例 。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表 假設(shè)指針 p指向雙向循環(huán)鏈表的某一個(gè)結(jié)點(diǎn)，那么， pllink指示 P所指結(jié)點(diǎn)的 前驅(qū)結(jié)點(diǎn) ， prlink指示 后繼結(jié)點(diǎn)。雙向鏈表的 結(jié)點(diǎn)有三個(gè)域 ： 左鏈接指針（ llink)， 數(shù)據(jù)域（ info)， 右鏈接指針域 (rlink)。如要找前驅(qū)，必須從表頭開始搜索。 在本例中程序只需調(diào)用類模板中的成員函數(shù)就可以完成所有鏈表操作。 清空該表 ， 再按升序生成鏈表并輸出 。 } //本函數(shù)所用方法可省一個(gè)工作指針，與 InsertOrder比較 單鏈表類型模板 單鏈表類型模板 【 例 】 由鍵盤輸入 16個(gè)整數(shù) ， 以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù) ， 生成兩個(gè)鏈表 ， 一個(gè)向前生成 ， 一個(gè)向后生成 ， 輸出兩個(gè)表 。 if(tempPlink==tail) tail=tempP。amp。} templatetypename T NodeT* ListT::DeleteNode(NodeT* p){ NodeT* tempP=head。 } tempQInsertAfter(p)。 //找第一個(gè)比插入結(jié)點(diǎn)大的結(jié)點(diǎn)，由 tempP指向 tempQ=tempP。} templatetypename Tvoid ListT::InsertOrder(NodeT *p){ NodeT *tempP=headlink,*tempQ=head。} templatetypename TNodeT* ListT::CreatNode(T data){ NodeT*tempP=new NodeT(data)。taillink=p。 if(tail==head) tail=p。} templatetypename Tvoid ListT::InsertFront(NodeT *p){ plink=headlink。 tempP=tempPlink。 while(tempP!=NULL){ couttempPinfo39。} return count。 while(tempP!=NULL){ tempP=tempPlink。 } //搜索成功返回該結(jié)點(diǎn)地址，不成功返回 NULL 單鏈表類型模板 templatetypename Tint ListT::Length(){ NodeT* tempP=headlink。tempPinfo!=data) tempP=tempPlink。 while(tempP!=NULLamp。 } //刪除 (釋放 )脫離下來的結(jié)點(diǎn) tail=head。 headlink=tempPlink。} templatetypename Tvoid ListT::MakeEmpty(){ NodeT *tempP。} templatetypename TListT::~List(){ MakeEmpty()。 //刪除指定結(jié)點(diǎn) }。 //按升序生成鏈表 NodeT*CreatNode(T data)。 //可用來向前生成鏈表 void InsertRear(NodeT* p)。 //計(jì)算單鏈表長(zhǎng)度 void PrintList()。 //清空一個(gè)鏈表，只余表頭結(jié)點(diǎn) NodeT* Find(T data)。 //構(gòu)造函數(shù)，生成頭結(jié)點(diǎn) (空鏈表 ) ~List()。 } 再定義鏈表類，操作包括建立有序鏈表、搜索遍歷、插入、刪除、取數(shù)據(jù)等 : templatetypename Tclass List{ NodeT *head,*tail。 //已在鏈尾 ,后面無結(jié)點(diǎn) else link=tempPlink。 } templatetypename TNodeT* NodeT::RemoveAfter(){ NodeT* tempP=link。 } templatetypename Tvoid NodeT::InsertAfter(NodeT* p){ plink=link。 data){ info=data。 單鏈表類型模板 看結(jié)點(diǎn)類成員函數(shù) : template typename T NodeT::Node(){link=NULL。 //刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) friend class ListT。 //生成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void InsertAfter(NodeT* p)。 //生成頭結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const T amp。 //數(shù)據(jù)域 NodeT *link。 首先看結(jié)點(diǎn)組織，采用結(jié)點(diǎn)類，凡與結(jié)點(diǎn)數(shù)據(jù)和指針操作有關(guān)函數(shù)作為成員函數(shù) : templatetypename Tclass List。 //如果要把該節(jié)點(diǎn)移入另一個(gè)鏈中 ， 則可將 q返回 。 plink=qlink。 } 單鏈表基本算法 5. 刪除單鏈表節(jié)點(diǎn) *p后面節(jié)點(diǎn) void del (node *p){ node *q。 qlink=plink。 void insert(node p,Datatype x){ node *q=new node。 //p為 NULL則未找到 } 返回值為指針 p， 指向鏈表中找到的結(jié)點(diǎn) 。 while(p!=NULL||pinfo!=data) p=plink。 //頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 } return head。 plink= headlink 。 while(cindata){ //建立的總是第一個(gè)結(jié)點(diǎn) p=new node。 head=new node。 //返回頭指針 } 單鏈表基本算法 head ^ info0 P ^ P info1 2. 向前生成鏈表算法 node *createup(){ node *head,*p。} //尾指針到鏈尾 tailnext=NULL。 //添入數(shù)據(jù) p0link= p1。 while(cindata){ //回車結(jié)束 p1=new(node)。 head=new node。 單鏈表基本算法 head p0 p1 info1 p0 p1 info0 p0 ^ 1. 向后生成鏈表算法： node *createdown(){ Datatype data。 即： newnode→ link=head； //注意：鏈表操作次序非常重要 head=newnode； 單鏈表基本算法 infox infoi1 infoi p ｑ newnode 插在中間 首先用工作指針 p找到指定結(jié)點(diǎn) ， 而讓指針 q指向緊跟其后的結(jié)點(diǎn) ， 令 infoi1所在結(jié)點(diǎn)的 link指針指向新結(jié)點(diǎn) ， 而后讓新結(jié)點(diǎn)的 link指向 infoi所在結(jié)點(diǎn) 。 單鏈表基本算法 newnode infox info0 info1 單鏈表的插入與刪除： 只要改變鏈中結(jié)點(diǎn)指針的值，無需移動(dòng)表中的元素，就能實(shí)現(xiàn)插入和刪除操作。 但結(jié)構(gòu)成員決不能是結(jié)構(gòu)自身類型 ， 即結(jié)構(gòu)不能自己定義自己 ， 這會(huì)導(dǎo)致一個(gè)無窮遞歸的定義 。 node *link。 節(jié)點(diǎn)定義如下： typedef int Datatype。 每個(gè)數(shù)據(jù)元素占用一個(gè)節(jié)點(diǎn) （ Node） 。線性表的邏輯結(jié)構(gòu)是 n個(gè)數(shù)據(jù)元素的有限序列（ a1,a2,…,an ）。對(duì)象的拷貝就是深拷貝了 。 淺拷貝與深拷貝 堆內(nèi)存是最常用的需要拷貝構(gòu)造函數(shù)自定義的資源，但 不是唯一 的，如打開文件等。 return *this。} else pName=NULL。 delete[] pName。 student::operator=(student amp。 delete[] pName。 if(pName) pName[0]=39。 coutpNameendl。 if(){ if(pName=new char[strlen()+1]) strcpy(pName,)。} 拷貝構(gòu)造函數(shù)： student::studen