数据结构与算法分析课件

第1章緒論數據（data）數據是資訊的載體，是描述客觀事物的數、字元、以及所有能輸入到電腦中，被電腦程式識別和處理的符號的集合數值性數據非數值性數據數據元素

(dataelement)數據的基本單位。在電腦程式中常作為一個整體進行考慮和處理有時一個數據元素可以由若干資料項目(DataItem)組成。數據元素又稱為元素、結點、記錄什麼是數據結構定義:

由某一數據元素的集合及該集合中所有數據元素之間的關係組成記為：

Data_Structure={D,S}

其中，D

是某一數據元素的集合，S是該集合中所有數據元素之間的關係組成的有限集合數據的邏輯結構數據的邏輯結構從邏輯關係上描述數據，與數據的存儲無關數據的邏輯結構可以看作是從具體問題抽象出來的數據模型數據的邏輯結構可歸結為以下四類線性結構樹形結構圖狀結構集合結構數據的存儲結構數據的存儲結構是邏輯結構用電腦語言的實現數據的存儲結構依賴於電腦語言順序存儲表示鏈接存儲表示順序存貯

所有元素存放在一片連續的存貯單元中，邏輯上相鄰的元素存放到電腦記憶體仍然相鄰

鏈式存貯

所有元素存放在可以不連續的存貯單元中，但元素之間的關係可以通過地址確定，邏輯上相鄰的元素存放到電腦記憶體後不一定是相鄰的數據類型數據類型

定義：一組性質相同的值的集合,以及定義於這個值集合上的一組操作的總稱如C語言中有如下數據類型

charintfloatdoublevoid

字元型整型浮點型雙精度型無值

構造數據類型由不同成分構成基本數據類型可以看作是電腦中已實現的數據結構抽象數據類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應用問題的數據模型由基本的數據類型組成,並包括含一組相關的服務（或稱操作）ADT有兩個重要特徵數據抽象

用ADT描述程式處理的實體時，強調的是其本質的特徵、其所能完成的功能以及它和外部用戶的介面（即外界使用它的方法）數據封裝

將實體的外部特性和其內部實現細節分離，並且對外部用戶隱藏其內部實現細節抽象數據類型的表示和實現

抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現算法

演算法是為了解決某類問題而規定的一個有限長的操作序列演算法定義演算法應具有的性質正確性具體性確定性有限性可讀性健壯性正確性

正確性指必須完成所期望的功能，對演算法是否“正確”的理解可以有如下四個層次：（1）程式中不含任何語法錯誤。（2）程式對於幾組輸入數據能夠得出滿足要求的結果。（3）程式對於精心選擇的、典型的、苛刻的並帶有刁難性的幾組輸入數據能夠得出滿足要求的結果。（4）程式對於一切輸入數據都能得出滿足要求的結果。具體性一個演算法必須由一系列具體操作組成，這時的“具體”指的所有操作都必須經過已實現的基本操作有限次來實現，並且所有操作都是可讀的、可執行的，每一操作必須在有限時間內完成。

確定性

演算法中的所有操作都必須有確切的含義，不能產生歧義，演算法的執行者或閱讀者都能明確其含義及如何執行。有限性

對於任意一組合法輸入值，在執行有限步驟之後一定能結束，即：演算法中的每個步驟都能在有限時間內完成可讀性

演算法應具備良好的可讀性，這樣的演算法有利於演算法的查錯及對演算法的理解，一般演算法的邏輯必須清楚、結構簡單，所有識別字必須具有實際含義，能見名知義。健壯性

健壯性指當輸入數據非法時，演算法能作適當的處理並作出反應，而不應死機或輸出異常結果演算法描述方法

用自然語言描述演算法

用我們日常生活中的自然語言（可以是中文形式，也可以是英文形式）也可以描述演算法用流程圖描述演算法

一個演算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述演算法的較好方法，目前在一些高級語言程式設計中仍然採用。也有其他的圖形輔助工具用其他方式描述演算法

我們還可以用數學語言或約定的符號語言來描述演算法

用C++描述演算法

在本課中，我們將採用類C++來描述演算法,所有演算法的描述都用C＋＋中的函數形式來描述

為表示各種狀態資訊，定義枚舉類型StatusCode供使用，具體聲明如下：//自定義類型enumStatusCode{SUCCESS,FAIL,UNDER_FLOW,OVER_FLOW,RANGE_ERROR,DUPLICATE_ERROR,NOT_PRESENT,ENTRY_INSERTED,ENTRY_FOUND,VISITED,UNVISITED};演算法和程式的關係

