《數(shù)據(jù)結(jié)構(gòu)與算法》第四章 棧、隊(duì)列和數(shù)組

第四章棧、隊(duì)列和數(shù)組4.1棧4.2隊(duì)列4.3數(shù)組4.1棧棧棧（stack）是限定僅在一端進(jìn)行插入和刪除的線性表。能進(jìn)行插入和刪除的這一端稱為棧頂（top），表的另一端稱為棧底（bottom）。插入和刪除元素都要涉及棧頂，因此棧頂是棧的最重要的概念。在棧頂插入一個(gè)元素稱為壓棧（push）或入棧，從棧頂刪除一個(gè)元素稱為出棧（pop）。當(dāng)我們用原來(lái)線性表的記號(hào)來(lái)表示棧的時(shí)候，?？梢詫憺椋篠=(a0,a1,…,an-1)當(dāng)指定an-1那一端為棧頂?shù)臅r(shí)候，另一端a0就是棧底。當(dāng)n=0時(shí)，稱為空棧。入棧時(shí)按a0,a1,…,an-1的次序入棧，而出棧時(shí)次序剛好相反，先退出an-1，然后才能退出an-2，最后退出a0。所以棧又稱為后進(jìn)先出（LIFO，LastInFirstOut）結(jié)構(gòu)。和線性表一樣，實(shí)現(xiàn)棧的方法有許多種，下面介紹兩種方法：順序棧和鏈?zhǔn)綏＃鼈兎謩e對(duì)應(yīng)于順序表和單鏈表，但實(shí)現(xiàn)起來(lái)更簡(jiǎn)單些。下面給出棧的抽象數(shù)據(jù)類型描述：棧的抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型stack{

實(shí)例

元素的線性表一端為棧底，另一端為棧頂操作

Create(): 創(chuàng)建一個(gè)空棧

isEmpty(): 如果棧為空，則返回TRUE，否 則返回FALSE

IsFull(): 如果棧滿，則返回TRUE，否則 返回FALSE

Top(): 返回棧頂元素

Add(x): 向棧中添加元素x

Delete(x): 刪除棧頂元素，并將它傳送給x

}4.1.1順序棧順序棧 用數(shù)組實(shí)現(xiàn)的棧。 實(shí)現(xiàn)中使用數(shù)組listarray保存棧中各元素，listarray說(shuō)明為私有類型，實(shí)現(xiàn)了對(duì)棧的封裝，這意味著對(duì)這個(gè)數(shù)組的訪問(wèn)只能通過(guò)類中定義的方法push()、pop()、topValue()等進(jìn)行，從而保證棧中數(shù)據(jù)的合法性。順序棧的具體實(shí)現(xiàn)如下：

classstack{ //基于數(shù)組的棧類

private:

intsize; //棧的最大容量

inttop; //棧頂元素的下標(biāo)

ELEM*listarray; //保存棧元素的數(shù)組

public:

stack(const

int

sz=LIST_SIZE) //構(gòu)造函數(shù)：初始化

{size=sz;top=0;listarray=newELEM[sz];}

~stack(); //析構(gòu)函數(shù)：釋放數(shù)組占用空間

{delete[]listarray;}

voidclear() //從棧中清除所有元素

{top=0;}

voidpush(constELEM&item)//將元素item壓入棧中

{assert(top<size);listarray[top++]=item;}

ELEMpop() //從棧頂彈出元素

{assert(!isEmpty());returnlistarray[--top];}

ELEMtopValue()const //返回棧頂元素的值

{assert(!isEmpty());returnlistarray[top-1];}

bool

isEmptyconst //如果棧為空則返回TRUE

{returntop==0;}

};4.1.2鏈?zhǔn)綏ｆ準(zhǔn)綏Ｋ?jiǎn)單地利用單鏈表，其運(yùn)算只是在表的一端進(jìn)行插入和刪除。唯一需要考慮的問(wèn)題是將單鏈表的哪一端看作棧頂，若將表尾看成棧頂，則每次進(jìn)棧（壓棧）和出棧時(shí)，都要從表頭找到表尾，其時(shí)間開(kāi)銷為O(n)（n為表中元素個(gè)數(shù)）。若將棧頂設(shè)在表頭，則進(jìn)出棧的時(shí)間開(kāi)銷僅O(1)。

