【正文】 機(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è)?？臻g b[0] t[0] t[1] b[1] 0 maxSize1 V 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 棧的鏈接表示 — 鏈?zhǔn)綏? ? 鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈?zhǔn)綏５臈ｍ斣阪滎^ top 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 鏈?zhǔn)綏? (Linked Stack) 類的定義 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 鏈棧類 templateclass ElemType class LinkStack { protected: // 鏈棧實(shí)現(xiàn)的數(shù)據(jù)成員 : NodeElemType *top。)) const。copy)。e) // 操作結(jié)果：將元素 e追加到棧頂 ,如成功則返加 SUCCESS, // 否則如動(dòng)態(tài)內(nèi)存已耗盡將返回 OVER_FLOW { NodeElemType *new_top = new NodeElemType(e, top)。 // 用 e返回棧頂元素 top = old_topnext。)) const // 操作結(jié)果：從棧底到棧頂依次對(duì)棧的每個(gè)元素調(diào)用函 // 數(shù) (*visit) { NodeElemType *tmpPtr。 } } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 表達(dá)式求值 ? 一個(gè)表達(dá)式由 操作數(shù) (亦稱運(yùn)算對(duì)象 )、 操作符 (亦稱運(yùn)算符 ) 和 分界符 組成 。amp。 (2) 從輸入流獲取一字符 ch。 操作結(jié)果：返回隊(duì)列長(zhǎng)度 2． bool Empty() const 初始條件：隊(duì)列已存在。 操作結(jié)果：刪除隊(duì)頭元素，并用 e返回其值。 } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 隊(duì)列 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 隊(duì)列 ( Queue ) 定義 ?隊(duì)列是只允許在一端刪除，在另一端插入的順序表 ?允許刪除的一端叫做隊(duì)頭 (front)，允許插入的一端叫做隊(duì)尾 (rear)。 ? 如在 +、 的前一個(gè)字符 (跳過(guò)空格 ,當(dāng)前一個(gè)字符不是運(yùn)算符時(shí)用 ‘ 0‘表示 )為 ‘ =‘或 ‘ (‘， 則為單目運(yùn)算符 。這些操作符主要用于比較。 tmpPtr != NULL。 // 用 e返回棧頂元素 return SUCCESS。 } else { // 操作成功 NodeElemType *old_top = top。 } templateclass ElemType LinkStackElemType::~LinkStack() // 操作結(jié)果：銷毀棧 { Clear()。e)。 // 判斷棧是否為空 void Clear()。 curPosition++) { // 從棧底到棧頂對(duì)棧復(fù)制 copy的元素 elems[curPosition 1] = [curPosition 1]。 curPosition++) { // 從棧底到棧頂對(duì)棧 copy的每個(gè)元素進(jìn)行復(fù)制 elems[curPosition 1] = [curPosition 1]。copy)。 // 入棧 StatusCode Top(ElemType amp。// 構(gòu)造函數(shù) virtual ~SqStack()。e) 初始條件：棧已存在且非空。)) const 初始條件：棧已存在。 // 賦值語(yǔ)句重載 }。 // 復(fù)制構(gòu)造函數(shù) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 Polynomial(const LinkListPolyItem amp。// 插入一項(xiàng) Polynomial operator +(const Polynomial amp。 // 多項(xiàng)式組成的線性表 public: // 抽象數(shù)據(jù)類型方法聲明 : Polynomial(){}。e)。)) const。 // 元素個(gè)數(shù) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 輔助函數(shù) NodeElemType *GetElemPtr(int position) const。 // 剩下的一個(gè)人為優(yōu)勝者 cout endl 優(yōu)勝者 : winer endl。 i n。此人即為優(yōu)勝者 { SimpleCircLinkListint la。operator =(const SimpleCircLinkListElemType amp。e)。 // 析構(gòu)函數(shù) int Length() const。 ? 循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的 next指針不為 0 (NULL)，而是指向了表的前端。 } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 else { // position合法 NodeElemType *tmpPtr。 // 位置不合法 } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 else { // position合法 NodeElemType *tmpPtr。 // 復(fù)制構(gòu)造函數(shù) SimpleLinkListElemType amp。 // 求指定位置的元素 StatusCode SetElem(int position, const ElemType amp。 // 無(wú)參數(shù)構(gòu)造函數(shù) virtual ~SimpleLinkList()。 // 數(shù)據(jù)域 NodeElemType *next。 // 取出 lb的一個(gè)元素 bItem 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 if (aItem == bItem) { isExist = true。 ()。 curPosition++) { // 被刪除元素之后的元素依次左移 GetElem(curPosition, tmp)。//將 e賦值到 position位置處 return SUCCESS。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 if (Full()) { // 線性表已滿返回 OVER_FLOW return OVER_FLOW。// 釋放存儲(chǔ)空間 elems = new ElemType[maxSize]。copy)。e) const。 // 初始化線性表 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn) // 方法聲明 : SqList(int size = DEFAULT_SIZE)。e) 初始條件：線性表已存在，1≤position≤Length()+1 。 操作結(jié)果：用 e返回第 position個(gè)元素的值。 操作結(jié)果：如線性表為空，則返回 true，否則返回 false。 // 遍歷求和 return s。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 算法和程序的關(guān)系 算法著重體現(xiàn)思路和方法 ， 程序著重體現(xiàn)計(jì)算機(jī)的實(shí)現(xiàn) 程序不一定滿足有窮性 （ 死循環(huán) ） ，另外 ， 程序中的指令必須是機(jī)器可執(zhí)行的 ， 算法中的指令無(wú)此限制 一個(gè)算法若用計(jì)算機(jī)語(yǔ)言來(lái)書寫 ，它就可以是一個(gè)程序 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 算法評(píng)價(jià)標(biāo)準(zhǔn) 時(shí)間特性 (時(shí)間復(fù)雜度 T(n) ) 空間特性 (空間復(fù)雜度 S(n) ) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 一個(gè)特定 算法的 “ 運(yùn)行工作量 ” 的大小，只依賴于 問(wèn)題的規(guī)模（通常用整數(shù)量 n表示），或者說(shuō)，它 是問(wèn)題規(guī)模的函數(shù) 。 （ 3）程序?qū)τ诰倪x擇的、典型的、苛刻的并帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。 （ 2）程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。也有其他的圖形輔助工具 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 用其它方式描述算法 我們還可以用數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來(lái)描述算法 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 用 C++描述算法 在本課中 ， 我們將采用類 C++來(lái)描述算法 ,所有算法的描述都用C＋＋中的函數(shù)形式來(lái)描述 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 為表示各種狀態(tài)信息，定義枚舉類型StatusCode供使用，具體聲明如下： // 自定義類型 enum StatusCode { SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED }。 j++) s = s + a[i][j]。 2． bool Empty() const 初始條件：線性表已存在。e) const 初始條件：線性表已存在，1≤position≤Length() 。 8． StatusCode Insert(int position, const ElemType amp。 // 判斷線性表是否已滿 void Init(int size)。 // 遍歷線性表 StatusCode GetElem(int position, elemType amp。 // 插入元素 SqList(const SqListelemType amp。 // 最大元素個(gè)數(shù) if (elems != NULL) delete []elems。 int len = Length()。 } SetElem(position, e)。 curPosition = len。lc) // 操作結(jié)果 : 用 lc返回 la和 lb表示的集合的差集 // 方 法 : 在 la中取出元素 ,在 lb中進(jìn)行查找 ,如果未在 lb中 // 出現(xiàn)了 ,將其插入到 lc { ElemType aItem, bItem。 bPosition++) { (bPosition, bItem)。 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 // 結(jié)點(diǎn)類 template class ElemType struct Node { // 數(shù)據(jù)成員 : ElemType data。 // 初始化線性表 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明 : SimpleLinkList()。e) const。copy)。e) // 操作結(jié)果：在線性表的第 position個(gè)位置前插入元素 e // position的取值范圍為 1≤position≤Length()+1 // position合法時(shí)返回 SUCCESS, 否則函數(shù)返回 // RANGE_ERROR { if (position 1 || position Length() + 1) { // position范圍錯(cuò) return RANGE_ERROR。e) // 操作結(jié)果：刪除線性表的第 position個(gè)位置的元素 , 并用 // e返回其值 , position的取值范圍為 // 1≤position≤Length(), position合法時(shí)函數(shù)返回 // SUCCESS,否則函數(shù)返回 RANGE_ERROR { if (position 1 || position Length()) { // position范圍錯(cuò) return RANGE_ERROR。 } } 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 循環(huán)鏈表 (Circular List) 四川大學(xué)計(jì)算機(jī)學(xué)院，主講教師：游洪躍 ? 循環(huán)鏈表是單鏈表的變形。 // 無(wú)參數(shù)的構(gòu)造函數(shù) virtual ~SimpleCircLinkList()。 // 求指定位置的元素 StatusCode Se