数组与十字链表

数组与十字链表1§4.1数组

数组是一种十分常用的结构

大多数程序设计语言都直接支持数组类型

数组的基本操作主要是元素定位

本节的主要内容是讨论数组的存贮映射方法

2§4.1.1数组的定义与运算

数组是由一组类型相同的数据元素构成，每个数据元素称为一个数组元素（简称元素）

每个元素受n个线性关系约束（n≥1），若它在第1～第n个线性关系中的序号分别为i1、i2……in,则称它的下标为i1、i2……in，若该数组的名为A，则记下标为i1、i2……in,的元素为，称该数组为n维数组。

3§4.1.1数组的定义与运算

数组的另一个定义数组定义为一个元素可直接按序号寻址的线性表

A=(A1,A2,…,Am)若Ai是简单元素（不是数组），则A是一维数组；若Ai是（k-1)维数组，则A是k维数组。

数组是从线性表的推广而来

4§4.1.1数组的定义与运算

图‑

一个3维数组的元素关系示意5§4.1.1数组的定义与运算一维数组的操作

给定一组下标，读出相应的元素。给定一组下标，修改相应的元素。

6§4.1.2

数组的存储结构与寻址问题

要求元素的存储地址能根据它的下标（即逻辑关系）计算出来，一般只采用顺序存储结构

偏移地址（相对地址）

选定一个基准（参考）存贮单元，问题中所涉及的地址值均以此参考单元为基准（为起点）设i1、i2、…、in为某n维数组中的一个元素的下标，则用Loc(i1,i2,…,in)表示此元素的相对地址可以将多维数组影射为一维结构，然后运用顺序存储方式。

7§4.1.3一维数组的存贮与寻址设一维数组为

A=(a0,a1,…,an)则它的元素ai的相对地址为

Loc(i)=i·c

若数组下标范围为

闭区间[l1,h1]内的整数，即

A=()则元素ai的相对地址为

Loc(i)=(i-l1)·c8§4.1.4二维数组的存贮二维数组的阵列形状

a11a12…a1n a21a22…a2n

A=……

am1am2…amn

常用的映射方法有两种：按行与按列

9§4.1.4二维数组的存贮

(一)按行存贮先行后列：先存贮行号较小的元素，行号相同者，先存贮列号较小者。

a11a12…a1n

a21a22…a2n……

am1am2…amn

───────────────────

第1行元素

第2行元素

第m行元素

10§4.1.4二维数组的存贮

(一)按行存贮设二维数组的行下标与列下标变化范围分别为闭区间[l1,h1]与[l2,h2]，按行存储，任一元素aij的相对地址计算公式为

Loc(i,j)=((h2-l2+1)(i-l1)+(j-l2))·c11§4.1.4二维数组的存贮

(一)按行存贮【例4.1】.设某二维数组的两个下标的范围分别为[-1,2]与[0,1]，它的元素按行存贮的次序为（用ai表示元素，每个元素占两个单元）：

相对地址02468101214元素

a-1,0a-1,1a0,0a0,1a1,0a1,1a2,0a2,1Loc(-1,1)＝((1-0+1)(-1+1)+(1-0))*2＝212§4.1.4二维数组的存贮

(二)按列存贮先列后行，即先存贮列号较小者，列号相同者先存贮行号较小者

a11a21…am1a12a22…am2……a1na2n…amn

───────────────────

第1列元素

第2列元素

第n列元素任一元素aij的相对地址计算公式为

Loc(i,j)=((j-l2)(h1–l1+1)+(i-l1))·c13§4.1.5多维数组的存贮

(一)按行存贮“左”下标优先的存贮方法【例4.1】设某三维数组的三个下标范围分别为[2,4]，[0,1]，[1,3]则它按行存贮的次序为

a201a202a203a211a212a213（接下行）

a301a302a303a311a312a313（接下行）

a401a402a403a411a412a41314§4.1.5多维数组的存贮(一)按行存贮“设n维数组第k维的下标范围是[lk,hk]，记

dk

=hk

-lk

+1，jk

=ik