stack……a1a2an^棧頂棧底stack^空棧圖4.1用單鏈表表示棧classstack{ //鏈?zhǔn)綏ｎ?/p>

private:

link*top; //指向棧頂元素的指針

public:

stack(constint

sz=LIST_SIZE) //構(gòu)造函數(shù)：初始化

{top=NULL；}

~stack(){clear();} //析構(gòu)函數(shù)：返回一切元素ELEM

voidclear(); //從棧中清除所有元素ELEM

voidpush(constELEM&item){ //將元素item壓入棧中

top=newlink(item,top)};

ELEMpop(); //從棧頂彈出元素

ELEMtopValue()const //獲得棧頂元素的值

{assert(!isEmpty());returntop->element;}

bool

isEmpty()const //如果棧為空則返回TRUE

{returntop==NULL;}

};voidstack::clear(){ //從棧中清除所有元素

while(top!=NULL) //返回鏈的所有結(jié)點(diǎn)給以可利用空間表

{link*temp=top;top=top->next;deletetemp;}

}

ELEMstack::pop(){ //從棧頂彈出元素

assert(!isEmpty());

ELEMtemp=top->element;

link*ltemp=top->next;

deletetop;

top=ltemp;

returntemp;

}4.1.3順序棧與鏈?zhǔn)綏５谋容^時(shí)間效率空間效率順序棧都只需要常數(shù)時(shí)間順序棧必須申請(qǐng)一個(gè)固定長(zhǎng)度的數(shù)組，當(dāng)棧中元素相對(duì)較少時(shí)，空間浪費(fèi)較大。當(dāng)某些應(yīng)用需要多個(gè)棧時(shí)，可以充分利用順序棧單向延伸的特性來(lái)節(jié)省空間，見(jiàn)圖4.2。鏈?zhǔn)綏ｆ準(zhǔn)綏５拈L(zhǎng)度雖然可變，但是對(duì)于每個(gè)元素都需要一個(gè)指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開(kāi)銷。公用空間top1top2圖4.2

存儲(chǔ)在一個(gè)數(shù)組中的兩個(gè)棧4.1.4棧的應(yīng)用例：一列貨運(yùn)列車共有n節(jié)車廂，每節(jié)車廂將從列車上卸下來(lái)停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1，…，n。貨運(yùn)列車按照第n站至第1站的次序經(jīng)過(guò)這些車站。車廂的編號(hào)與它們的目的地相同。為了便于從列車上卸掉相應(yīng)的車廂，必須事先排好這些車廂，使各車廂從前至后按編號(hào)1到n的次序排列。我們?cè)谝粋€(gè)轉(zhuǎn)軌站里完成車廂的排列工作。在轉(zhuǎn)軌站中有一個(gè)入軌，一個(gè)出軌和k個(gè)緩沖鐵軌（位于入軌和出軌之間）。

[581742963]入軌出軌H1H2H3(a)[987654321]H1H2H3(b)圖4.3具有三個(gè)緩沖鐵軌的轉(zhuǎn)軌站為了重排車廂，需從前至后依次檢查入軌處的所有車廂，如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去；如果不是，則把它移動(dòng)到緩沖鐵軌上去，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。緩沖鐵軌是按照后進(jìn)先出（LIFO）的方式使用的，因?yàn)檐噹倪M(jìn)和出都是在緩沖鐵軌的頂部進(jìn)行的。在重排車廂的過(guò)程中，僅允許以下移動(dòng)：車廂可以從入軌的前部（即右端）移動(dòng)到一個(gè)緩沖鐵軌的頂部或出軌的左端；車廂可以從一個(gè)緩沖鐵軌的頂部移動(dòng)到出軌的左端。

369H1H2H3(a)369H1H2H3(b)247圖4.4緩沖鐵軌中間狀態(tài)方法描述用k個(gè)單鏈表形式的棧來(lái)模擬k個(gè)緩沖鐵軌；函數(shù)Railroad()用于確定重排n個(gè)車廂，它最多可使用k個(gè)緩沖鐵軌并假定車廂的初始次序?yàn)閜[1:n]。如果不能成功地重排，Railroad返回FALSE，否則返回TRUE；Output()用于把一節(jié)車廂從緩沖鐵軌送至出軌處；函數(shù)Hold()根據(jù)車廂分配規(guī)則把車廂c送入某個(gè)緩沖鐵軌；Railroad()函數(shù)bool

Railroad(intp[],intn,intk)