演算法著重體現思路和方法，程式著重體現電腦的實現程式不一定滿足有窮性（死迴圈），另外，程式中的指令必須是機器可執行的，演算法中的指令無此限制一個演算法若用電腦語言來書寫，它就可以是一個程式演算法評價標準時間特性(時間複雜度T(n)

)空間特性(空間複雜度S(n)

)

一個特定演算法的“運行工作量”的大小，只依賴於問題的規模（通常用整數量n表示），或者說，它是問題規模的函數。

假如，隨著問題規模n的增長，演算法執行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為演算法的(漸近)時間複雜度。

從演算法中選取一種對於所研究的問題來說是基本操作

的原操作，以該基本操作在演算法中重複執行的次數作為演算法運行時間的衡量準則。例矩陣元素之和template<classElemType>ElemTypeSum(ElemTypea[][MAX_SIZE],intn)//操作結果:返回矩陣a中元素之和{ ElemTypes=0; //暫存和

for(inti=0;i<n;i++) for(intj=0;j<n;j++) s=s+a[i][j]; //遍曆求和

returns; //返回元素之和}基本操作:

加法“+”時間複雜度:

O(n2)四、演算法的存儲空間需求演算法的空間複雜度定義為:

表示隨著問題規模n的增大，演算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))面向對象的概念面向對象=對象＋類＋繼承對象由一組屬性值和在這組值上的一組服務（或稱操作）構成為什麼選用面向對象及C++語言

講述數據結構？PASCAL與C描述是面向過程的C++描述兼有面向過程與面向對象的特點用面向對象及C++描述與國際接軌，是市場需要第2章線性表線性表(LinearList)線性表的定義和特點定義

n（0）個數據元素的有限序列，記作

（a1,a2,…,an）

ai是表中數據元素，n是表長度。

遍曆逐項訪問：

從前向後從後向前

線性表的特點除第一個元素外，其他每一個元素有一個且僅有一個直接前驅。除最後一個元素外，其他每一個元素有一個且僅有一個直接後繼。a1a2a3a4a5a6線性表基本操作

1．intLength()const

初始條件：線性表已存在。

操作結果：返回線性表元素個數。

2．boolEmpty()const

初始條件：線性表已存在。

操作結果：如線性表為空，則返回true，否則返回false。3．voidClear()

初始條件：線性表已存在。

操作結果：清空線性表。

4．voidTraverse(void(*visit)(const

ElemType&))const

初始条件：线性表已存在。

操作结果：依次对线性表的每个元素调用函数(*visit)。5．StatusCodeGetElem(intposition,

ElemType&e)const

初始条件：线性表已存在，1≤position≤Length()。

操作结果：用e返回第position個元素的值。

6．StatusCodeSetElem(intposition,

constElemType&e)

初始条件：线性表已存在，1≤position≤Length()。

操作结果：将线性表的第position個位置的元素賦值為e。7．StatusCodeDelete(intposition, ElemType&e)

初始條件：線性表已存在，1≤position≤Length()。

操作结果：删除线性表的第position個位置的元素,並用e返回其值，長度減1。

8．StatusCodeInsert(intposition, constElemType&e)

初始條件：線性表已存在，1≤position≤Length()+1。

操作結果：線上性表的第position個位置前插入元素e，長度加1。線性表的順序存儲結構順序表(SequentialList)順序表的定義和特點定義將線性表中的元素相繼存放在一個連續的存儲空間中。可利用一維數組描述存儲結構特點線性表的順序存儲方式遍曆順序訪問

253457164809

012345data順序表(SeqList)類的定義//順序表類template<classelemType>classSqList{protected://順序表實現的數據成員: intcount; //元素個數

intmaxSize; //順序表最大元素個數

elemType*elems; //元素存儲空間//輔助函數

boolFull()const; //判斷線性表是否已滿

voidInit(intsize); //初始化線性表public://抽象數據類型方法聲明及重載編譯系統默認//方法聲明: SqList(intsize=DEFAULT_SIZE);//構造函數

virtual~SqList(); //析構函數

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空 voidTraverse(void(*Visit)(constelemType&)) const; //遍曆線性表

StatusCodeGetElem(intposition,elemType&e) const; //求指定位置的元素

StatusCodeSetElem(intposition,constelemType&e); //設置指定位置的元素值

StatusCodeDelete(intposition,elemType&e); //刪除元素

StatusCodeInsert(intposition,constelemType&e);

//插入元素

SqList(constSqList<elemType>©);

//複製構造函數

