《数据结构与算法》第四章 栈、队列和数组

第四章栈、队列和数组4.1栈4.2队列4.3数组4.1栈栈栈（stack）是限定仅在一端进行插入和删除的线性表。能进行插入和删除的这一端称为栈顶（top），表的另一端称为栈底（bottom）。插入和删除元素都要涉及栈顶，因此栈顶是栈的最重要的概念。在栈顶插入一个元素称为压栈（push）或入栈，从栈顶删除一个元素称为出栈（pop）。当我们用原来线性表的记号来表示栈的时候，栈可以写为：S=(a0,a1,…,an-1)当指定an-1那一端为栈顶的时候，另一端a0就是栈底。当n=0时，称为空栈。入栈时按a0,a1,…,an-1的次序入栈，而出栈时次序刚好相反，先退出an-1，然后才能退出an-2，最后退出a0。所以栈又称为后进先出（LIFO，LastInFirstOut）结构。和线性表一样，实现栈的方法有许多种，下面介绍两种方法：顺序栈和链式栈，它们分别对应于顺序表和单链表，但实现起来更简单些。下面给出栈的抽象数据类型描述：栈的抽象数据类型描述抽象数据类型stack{

实例

元素的线性表一端为栈底，另一端为栈顶操作

Create(): 创建一个空栈

isEmpty(): 如果栈为空，则返回TRUE，否 则返回FALSE

IsFull(): 如果栈满，则返回TRUE，否则 返回FALSE

Top(): 返回栈顶元素

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

Delete(x): 删除栈顶元素，并将它传送给x

}4.1.1顺序栈顺序栈 用数组实现的栈。 实现中使用数组listarray保存栈中各元素，listarray说明为私有类型，实现了对栈的封装，这意味着对这个数组的访问只能通过类中定义的方法push()、pop()、topValue()等进行，从而保证栈中数据的合法性。顺序栈的具体实现如下：

