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

(dataelement)數(shù)據(jù)的基本單位。在電腦程式中常作為一個(gè)整體進(jìn)行考慮和處理有時(shí)一個(gè)數(shù)據(jù)元素可以由若干資料項(xiàng)目(DataItem)組成。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄什麼是數(shù)據(jù)結(jié)構(gòu)定義:

由某一數(shù)據(jù)元素的集合及該集合中所有數(shù)據(jù)元素之間的關(guān)係組成記為：

Data_Structure={D,S}

其中，D

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

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

鏈?zhǔn)酱尜A

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

定義：一組性質(zhì)相同的值的集合,以及定義於這個(gè)值集合上的一組操作的總稱如C語(yǔ)言中有如下數(shù)據(jù)類型

charintfloatdoublevoid

字元型整型浮點(diǎn)型雙精度型無值

構(gòu)造數(shù)據(jù)類型由不同成分構(gòu)成基本數(shù)據(jù)類型可以看作是電腦中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型

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

用ADT描述程式處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特徵、其所能完成的功能以及它和外部用戶的介面（即外界使用它的方法）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，並且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)算法

演算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列演算法定義演算法應(yīng)具有的性質(zhì)正確性具體性確定性有限性可讀性健壯性正確性

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

確定性

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

對(duì)於任意一組合法輸入值，在執(zhí)行有限步驟之後一定能結(jié)束，即：演算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成可讀性

演算法應(yīng)具備良好的可讀性，這樣的演算法有利於演算法的查錯(cuò)及對(duì)演算法的理解，一般演算法的邏輯必須清楚、結(jié)構(gòu)簡(jiǎn)單，所有識(shí)別字必須具有實(shí)際含義，能見名知義。健壯性

健壯性指當(dāng)輸入數(shù)據(jù)非法時(shí)，演算法能作適當(dāng)?shù)奶幚韥K作出反應(yīng)，而不應(yīng)死機(jī)或輸出異常結(jié)果演算法描述方法

用自然語(yǔ)言描述演算法

用我們?nèi)粘Ｉ钪械淖匀徽Z(yǔ)言（可以是中文形式，也可以是英文形式）也可以描述演算法用流程圖描述演算法

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

我們還可以用數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來描述演算法

用C++描述演算法

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

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

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

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

)

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

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

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

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

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

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

加法“+”時(shí)間複雜度:

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

表示隨著問題規(guī)模n的增大，演算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=O(g(n))面向?qū)ο蟮母拍蠲嫦驅(qū)ο?對(duì)象＋類＋繼承對(duì)象由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成為什麼選用面向?qū)ο蠹癈++語(yǔ)言

講述數(shù)據(jù)結(jié)構(gòu)？PASCAL與C描述是面向過程的C++描述兼有面向過程與面向?qū)ο蟮奶攸c(diǎn)用面向?qū)ο蠹癈++描述與國(guó)際接軌，是市場(chǎng)需要第2章線性表線性表(LinearList)線性表的定義和特點(diǎn)定義

n（0）個(gè)數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

ai是表中數(shù)據(jù)元素，n是表長(zhǎng)度。

遍曆逐項(xiàng)訪問：

從前向後從後向前

線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最後一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接後繼。a1a2a3a4a5a6線性表基本操作

1．intLength()const

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

操作結(jié)果：返回線性表元素個(gè)數(shù)。

2．boolEmpty()const

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

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

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

操作結(jié)果：清空線性表。

4．voidTraverse(void(*visit)(const

ElemType&))const

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

操作結(jié)果：依次對(duì)線性表的每個(gè)元素調(diào)用函數(shù)(*visit)。5．StatusCodeGetElem(intposition,

ElemType&e)const

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

操作結(jié)果：用e返回第position個(gè)元素的值。

6．StatusCodeSetElem(intposition,

constElemType&e)

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

操作結(jié)果：將線性表的第position個(gè)位置的元素賦值為e。7．StatusCodeDelete(intposition, ElemType&e)

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

操作結(jié)果：刪除線性表的第position個(gè)位置的元素,並用e返回其值，長(zhǎng)度減1。

8．StatusCodeInsert(intposition, constElemType&e)

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

操作結(jié)果：線上性表的第position個(gè)位置前插入元素e，長(zhǎng)度加1。線性表的順序存儲(chǔ)結(jié)構(gòu)順序表(SequentialList)順序表的定義和特點(diǎn)定義將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中?？衫靡痪S數(shù)組描述存儲(chǔ)結(jié)構(gòu)特點(diǎn)線性表的順序存儲(chǔ)方式遍曆順序訪問

253457164809

012345data順序表(SeqList)類的定義//順序表類template<classelemType>classSqList{protected://順序表實(shí)現(xiàn)的數(shù)據(jù)成員: intcount; //元素個(gè)數(shù)