SqList<elemType>&operator=(const SqList<elemType>©); //賦值語句重載};順序表輔助函數的實現template<classElemType>boolSqList<ElemType>::Full()const//操作結果：如線性表已滿，則返回true，否則返回false{ returncount==maxSize;}template<classElemType>voidSqList<ElemType>::Init(intsize)//操作結果：初始化線性表為最大元素個數為size的空線// 性表{ maxSize=size; //最大元素個數

if(elems!=NULL)delete[]elems;//釋放存儲空間

elems=newElemType[maxSize];//分配存儲空間

count=0; //空線性表元素個數為0}template<classElemType>SqList<ElemType>::SqList(intsize)//操作結果：構造一個最大元素個數為size的空順序表{ elems=NULL; //未分配存儲空間前,elems為空

Init(size); //初始化線性表}template<classElemType>SqList<ElemType>::~SqList()//操作結果：銷毀線性表{ delete[]elems; //釋放存儲空間}順序表部分公共操作的實現表項的插入25345716480963

01234567data50插入x2534575016480963

01234567data50itemplate<classElemType>StatusCodeSqList<ElemType>::Insert(intposition, constElemType&e)//操作結果：線上性表的第position個位置前插入元素e,// position的的取值範圍為1≤position≤Length()+1// 如線性表已滿,則返回OVER_FLOW,// 如position合法,則返回SUCCESS,否則函數返回// RANGE_ERROR{ ElemTypetmp;

if(Full()) { //線性表已滿返回OVER_FLOW returnOVER_FLOW; } elseif(position<1||position>len+1) { //position範圍錯

returnRANGE_ERROR; }

else { //成功

count++; //插入後元素個數將自增1 for(intcurPosition=len; curPosition>=position;curPosition--) { //插入位置之後的元素右移

GetElem(curPosition,tmp); SetElem(curPosition+1,tmp); } SetElem(position,e);//將e賦值到position位置處

returnSUCCESS;//插入成功

}}表項的刪除2534575016480963

01234567data16刪除

x25345750480963

01234567datatemplate<classElemType>StatusCodeSqList<ElemType>::Delete(intposition, ElemType&e)//操作結果：刪除線性表的第position個位置的元素,並前// 用e返回其值,position的的取值範圍為// 1≤position≤Length(),position合法時函數返回// SUCCESS,否則函數返回RANGE_ERROR{ intlen=Length(); ElemTypetmp; if(position<1||position>=len) { //position範圍錯

returnRANGE_ERROR; }

else { //position合法

GetElem(position,e);

//用e返回被刪除元素的值

for(intcurPosition=position+1; curPosition<=len;curPosition++) { //被刪除元素之後的元素依次左移

GetElem(curPosition,tmp); SetElem(curPosition-1,tmp); } count--; //刪除後元素個數將自減1 returnSUCCESS; }}順序表的應用：集合的“交”運算//檔路徑名:s2_1\alg.htemplate<classElemType>voidDifference(constSqList<ElemType>&la,constSqList<ElemType>&lb,SqList<ElemType>&lc)//操作結果:用lc返回la和lb表示的集合的差集//方法:在la中取出元素,在lb中進行查找,如果未在lb中// 出現了,將其插入到lc{ ElemTypeaItem,bItem; lc.Clear(); //清空lc for(intaPosition=1;aPosition<=la.Length(); aPosition++) { la.GetElem(aPosition,aItem);

//取出la的一個元素aItem boolisExist=false;

//表示aItem是否在lb中出現

for(intbPosition=1;bPosition<=lb.Length(); bPosition++) { lb.GetElem(bPosition,bItem);

//取出lb的一個元素bItem if(aItem==bItem) { isExist=true; //aItem同時在la和lb中

//出現,置isExist為true break; //退出內層迴圈

} } if(!isExist) { //aItem在la中出現,而未在lb中未出現, // 將其插入到lc中

lc.Insert(lc.Length()+1,aItem); } }}線性表的鏈式存儲結構特點每個元素(表項)由結點(Node)構成。線性結構結點可以不連續存儲表可擴充單鏈表

(SinglyLinkedList)單鏈表的類範本類範本將類的數據成員和成員函數設計得更完整、更靈活。類範本更易於複用。在單鏈表的類範本定義中，增加了表頭結點。//結點類template<classElemType>structNode{//數據成員: ElemTypedata; //數據域

Node<ElemType>*next; //指針域//構造函數: Node(); //無參數的構造函數

Node(ElemTypeitem,Node<ElemType>*link= NULL);//已知數數據域和指針域建立結構};//簡單線性鏈表類template<classElemType>classSimpleLinkList{protected://鏈表實現的數據成員: Node<ElemType>*head; //頭結點指針//輔助函數

Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個結點的指針