{ //k個(gè)緩沖鐵軌，車廂初始次序?yàn)閜[1:n]

//如果重排成功，返回TRUE，否則返回FALSE

//如果內(nèi)存不足，則引發(fā)異常NoMemory

//創(chuàng)建與緩沖鐵軌對(duì)應(yīng)的堆棧

LinkedStack*H;

H=newLinkedStack[k+1];

int

NowOut=1; //下一次要輸出的車廂

int

minH=n+1; //緩沖鐵軌中編號(hào)最小的車廂

int

minS; //minH號(hào)車廂對(duì)應(yīng)的緩沖鐵軌//車廂重排

for(inti=1;i<=n;i++)

if(p[i]==NowOut){ //直接輸出

cout<<”Movecar“<<p[i]<<”frominputtooutput”<<endl;

NowOut++;

//從緩沖鐵軌中輸出

while(minH==NowOut){//從緩沖鐵軌中輸出

Output(minH,minS,H,k,n);

NowOut++;

}

}

else{ //將p[i]送入某個(gè)緩沖鐵軌

if(!Hold(p[i],minH,minS,H,k,n))

returnFALSE;}

returnTRUE;

}Output()函數(shù)

voidOutput(int&minH,int&minS,LinkedStackH[]，intk,intn)

{//把車廂從緩沖鐵軌送至出軌處，同時(shí)修改minS和minH

intc; //車廂索引

//從棧minS刪除編號(hào)最小的車廂minH

H[minS].pop();

cout<<”Movecar“<<minH<<”fromholdingtrack”<<minS <<”tooutput”<<endl;

//檢查所有的棧頂，查找新的minH和minS

minH==n+2;

for(inti=1;i<=k;i++)

if(!H[i].IsEmpty()&&(c=H[i].Top())<minH){

minH=c;

minS=i;}

}Hold()函數(shù)boolHold(intc,int&minH,int&minS,LinkedStack<int>H[],n)

{//在一個(gè)緩沖鐵軌中放入車廂c，如果沒(méi)有可用的緩沖鐵軌，則返回FALSE

//如果空間不足，則引發(fā)異常NoMemory，否則返回TRUE

int

BestTrack=0, //目前最優(yōu)的鐵軌

BestTop=n+1, //最優(yōu)鐵軌上的頭輛車廂

intx, //車廂索引

for(inti=1;i<=k;i++) //掃描緩沖鐵軌

if(!H[i].isEmpty()){ //鐵軌i不空

x=H[i].topValue();

if(c<x&&x<BestTop){

BestTop=x;

BestTrack=i;}}

else //鐵軌i為空

if(!BestTrack)BestTrack=i;

if(!BestTrack)returnFALSE;//沒(méi)有可用的鐵軌

//把車廂c送入緩沖鐵軌

H[BesyTrack].Add(c);

cout<<“Movecar“<<c<<“frominput”“toholdingtrack”<<BestTrack<<endl;

if(c<minH){minH==c;minS=BestTrack;}//必要時(shí)修改minH和minS

returnture;

}4.2.1隊(duì)列的定義及基本運(yùn)算隊(duì)列

只能在表的一端插入，在另一端刪除的線性表。能進(jìn)行插入的一端稱為隊(duì)列的尾，能進(jìn)行刪除的一端稱為隊(duì)列的頭。在隊(duì)列尾部插入時(shí)稱為入隊(duì)（enqueue）操作，從隊(duì)列頭部刪除時(shí)稱為出隊(duì)（dequeue）操作。這種先來(lái)先服務(wù)的特性稱為先進(jìn)先出（FirstInFirstOut），簡(jiǎn)稱FIFO。當(dāng)我們用原來(lái)線性表的記號(hào)來(lái)表示隊(duì)列的時(shí)候，隊(duì)列可以寫為：Q=(a0,a1,…,an-1)其中a0的一端為隊(duì)列的頭，an-1的一端為隊(duì)列的尾。隊(duì)列的抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型Queue{

實(shí)例

元素的線性表，一端稱為front,另一端稱為rear;

操作

Create(): 創(chuàng)建一個(gè)新的隊(duì)列；

IsEmpty(): 如果隊(duì)列為空，則返回TRUE，否則返 回FALSE；

IsFull(): 如果隊(duì)列滿，則返回TRUE，否則返回 FALSE；

First(): 返回隊(duì)列的第一個(gè)元素；

Last(): 返回隊(duì)列的最后一個(gè)元素；

Add(x): 向隊(duì)列中添加元素x；

Delete(x): 刪除隊(duì)列的頭元素，并送入x；

}4.2.2順序隊(duì)列順序隊(duì)列放寬隊(duì)列所有元素必須存儲(chǔ)在數(shù)組前n個(gè)位置這個(gè)限制，在隊(duì)列的操作過(guò)程中，隊(duì)列的內(nèi)容可以在數(shù)組中移動(dòng)。為了掌握隊(duì)列的位置，必須設(shè)兩個(gè)指標(biāo)分別指向隊(duì)列的頭和尾，指向隊(duì)列頭的叫做front，指向隊(duì)列尾的叫做rear。在出隊(duì)列和入隊(duì)列時(shí)，分別根據(jù)這兩個(gè)值，可以只用O(1)的時(shí)間開(kāi)銷完成操作。按照上述做法，從空隊(duì)列開(kāi)始，依次將5、12、9、37插入隊(duì)列，此后，先使5，12依次出隊(duì)列，再將25，8，16依次插入隊(duì)列，再讓9出隊(duì)列，將7，4，19，20插入。512937frontrear(a)93725816front(b)rear37258167419front(c“滿”)rear圖4.5經(jīng)過(guò)多次使用后，順序隊(duì)列在數(shù)組中的情況循環(huán)存儲(chǔ)