intmaxSize; //順序表最大元素個(gè)數(shù)

elemType*elems; //元素存儲(chǔ)空間//輔助函數(shù)

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

voidInit(intsize); //初始化線性表public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)//方法聲明: SqList(intsize=DEFAULT_SIZE);//構(gòu)造函數(shù)

virtual~SqList(); //析構(gòu)函數(shù)

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

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

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

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

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

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

StatusCodeInsert(intposition,constelemType&e);

//插入元素

SqList(constSqList<elemType>©);

//複製構(gòu)造函數(shù)

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

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

elems=newElemType[maxSize];//分配存儲(chǔ)空間

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

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

01234567data50插入x2534575016480963

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

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

returnRANGE_ERROR; }

else { //成功

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

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

returnSUCCESS;//插入成功

}}表項(xiàng)的刪除2534575016480963

01234567data16刪除

x25345750480963

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

returnRANGE_ERROR; }

else { //position合法

GetElem(position,e);

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

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

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

//取出la的一個(gè)元素aItem boolisExist=false;

//表示aItem是否在lb中出現(xiàn)

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

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

//出現(xiàn),置isExist為true break; //退出內(nèi)層迴圈

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

lc.Insert(lc.Length()+1,aItem); } }}線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)結(jié)點(diǎn)可以不連續(xù)存儲(chǔ)表可擴(kuò)充單鏈表

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

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

Node(ElemTypeitem,Node<ElemType>*link= NULL);//已知數(shù)數(shù)據(jù)域和指針域建立結(jié)構(gòu)};//簡(jiǎn)單線性鏈表類template<classElemType>classSimpleLinkList{protected://鏈表實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*head; //頭結(jié)點(diǎn)指針//輔助函數(shù)

Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個(gè)結(jié)點(diǎn)的指針

voidInit(); //初始化線性表public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SimpleLinkList(); //無參數(shù)構(gòu)造函數(shù)

virtual~SimpleLinkList(); //析構(gòu)函數(shù)

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

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

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

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

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

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

//刪除元素

StatusCodeInsert(intposition,constElemType&e);

//插入元素

SimpleLinkList(constSimpleLinkList<ElemType> ©); //複製構(gòu)造函數(shù)

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

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

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

returnRANGE_ERROR; //位置不合法

} else { //position合法

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

//取出指向第position-1個(gè)結(jié)點(diǎn)的指針

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

tmpPtr->next=newPtr;

//將tmpPtr插入到鏈表中

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

returnRANGE_ERROR; } else { //position合法

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

//取出指向第position-1個(gè)結(jié)點(diǎn)的指針

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

//nextPtr為tmpPtr的後繼

tmpPtr->next=nextPtr->next;//刪除結(jié)點(diǎn)

e=nextPtr->data;//用e返回被刪結(jié)點(diǎn)元素值

deletenextPtr; //釋放被刪結(jié)點(diǎn)

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

Node<ElemType>*GetElemPtr(intposition)const;

//返回指向第position個(gè)結(jié)點(diǎn)的指針

voidInit(); //初始化線性表public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SimpleCircLinkList(); //無參數(shù)的構(gòu)造函數(shù)

virtual~SimpleCircLinkList(); //析構(gòu)函數(shù)

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

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

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

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

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

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

//刪除元素

StatusCodeInsert(intposition,constElemType&e);

//插入元素

SimpleCircLinkList(const SimpleCircLinkList<ElemType>©);

//複製構(gòu)造函數(shù)

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

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

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

intposition=0; //報(bào)數(shù)到的人在鏈表中序號(hào)

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

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

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

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

cout<<endl<<"優(yōu)勝者:"<<winer<<endl;}雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和後繼方向都能遊歷(遍曆)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)：前驅(qū)方向

後繼方向雙向鏈表通常採(cǎi)用帶表頭結(jié)點(diǎn)的迴圈鏈表形式。雙向迴圈鏈表示例在鏈表結(jié)構(gòu)中保存當(dāng)前位置和元素個(gè)數(shù)

前面講解了三種線性表的三種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，這三種結(jié)構(gòu)實(shí)現(xiàn)比較一致，處理簡(jiǎn)單，特別適合於初學(xué)者，但許多應(yīng)用程式是按順序處理線性表的中數(shù)據(jù)元素的，也就是處理完一個(gè)數(shù)據(jù)元素後再處理下一個(gè)數(shù)據(jù)元素，也可能要幾次引用同一個(gè)數(shù)據(jù)元素，比如在訪問下一個(gè)數(shù)據(jù)元素之前做GetElem和SetElem操作，對(duì)於這類應(yīng)用程式，前面的鏈表實(shí)現(xiàn)效率低下，這時(shí)最好在鏈表結(jié)構(gòu)中保存當(dāng)前位置和元素個(gè)數(shù)。//線性鏈表類template<classElemType>classLinkList{protected://鏈表實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*head; //頭結(jié)點(diǎn)指針