classstack{ //基于数组的栈类

private:

intsize; //栈的最大容量

inttop; //栈顶元素的下标

ELEM*listarray; //保存栈元素的数组

public:

stack(const

int

sz=LIST_SIZE) //构造函数：初始化

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

~stack(); //析构函数：释放数组占用空间

{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链式栈链式栈它简单地利用单链表，其运算只是在表的一端进行插入和删除。唯一需要考虑的问题是将单链表的哪一端看作栈顶，若将表尾看成栈顶，则每次进栈（压栈）和出栈时，都要从表头找到表尾，其时间开销为O(n)（n为表中元素个数）。若将栈顶设在表头，则进出栈的时间开销仅O(1)。

stack……a1a2an^栈顶栈底stack^空栈图4.1用单链表表示栈classstack{ //链式栈类

private:

link*top; //指向栈顶元素的指针

public:

stack(constint

sz=LIST_SIZE) //构造函数：初始化

{top=NULL；}

~stack(){clear();} //析构函数：返回一切元素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) //返回链的所有结点给以可利用空间表

{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顺序栈与链式栈的比较时间效率空间效率顺序栈都只需要常数时间顺序栈必须申请一个固定长度的数组，当栈中元素相对较少时，空间浪费较大。当某些应用需要多个栈时，可以充分利用顺序栈单向延伸的特性来节省空间，见图4.2。链式栈链式栈的长度虽然可变，但是对于每个元素都需要一个指针域，这又产生了结构性空间开销。公用空间top1top2图4.2

存储在一个数组中的两个栈4.1.4栈的应用例：一列货运列车共有n节车厢，每节车厢将从列车上卸下来停放在不同的车站。假定n个车站的编号分别为1，…，n。货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须事先排好这些车厢，使各车厢从前至后按编号1到n的次序排列。我们在一个转轨站里完成车厢的排列工作。在转轨站中有一个入轨，一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。

[581742963]入轨出轨H1H2H3(a)[987654321]H1H2H3(b)图4.3具有三个缓冲铁轨的转轨站为了重排车厢，需从前至后依次检查入轨处的所有车厢，如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去；如果不是，则把它移动到缓冲铁轨上去，直到按输出次序要求轮到它时才将它放到出轨上。缓冲铁轨是按照后进先出（LIFO）的方式使用的，因为车厢的进和出都是在缓冲铁轨的顶部进行的。在重排车厢的过程中，仅允许以下移动：车厢可以从入轨的前部（即右端）移动到一个缓冲铁轨的顶部或出轨的左端；车厢可以从一个缓冲铁轨的顶部移动到出轨的左端。

369H1H2H3(a)369H1H2H3(b)247图4.4缓冲铁轨中间状态方法描述用k个单链表形式的栈来模拟k个缓冲铁轨；函数Railroad()用于确定重排n个车厢，它最多可使用k个缓冲铁轨并假定车厢的初始次序为p[1:n]。如果不能成功地重排，Railroad返回FALSE，否则返回TRUE；Output()用于把一节车厢从缓冲铁轨送至出轨处；函数Hold()根据车厢分配规则把车厢c送入某个缓冲铁轨；Railroad()函数bool

Railroad(intp[],intn,intk)

{ //k个缓冲铁轨，车厢初始次序为p[1:n]

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

//如果内存不足，则引发异常NoMemory

//创建与缓冲铁轨对应的堆栈

LinkedStack*H;

H=newLinkedStack[k+1];

int

NowOut=1; //下一次要输出的车厢

int

minH=n+1; //缓冲铁轨中编号最小的车厢

int

minS; //minH号车厢对应的缓冲铁轨//车厢重排

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]送入某个缓冲铁轨

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

returnFALSE;}

returnTRUE;

}Output()函数

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

{//把车厢从缓冲铁轨送至出轨处，同时修改minS和minH

intc; //车厢索引

//从栈minS删除编号最小的车厢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()函数boolHold(intc,int&minH,int&minS,LinkedStack<int>H[],n)

{//在一个缓冲铁轨中放入车厢c，如果没有可用的缓冲铁轨，则返回FALSE

//如果空间不足，则引发异常NoMemory，否则返回TRUE

int

BestTrack=0, //目前最优的铁轨

BestTop=n+1, //最优铁轨上的头辆车厢

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;//没有可用的铁轨

//把车厢c送入缓冲铁轨

H[BesyTrack].Add(c);

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

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

returnture;

}4.2.1队列的定义及基本运算队列

只能在表的一端插入，在另一端删除的线性表。能进行插入的一端称为队列的尾，能进行删除的一端称为队列的头。在队列尾部插入时称为入队（enqueue）操作，从队列头部删除时称为出队（dequeue）操作。这种先来先服务的特性称为先进先出（FirstInFirstOut），简称FIFO。当我们用原来线性表的记号来表示队列的时候，队列可以写为：Q=(a0,a1,…,an-1)其中a0的一端为队列的头，an-1的一端为队列的尾。队列的抽象数据类型描述抽象数据类型Queue{

实例

元素的线性表，一端称为front,另一端称为rear;

操作

Create(): 创建一个新的队列；

IsEmpty(): 如果队列为空，则返回TRUE，否则返 回FALSE；

IsFull(): 如果队列满，则返回TRUE，否则返回 FALSE；

First(): 返回队列的第一个元素；

Last(): 返回队列的最后一个元素；

Add(x): 向队列中添加元素x；

Delete(x): 删除队列的头元素，并送入x；

}4.2.2顺序队列顺序队列放宽队列所有元素必须存储在数组前n个位置这个限制，在队列的操作过程中，队列的内容可以在数组中移动。为了掌握队列的位置，必须设两个指标分别指向队列的头和尾，指向队列头的叫做front，指向队列尾的叫做rear。在出队列和入队列时，分别根据这两个值，可以只用O(1)的时间开销完成操作。按照上述做法，从空队列开始，依次将5、12、9、37插入队列，此后，先使5，12依次出队列，再将25，8，16依次插入队列，再让9出队列，将7，4，19，20插入。512937frontrear(a)93725816front(b)rear37258167419front(c“满”)rear图4.5经过多次使用后，顺序队列在数组中的情况循环存储

“循环存储”的思想，将数组的尾和头接起来构成一个“环形”，下一个数据20可以放在数组的第0个位置。如果紧接着将15，6插入队列，如图4.6。2037258167419

frontrear(a)2015637258167419

front(b满)rear201537258167419front(c)rear图4.6队列的循环存放问题

队列处理条件队列满的条件放宽队列尾追上队列头的条件，在数组中故意“浪费”一个元素位置，当rear=front-2时，就认为队列满了。队列空的条件

rear=front-1，因为当第一个元素入队列时，放在rear+1的位置，此时队列中只有一个元素，front和rear都指向它(front=rear)。另外，在实现循环存放时有一个小的技术问题，如何使之“头尾相接”呢？在C++中有取模运算符%，当数组的长度为n时，因为n%n=0，正好解决了这个问题。顺序队列类的实现：

classqueue{ //基于数组的队列类

private:

intsize; //队列的最大长度

intfront; //队列头前一位置的指标

intrear; //队列尾的指标

ELEM*listarray; //放置表元素的数组

public:

queue(const

int

sz=LIST_SIZE) //构造函数

{//使队列所在数组多出一个位置，为了有一个空槽

size=sz+1;

front=rear=0;

listarray=newELEM[size];}

~queue(){delete[]listarray;} //析构函数

voidclear(){front=rear;} //清除队列

voidenqueue(constELEM&);//将元素加入队列尾部

ELEMdequeue(); //使队列头部元素出队列

ELEMfirstValue()const{ //取队列头部元素的值

assert(!isEmpty());

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

bool

isEmpty()const //如果队列为空则取TRUE值

{returnfront==rear;}

};入队列及出队列入队列时需要先判断队列不能已满，相应地出队列时，队列不能为空。入队列、出队列的实现如下：

//将元素ELEM加入队列尾部

voidqueue::enqueue(constELEM&item){

assert(((rear+1)%size)!=front); //队列必须不是满的

rear=(rear+1)%size; //队尾指标加1 listarray[rear]=item;

}

ELEMqueue::dequeue(){ //使队列头部元素出队列

assert(!isEmpty()); //队列必须非空

front=(front+1)%size; //队列头指标加1

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

}4.2.2链式队列链式队列对于原来的单链表改为设两个指针，一个指向表头结点，称为front，另一个指向表尾结点，称为rear。

queue……a1a2an^frontrearqueue^空队列图4.7用链表表示队列链式队列的实现

classqueue{ //链式队列类

private:

link*front; //指向队列头结点的指针

link*rear; //指向队列尾结点的指针

public:

queue(const

int

sz=LIST_SIZE) //构造函数：初始化

{front=rear=NULL;}

~queue(){clear();} //析构函数:返回保存元素ELEM的链

voidclear(); //清除队列中所有元素

voidenqueue(constELEM&) //将元素加入队列尾部

ELEMdequeue(); //使队列头部元素出队列

ELEMfirstValue()const //取队列头元素的值

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

bool

isEmpty()const //当队列为空时返回TRUE值

{returnfront==NULL;}

};

voidqueue::clear(){ //从队列中清除所有元素

while(front!=NULL) //返回所有链表结点到可利用空间表

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

rear=NULL;

}

//将元素ELEM加入队列尾部

voidqueue::enqueue(constELEM&item){

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

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

rear=rear->next;

}

elsefront=rear=newlink(item,NULL); //队列空时的处理办法

}

ELEMqueue::dequeue(){ //队列头元素出队列

assert(!isEmpty()); //队列必须非空

ELEMtemp=front->element; //存储从队列出来的元素的值

link*ltemp=front; //保留从队列出来的链表结点

front=front->next; //队列头指针指向下一个结点

deleteltemp; //返回出队列的结点到自由空间

if(front==NULL)rear=NULL; //最后一个元素出队列 时的情况

returntemp; //返回元素的值

}4.2.3队列的应用例：重新考虑4.1.4中提到的火车车厢重排问题，不过这次假设缓冲铁轨位于入轨和出轨之间，由于这时缓冲铁轨均按先进先出（FIFO）的方式工作，因此可将它们视为队列。如图4.8所示。[581742963]入轨出轨H1H2H3图4.8三个缓冲铁轨示例[987654321]为了实现上述思想，我们可以采用链式队列描述车厢重排算法。使用队列来重排车厢的实现如下：voidOutput(int&minH,int&minQ,LinkedQueqe<int>H[],intk,intn)

{//

intc; //车厢编号

//从队列minQ中删除编号最小的车厢minH

H[minQ].dequeue();

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

//通过检查所有队列的首部，寻找新的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移到缓冲铁轨中

//如果没有可用的缓冲铁轨，则返回FALSE，否则返回TRUE

//为车厢c寻找最优的缓冲铁轨

//初始化

int

BestTrack=0; //目前最优的铁轨

BestLast=0; //BestTrack中最后一节车厢

intx; //车厢编号

//扫描缓冲铁轨

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

{

if(!H[i].isEmpty())//铁轨i不为空

{

x=H[i].last();

if(c>x&&x>BestLast)

{//铁轨i尾部的车厢编号较大

BestLast=x;

BestTrack=i;

}

}

else //铁轨i为空

BestTrack=i;

}

if(!BestTrack)returnFALSE; //没有可用的铁轨

//把c移动到最优铁轨

H[BestTrack].enqueue(c);

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

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

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

returnture;

}4.3数组一维数组只是线性表的特殊形式（没有插入和删除操作），本节主要讲二维及以上的数组。

n（n≥2）维数组也可以看成线性表的推广，即将每个n-1维数组作为线性表的元素。但这只是一种看法，由于数组运算的特点，套用线性表的实现方法是没有意义的。 本节将讨论数组的存储方式（包括特殊数组的存储方式）以及有关的运算，最后给出应用实例。4.3.1数组的抽象数据类型数据对象array的每个实例是形如（index,value）的数据对集合，其中任意两对数据的index值都不相同。有关数组的操作如下：Create：创建一个初始为空的数组（即不含任何数据）；Store：向数组中添加一对（index,value）数据；Retrieve：返回数组中具有给定index值的value值；抽象数据类型Array抽象数据类型Array{

实例

形如(index,value)的数据对集合，其中任意两对数据的index值都不相同。

操作

Create(); 创建一个空的数组

Store(index,value); 添加数据(index,value)，同时删 除具有相同index值的数据对（如果存在）

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

}例4.1

上个星期每天的最高温度可用如下的数组来表示：

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

数组中每一对数据都包含一个索引(星期几)和一个值

(当天的最高温度)，数组的名字为high。 通过执行如下操作，可将星期一的温度改为29

Store(星期一，29)

通过执行如下操作，还可找到星期五的最高温度：

Retrieve(星期五)

在约定的情况下，也可以采用如下数组来描述每天的 最高温度：

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

4.3.2数组的存储方式 在实现中主要采取顺序存储方式。但是对n维数（n≥2）来说，用什么顺序存储数组中各元素，才能根据索引值index方便地找到元素位置，是一个值得讨论的问题。顺序存储方式按行排列 先排数组的第一行，紧随其后排第二行，依此类推。按列排列 先排数组的第一列，紧随其后排第二列，依此类推。 在C++中，值为整数类型的k维数组score可用如下语句来创建：int

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

因此，这个数组最多可以容纳n=u1u2u3…uk个元素。整个数组所需要的内存空间为sizeof(score)=n*sizeof(int)个字节。假设其开始地址为start，则该空间将延伸至start+sizeof(score)-1。 为了实现与数组相关的函数Store和Retrieve，必须确定索引值与地址[start,start+sizeof(score)-1]之间的对应，实际上就是把数组索引[i1][i2][i3]…[ik]映射到[0，n-1]的某个函数map(i1,i2,i3,…,ik)，使得该索引所对应的元素值存储在以下位置：start+map(i1,i2,i3,…,ik)*sizeof(int)。例：设有二维数组intscore[3][6]，它对应一个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]的索引排列表行主映射 将索引表格按行自左至右进行连续编号，即可得到如下所示的映射结果，这种把二维数组中的位置映射为[0，n-1]中某个数的方式称为行主映射。01234567891011121314151617

列主映射也有一些程序设计语言，对索引表格从第一列开始，从上到下进行连续编号，直到最后一列，这种方式是列主映射。如下所示。03691215147101316258111417 行主映射所对应的映射函数为：

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

其中u2是数组的列数。这个表达式的正确性在于：在对索引[i1][i2]进行编号时，前面已对i1个整行（每行u2列）进行了编号，故为i1*u2，然后，再加上不满一行的i2即可。 让我们用前面给出的3*6数组进行验证。由于其列数为6，所以映射公式变成：map(i1,i2)=6*i1+i2

因此有map(1,3)=9,map(2,4)=6*2+4=16。与图4.10(a)中给出的编号一致。类似地，列主映射所对应的映射函数为：map(i1,i2)=i2*u1+i1

对于二维数组的映射方法也可以推广到高维数组，例如三维数组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]

对于一般三维数组score[u1][u2][u3]，其行主映射函数应为：map(i1,i2,i3)=i1*u2*u3+i2*u3+i34.3.3特殊数组对称矩阵和三角矩阵

对称矩阵

M是一个对称矩阵当且仅当对所有的i和j有M(i,j)=M(j,i)。如图4.11(a)所示。上三角矩阵

M是一个上三角矩阵当且仅当i>j时有M(i,j)=0。如图4.11(b)所示。下三角矩阵

M是一个下三角矩阵当且仅当i<j时有M(i,j)=0。如图4.11(c)所示。

1234

2865

3697

45701234

0567

0080

00091000

2300

4560

78910(a)对称矩阵(b)上三角矩阵（c）下三角矩阵

图4.11特殊矩阵的几种形式 以下三角矩阵为例，我们考虑用一个一维数组只存储它的下三角各元素，也可以有两种方法：按行存储和按列存储。例如对于图4.11(c)的矩阵，若按行存储，它的各元素的次序应是1、2、3、4、5、6、7、8、9、10；若按列存储，它的各元素的次序应是1、2、4、7、3、5、8、6、9、10。 对于一般n*n的矩阵L来说，其下（上）三角部分只有n(n+1)/2个元素，而不用存储全部的n2个元素。当然，要容易找到矩阵元素L(i,j)在一维数组中的位置，即要给出索引(i,j)对一维数组下标的映射函数，三角矩阵的映射函数map(i,j)=1+2+3+…+i-1+j-1=i(i-1)∕2+j-1(1≤i≤n,1≤j≤i)。 采用这个公式，容易写出数组抽象数据类型中的Store和Retrieve函数。下三角矩阵的Store和Retrieve函数如下：

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; //矩阵阶数

L*t; //存储下三角矩阵的一维数组

};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; //下标越界处理

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

elsereturn0;

}稀疏矩阵 当用矩阵表示某个数学模型时，经常出现有大量的零元素，而非零元素倒反而很少，这种矩阵就是稀疏矩阵。

为节省空间，一般只存储稀疏矩阵中的非零元素，在存储非零元素时必须将它的行号和列号一起存储起来，即要组成一个三元组(i,j,v)的形式才行，其中i表示行号，j表示列号，v表示非零元素的值。

设有稀疏矩阵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; //矩阵的行，列数

intterms; //非零元素数目

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

int

MaxTerms; //三元组表的大小

}；三元组表示下，对稀疏矩阵进行转置运算的算法如下所示：

voidSparseMatrix::Transpose(SparseMatrixb)const

{

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

b.cols=rows; //设置转置特征

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];

//以下执行转置操作

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

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

b.a[j].r