“循環(huán)存儲(chǔ)”的思想，將數(shù)組的尾和頭接起來(lái)構(gòu)成一個(gè)“環(huán)形”，下一個(gè)數(shù)據(jù)20可以放在數(shù)組的第0個(gè)位置。如果緊接著將15，6插入隊(duì)列，如圖4.6。2037258167419

frontrear(a)2015637258167419

front(b滿)rear201537258167419front(c)rear圖4.6隊(duì)列的循環(huán)存放問(wèn)題

隊(duì)列處理?xiàng)l件隊(duì)列滿的條件放寬隊(duì)列尾追上隊(duì)列頭的條件，在數(shù)組中故意“浪費(fèi)”一個(gè)元素位置，當(dāng)rear=front-2時(shí)，就認(rèn)為隊(duì)列滿了。隊(duì)列空的條件

rear=front-1，因?yàn)楫?dāng)?shù)谝粋€(gè)元素入隊(duì)列時(shí)，放在rear+1的位置，此時(shí)隊(duì)列中只有一個(gè)元素，front和rear都指向它(front=rear)。另外，在實(shí)現(xiàn)循環(huán)存放時(shí)有一個(gè)小的技術(shù)問(wèn)題，如何使之“頭尾相接”呢？在C++中有取模運(yùn)算符%，當(dāng)數(shù)組的長(zhǎng)度為n時(shí)，因?yàn)閚%n=0，正好解決了這個(gè)問(wèn)題。順序隊(duì)列類的實(shí)現(xiàn)：

classqueue{ //基于數(shù)組的隊(duì)列類

private:

intsize; //隊(duì)列的最大長(zhǎng)度

intfront; //隊(duì)列頭前一位置的指標(biāo)

intrear; //隊(duì)列尾的指標(biāo)

ELEM*listarray; //放置表元素的數(shù)組

public:

queue(const

int

sz=LIST_SIZE) //構(gòu)造函數(shù)

{//使隊(duì)列所在數(shù)組多出一個(gè)位置，為了有一個(gè)空槽

size=sz+1;

front=rear=0;

listarray=newELEM[size];}

~queue(){delete[]listarray;} //析構(gòu)函數(shù)

voidclear(){front=rear;} //清除隊(duì)列

voidenqueue(constELEM&);//將元素加入隊(duì)列尾部

ELEMdequeue(); //使隊(duì)列頭部元素出隊(duì)列

ELEMfirstValue()const{ //取隊(duì)列頭部元素的值

assert(!isEmpty());

returnlistarray[(front+1)%size];}

bool

isEmpty()const //如果隊(duì)列為空則取TRUE值

{returnfront==rear;}

};入隊(duì)列及出隊(duì)列入隊(duì)列時(shí)需要先判斷隊(duì)列不能已滿，相應(yīng)地出隊(duì)列時(shí)，隊(duì)列不能為空。入隊(duì)列、出隊(duì)列的實(shí)現(xiàn)如下：

//將元素ELEM加入隊(duì)列尾部

voidqueue::enqueue(constELEM&item){

assert(((rear+1)%size)!=front); //隊(duì)列必須不是滿的

rear=(rear+1)%size; //隊(duì)尾指標(biāo)加1 listarray[rear]=item;

}