voidInit(); //初始化線性表public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: SimpleLinkList(); //無參數構造函數

virtual~SimpleLinkList(); //析構函數

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆線性表

StatusCodeGetElem(intposition,ElemType&e) const; //求指定位置的元素

StatusCodeSetElem(intposition,constElemType &e); //設置指定位置的元素值 StatusCodeDelete(intposition,ElemType&e);

//刪除元素

StatusCodeInsert(intposition,constElemType&e);

//插入元素

SimpleLinkList(constSimpleLinkList<ElemType> ©); //複製構造函數

SimpleLinkList<ElemType>&operator=(const SimpleLinkList<ElemType>©);

//賦值語句重載};單鏈表中的插入與刪除插入newPtr=newNode<ElemType>(e,tmpPtr->next);tmpPtr->next=newPtr;

template<classElemType>StatusCodeSimpleLinkList<ElemType>::Insert( intposition,constElemType&e)//操作結果：線上性表的第position個位置前插入元素e// position的取值範圍為1≤position≤Length()+1// position合法時返回SUCCESS,否則函數返回// RANGE_ERROR{ if(position<1||position>Length()+1) { //position範圍錯

returnRANGE_ERROR; //位置不合法

} else { //position合法

Node<ElemType>*tmpPtr; tmpPtr=GetElemPtr(position-1);

//取出指向第position-1個結點的指針

Node<ElemType>*newPtr; newPtr=newNode<ElemType>(e, tmpPtr->next); //生成新結點

tmpPtr->next=newPtr;

//將tmpPtr插入到鏈表中

returnSUCCESS; }}刪除在單鏈表中刪除含b的結點template<classElemType>StatusCodeSimpleLinkList<ElemType>::Delete(intposition,ElemType&e)//操作結果：刪除線性表的第position個位置的元素,並用// e返回其值,position的取值範圍為// 1≤position≤Length(),position合法時函數返回// SUCCESS,否則函數返回RANGE_ERROR{ if(position<1||position>Length()) { //position範圍錯

returnRANGE_ERROR; } else { //position合法

Node<ElemType>*tmpPtr; tmpPtr=GetElemPtr(position-1);

//取出指向第position-1個結點的指針

Node<ElemType>*nextPtr=tmpPtr->next;

//nextPtr為tmpPtr的後繼

tmpPtr->next=nextPtr->next;//刪除結點

e=nextPtr->data;//用e返回被刪結點元素值

deletenextPtr; //釋放被刪結點

returnSUCCESS; }}迴圈鏈表(CircularList)迴圈鏈表是單鏈表的變形。迴圈鏈表最後一個結點的next指針不為0(NULL)，而是指向了表的前端。為簡化操作，在迴圈鏈表中往往加入表頭結點。迴圈鏈表的特點是：只要知道表中某一結點的地址，就可搜尋到所有其他結點的地址。迴圈鏈表示例//簡單迴圈鏈表類template<classElemType>classSimpleCircLinkList{protected://迴圈鏈表實現的數據成員: Node<ElemType>*head; //頭結點指針//輔助函數

Node<ElemType>*GetElemPtr(intposition)const;

//返回指向第position個結點的指針

voidInit(); //初始化線性表public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: SimpleCircLinkList(); //無參數的構造函數

virtual~SimpleCircLinkList(); //析構函數

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆線性表

StatusCodeGetElem(intposition,ElemType&e) const; //求指定位置的元素

StatusCodeSetElem(intposition,constElemType &e); //設置指定位置的元素值 StatusCodeDelete(intposition,ElemType&e);

//刪除元素

StatusCodeInsert(intposition,constElemType&e);

//插入元素

SimpleCircLinkList(const SimpleCircLinkList<ElemType>©);

//複製構造函數

SimpleCircLinkList<ElemType>&operator=(const SimpleCircLinkList<ElemType>©);

//賦值語句重載};用迴圈鏈表求解約瑟夫問題約瑟夫問題的提法

n個人圍成一個圓圈，首先第1個人從1開始一個人一個人順時針報數,報到第m個人，令其出列。然後再從下一個人開始，從1順時針報數，報到第m個人，再令其出列，…，如此下去,直到圓圈中只剩一個人為止。此人即為優勝者。例如n=8m=3//檔路徑名:s2_5\alg.hvoidJosephus(intn,intm)//操作結果:n個人圍成一個圓圈，首先第1個人從1開始一// 個人一個人順時針報數,報到第m個人，令其出列。// 然後再從下一個人開始，從1順時針報數報到第m// 個人，再令其出列，…，如此下去,直到圓圈中只// 剩一個人為止。此人即為優勝者{ SimpleCircLinkList<int>la; //定義空迴圈鏈表