-lk，k=1,2,…,n则Loc(i1,i2,…,in)＝c·(j1d2d3…dn

+j2d3…dn+…+jn-1dn+jn)例如，三维数组的寻址公式为

Loc(i1i2i3)＝c·(j1d2d3+j2d3+j3)15§4.1.5多维数组的存贮(二)按列存贮右下标（最后一维下标为最右）优先的存贮映射方式

a201a301a401a211a311a411（接下行）

a202a302a402a212a312a412（接下行）

a203a303a403a213a313a413n维数组按列存贮的寻址公式为

Loc(i1,i2…in)=c·(j1+d1j2+d1d2j3+…+d1d2…dn-1jn)例如，对三维数组，按列存储寻址公式为

Loc(i1i2i3)＝

c·(j1+d1j2+d1d2j3)16§4.1.6寻址公式的计算

秦九韶法变换式(F4.1)中的主要部份

j1d2d3…dn

+j2d3…dn+…+jn-1dn+jn=(j1d2+j2)d3…dn

+j3d4…dn+…+jn-1dn+jn=((j1d2+j2)d3+j3)d4…dn

+j4d5…dn+…+jn-1dn+jn=……=(…(j1d2+j2)d3+j3)d4+j4)d5+…+jn-1)dn+jn=(…((0*d1+j1)d2+j2)d3+j3)d4+j4)d5+…+jn-1)dn+jn

17§4.1.6寻址公式的计算此式可按下法计算

s=0; k=1; while(k<=n) { s=s*dk+jk

; k=k+1;}18§4.1.6寻址公式的计算longGetArrayElemAddress

(longl[],longh[],longi[],longn,intc){longk,s;

s=0;for(k=1;k<=n;k++)s=s*(h[k]–l[k]+1)+(i[k]–l[k]);returns;}19§4.2特殊数组

二维数组在形式上是矩阵

特殊矩阵：元素分布具有一定规律

对称矩阵

上/下三角矩阵

稀疏矩阵：零元素（或相同元素）居多数的矩阵

20§4.2.1对称矩阵若n阶方阵元素满足

aij=aji

（i,j为任意的在下标范围内的数）则称其为对称矩阵。

有近1/2元素是相同的，所以可只存贮不同元素主对角线及其之下的元素为下三角元素，主对角线及其之上元素为上三角元素

a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a4421§4.2.1对称矩阵

1．按行存贮下三角

存贮次序为

a11a21a22a31a32a33a41a42a43a44寻址公式为

Loc(i,j)=((i-l1)(i-l1+1)/2+(j-l2))·c…………当i≥jLoc(i,j)=Loc(j,i)……当i＜j22§4.2.1对称矩阵

2．按列存贮下三角

下三角按列存贮映射方法为：

a11a21a31a41a22a23a24a33a34a44这种存贮方式的寻址公式为

Loc(i,j)=((j-l2)(2n-j+l2+1)/2+(j-i+l1-l2))*c……当i≥jLoc(i,j)=Loc(j,i)…当i＜j23§4.2.2下/上三角矩阵

下/上三角矩阵

矩阵主对线上方/下方元素全为0存贮方式完全同对称矩阵

寻址:对下三角，i<j时元素值为0；对上三角，i>j时元素值为0，对0值元素无需寻址。

24§4.3稀疏矩阵压缩存贮

:不存贮零元素

必须显式地指出每个元素逻辑次

对每个非0元素，用如下形式的一个三元组表示：（行号，列号，元素值）各非0元素对应的三元组构成的集合就是相应的稀疏矩阵的逻辑表示

§4.3.1稀疏矩阵的逻辑表示

25【例4.2】稀疏矩阵

002000 003001M= 100000 000000 405000的三元组集合为

M={(1,3,2),(2,3,3),(2,6,1),(3,1,1),(5,1,4),(5,3,5)}§4.3.1稀疏矩阵的逻辑表示

有二种表示方法：三元组表表示法十字链表表示法26(一)存贮方法将稀疏矩阵视为由非0元素的形如（行号，列号，