ELEMqueue::dequeue(){ //使隊(duì)列頭部元素出隊(duì)列

assert(!isEmpty()); //隊(duì)列必須非空

front=(front+1)%size; //隊(duì)列頭指標(biāo)加1

returnlistarray[front]; //返回頭元素的值

}4.2.2鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列對(duì)于原來(lái)的單鏈表改為設(shè)兩個(gè)指針，一個(gè)指向表頭結(jié)點(diǎn)，稱為front，另一個(gè)指向表尾結(jié)點(diǎn)，稱為rear。

queue……a1a2an^frontrearqueue^空隊(duì)列圖4.7用鏈表表示隊(duì)列鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)

classqueue{ //鏈?zhǔn)疥?duì)列類

private:

link*front; //指向隊(duì)列頭結(jié)點(diǎn)的指針

link*rear; //指向隊(duì)列尾結(jié)點(diǎn)的指針

public:

queue(const

int

sz=LIST_SIZE) //構(gòu)造函數(shù)：初始化

{front=rear=NULL;}

~queue(){clear();} //析構(gòu)函數(shù):返回保存元素ELEM的鏈

voidclear(); //清除隊(duì)列中所有元素

voidenqueue(constELEM&) //將元素加入隊(duì)列尾部

ELEMdequeue(); //使隊(duì)列頭部元素出隊(duì)列

ELEMfirstValue()const //取隊(duì)列頭元素的值

{assert(!isEmpty());returnfront->element;}

bool

isEmpty()const //當(dāng)隊(duì)列為空時(shí)返回TRUE值

{returnfront==NULL;}

};

voidqueue::clear(){ //從隊(duì)列中清除所有元素

while(front!=NULL) //返回所有鏈表結(jié)點(diǎn)到可利用空間表

{rear=front;front=front->next;deleterear;}

rear=NULL;

}

//將元素ELEM加入隊(duì)列尾部

voidqueue::enqueue(constELEM&item){

if(rear!=NULL){ //隊(duì)列非空，加到尾部

rear->next=newlink(item,NULL);

rear=rear->next;

}

elsefront=rear=newlink(item,NULL); //隊(duì)列空時(shí)的處理辦法

}

ELEMqueue::dequeue(){ //隊(duì)列頭元素出隊(duì)列

assert(!isEmpty()); //隊(duì)列必須非空

ELEMtemp=front->element; //存儲(chǔ)從隊(duì)列出來(lái)的元素的值

link*ltemp=front; //保留從隊(duì)列出來(lái)的鏈表結(jié)點(diǎn)

front=front->next; //隊(duì)列頭指針指向下一個(gè)結(jié)點(diǎn)

deleteltemp; //返回出隊(duì)列的結(jié)點(diǎn)到自由空間

if(front==NULL)rear=NULL; //最后一個(gè)元素出隊(duì)列 時(shí)的情況

returntemp; //返回元素的值

}4.2.3隊(duì)列的應(yīng)用例：重新考慮4.1.4中提到的火車車廂重排問(wèn)題，不過(guò)這次假設(shè)緩沖鐵軌位于入軌和出軌之間，由于這時(shí)緩沖鐵軌均按先進(jìn)先出（FIFO）的方式工作，因此可將它們視為隊(duì)列。如圖4.8所示。[581742963]入軌出軌H1H2H3圖4.8三個(gè)緩沖鐵軌示例[987654321]為了實(shí)現(xiàn)上述思想，我們可以采用鏈?zhǔn)疥?duì)列描述車廂重排算法。使用隊(duì)列來(lái)重排車廂的實(shí)現(xiàn)如下：voidOutput(int&minH,int&minQ,LinkedQueqe<int>H[],intk,intn)

{//

intc; //車廂編號(hào)

//從隊(duì)列minQ中刪除編號(hào)最小的車廂minH

H[minQ].dequeue();

cout<<”Movecar“<<minH<<“fromholdingtrack”<<minQ <<”tooutput”<<endl;

//通過(guò)檢查所有隊(duì)列的首部，尋找新的minH和 minQ

minH=n+2;

for(inti=1,i<=k;i++)

if(!H[i].isEmpty()&&(c=H[i].firstValue())<minH)

{ minH=c;

minQ=i;}

}boolHold(intc,int&minH,int&minQ,LinkedQueue<int>H[],intk)