mutableintcurPosition; //當(dāng)前位置的序號(hào)

mutableNode<ElemType>*curPtr;

//指向當(dāng)前位置的指針

intcount; //元素個(gè)數(shù)//輔助函數(shù)

Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個(gè)結(jié)點(diǎn)的指針

voidInit(); //初始化線性表public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: LinkList(); //無參數(shù)的構(gòu)造函數(shù)

virtual~LinkList(); //析構(gòu)函數(shù)

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

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

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

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

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

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

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

LinkList(constLinkList<ElemType>©); //複製構(gòu)造函數(shù)

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

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

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

一般情況下的一元稀疏多項(xiàng)式可寫成

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

是指數(shù)為ei

的項(xiàng)的非零係數(shù)，

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

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

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

//多項(xiàng)式組成的線性表public: //抽象數(shù)據(jù)類型方法聲明: Polynomial(){}; //無參構(gòu)造函數(shù)

~Polynomial(){}; //析構(gòu)函數(shù)

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

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

Polynomialoperator+(constPolynomial&p)const;

//加法運(yùn)算符重載

Polynomialoperator-(constPolynomial&p)const;

//減法運(yùn)算符重載

Polynomialoperator*(constPolynomial&p)const;

//乘法運(yùn)算符重載

Polynomial(constPolynomial©);

//複製構(gòu)造函數(shù) Polynomial(constLinkList<PolyItem> ©LinkList);

//由多項(xiàng)式組成的線性表構(gòu)造多項(xiàng)式

Polynomial&operator=(constPolynomial©);

//賦值語(yǔ)句重載

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

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

topbottom1．intLength()const

初始條件：棧已存在。

操作結(jié)果：返回棧元素個(gè)數(shù)。

2．boolEmpty()const

初始條件：棧已存在。

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

3．voidClear()

初始條件：棧已存在。

操作結(jié)果：清空棧。

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

初始條件：棧已存在。

操作結(jié)果：從棧底到棧頂依次對(duì)棧的每個(gè)元素調(diào)用函數(shù)(*visit)

5．StatusCodePush(constElemType&e)

初始條件：棧已存在。

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

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

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

操作結(jié)果：用e返回棧頂元素。

a1a2an……7．StatusCodePop(ElemType&e)

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

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

……

棧的數(shù)組表示

—順序棧

//順序棧類template<classElemType>classSqStack{protected://順序棧的數(shù)據(jù)成員: intcount; //元素個(gè)數(shù)

intmaxSize; //棧最大元素個(gè)數(shù)

ElemType*elems; //元素存儲(chǔ)空間//輔助函數(shù)

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

voidInit(intsize); //初始化棧public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SqStack(intsize=DEFAULT_SIZE);//構(gòu)造函數(shù)

virtual~SqStack(); //析構(gòu)函數(shù)

intLength()const; //求棧長(zhǎng)度

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

voidClear(); //將棧清空

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

StatusCodePush(constElemType&e); //入棧

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

StatusCodePop(ElemType&e); //出棧

SqStack(constSqStack<ElemType>©);

//複製構(gòu)造函數(shù)

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

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

count=copy.count; //棧元素個(gè)數(shù)

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

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

count=copy.count; //複製棧元素個(gè)數(shù)

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

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

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧ctopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptop

雙棧共用一個(gè)?？臻gb[0]t[0]t[1]b[1]0maxSize-1V棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^top鏈?zhǔn)綏?LinkedStack)類的定義//鏈棧類template<classElemType>classLinkStack{protected://鏈棧實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*top; //棧頂指針//輔助函數(shù)

voidInit(); //初始化棧public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: LinkStack(); //無參數(shù)的構(gòu)造函數(shù)

virtual~LinkStack(); //析構(gòu)函數(shù)

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

voidClear(); //將棧清空

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

StatusCodePush(constElemType&e); //入棧

StatusCodeTop(ElemType&e)const;

//返回棧頂元素

StatusCodePop(ElemType&e); //出棧

LinkStack(constLinkStack<ElemType>©);

//複製構(gòu)造函數(shù)

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

returnOVER_FLOW; } else { //操作成功

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

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

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

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

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

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

} for(tmpPtr=tmpS.top;tmpPtr!=NULL; tmpPtr=tmpPtr->next) { //從棧頂?shù)綏５滓来沃赶驐mpS的每個(gè)元素

(*Visit)(tmpPtr->data); }}運(yùn)算式求值一個(gè)運(yùn)算式由運(yùn)算元(亦稱運(yùn)算對(duì)象)、操作符

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

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

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