intposition=0; //報數到的人在鏈表中序號

intout,winer; for(intk=1;k<=n;k++)la.Insert(k,k);

//建立數據域為1,2,..,n的迴圈鏈表 cout<<"出列者:"; for(inti=1;i<n;i++) { //迴圈n-1次，讓n-1個個出列

for(intj=1;j<=m;j++) { //從1報數到m position++; if(position>la.Length()) position=1; } la.Delete(position--,out);//報數到m的人出列

cout<<out<<""; } la.GetElem(1,winer); //剩下的一個人為優勝者

cout<<endl<<"優勝者:"<<winer<<endl;}雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅和後繼方向都能遊歷(遍曆)的線性鏈表。雙向鏈表每個結點結構：前驅方向

後繼方向雙向鏈表通常採用帶表頭結點的迴圈鏈表形式。雙向迴圈鏈表示例在鏈表結構中保存當前位置和元素個數

前面講解了三種線性表的三種鏈式存儲結構，這三種結構實現比較一致，處理簡單，特別適合於初學者，但許多應用程式是按順序處理線性表的中數據元素的，也就是處理完一個數據元素後再處理下一個數據元素，也可能要幾次引用同一個數據元素，比如在訪問下一個數據元素之前做GetElem和SetElem操作，對於這類應用程式，前面的鏈表實現效率低下，這時最好在鏈表結構中保存當前位置和元素個數。//線性鏈表類template<classElemType>classLinkList{protected://鏈表實現的數據成員: Node<ElemType>*head; //頭結點指針

mutableintcurPosition; //當前位置的序號

mutableNode<ElemType>*curPtr;

//指向當前位置的指針

intcount; //元素個數//輔助函數

Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個結點的指針

voidInit(); //初始化線性表public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: LinkList(); //無參數的構造函數

virtual~LinkList(); //析構函數

intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空

voidClear(); //將線性表清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆線性表 StatusCodeGetElem(intposition,ElemType&e) const; //求指定位置的元素

StatusCodeSetElem(intposition,constElemType &e); //設置指定位置的元素值

StatusCodeDelete(intposition,ElemType&e); //刪除元素

StatusCodeInsert(intposition,constElemType&e); //插入元素

LinkList(constLinkList<ElemType>©); //複製構造函數

LinkList<ElemType>&operator=(const LinkList<ElemType>©);

//賦值語句重載};在電腦中，可以用一個線性表來表示:P=(p0,p1,…，pn)多項的鏈表表示一元多項式但是對於形如

S(x)=1+3x10000–2x20000的多項式，上述表示方法是否合適？

一般情況下的一元稀疏多項式可寫成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指數為ei

的項的非零係數，

0≤e1<e2<┄<em=n可以下列線性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）

P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))表示//多項式類classPolynomial{protected://多項式實現的數據成員: LinkList<PolyItem>polyList;

//多項式組成的線性表public: //抽象數據類型方法聲明: Polynomial(){}; //無參構造函數

~Polynomial(){}; //析構函數

intLength()const; //求多項式的項數 boolIsZero()const; //判斷多項式是否為0 voidSetZero(); //將多項式置為0 voidDisplay(); //顯示多項式

voidInsItem(constPolyItem&item);//插入一項

Polynomialoperator+(constPolynomial&p)const;

//加法運算符重載

Polynomialoperator-(constPolynomial&p)const;

//減法運算符重載

Polynomialoperator*(constPolynomial&p)const;

//乘法運算符重載

Polynomial(constPolynomial©);

//複製構造函數 Polynomial(constLinkList<PolyItem> ©LinkList);

//由多項式組成的線性表構造多項式

Polynomial&operator=(constPolynomial©);

//賦值語句重載

Polynomial&operator=(constLinkList<PolyItem> ©LinkList); //賦值語句重載};第3章棧和佇列棧和佇列是限定插入和刪除只能在表的“端點”進行的線性表。棧和佇列是兩種常用的數據類型棧只允許在一端插入和刪除的線性表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點後進先出(LIFO)棧(Stack)退棧進棧a1anan-1

topbottom1．intLength()const

初始條件：棧已存在。

操作結果：返回棧元素個數。

2．boolEmpty()const

初始條件：棧已存在。

操作結果：如棧為空，則返回true，否則返回false