{ //把車廂c移到緩沖鐵軌中

//如果沒(méi)有可用的緩沖鐵軌，則返回FALSE，否則返回TRUE

//為車廂c尋找最優(yōu)的緩沖鐵軌

//初始化

int

BestTrack=0; //目前最優(yōu)的鐵軌

BestLast=0; //BestTrack中最后一節(jié)車廂

intx; //車廂編號(hào)

//掃描緩沖鐵軌

for(inti=1;i<=k;i++)

{

if(!H[i].isEmpty())//鐵軌i不為空

{

x=H[i].last();

if(c>x&&x>BestLast)

{//鐵軌i尾部的車廂編號(hào)較大

BestLast=x;

BestTrack=i;

}

}

else //鐵軌i為空

BestTrack=i;

}

if(!BestTrack)returnFALSE; //沒(méi)有可用的鐵軌

//把c移動(dòng)到最優(yōu)鐵軌

H[BestTrack].enqueue(c);

cout<<”Movecar“<<c<<”frominput”<<”toholdingtrack”<<BestTrack<<endl;

//如果有必要，則修改minH和minQ

if(c<minH){minH=c;minQ=BestTrack;}

returnture;

}4.3數(shù)組一維數(shù)組只是線性表的特殊形式（沒(méi)有插入和刪除操作），本節(jié)主要講二維及以上的數(shù)組。

n（n≥2）維數(shù)組也可以看成線性表的推廣，即將每個(gè)n-1維數(shù)組作為線性表的元素。但這只是一種看法，由于數(shù)組運(yùn)算的特點(diǎn)，套用線性表的實(shí)現(xiàn)方法是沒(méi)有意義的。 本節(jié)將討論數(shù)組的存儲(chǔ)方式（包括特殊數(shù)組的存儲(chǔ)方式）以及有關(guān)的運(yùn)算，最后給出應(yīng)用實(shí)例。4.3.1數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象array的每個(gè)實(shí)例是形如（index,value）的數(shù)據(jù)對(duì)集合，其中任意兩對(duì)數(shù)據(jù)的index值都不相同。有關(guān)數(shù)組的操作如下：Create：創(chuàng)建一個(gè)初始為空的數(shù)組（即不含任何數(shù)據(jù)）；Store：向數(shù)組中添加一對(duì)（index,value）數(shù)據(jù)；Retrieve：返回?cái)?shù)組中具有給定index值的value值；抽象數(shù)據(jù)類型Array抽象數(shù)據(jù)類型Array{

實(shí)例

形如(index,value)的數(shù)據(jù)對(duì)集合，其中任意兩對(duì)數(shù)據(jù)的index值都不相同。

操作

Create(); 創(chuàng)建一個(gè)空的數(shù)組

Store(index,value); 添加數(shù)據(jù)(index,value)，同時(shí)刪 除具有相同index值的數(shù)據(jù)對(duì)（如果存在）

Retrieve(index); 返回索引值為index的value值

}例4.1

上個(gè)星期每天的最高溫度可用如下的數(shù)組來(lái)表示：

high={(星期日,30),(星期一,28),(星期二,29),(星期三, 32),(星期四,28),(星期五,30),(星期六,31)}

數(shù)組中每一對(duì)數(shù)據(jù)都包含一個(gè)索引(星期幾)和一個(gè)值

(當(dāng)天的最高溫度)，數(shù)組的名字為high。 通過(guò)執(zhí)行如下操作，可將星期一的溫度改為29

Store(星期一，29)

通過(guò)執(zhí)行如下操作，還可找到星期五的最高溫度：

Retrieve(星期五)

在約定的情況下，也可以采用如下數(shù)組來(lái)描述每天的 最高溫度：

high={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}

4.3.2數(shù)組的存儲(chǔ)方式 在實(shí)現(xiàn)中主要采取順序存儲(chǔ)方式。但是對(duì)n維數(shù)（n≥2）來(lái)說(shuō)，用什么順序存儲(chǔ)數(shù)組中各元素，才能根據(jù)索引值index方便地找到元素位置，是一個(gè)值得討論的問(wèn)題。順序存儲(chǔ)方式按行排列 先排數(shù)組的第一行，緊隨其后排第二行，依此類推。按列排列 先排數(shù)組的第一列，緊隨其后排第二列，依此類推。 在C++中，值為整數(shù)類型的k維數(shù)組score可用如下語(yǔ)句來(lái)創(chuàng)建：int

score[u1][u2][u3]…[uk]