<運(yùn)算元><運(yùn)算元><操作符>，如AB+；運(yùn)算式的中綴表示

運(yùn)算式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先順序高的先計(jì)算；優(yōu)先順序相同的自左向右計(jì)算；當(dāng)使用括弧時(shí)從最內(nèi)層括弧開始計(jì)算。C++中操作符的優(yōu)先順序

優(yōu)先順序

操作符

1 單目+、-、！

2 *、/、% 3 +、-

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

中綴運(yùn)算式中各個(gè)算術(shù)操作符的優(yōu)先順序isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括弧配對(duì)或棧底的‘=’號(hào)與輸入流最後的‘=’號(hào)配對(duì)時(shí)。中綴算術(shù)運(yùn)算式求值中綴算術(shù)運(yùn)算式求值使用兩個(gè)棧，操作符棧OPTR(operator)，運(yùn)算元棧OPND(operand)，對(duì)中綴運(yùn)算式求值的一般規(guī)則：(1)在OPTR棧中壓入一個(gè)‘=’。(2)從輸入流獲取一字元ch。(3)取出OPTR的棧頂OPTR_top。(4)當(dāng)OPTR_top!=‘=’或ch!=‘=’時(shí),迴圈執(zhí)行以下工作,否則結(jié)束演算法。此時(shí)在OPND棧的棧頂?shù)玫竭\(yùn)算結(jié)果。

while(OPTR_top!=‘=’

||ch!=‘=’){

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

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

若isp(OPTR_top)<icp(ch)，則ch進(jìn)OPTR棧，從中綴運(yùn)算式取下一字元送入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ì)消括弧，然後從中綴運(yùn)算式取下一字元送入ch。

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

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

a2

a3

anfrontrear

1．intLength()const

初始條件：佇列已存在。

操作結(jié)果：返回佇列長(zhǎng)度

2．boolEmpty()const

初始條件：佇列已存在。

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

3．voidClear()

初始條件：佇列已存在。

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

初始條件：佇列已存在。

操作結(jié)果：依次對(duì)佇列的每個(gè)元素調(diào)用函數(shù)(*visit)

5．StatusCodeOutQueue(ElemType&e)

初始條件：佇列非空。

操作結(jié)果：刪除隊(duì)頭元素，並用e返回其值。

a1a2an……

6．StatusCodeGetHead(ElemType&e)const

初始條件：佇列非空。

操作結(jié)果：用e返回隊(duì)頭元素。

a1a2an……7．StatusCodeInQueue(constElemType&e)

初始條件：佇列已存在。

操作結(jié)果：插入元素e為新的隊(duì)尾。a1a2anx……佇列的鏈接表示—鏈?zhǔn)絹辛?/p>

隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)絹辛性谶M(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。隊(duì)空條件為front==NULLfrontrear//鏈佇列類template<classElemType>classLinkQueue{protected://鏈佇列實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*front,*rear;//隊(duì)頭隊(duì)尾指指//輔助函數(shù): voidInit(); //初始化佇列public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: LinkQueue(); //無參數(shù)的構(gòu)造函數(shù)

virtual~LinkQueue(); //析構(gòu)函數(shù)

intLength()const; //求佇列長(zhǎng)度

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

voidClear(); //將佇列清空

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

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

StatusCodeGetHead(ElemType&e)const;

//取隊(duì)頭操作

StatusCodeInQueue(constElemType&e);//入隊(duì)

LinkQueue(constLinkQueue<ElemType>©);

//複製構(gòu)造函數(shù)

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

進(jìn)隊(duì)時(shí)將新元素按

rear指示位置加入再將隊(duì)尾指針先進(jìn)一rear=rear+1。

出隊(duì)時(shí)將下標(biāo)為

front的元素取出,再將隊(duì)頭指針先進(jìn)一front=front+1。

隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)；隊(duì)空時(shí)再出隊(duì)將隊(duì)空處理。解決辦法之一：將佇列元素存放數(shù)組首尾相接，形成迴圈(環(huán)形)佇列。

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

==

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

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

intmaxSize; //佇列最大元素個(gè)數(shù)

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

voidInit(); //初始化佇列public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SqQueue(intsize=DEFAULT_SIZE);//構(gòu)造函數(shù)

virtual~SqQueue(); //析構(gòu)函數(shù)

intLength()const; //求佇列長(zhǎng)度

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

voidClear(); //將佇列清空

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

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

StatusCodeGetHead(ElemType&e)const;

//取隊(duì)頭操作

StatusCodeInQueue(constElemType&e);//入隊(duì)

SqQueue(constSqQueue<ElemType>©);

//複製構(gòu)造函數(shù)

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