3．voidClear()

初始條件：棧已存在。

操作結果：清空棧。

4．voidTraverse(void(*Visit)(constElemType&))const

初始條件：棧已存在。

操作結果：從棧底到棧頂依次對棧的每個元素調用函數(*visit)

5．StatusCodePush(constElemType&e)

初始條件：棧已存在。

操作結果：插入元素e為新的棧頂元素。

a1a2anx……6．StatusCodeTop(ElemType&e)const

初始條件：棧已存在且非空。

操作結果：用e返回棧頂元素。

a1a2an……7．StatusCodePop(ElemType&e)

初始條件：棧已存在且非空。

操作結果：刪除棧頂元素，並用e返回棧頂元素。a1a2anan-1

……

棧的數組表示

—順序棧

//順序棧類template<classElemType>classSqStack{protected://順序棧的數據成員: intcount; //元素個數

intmaxSize; //棧最大元素個數

ElemType*elems; //元素存儲空間//輔助函數

boolFull()const; //判斷棧是否已滿

voidInit(intsize); //初始化棧public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: SqStack(intsize=DEFAULT_SIZE);//構造函數

virtual~SqStack(); //析構函數

intLength()const; //求棧長度

boolEmpty()const; //判斷棧是否為空

voidClear(); //將棧清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆棧

StatusCodePush(constElemType&e); //入棧

StatusCodeTop(ElemType&e)const;//返回棧頂

StatusCodePop(ElemType&e); //出棧

SqStack(constSqStack<ElemType>©);

//複製構造函數

SqStack<ElemType>&operator=(const SqStack<ElemType>©);//賦值語句重載};複製構造函數template<classElemType>SqStack<ElemType>::SqStack(constSqStack<ElemType>©)//操作結果：由棧copy構造新棧--複製構造函數{ elems=NULL; //未分配存儲空間前,elems為空

Init(copy.maxSize); //初始化新棧

count=copy.count; //棧元素個數

for(intcurPosition=1;curPosition<=Length(); curPosition++) { //從棧底到棧頂對棧copy的每個元素進行複製

elems[curPosition-1]= copy.elems[curPosition-1]; }}template<classElemType>SqStack<ElemType>&SqStack<ElemType>::operator= (constSqStack<ElemType>©)//操作結果：將棧copy賦值給當前棧--賦值語句重載{ if(©!=this) { Init(copy.maxSize); //初始化當前棧

count=copy.count; //複製棧元素個數

for(intcurPosition=1;curPosition<= Length();curPosition++) { //從棧底到棧頂對棧複製copy的元素

elems[curPosition-1]= copy.elems[curPosition-1]; } } return*this;}

top空棧toptoptoptoptopa進棧b進棧aababcdee進棧abcdef進棧溢出abdee退棧ctopc退棧b退棧abaa退棧空棧topabdd退棧ctopabctoptop

雙棧共用一個棧空間b[0]t[0]t[1]b[1]0maxSize-1V棧的鏈接表示—鏈式棧鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執行鏈式棧的棧頂在鏈頭top鏈式棧(LinkedStack)類的定義//鏈棧類template<classElemType>classLinkStack{protected://鏈棧實現的數據成員: Node<ElemType>*top; //棧頂指針//輔助函數

voidInit(); //初始化棧public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: LinkStack(); //無參數的構造函數

virtual~LinkStack(); //析構函數

intLength()const; //求棧長度 boolEmpty()const; //判斷棧是否為空

voidClear(); //將棧清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆棧

StatusCodePush(constElemType&e); //入棧

StatusCodeTop(ElemType&e)const;

//返回棧頂元素

StatusCodePop(ElemType&e); //出棧

LinkStack(constLinkStack<ElemType>©);

//複製構造函數

LinkStack<ElemType>&operator=(const LinkStack<ElemType>©);//重載賦值};template<classElemType>LinkStack<ElemType>::LinkStack()//操作結果：構造一個空棧表{ Init();}template<classElemType>LinkStack<ElemType>::~LinkStack()//操作結果：銷毀棧{ Clear();}template<classElemType>StatusCodeLinkStack<ElemType>::Push( constElemType&e)//操作結果：將元素e追加到棧頂,如成功則返加SUCCESS,// 否則如動態記憶體已耗盡將返回OVER_FLOW{ Node<ElemType>*new_top= newNode<ElemType>(e,top); if(new_top==NULL) { //動態記憶體耗盡