因此，這個(gè)數(shù)組最多可以容納n=u1u2u3…uk個(gè)元素。整個(gè)數(shù)組所需要的內(nèi)存空間為sizeof(score)=n*sizeof(int)個(gè)字節(jié)。假設(shè)其開(kāi)始地址為start，則該空間將延伸至start+sizeof(score)-1。 為了實(shí)現(xiàn)與數(shù)組相關(guān)的函數(shù)Store和Retrieve，必須確定索引值與地址[start,start+sizeof(score)-1]之間的對(duì)應(yīng)，實(shí)際上就是把數(shù)組索引[i1][i2][i3]…[ik]映射到[0，n-1]的某個(gè)函數(shù)map(i1,i2,i3,…,ik)，使得該索引所對(duì)應(yīng)的元素值存儲(chǔ)在以下位置：start+map(i1,i2,i3,…,ik)*sizeof(int)。例：設(shè)有二維數(shù)組intscore[3][6]，它對(duì)應(yīng)一個(gè)3行6

列的矩陣，其索引排列成為表格形式如圖4.9。 [0][0][0][1][0][2][0][3][0][4][0][5] [1][0][1][1][1][2][1][3][1][4][1][5] [2][0][2][1][2][2][2][3][2][4][2][5]圖4.9intscore[3][6]的索引排列表行主映射 將索引表格按行自左至右進(jìn)行連續(xù)編號(hào)，即可得到如下所示的映射結(jié)果，這種把二維數(shù)組中的位置映射為[0，n-1]中某個(gè)數(shù)的方式稱為行主映射。01234567891011121314151617

列主映射也有一些程序設(shè)計(jì)語(yǔ)言，對(duì)索引表格從第一列開(kāi)始，從上到下進(jìn)行連續(xù)編號(hào)，直到最后一列，這種方式是列主映射。如下所示。03691215147101316258111417 行主映射所對(duì)應(yīng)的映射函數(shù)為：

map(i1,i2)=i1*u2+i2

其中u2是數(shù)組的列數(shù)。這個(gè)表達(dá)式的正確性在于：在對(duì)索引[i1][i2]進(jìn)行編號(hào)時(shí)，前面已對(duì)i1個(gè)整行（每行u2列）進(jìn)行了編號(hào)，故為i1*u2，然后，再加上不滿一行的i2即可。 讓我們用前面給出的3*6數(shù)組進(jìn)行驗(yàn)證。由于其列數(shù)為6，所以映射公式變成：map(i1,i2)=6*i1+i2

因此有map(1,3)=9,map(2,4)=6*2+4=16。與圖4.10(a)中給出的編號(hào)一致。類似地，列主映射所對(duì)應(yīng)的映射函數(shù)為：map(i1,i2)=i2*u1+i1

對(duì)于二維數(shù)組的映射方法也可以推廣到高維數(shù)組，例如三維數(shù)組score[3][2][4]中的索引按行主映射的排列為：[0][0][0]，[0][0][1]，[0][0][2]，[0][0][3]，[0][1][0]，[0][1][1]，[0][1][2]，[0][1][3][1][0][0]，[1][0][1]，[1][0][2]，[1][0][3]，[1][1][0]，[1][1][1]，[1][1][2]，[1][1][3][2][0][0]，[2][0][1]，[2][0][2]，[2][0][3]，[2][1][0]，[2][1][1]，[2][1][2]，[2][1][3]

對(duì)于一般三維數(shù)組score[u1][u2][u3]，其行主映射函數(shù)應(yīng)為：map(i1,i2,i3)=i1*u2*u3+i2*u3+i34.3.3特殊數(shù)組對(duì)稱矩陣和三角矩陣

對(duì)稱矩陣

M是一個(gè)對(duì)稱矩陣當(dāng)且僅當(dāng)對(duì)所有的i和j有M(i,j)=M(j,i)。如圖4.11(a)所示。上三角矩陣

M是一個(gè)上三角矩陣當(dāng)且僅當(dāng)i>j時(shí)有M(i,j)=0。如圖4.11(b)所示。下三角矩陣

M是一個(gè)下三角矩陣當(dāng)且僅當(dāng)i<j時(shí)有M(i,j)=0。如圖4.11(c)所示。

1234

2865

3697

45701234

0567

0080

00091000

2300

4560

78910(a)對(duì)稱矩陣(b)上三角矩陣（c）下三角矩陣