元素值）的三元组构成的线性表

表中三元组按行序（或列序）排列，采用连续存贮结构

这种非0元素三元组线性表的连续存贮结构就称为稀疏矩阵的三元组表存贮法。

§4.3.2三元组表法

27(一)存贮方法【例4.3】上节例（【例4.2】）中的矩阵M的按行排列的线性表（顺序存贮结构）如下所示

§4.3.2三元组表法行号列号元素值56613223326131151453500200000300110000000000040500028(二)三元组对象描述structTTriTuple{longrow,col;floatval;

operator==(TTriTuple&i1){return(row==i1.row&&col==i1.col&&val==i1.val);}§4.3.2三元组表法29(二)三元组对象描述TTriTuple&operator=(TTriTuple&i1){this->row=i1.row;this->col=i1.col;this->val=i1.val;returni1;};

};//TTriTuple

§4.3.2三元组表法30(二)三元组对象描述ostream&operator<<(ostream&oo,TTriTuple&i1){oo<<"("<<i1.row<<","<<i1.col<<","<<i1.val<<")";returnoo;}§4.3.2三元组表法31(二)三元组对象描述classTTriTupleArray:publicTLinearListSqu<TTriTuple>{longrows,cols;floattheZero;//稀疏矩阵中相同元素的值，一般是零

longAddNew

(longi,longj,floatx);

§4.3.2三元组表法32(二)三元组对象描述public:

TTriTupleArray

();

TTriTupleArray

(longmSize);float&Get(longi,longj);voidSet(longi,longj,floatx);longGetRowsCols

(long&r,long&c);longAddNew

(longi,longj,floatx);floatDelete(longi,longj);int

Trans1(TTriTupleArray&tu);int

Trans2(TTriTupleArray&tu);

};§4.3.2三元组表法33(二)三元组对象描述相应的初始化函数为：TTriTupleArray::TTriTupleArray

():TLinearListSqu<TTriTuple>(){rows=0;cols=0;theZero=0;}§4.3.2三元组表法34(二)三元组对象描述TTriTupleArray::TTriTupleArray(longmSize):TLinearListSqu<TTriTuple>(mSize){rows=0;cols=0;theZero=0;}§4.3.2三元组表法35Get(i,j)----返回下标为（i,j）的元素的值的引用。

Set(i,j,x)----将下标为（i,j）的元素的值置为xTrans()----将三元组所代表的矩阵转置

§4.3.3三元组表的操作

36为了方便地动态获取三元组表矩阵的最大行号和列号，特设立GetRowsCols(long&r,long&c)，它的源代码为：

longTTriTupleArray::GetRowsCols