returnOVER_FLOW; } else { //操作成功

top=new_top; returnSUCCESS; }}template<classElemType>StatusCodeLinkStack<ElemType>::Pop(ElemType&e)//操作結果：如棧非空,刪除棧頂元素,並用e返回棧頂元素,// 函數返回SUCCESS,否則函數返回UNDER_FLOW{ if(Empty()) { //棧空

returnUNDER_FLOW; } else { //操作成功

Node<ElemType>*old_top=top; //舊棧頂

e=old_top->data; //用e返回棧頂元素

top=old_top->next; //top指向新棧頂

deleteold_top; //刪除舊棧頂

returnSUCCESS; }}template<classElemType>StatusCodeLinkStack<ElemType>::Top(ElemType&e) const//操作結果：如棧非空,用e返回棧頂元素,函數返回\// SUCCESS,否則函數返回UNDER_FLOW{ if(Empty()) { //棧空

returnUNDER_FLOW; } else { //棧非空,操作成功

e=top->data; //用e返回棧頂元素

returnSUCCESS; }}template<classElemType>voidLinkStack<ElemType>::Traverse(void(*Visit)( constElemType&))const//操作結果：從棧底到棧頂依次對棧的每個元素調用函// 數(*visit){ Node<ElemType>*tmpPtr; LinkStack<ElemType>tmpS; //臨時棧

for(tmpPtr=top;tmpPtr!=NULL; tmpPtr=tmpPtr->next) { //用tmpPtr依次指向當前棧的每個元素

tmpS.Push(tmpPtr->data); //每個元素入棧

} for(tmpPtr=tmpS.top;tmpPtr!=NULL; tmpPtr=tmpPtr->next) { //從棧頂到棧底依次指向棧tmpS的每個元素

(*Visit)(tmpPtr->data); }}運算式求值一個運算式由運算元(亦稱運算對象)、操作符

(亦稱運算符)和分界符組成。算術運算式有三種表示：中綴(infix)表示

<運算元><操作符><運算元>，如A+B；首碼(prefix)表示

<操作符><運算元><運算元>，如+AB；尾碼(postfix)表示

<運算元><運算元><操作符>，如AB+；運算式的中綴表示

運算式中相鄰兩個操作符的計算次序為：優先順序高的先計算；優先順序相同的自左向右計算；當使用括弧時從最內層括弧開始計算。C++中操作符的優先順序

優先順序

操作符

1 單目+、-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 一般運算式的操作符有4種類型：算術操作符如雙目操作符（+、-、*、/和%）以及單目操作符（+、-）。關係操作符包括<、<=、==、!=、>=、>。這些操作符主要用於比較。邏輯操作符如與(&&)、或(||)、非(!)。括弧‘(’和‘)’它們的作用是改變運算順序。

中綴運算式中各個算術操作符的優先順序isp叫做棧內(instackpriority)優先數icp叫做棧外(incomingpriority)優先數。操作符優先數相等的情況只出現在括弧配對或棧底的‘=’號與輸入流最後的‘=’號配對時。中綴算術運算式求值中綴算術運算式求值使用兩個棧，操作符棧OPTR(operator)，運算元棧OPND(operand)，對中綴運算式求值的一般規則：(1)在OPTR棧中壓入一個‘=’。(2)從輸入流獲取一字元ch。(3)取出OPTR的棧頂OPTR_top。(4)當OPTR_top!=‘=’或ch!=‘=’時,迴圈執行以下工作,否則結束演算法。此時在OPND棧的棧頂得到運算結果。

while(OPTR_top!=‘=’

||ch!=‘=’){

①若ch不是操作符，則將字元放回輸入流(cin.putback)，讀運算元newoperand並進OPND棧，並讀入下一字元送入ch；

②若ch是操作符，比較icp(ch)的優先順序和isp(OPTR_top)的優先順序：

若isp(OPTR_top)<icp(ch)，則ch進OPTR棧，從中綴運算式取下一字元送入ch；

若isp(OPTR_top)>icp(ch)，則從OPND棧退出a2和a1，從OPTR棧退出θ,形成運算指令(a1)θ(a2)，結果進OPND棧；

若isp(OPTR_top)==icp(ch)且ch==

“)”，則從OPTR棧退出棧頂的“(”，對消括弧，然後從中綴運算式取下一字元送入ch。

③取出OPTR的棧頂OPTR_top。}佇列佇列(

Queue)定義佇列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進先出(FIFO,FirstInFirstOut)a1

a2

a3

anfrontrear

1．intLength()const

初始條件：佇列已存在。

操作結果：返回佇列長度

2．boolEmpty()const

初始條件：佇列已存在。

操作結果：如佇列為空，則返回true，否則返回false