圖4.11特殊矩陣的幾種形式 以下三角矩陣為例，我們考慮用一個(gè)一維數(shù)組只存儲(chǔ)它的下三角各元素，也可以有兩種方法：按行存儲(chǔ)和按列存儲(chǔ)。例如對(duì)于圖4.11(c)的矩陣，若按行存儲(chǔ)，它的各元素的次序應(yīng)是1、2、3、4、5、6、7、8、9、10；若按列存儲(chǔ)，它的各元素的次序應(yīng)是1、2、4、7、3、5、8、6、9、10。 對(duì)于一般n*n的矩陣L來(lái)說(shuō)，其下（上）三角部分只有n(n+1)/2個(gè)元素，而不用存儲(chǔ)全部的n2個(gè)元素。當(dāng)然，要容易找到矩陣元素L(i,j)在一維數(shù)組中的位置，即要給出索引(i,j)對(duì)一維數(shù)組下標(biāo)的映射函數(shù)，三角矩陣的映射函數(shù)map(i,j)=1+2+3+…+i-1+j-1=i(i-1)∕2+j-1(1≤i≤n,1≤j≤i)。 采用這個(gè)公式，容易寫出數(shù)組抽象數(shù)據(jù)類型中的Store和Retrieve函數(shù)。下三角矩陣的Store和Retrieve函數(shù)如下：

classLowerMatrix{

public:

LowerMatrix(intsize=10)

{n=size;t=newL[n*(n+1)/2]}

~LowerMatrix(){delete[]t;}

LowerMatrix&Store(constL&x,inti,intj);

LRetrieve(inti,intj)const;

private:

intn; //矩陣階數(shù)

L*t; //存儲(chǔ)下三角矩陣的一維數(shù)組

};LowerMatrix&LowerMatrix::Store(constx,inti,intj)

{//

if(i<1||j<1||i>n||j>n)

ERROR;

if(i>=j)t[i*(i-1)/2+j-1]=x; //下三角部分

elseif(x!=0)ERROR; //上三角部分的元素全部為零

return*this;

}

LLowerMatrix::Retrieve(inti,intj)const

{ //返回L(i,j)的值

if(i<1||j<1||i>n||j>n)

throwERROR; //下標(biāo)越界處理

if(i>=j)returnt[i*(i-1)/2+j-1];

elsereturn0;

}稀疏矩陣 當(dāng)用矩陣表示某個(gè)數(shù)學(xué)模型時(shí)，經(jīng)常出現(xiàn)有大量的零元素，而非零元素倒反而很少，這種矩陣就是稀疏矩陣。

為節(jié)省空間，一般只存儲(chǔ)稀疏矩陣中的非零元素，在存儲(chǔ)非零元素時(shí)必須將它的行號(hào)和列號(hào)一起存儲(chǔ)起來(lái)，即要組成一個(gè)三元組(i,j,v)的形式才行，其中i表示行號(hào)，j表示列號(hào)，v表示非零元素的值。

設(shè)有稀疏矩陣S S=0890000

10000

00-30000

120

00160000

02400600

150000

-70i1123345566J2311632516v891-3121624615-7圖4.12稀疏矩陣的三元組表三元組描述classTerm{

private:

inti,j;

Tv;

};

以三元組表表示的稀疏矩陣類可描述為：

classSparseMatrix

{

public:

SparseMatrix(int

maxTerm=20);

~SparseMatrix(){delete[]a}；

voidTranspose(SparseMatrix…)const;

voidAdd(const

SparseMatrix

b,c)const;

private:

voidAppend(constTermt);

introws,cols; //矩陣的行，列數(shù)

intterms; //非零元素?cái)?shù)目

Term<T>*a; //三元組表

int

MaxTerms; //三元組表的大小

}；三元組表示下，對(duì)稀疏矩陣進(jìn)行轉(zhuǎn)置運(yùn)算的算法如下所示：

voidSparseMatrix::Transpose(SparseMatrixb)const

{

if(terms>b.MaxTerms)throwNoMem(); //

b.cols=rows; //設(shè)置轉(zhuǎn)置特征

b,rows=cols;

b.terms=terms;

int*ColSize,*RowNext;

ColSize=newint[cols+1]；

RowNext=newint[rows+1];

for(inti=1;i<=terms;i++) //初始化

ColSize[i]=0;

for(inti=0;i<=terms;i++)

ColSize[a[i].col]++;

RowNext[1]=0;

for(inti=2;i<=cols;i++)

RowNext[i]=RowNext[i-1]+ColSize[i-1];

//以下執(zhí)行轉(zhuǎn)置操作

for(inti=0;i<terms;i++){

intj=RowNext[a[i].col]++;

b.a[j].r