【正文】 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 輔助函數(shù) NodeElemType *GetElemPtr(int position) const。 // 析構(gòu)函數(shù) int Length() const。)) const。e)。e)。operator =(const LinkListElemType amp。 // 多項(xiàng)式組成的線性表 public: // 抽象數(shù)據(jù)類(lèi)型方法聲明 : Polynomial(){}。 // 判斷多項(xiàng)式是否為 0 void SetZero()。// 插入一項(xiàng) Polynomial operator +(const Polynomial amp。 // 減法運(yùn)算符重載 Polynomial operator *(const Polynomial amp。 // 復(fù)制構(gòu)造函數(shù) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 Polynomial(const LinkListPolyItem amp。copy)。 // 賦值語(yǔ)句重載 }。 2． bool Empty() const 初始條件：棧已存在。)) const 初始條件：棧已存在。 a1 a2 an x … … 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 6． StatusCode Top(ElemType amp。e) 初始條件：棧已存在且非空。 // 棧最大元素個(gè)數(shù) ElemType *elems。// 構(gòu)造函數(shù) virtual ~SqStack()。 // 將棧清空 void Traverse(void (*Visit)(const ElemType amp。 // 入棧 StatusCode Top(ElemType amp。 // 出棧 SqStack(const SqStackElemType amp。copy)。 // 未分配存儲(chǔ)空間前 ,elems為空 Init()。 curPosition++) { // 從棧底到棧頂對(duì)棧 copy的每個(gè)元素進(jìn)行復(fù)制 elems[curPosition 1] = [curPosition 1]。copy != this) { Init()。 curPosition++) { // 從棧底到棧頂對(duì)棧復(fù)制 copy的元素 elems[curPosition 1] = [curPosition 1]。 // 初始化棧 public: // 抽象數(shù)據(jù)類(lèi)型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明 : LinkStack()。 // 判斷棧是否為空 void Clear()。e)。e)。operator =(const LinkStackElemType amp。 } templateclass ElemType LinkStackElemType::~LinkStack() // 操作結(jié)果：銷(xiāo)毀棧 { Clear()。 } else { // 操作成功 top = new_top。 } else { // 操作成功 NodeElemType *old_top = top。 // 刪除舊棧頂 return SUCCESS。 // 用 e返回棧頂元素 return SUCCESS。 // 臨時(shí)棧 for (tmpPtr = top。 tmpPtr != NULL。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 C++中操作符的優(yōu)先級(jí) 優(yōu)先級(jí) 操作符 1 單目 + 、 、！ 2 *、 /、 % 3 +、 4 、 =、 、 = 5 ==、 != 6 amp。這些操作符主要用于比較。 4 括號(hào)‘ (‘和‘ )‘ 它們的作用是改變運(yùn)算順序。 ? 如在 +、 的前一個(gè)字符 (跳過(guò)空格 ,當(dāng)前一個(gè)字符不是運(yùn)算符時(shí)用 ‘ 0‘表示 )為 ‘ =‘或 ‘ (‘， 則為單目運(yùn)算符 。 (4) 當(dāng) OPTR_top!=?=‘或 ch != ?=‘ 時(shí) , 循環(huán)執(zhí)行以下工作 , 否則結(jié)束算法 。 } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 隊(duì)列 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 隊(duì)列 ( Queue ) 定義 ?隊(duì)列是只允許在一端刪除，在另一端插入的順序表 ?允許刪除的一端叫做隊(duì)頭 (front)，允許插入的一端叫做隊(duì)尾 (rear)。 操作結(jié)果：清空隊(duì)列 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 4． void Traverse(void (*Visit)(const ElemType amp。 操作結(jié)果：刪除隊(duì)頭元素，并用 e返回其值。 操作結(jié)果：依次對(duì)隊(duì)列的每個(gè)元素調(diào)用函數(shù) (*visit) 5． StatusCode OutQueue(ElemType amp。 操作結(jié)果：返回隊(duì)列長(zhǎng)度 2． bool Empty() const 初始條件：隊(duì)列已存在。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 while(OPTR_top!=?=‘ ||ch != ?=‘ ){ ① 若 ch不 是 操作符 ， 則 將字符放回輸入流 ()，讀操作數(shù) newoperand并進(jìn) OPND棧 ， 并讀入下一字符送入 ch； ② 若 ch是 操作符 ， 比較 icp(ch)的優(yōu)先級(jí)和 isp(OPTR_top)的優(yōu)先級(jí)： ? 若 isp(OPTR _top)icp(ch)， 則 ch進(jìn) OPTR棧 ， 從中綴表達(dá)式取下一字符送入 ch； ? 若 isp(OPTR _top)icp(ch)， 則從 OPND棧 退出 a2和 a1，從 OPTR棧 退出 θ, 形成運(yùn)算指令 (a1)θ(a2)， 結(jié)果進(jìn)OPND棧 ； ? 若 isp(OPTR _top)==icp(ch)且 ch == ―)‖， 則從 OPTR棧 退出棧頂?shù)?“ (‖， 對(duì)消括號(hào) ， 然后從中綴表達(dá)式取下一字符送入 ch 。 (2) 從輸入流獲取一字符 ch。 ? 操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在 括號(hào)配對(duì) 或 棧底的 ‘ =‘號(hào)與輸入流最后的 ‘ =‘號(hào)配對(duì) 時(shí) 。amp。 7 || 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 ? 一般表達(dá)式的操作符有 4種類(lèi)型 ： 1 算術(shù)操作符 如雙目操作符（ +、 、 *、/ 和 %）以及單目操作符（ +、 ）。 } } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 表達(dá)式求值 ? 一個(gè)表達(dá)式由 操作數(shù) (亦稱(chēng)運(yùn)算對(duì)象 )、 操作符 (亦稱(chēng)運(yùn)算符 ) 和 分界符 組成 。 tmpPtr = tmpPtrnext) { // 用 tmpPtr依次指向當(dāng)前棧的每個(gè)元素 (tmpPtrdata)。)) const // 操作結(jié)果：從棧底到棧頂依次對(duì)棧的每個(gè)元素調(diào)用函 // 數(shù) (*visit) { NodeElemType *tmpPtr。e) const // 操作結(jié)果：如棧非空 ,用 e返回棧頂元素 ,函數(shù)返回 \ // SUCCESS,否則函數(shù)返回 UNDER_FLOW { if(Empty()) { // 棧空 return UNDER_FLOW。 // 用 e返回棧頂元素 top = old_topnext。 } } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 templateclass ElemType StatusCode LinkStackElemType::Pop(ElemType amp。e) // 操作結(jié)果：將元素 e追加到棧頂 ,如成功則返加 SUCCESS, // 否則如動(dòng)態(tài)內(nèi)存已耗盡將返回 OVER_FLOW { NodeElemType *new_top = new NodeElemType(e, top)。 //重載賦值 }。copy)。e) const。)) const。 // 析構(gòu)函數(shù) int Length() const。 } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 top 空棧 top top top top top a 進(jìn)棧 b 進(jìn)棧 a a b a b c d e e 進(jìn)棧 a b c d e f 進(jìn)棧溢出 a b d e e 退棧 c 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 top c 退棧 b 退棧 a b a a 退棧 空 棧 top a b d d 退棧 c top a b c top top 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 雙棧共享一個(gè)棧空間 b[0] t[0] t[1] b[1] 0 maxSize1 V 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 棧的鏈接表示 — 鏈?zhǔn)綏? ? 鏈?zhǔn)綏o(wú)棧滿(mǎn)問(wèn)題，空間可擴(kuò)充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈?zhǔn)綏５臈ｍ斣阪滎^ top 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 鏈?zhǔn)綏? (Linked Stack) 類(lèi)的定義 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 鏈棧類(lèi) templateclass ElemType class LinkStack { protected: // 鏈棧實(shí)現(xiàn)的數(shù)據(jù)成員 : NodeElemType *top。 // 復(fù)制棧元素個(gè)數(shù) for (int curPosition = 1。SqStackElemType::operator = (const SqStackElemType amp。 // 棧元素個(gè)數(shù) for (int curPosition = 1。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 復(fù)制構(gòu)造函數(shù) templateclass ElemType SqStackElemType::SqStack(const SqStackElemType amp。 // 復(fù)制構(gòu)造函數(shù) SqStackElemType amp。// 返回棧頂 StatusCode Pop(ElemType amp。 // 遍歷棧 StatusCode Push(const ElemType amp。 // 求棧長(zhǎng)度 bool Empty() const。 // 判斷棧是否已滿(mǎn) void Init(int size)。 a1 a2 an an1 … … 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 棧的數(shù)組表示 — 順序棧 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 順序棧類(lèi) templateclass ElemType class SqStack { protected: // 順序棧的數(shù)據(jù)成員 : int count。 操作結(jié)果：用 e返回棧頂元素。e) 初始條件：棧已存在。 操作結(jié)果：清空棧。 棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 棧 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 ? 只允許在一端插入和刪除的線性表 ? 允許插入和刪除 的一端稱(chēng)為 棧頂 (top)，另一端稱(chēng) 為 棧底 (bottom) ? 特點(diǎn) 后進(jìn)先出 (LIFO) 棧 ( Stack ) 退棧 進(jìn)棧 a1 an an1 ? top bottom 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 1． int Length() const 初始條件：棧已存在。operator =(const LinkListPolyItem amp。 // 由多項(xiàng)式組成的線性表構(gòu)造多項(xiàng)式 Polynomial amp。 // 乘法運(yùn)算符重載 Polynomial(const Polynomial amp。 // 加法運(yùn)算符重載 Polynomial operator (const Polynomial amp。 // 顯示多項(xiàng)式 void InsItem( const PolyItem amp。 // 析構(gòu)函數(shù) int Length() const。 // 賦值語(yǔ)句重載 }。copy)。e)。e) const。 // 判斷線性表是否為空 void Cl