3．voidClear()

初始條件：佇列已存在。

操作結果：清空佇列4．voidTraverse(void(*Visit)(constElemType&))const

初始條件：佇列已存在。

操作結果：依次對佇列的每個元素調用函數(*visit)

5．StatusCodeOutQueue(ElemType&e)

初始條件：佇列非空。

操作結果：刪除隊頭元素，並用e返回其值。

a1a2an……

6．StatusCodeGetHead(ElemType&e)const

初始條件：佇列非空。

操作結果：用e返回隊頭元素。

a1a2an……7．StatusCodeInQueue(constElemType&e)

初始條件：佇列已存在。

操作結果：插入元素e為新的隊尾。a1a2anx……佇列的鏈接表示—鏈式佇列

隊頭在鏈頭，隊尾在鏈尾。鏈式佇列在進隊時無隊滿問題，但有隊空問題。隊空條件為front==NULLfrontrear//鏈佇列類template<classElemType>classLinkQueue{protected://鏈佇列實現的數據成員: Node<ElemType>*front,*rear;//隊頭隊尾指指//輔助函數: voidInit(); //初始化佇列public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: LinkQueue(); //無參數的構造函數

virtual~LinkQueue(); //析構函數

intLength()const; //求佇列長度

boolEmpty()const; //判斷佇列是否為空

voidClear(); //將佇列清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆佇列

StatusCodeOutQueue(ElemType&e);//出隊操作

StatusCodeGetHead(ElemType&e)const;

//取隊頭操作

StatusCodeInQueue(constElemType&e);//入隊

LinkQueue(constLinkQueue<ElemType>©);

//複製構造函數

LinkQueue<ElemType>&operator=(const LinkQueue<ElemType>©);//重載賦值};順序佇列的進隊和出隊frontrear空佇列frontrearA進隊AfrontrearB進隊ABfrontrearC,D進隊ABCDfrontrearA退隊BCDfrontrearB退隊CDfrontrearE,F,G進隊CDEFGCDEFGfrontrearH進隊,溢出佇列的進隊和出隊原則

進隊時將新元素按

rear指示位置加入再將隊尾指針先進一rear=rear+1。

出隊時將下標為

front的元素取出,再將隊頭指針先進一front=front+1。

隊滿時再進隊將溢出出錯；隊空時再出隊將隊空處理。解決辦法之一：將佇列元素存放數組首尾相接，形成迴圈(環形)佇列。

01234567front01234567front01234567frontrearAABCrearrear空佇列A進隊B,C進隊0123456701234567A退隊B退隊01234567D,E,F,G,H,I進隊frontBCrearAfrontBCrearfrontCrearDEFGHI佇列存放數組被當作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize-1直接進到0，可用語言的取模(餘數)運算實現。隊頭指針進1:front=(front+1)%maxSize;隊尾指針進1:rear=(rear+1)%maxSize;佇列初始化：front=rear=0;隊空條件：front

==

rear;隊滿條件：(rear+1)%maxSize==front

迴圈佇列(CircularQueue)//迴圈佇列類template<classElemType>classSqQueue{protected: intfront,rear; //隊頭隊尾

intmaxSize; //佇列最大元素個數

ElemType*elem; //元素存儲空間//輔助函數: boolFull()const; //判斷棧是否已滿

voidInit(); //初始化佇列public://抽象數據類型方法聲明及重載編譯系統默認方法聲明: SqQueue(intsize=DEFAULT_SIZE);//構造函數

virtual~SqQueue(); //析構函數

intLength()const; //求佇列長度

boolEmpty()const; //判斷佇列是否為空

voidClear(); //將佇列清空

voidTraverse(void(*Visit)(constElemType&)) const; //遍曆佇列

StatusCodeOutQueue(ElemType&e);//出隊操作

StatusCodeGetHead(ElemType&e)const;

//取隊頭操作

StatusCodeInQueue(constElemType&e);//入隊

SqQueue(constSqQueue<ElemType>©);

//複製構造函數

SqQueue<ElemType>&operator=(const SqQueue<ElemType>©);//賦值語句重載};template<classElemType>boolSqQueue<ElemType>::Full()const//操作結果：如佇列已滿，則返回true，否則返回false{ returnLength()==maxSize-1;}template<classElemType>voidSqQueue<ElemType>::Init()//操作結果：初始化佇列{ rear=front=0;}template<classElemType>intSqQueue<ElemType>::Length()const//操作結果：返回佇列長度 { return(rear-front+maxSize)%maxSize;}template<classElemType>voidSqQu