(long&r,long&c){longk;

r=0;c=0;for(k=0;k<len;k++){if(r<room[k].row)r=room[k].row;if(c<room[k].col)c=room[k].col;

}returnk;//返回非零元素个数}§4.3.3三元组表的操作37当一个元素由零变为非零时，需要在三元组表中增加新元素，该工作由下列AddNew函数完成

longTTriTupleArray::AddNew

(longi,longj,floatx){longk,kk;

k=len-1;while(k>=0){if(i<room[k].row)k--;elsebreak;}§4.3.3三元组表的操作38while(k>=0&&room[k].row==i){if(j<room[k].col)k--;elsebreak;}

if(k>=0&&i==room[k].row&&j==room[k].col)

{room[k].val=x;returnk;}for(kk=len-1;kk>k;kk--) room[kk+1]=room[kk];room[k+1].row=i;room[k+1].col=j;room[k+1].val=x;len++;if(i>rows)rows++;if(j>cols)cols++;returnk+1;}39下面是具体的Get和Set函数的实现：

float&TTriTupleArray::Get(longi,longj){longk;

k=0;while(k<len){if(room[k].row==i)if(room[k].col==j)break;k++;}if(k==len)returntheZero;returnroom[k].val;}40voidTTriTupleArray::Set(longi,longj,floatx){longk;

k=0;while(k<len){if(room[k].row==i){if(room[k].col==j)break;}k++;}41if(k==len){if(x!=theZero)AddNew(i,j,x);}else{if(x!=theZero)room[k].val=x;elseDelete(i,j);}}42

若矩阵是用二维数组表示的，转置过程可描述如下：

inta[m][n],b[n][m];…………for(i=0;i<m;i++)for(j=0;j<n;j++)b[j][i]=a[i][j];§4.3.4转置操作43

如果矩阵是用三元组表表示的，可以利用Get和Setfor(i=0;i<m;i++)for(j=0;j<n;j++)b.Set(j,i,a.Get(I,j));§4.3.4转置操作

44直接实现转置的讨论：显然的做法是：将每个元素的行号和列号分别互换；对三元组表排序，使其中元素按行序（或列序）排列。时间复杂度O(n)+O(nlog(n))要降低时间复杂度，一个显然的做法是免去排序操作§4.3.4转置操作

45

使在进行元素的行号和列号互换的过程中，顺便实现行序（列序）排列

将a的每个元素从三元组表中取出，交换它们的行号值与列号值；

将所取出的三元组元素存入目标三元组表b中适当位置，使三元组表b保持行序/列序。

§4.3.4转置操作

46【例4.4】.这里给出一个稀疏矩阵A与它的三元组形式a以及它们的转置形式B与其三元组形式b行号列号元素值145213342521552行号列号元素值123251415432552转置三元组(行序)三元组(行序)转置47(一)转置算法(I)该算法可概括为“直接取，顺序存”

即第1次从a中选取一个适当元素放置到b中的第1个位置，第2次从a中选取一个适当元素放到b中的第2个位置，……其过程可描述如下：

pb=1;/*pb为b中当前空位置中编号最小的位置的指示器*/for（col=最小列号;col<=最大列号;col++）{在a中按从头到尾的次序，查找有无列号为col的三元组;若有，则将其行列交换后存入b中pb所指位置;pb加1;}§4.3.4转置操作

48(一)转置算法(I)intTTriTupleArray::Trans1(TTriTupleArray&tu){longpa,pb,col;longmCols,mRows;

if(len<1)return0;tu.ResizeRoom(len);GetRowsCols(mRows,mCols);pb=0;§4.3.4转置操作

49(一)转置算法(I)for(col=1;col<=mCols;col++){for(pa=0;pa<len;pa++)if(room[pa].col==col){tu.room[pb].row=room[pa].col;tu.room[pb].col=room[pa].row;tu.room[pb].val=room[pa].val;pb++;}}

tu.cols=mRows;tu.rows=mCols;tu.len=len;returnlen;}§4.3.4转置操作

50(二)转置算法(II)该算法可概括为“顺序取，直接存”

即依次从a中第1、第2、

……位置取元素，交换它们的行列位置后放置在b中适当位置

该过程可描述为：

for(pa=1;pa<=非0元素个数;pa++){

为a的pa元素确定它在b中应放位置pb;将a的pa元素行列值交换后存入b中pb位置;}§4.3.4转置操作

51(二)转置算法(II)设一个一维数组cpos[]，令cpos[i]=表示原矩阵第i列上第1个非0元素在b中应放置的位置在此基础上，上列程序可进一步细化为：for(pa=起点;pa<=终点;pa++){col=a.room[pa].col;pb=cpos[col];b.room[pb].row=a.room[pa].col;b.room[pb].col=a.room[pa].row;b.room[pb].val=a.room[pb].val;cpos[col]++;/*使cpos[col]为col列上的下一个非0元素

在b中应放置的位置*/

}§4.3.4转置操作

52(二)转置算法(II)至此，问题变为如何求得cpos数组。为了求得cpos，我们引入另一个一维数组cnum[]，令

cnum[i]=

表示原矩阵中第i列上非0元素个数这样，cpos可用下列递推公式求得：

cpos[1]=1 cpos[i]=cpos[i-1]+cnum[i-1]i>=2其对应的程序实现为：

cpos[1]=1; for(col=2;col<=最大列号;col++) cpos[col]=cpos[col-1]+cnum[col-1];§4.3.4转置操作

53(二)转置算法(II)完整算法程序

intTTriTupleArray::Trans2(TTriTupleArray&tu){longpa,pb,col;longmCols,mRows;

if(len<1)return0;tu.ResizeRoom(len);GetRowsCols(mRows,mCols);

long*cnum,*cpos;cnum=newlong[mCols+1];cpos=newlong[mCols+1];§4.3.4转置操作

54(二)转置算法(II)pb=0;for(col=1;col<=mCols;col++)cnum[col]=0;for(pa=0;pa<len;pa++)cnum[room[pa].col]++;

cpos[1]=0;for(col=2;col<=mCols;col++)cpos[col]=cpos[col-1]+cnum[col-1];§4.3.4转置操作

55for(pa=0;pa<len;pa++){col=room[pa].col;pb=cpos[col];tu.room[pb].row=room[pa].col;tu.room[pb].col=room[pa].row;tu.room[pb].val=room[pa].val;cpos[col]++;}

tu.cols=mRows;tu.rows=mCols;tu.len=len;

delete[]cnum;delete[]cpos;returnlen;}56§4.4十字链表

稀疏矩阵的一种链式表示

一切具有正交关系的结构，都可用十字链表存储

57§4.4.1存贮方式

(a)稀疏矩阵中每个非0元素对应一个十字链结点，每个结点的结构为(b)每行/列设一个表头结点（结构同元素结点），以down/right链构成循环链表(c)设一个总头结点（结构同元素结点），令总头结点和各个列/行头结点，用val字段按列/行序构成一个循环单链表。

rowcolvaldownright58§4.4.1存贮方式(d)令总头结点的row，col与val分别表示矩阵（或非0元素）的最大行号、列号与非0元素个数，而down/right指向第1列/行的头结点。该总头结点可作为整个十字链表的代表。(e)由于行与列的头结点分别使用right域与down域(不同时使用)，故第i列与第i行头结点可合用同一个头结点（对所有可能的i），以节省存贮空间。(f)有时设置一个一维数组headNodes[]，使headNodes[i]指向i行/列的头结点。59§4.4.1存贮方式【例4.5】设有一个如下形式的矩阵：它所对应的十字链表如下页：604572112222200211135211211241211312334211221442图‑

十字链表示意图61§4.4.2十字链表对象

template<classTElem>structTCrossNode{longrow,col;

union{TElemval;TCrossNode*next;};TCrossNode*down,*right;62§4.4.2十字链表对象operator==(TCrossNode&oo){return(row==oo.row&&col==oo.col&&val==oo.val);};

TCrossNode&operator=(TCrossNode&oo){this->row=oo.row;this->col=oo.col;this->val=oo.val;returnoo;};

}63§4.4.2十字链表对象我们将十字链表定义为包含指向十字链表总头结点的指针的对象。

template<classTElem>classTCrossLink{TCrossNode<TElem>*head;longrows,cols;inttheZero;

voidReleaseAll

(void);TCrossNode<TElem>*Insert(TCrossNode<TElem>*pNode,longi,longj);int

Insert(TElem&x,longi,longj);int

Delete(longi,longj);64§4.4.2十字链表对象public:longlen;

TCrossLink

();

TCrossLink

(longrows,longcols);

~TCrossLink

();

TCrossNode<TElem>*Init(longrows,longcols);

TElem&Get(longi,longj);TCrossNode<TElem>*GetNode

(longi,longj);TCrossNode<TElem>*Set(longi,longj,TElem&x);

TCrossNode<TElem>*TCrossLink::GetHead

(longk);

int

Print();

};65§4.4.3基本操作的实现

(一)初始化操作该函数生成一个具有rows1行和cols1列的空的十字链表。template<classTElem>TCrossNode<TElem>*TCrossLink<TElem>::Init(longrows1,longcols1){TCrossNode<TElem>*p,*h;longrc;

rc=rows1;if(rc<cols1)rc=cols1;图‑

空十字链表02000000……66§4.4.3基本操作的实现(一)初始化操作if(head!=NULL)ReleaseAll();

h=newTCrossNode<TElem>;if(h==NULL)throwTExcepComm(3);

h->next=h;h->row=rows1;h->col=cols1;67§4.4.3基本操作的实现(一)初始化操作for(longi=0;i<rc;i++){p=newTCrossNode<TElem>;p->row=p->col=0;p->down=p;p->right=p;

p->next=h->next;h->next=p;}

rows=rows1;cols=cols1;head=h;returnh;}68§4.4.3基本操作的实现(二)插入操作两个插入版本，一个是将存在的链结点插入，另一个是已知元素值进行插入，它通过调用前者实现。template<classTElem>TCrossNode<TElem>*TCrossLink<TElem>::Insert(TCrossNode<TElem>*pNode){longi,j;TCrossNode<TElem>*p,*p0;

i=pNode->row;j=pNode->col;p0=GetHead(i);//得到行i的头结点。然后在行i上插入pNodeif(p0==NULL)throwTExcepComm(1);p=p0;69§4.4.3基本操作的实现(二)插入操作

while(p->right!=p0&&p->right->col<j)//寻找插入位置pp=p->right;pNode->right=p->right;//在p后插入pNodep->right=pNode;

p0=GetHead(j);//得到列j的头结点。然后在列j上插入pNodeif(p0==NULL)throwTExcepComm(1);p=p0;while(p->down!=p0&&p->down->row<i)//寻找插入位置pp=p->down;pNode->down=p->down;//在p后插入pNodep->down=pNode;

len++;returnhead;};70§4.4.3基本操作的实现(二)插入操作

template<classTElem>TCrossNode<TElem>*Insert(TElem&x,longi,longj){TCrossNode<TElem>*p;

p=newTCrossNode<TElem>;if(p==NULL)throwTExcepComm(3);

p->row=i;p->col=j;p->val=x;Insert(p);returnp;}71§4.4.3基本操作的实现(三)删除操作留做练习。72§4.4.3基本操作的实现(四)Get类操作Get类操作实现按数组方式访问十字链表，即已知行号和列号求出元素值。

有两个版本第一个是已知行号和列号求对应元素结点的指针第二个是是已知行号和列号求对应元素的值。后者可在前者基础上实现。实现方法是搜索给定行（或列）对应的链表，查找列号（或行号）为给定列号（或行号）的结点。73§4.4.3基本操作的实现(四)Get类操作template<classTElem>TCrossNode<TElem>*TCrossLink<TElem>::GetNode

(longi,longj){TCrossNode<TElem>*p,*p0;

p0=GetHead(i);if(p0==NULL)returnNULL;p=p0;while(p->right!=p0&&p->right->col<j)p=p->right;if(p->right->col==j)returnp->right;elsereturnNULL;}74§4.4.3基本操作的实现(四)Get类操作template<classTElem>TElem&TCrossLink<TElem>::Get(longi,longj){TCrossNode<TElem>*p;p=GetNode(i,j);if(p==NULL)return(TElem)theZero;elsereturnp->val;}75§4.4.3基本操作的实现(五)Set类操作Get类操作实现按数组方式给元素置值即已知行号和列号，给对应的元素置值。需要先按给定的行号和列号查找对应的元素查找到时，直接赋值即可，但当赋0值时应删除对应的结点查不到时，要调用Insert新插入一个结点76§4.4.3基本操作的实现(五)Set类操作template<classTElem>TCrossNode<TElem>*TCrossLink<TElem>::Set(longi,longj,TElem&x){TCrossNode<TElem>*p,*p0;

if(x==0){p=Delete(i,j);if(p!=NULL){deletep;returnhead;}elsethrowTExcepComm(1);}77§4.4.3基本操作的实现(五)Set类操作p0=GetHead(i);if(p0==NULL)throwTExcepComm(1);p=p0;while(p->right!=p0&&p->right->col<j)p=p->right;if(p->right->col==j)p->right->val=x;else{p=newTCrossNode<TElem>;p->row=i;p->col=j;p->val=x;Insert(p);}returnp;}78§4.4.3基