1
2
§ 4.1 数组
? 数组是一种十分常用的结构
? 大多数程序设计语言都直接支持数组类型
? 数组的基本操作主要是元素定位
? 本节的主要内容是讨论数组的存贮映射方法
3
§ 4.1.1 数组的定义与运算
? 数组 是由一组类型相同的数据元素构成，每个
数据元素称为一个数组元素（简称元素）
? 每个元素受 n 个线性关系约束（ n≥ 1），若它
在第 1～第 n个线性关系中的序号分别为 i1、
i2……i n,则称它的 下标 为 i1,i2……i n，若该数
组的名为 A，则记下标为 i1,i2……i n,的元素为，
称该数组为 n维 数组。
4
§ 4.1.1 数组的定义与运算
? 数组 的另一个定义
? 数组定义为一个元素可直接按序号寻址的线性表
A=(A1,A2,…,Am)
若 Ai是简单元素（不是数组），则 A是一维数组；若 Ai是
（ k-1)维数组，则 A是 k维数组。
数组是从线性表的推广
而来
5
§ 4.1.1 数组的定义与运算
图 - 一个 3维数组的元素关系示意
1321 ?iiia
321,1 iiia ?
321,1 iiia ?
321 iiia
321,1 iiia ?
321,1 iiia ?
1321 ?iiia
6
§ 4.1.1 数组的定义与运算
? 一维数组的操作
– 给定一组下标, 读出相应的元素 。
– 给定一组下标，修改相应的元素。
7
§ 4.1.2 数组的存储结构与寻址问题
? 要求元素的存储地址能根据它的下标（即逻辑关系）
计算出来, 一般只采用顺序存储结构
? 偏移地址（相对地址）
– 选定一个基准（参考）存贮单元，问题中所涉及的地址值均
以此参考单元为基准（为起点）
– 设 i1,i2,…, in为某 n维数组中的一个元素的下标，则用
Loc(i1,i2,…,in)表示此元素的相对地址
? 可以将多维数组影射为一维结构，然后运用顺序存储
方式。
8
§ 4.1.3 一维数组的存贮与寻址
? 设一维数组为
A=(a0,a1,…,a n)
则它的元素 ai的相对地址为
Loc(i)=i · c
? 若数组下标范围为 闭区间 [l1,h1]内的整数，即
A=( )
则元素 ai的相对地址为
Loc(i)=(i-l1) · c
111,.,,,,1 hll aaa ?
9
§ 4.1.4 二维数组的存贮
? 二维数组的阵列形状
a11 a12 … a 1n
a21 a22 … a2n
A = ……
am1 am2 … a mn
? 常用的映射方法有两种,按行 与 按列
10
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 先行后列：先存贮行号较小的元素，行号相同者，先
存贮列号较小者。
a11 a12 … a1n a21 a22 … a2n …… am1 am2 … amn
────── ─────── ──────
第 1行元素 第 2行元素 第 m行元素
11
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 设二维数组的行下标与列下标变化范围分别为闭区间
[l1,h1]与 [l2,h2]，按行存储,任一元素 aij的相对地址计
算公式为
Loc(i,j) = ( (h2 - l2+1) (i-l1) + (j-l2) ) · c
12
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 【 例 4.1】,设某二维数组的两个下标的范围分别为 [-1,2]
与 [0,1]，它的元素按行存贮的次序为（用 ai表示元素，
每个元素占两个单元）：
相对地址 0 2 4 6 8 10 12 14
元素 a-1,0 a-1,1 a0,0 a0,1 a1,0 a1,1 a2,0 a2,1
Loc(-1,1)＝ ( (1-0+1)(-1+1)+(1-0) )*2
＝ 2
13
§ 4.1.4 二维数组的存贮
? (二 )按列存贮
? 先列后行，即先存贮列号较小者，列号相同者先存贮
行号较小者
a11 a21 … am1 a12 a22 … am2 …… a1n a2n … amn
────── ─────── ──────
第 1列元素 第 2列元素 第 n列元素
? 任一元素 aij的相对地址计算公式为
Loc(i,j) = ( (j-l2) (h1 – l1+1) + (i-l1) ) · c
14
§ 4.1.5 多维数组的存贮
? (一 )按行存贮
?, 左, 下标优先的存贮方法
【 例 4.1】 设某三维数组的三个下标范围分别为
[2,4],[0,1],[1,3]
则它按行存贮的次序为
a201 a202 a203 a211 a212 a213 （ 接下行 ）
a301 a302 a303 a311 a312 a313 （ 接下行 ）
a401 a402 a403 a411 a412 a413
15
§ 4.1.5 多维数组的存贮
? (一 )按行存贮
?,设 n维数组第 k维的下标范围是 [lk,hk]，记
dk = hk - lk + 1,jk = ik - lk,k= 1,2,…,n
则 Loc(i1,i2,…,i n)＝ c·(j1d2d3…d n + j2d3…d n +…+j n-1dn + jn)
? 例如，三维数组的寻址公式为
Loc(i1i2i3)＝ c·(j1d2d3 + j2d3 + j3)
16
§ 4.1.5 多维数组的存贮
? (二 )按列存贮
? 右下标（最后一维下标为最右）优先的存贮映射方式
a201 a301 a401 a211 a311 a411 （ 接下行 ）
a202 a302 a402 a212 a312 a412 （ 接下行 ）
a203 a303 a403 a213 a313 a413
? n维数组按列存贮的寻址公式为
Loc(i1,i2 … i n) = c · (j1 + d1j2 + d1d2j3 + …+ d 1d2 …d n-1jn)
? 例如，对三维数组，按列存储寻址公式为
Loc(i1i2i3) ＝ c·( j1+d1j2 + d1d2j3 )
17
§ 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
18
§ 4.1.6 寻址公式的计算
? 此式可按下法计算
s=0;
k=1;
while (k<=n)
{
s = s*dk+jk ;
k = k+1;
}
19
§ 4.1.6 寻址公式的计算
longGetArrayElemAddress (longl[],longh[],long i[],long n,int c)
{
long k,s;
s=0;
for (k=1; k<=n; k++)
s = s*(h[k] – l[k] + 1) + (i[k] – l[k]);
return s;
}
20
§ 4.2 特殊数组
? 二维数组在形式上是矩阵
? 特殊矩阵, 元素分布具有一定规律
– 对称矩阵
– 上 /下三角矩阵
? 稀疏矩阵, 零元素 （ 或相同元素 ） 居多数的矩阵
21
§ 4.2.1 对称矩阵
? 若 n阶方阵元素满足
aij=aji （ i,j为任意的在下标范围内的数 ）
则称其为 对称矩阵 。
? 有近 1/2元素是相同的, 所以可只存贮不同元素
? 主对角线及其之下的元素为下三角元素, 主对角线及其之上元素为
上三角元素
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
22
§ 4.2.1 对称矩阵
1,按行存贮下三角
? 存贮次序为
a11 a21 a22 a31 a32 a33 a41 a42 a43 a44
? 寻址公式为
Loc(i,j) = ((i-l1)(i-l1+1) /2 +(j-l2)) ·c ………… 当 i≥j
Loc(i,j) = Loc(j,i) …………………… 当 i＜ j
23
§ 4.2.1 对称矩阵
2,按列存贮下三角
? 下三角按列存贮映射方法为：
a11 a21 a31 a41 a22 a23 a24 a33 a34 a44
? 这种存贮方式的寻址公式为
Loc(i,j) = ((j-l2)(2n-j+l2+1)/2 + (j-i+l1-l2))*c …… 当 i≥j
Loc(i,j) =Loc(j,i) ………………… 当 i＜ j
24
§ 4.2.2 下 /上三角矩阵
? 下 /上三角矩阵
矩阵主对线上方 /下方元素全为 0
? 存贮方式完全同对称矩阵
? 寻址,
– 对下三角, i<j时元素值为 0；
– 对上三角, i>j时元素值为 0,对 0值元素无需寻址 。
25
§ 4.3 稀疏矩阵
? 压缩存贮,不存贮零元素
? 必须显式地指出每个元素逻辑次
? 对每个非 0元素, 用如下形式的一个三元组表示：
（ 行号, 列号, 元素值 ）
? 各非 0元素对应的三元组构成的集合就是相应的
稀疏矩阵的逻辑表示
§ 4.3.1 稀疏矩阵的逻辑表示
26
?【 例 4.2】 稀疏矩阵
0 0 2 0 0 0
0 0 3 0 0 1
M = 1 0 0 0 0 0
0 0 0 0 0 0
4 0 5 0 0 0
的三元组集合为
M={(1,3,2),(2,3,3),(2,6,1),(3,1,1),(5,1,4),(5,3,5) }
§ 4.3.1 稀疏矩阵的逻辑表示
有二种表示方法：
三元组表表示法
十字链表表示法
27
? (一 ) 存贮方法
? 将稀疏矩阵视为由非 0元素的形如（行号，列号，
元素值）的三元组构成的线性表
? 表中三元组按行序（或列序）排列，采用连续
存贮结构
? 这种非 0 元素三元组线性表的连续存贮结构就称
为稀疏矩阵的 三元组表存贮法 。
§ 4.3.2 三元组表法
28
?(一 ) 存贮方法
?【 例 4.3】 上节例（ 【 例 4.2】 ）中的矩阵 M 的按行排列的线性表（顺
序存贮结构）如下所示
§ 4.3.2 三元组表法
行号 列号 元素值
5 6 6
1 3 2
2 3 3
2 6 1
3 1 1
5 1 4
5 3 5
0 0 2 0 0 0
0 0 3 0 0 1
1 0 0 0 0 0
0 0 0 0 0 0
4 0 5 0 0 0
29
?(二 )三元组对象描述
struct TTriTuple
{
long row,col;
float val;
operator ==( TTriTuple &i1)
{
return (row == i1.row && col==i1.col && val==i1.val);
}
§ 4.3.2 三元组表法
30
?(二 )三元组对象描述
TTriTuple& operator =( TTriTuple &i1)
{
this->row = i1.row;
this->col = i1.col;
this->val = i1.val;
return i1;
};
}; // TTriTuple
§ 4.3.2 三元组表法
31
?(二 )三元组对象描述
ostream& operator << (ostream& oo,TTriTuple &i1)
{
oo<<"("<<i1.row<<","<<i1.col<<","<<i1.val<<") ";
return oo;
}
§ 4.3.2 三元组表法
32
?(二 )三元组对象描述
class TTriTupleArray, public TLinearListSqu<TTriTuple>
{
long rows,cols;
float theZero; // 稀疏矩阵中相同元素的值, 一般是零
long AddNew (long i,long j,float x);
§ 4.3.2 三元组表法
33
?(二 )三元组对象描述
public:
TTriTupleArray( );
TTriTupleArray( long mSize);
float& Get ( long i,long j);
void Set ( long i,long j,float x);
longGetRowsCols ( long &r,long &c);
longAddNew ( long i,long j,float x);
float Delete ( long i,long j);
int Trans1( TTriTupleArray &tu);
int Trans2( TTriTupleArray &tu);
} ;
§ 4.3.2 三元组表法
34
?(二 )三元组对象描述
?相应的初始化函数为：
TTriTupleArray::TTriTupleArray ( ):TLinearListSqu<TTriTuple>()
{
rows=0;
cols=0;
theZero=0;
}
§ 4.3.2 三元组表法
35
?(二 )三元组对象描述
TTriTupleArray,,TTriTupleArray (long mSize):
TLinearListSqu <TTriTuple> (mSize)
{
rows=0;
cols=0;
theZero=0;
}
§ 4.3.2 三元组表法
36
? Get(i,j)----返回下标为（ i,j）的元素的值的引用。
? Set(i,j,x)----将下标为（ i,j）的元素的值置为 x
? Trans( )----将三元组所代表的矩阵转置
§ 4.3.3 三元组表的操作
37
?为了方便地动态获取三元组表矩阵的最大行号和列号，特设立
GetRowsCols(long &r,long &c)，它的源代码为：
longTTriTupleArray::GetRowsCols( long &r,long &c)
{
long k;
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;
}
return k; //返回非零元素个数
}
§ 4.3.3 三元组表的操作
38
?当一个元素由零变为非零时，需要在三元组表中增加新元素，该工
作由下列 AddNew函数完成
longTTriTupleArray::AddNew ( long i,long j,float x)
{
long k,kk;
k=len-1;
while (k>=0)
{
if (i < room[k].row) k--;
else break;
}
§ 4.3.3 三元组表的操作
39
while (k>=0 && room[k].row==i)
{
if (j < room[k].col) k--;
else break;
}
if (k>=0 && i==room[k].row&& j==room[k].col )
{ room[k].val=x; return k; }
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++;
return k+1;
}
40
?下面是具体的 Get和 Set函数的实现：
float& TTriTupleArray::Get ( long i,long j)
{
long k;
k=0;
while (k<len)
{
if (room[k].row==i)
if (room[k].col==j) break;
k++;
}
if (k==len) return theZero;
return room[k].val;
}
41
void TTriTupleArray::Set ( long i,long j,float x)
{
long k;
k=0;
while (k<len)
{
if (room[k].row==i)
{
if (room[k].col==j) break;
}
k++;
}
42
if( k==len)
{
if (x!=theZero)
AddNew(i,j,x);
}
else
{
if (x!=theZero) room[k].val = x;
else Delete(i,j);
}
}
43
? 若矩阵是用二维数组表示的, 转置过程可描述如下：
int a[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 转置操作
44
? 如果矩阵是用三元组表表示的，可以利用 Get和 Set
for (i=0; i<m; i++)
for (j=0; j<n; j++)
b.Set(j,i,a.Get(I,j) );
§ 4.3.4 转置操作
45
? 直接实现转置 的讨论：
? 显然的做法是：
– 将每个元素的行号和列号分别互换；
– 对三元组表排序，使其中元素按行序（或列序）排列。
? 时间复杂度 O(n)+O(nlog(n))
? 要降低时间复杂度，一个显然的做法是免去排序操作
§ 4.3.4 转置操作
46
? 使在进行元素的行号和列号互换的过程中，顺便实现
行序（列序）排列
– 将 a的每个元素从三元组表中取出，交换它们的行号值与列号
值；
– 将所取出的三元组元素存入目标三元组表 b中适当位置，使三
元组表 b保持行序 /列序。
§ 4.3.4 转置操作
47
?【 例 4.4】,这里给出一个稀疏矩阵 A与它的三元组形式 a以及它们的转
置形式 B与其三元组形式 b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
020010
000000
002000
000003
005000
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00000
20000
00205
00000
10000
00030
B
行号 列号 元素值
1 4 5
2 1 3
3 4 2
5 2 1
5 5 2
行号 列号 元素值
1 2 3
2 5 1
4 1 5
4 3 2
5 5 2
转置
三元组 (行序 ) 三元组 (行序 )
转置
48
? (一 ) 转置算法 (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 转置操作
49
?(一 ) 转置算法 (I)
int TTriTupleArray::Trans1 (TTriTupleArray &tu)
{
long pa,pb,col;
long mCols,mRows;
if (len<1) return 0;
tu.ResizeRoom(len);
GetRowsCols(mRows,mCols);
pb=0;
§ 4.3.4 转置操作
50
?(一 ) 转置算法 (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;
return len;
}
§ 4.3.4 转置操作
51
? (二 )转置算法 (II)
? 该算法可概括为, 顺序取，直接存,
– 即依次从 a中第 1、第 2,…… 位置取元素，交换它们的行列位
置后放置在 b中适当位置
– 该过程可描述为：
for (pa=1; pa<=非 0元素个数 ; pa++)
{
为 a的 pa元素确定它在 b中应放位置 pb;
将 a的 pa元素行列值交换后存入 b中 pb位置 ;
}
§ 4.3.4 转置操作
52
? (二 )转置算法 (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 转置操作
53
? (二 )转置算法 (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 转置操作
54
?(二 )转置算法 (II)
?完整算法程序
int TTriTupleArray::Trans2 (TTriTupleArray &tu)
{
long pa,pb,col;
long mCols,mRows;
if (len<1) return 0;
tu.ResizeRoom(len);
GetRowsCols(mRows,mCols);
long *cnum,*cpos;
cnum=new long[mCols+1];
cpos=new long[mCols+1];
§ 4.3.4 转置操作
55
?(二 )转置算法 (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 转置操作
56
for (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;
return len;
}
57
§ 4.4十字链表
? 稀疏矩阵的一种链式表示
? 一切具有正交关系的结构，都可用十字链表存
储
58
§ 4.4.1 存贮方式
(a)稀疏矩阵中每个非 0元素对应一个十字链结点，每个
结点的结构为
(b)每行 /列设一个表头结点（结构同元素结点），以
down/right链构成循环链表
(c)设一个总头结点（结构同元素结点），令总头结点和
各个列 /行头结点，用 val字段按列 /行序构成一个循环
单链表。
row col val
down right
59
§ 4.4.1 存贮方式
(d) 令总头结点的 row,col与 val 分别表示矩阵 （ 或非 0元
素 ） 的最大行号, 列号与非 0元素个数, 而 down/right
指向第 1列 /行的头结点 。 该总头结点可作为整个十字
链表的代表 。
(e)由于行与列的头结点分别使用 right域与 down域 (不同时
使用 ),故第 i列与第 i 行头结点可合用同一个头结点
（ 对所有可能的 i）, 以节省存贮空间 。
(f)有时设置一个一维数组 headNodes[ ], 使 headNodes[i]
指向 i行 /列的头结点 。
60
§ 4.4.1 存贮方式
?【 例 4.5】 设有一个如下形式的矩阵：
?它所对应的十字链表如 下页：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
02010
00402
01001
00500
A
61
4 5 7 2 1 1 2 2 2 2 2 0 0
2 1 1 1 3 5
2 1 1 2 1 1 2 4 1
2 1 1 3 1 2 3 3 4
2 1 1 2 2 1 4 4 2
图 - 十字链表示意图
??
?
?
?
?
?
??
?
?
?
?
?
?
02010
00402
01001
00500
A
62
§ 4.4.2 十字链表对象
template <class TElem>
struct TCrossNode
{
long row,col;
union {
TElem val;
TCrossNode *next;
};
TCrossNode *down,*right;
63
§ 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;
return oo;
};
}
64
§ 4.4.2 十字链表对象
?我们将十字链表定义为包含指向十字链表总头结点的指针的对象 。
template <class TElem>
class TCrossLink
{
TCrossNode<TElem> *head;
longrows,cols;
int theZero;
void ReleaseAll ( void);
TCrossNode<TElem> *Insert ( TCrossNode<TElem> *pNode,long i,
longj);
int Insert ( TElem& x,long i,long j);
int Delete( long i,long j);
65
§ 4.4.2 十字链表对象
public:
longlen;
TCrossLink( );
TCrossLink( long rows,long cols);
~TCrossLink( );
TCrossNode<TElem>* Init ( long rows,long cols);
TElem& Get (long i,long j);
TCrossNode<TElem>* GetNode ( long i,long j);
TCrossNode<TElem> * Set ( long i,long j,TElem& x);
TCrossNode<TElem>* TCrossLink::GetHead ( long k);
int Print( );
} ;
66
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
? 该函数生成一个具有 rows1行和 cols1列的空的十字链表。
template <class TElem>
TCrossNode<TElem>* TCrossLink<TElem>::Init (long rows1,long cols1)
{
TCrossNode<TElem> *p,*h;
long rc;
rc=rows1;
if (rc<cols1) rc=cols1;
图 - 空十字链表
0 2 0 0 0 0 0 0 … …
67
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
if (head!=NULL) ReleaseAll();
h= new TCrossNode<TElem>;
if (h==NULL) throw TExcepComm(3);
h->next = h;
h->row=rows1;
h->col=cols1;
68
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
for (long i=0; i<rc; i++)
{
p = new TCrossNode<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;
return h;
}
69
§ 4.4.3 基本操作的实现
?(二 )插入操作
?两个插入版本，一个是将存在的链结点插入，另一个是已知元素值
进行插入，它通过调用前者实现。
template <class TElem>
TCrossNode<TElem> *TCrossLink<TElem>::
Insert (TCrossNode<TElem> *pNode)
{
long i,j;
TCrossNode<TElem> *p,*p0;
i=pNode->row;
j=pNode->col;
p0 = GetHead(i); //得到行 i的头结点 。 然后在行 i上插入 pNode
if (p0==NULL) throw TExcepComm(1);
p=p0;
70
§ 4.4.3 基本操作的实现
?(二 )插入操作
while (p->right!=p0 && p->right->col<j) //寻找插入位置 p
p = p->right;
pNode->right = p->right; //在 p后插入 pNode
p->right = pNode;
p0 = GetHead(j); //得到列 j的头结点 。 然后在列 j上插入 pNode
if (p0==NULL) throw TExcepComm(1);
p=p0;
while (p->down!=p0 && p->down->row<i) //寻找插入位置 p
p = p->down;
pNode->down = p->down; //在 p后插入 pNode
p->down = pNode;
len++;
return head;
} ;
71
§ 4.4.3 基本操作的实现
?(二 )插入操作
template <class TElem>
TCrossNode<TElem> *Insert (TElem& x,long i,long j)
{
TCrossNode<TElem> *p;
p = new TCrossNode<TElem>;
if (p==NULL) throw TExcepComm(3);
p->row=i;
p->col=j;
p->val=x;
Insert(p);
return p;
}
72
§ 4.4.3 基本操作的实现
?(三 )删除操作
留做练习 。
73
§ 4.4.3 基本操作的实现
? (四 ) Get类操作
? Get类操作实现按数组方式访问十字链表, 即已知行号
和列号求出元素值 。
? 有两个版本
– 第一个是已知行号和列号求对应元素结点的指针
– 第二个是是已知行号和列号求对应元素的值 。
– 后者可在前者基础上实现 。
– 实现方法是搜索给定行 （ 或列 ） 对应的链表, 查找列号 （ 或
行号 ） 为给定列号 （ 或行号 ） 的结点 。
74
§ 4.4.3 基本操作的实现
?(四 ) Get类操作
template <class TElem>
TCrossNode<TElem>* TCrossLink<TElem>::GetNode (long i,long j)
{
TCrossNode<TElem> *p,*p0;
p0 = GetHead(i);
if (p0==NULL) return NULL;
p=p0;
while (p->right!=p0 && p->right->col<j)
p = p->right;
if (p->right->col==j) return p->right;
else return NULL;
}
75
§ 4.4.3 基本操作的实现
?(四 ) Get类操作
template <class TElem>
TElem& TCrossLink<TElem>::Get (long i,long j)
{
TCrossNode<TElem> *p;
p= GetNode(i,j);
if (p==NULL) return (TElem)theZero;
else return p->val;
}
76
§ 4.4.3 基本操作的实现
? (五 ) Set类操作
? Get类操作实现按数组方式给元素置值
– 即已知行号和列号，给对应的元素置值。
? 需要先按给定的行号和列号查找对应的元素
? 查找到时，直接赋值即可，但当赋 0值时应删除对应的
结点
? 查不到时，要调用 Insert新插入一个结点
77
§ 4.4.3 基本操作的实现
?(五 ) Set类操作
template <class TElem>
TCrossNode<TElem> * TCrossLink<TElem>::Set ( long i,long j,TElem& x)
{
TCrossNode<TElem> *p,*p0;
if (x==0)
{
p=Delete(i,j);
if (p!=NULL)
{delete p;
return head;
}
else throw TExcepComm(1);
}
78
§ 4.4.3 基本操作的实现
?(五 ) Set类操作
p0 = GetHead(i);
if (p0==NULL) throw TExcepComm(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 = new TCrossNode<TElem>;
p->row = i;
p->col = j;
p->val = x;
Insert(p);
}
return p;
}
79
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 设有两个 m× n矩阵 A与 B，它们均按十字链表存贮。
? 现考虑操作 A←A+B,即将 B加到 A 上，两矩阵相加，就
是对应元素相加,aij+bij。
? 该操作的实现：
for (i=1; i<=B.rows; i++)
{
for (j=1; j<=B.cols; j++)
A.Set(i,j,A.Get(I,j)+B.Get(i,j));
}
80
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 下面考虑不借助 Get和 Set进行加法。
? 我们可以采用逐行相加的方法，即逐次将 B的各行加到 A
上
for (i=1; i<=m; i++)
{
pHB=B.GetHead(i); //求 B中第 i行头结点
将 B的第 i行加到 A的第 i行上 ;
}
81
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 问题就转化成了如何, 将 B的第 i行加到 A的第 i行上,
? 该项操作的实现与多项式加法十分类似，其过程可描述
为：
pHA = A.GetHead(i); //求得 A的第 i行头结点
pA=pHA->right; //pA指向 A中 i行上当前待处理的结点
pB=pHB->right; //pB指向 B中 i行上当前待处理的结点
pA0=pHA;
pB0=pHB; //pA0与 pB0分别为 pA与 pB的前趋
82
§ 4.4.3 基本操作的实现
while (pB->right!=pHB) //处理 B的 i行上各结点
{
if (pA->col < pB→col)
{
pA0=pA;
pA=pA→right ; //pA后移一步
}
else
if (pA->col > pB→col)
{
从 pB复制一结点 p；
将 p插入到 A的 i行链表中 pA之前,即 pA0前；
将 p插入到 A的 pB→col 列链表中适当位置；
pB0=pB;
pB=pB->right;
?}
83
else //pB->col==pA->col
{
pA->val = pA->val + pB->val;
if (pA->val !=0 )
{
pA0=pA;
pA=pA→right ;
pB0=pB;
pB=pB→right ;
} //pA与 pB分别后移一步
else
{
将 pA从十字链表中摘除 ;
释放 pA;
pA=pA0->right; //令 pA指向被删结点的下一结点
pB=pB→right ; //pB后移一步
}
}
} //while }
84
习 题 4
? 4.1 分别证明 n维数组的按行与按列存贮的寻址公式,
? 4.2,设 4维数组的 4个下标的范围分别为 [-1,0],[1,2]，
[1,3],[-2,-1],请分别按行序和按列序列出各元素 。
? 4.3对上题, 分别计算元素 a-1,2,2-2 的按行存贮与按列存
贮的相对地址 （ 设每个元素占 2个单元 ）
? 4.4,写出 n维数组按列存贮的寻址公式的计算函数,
? 4.5 设 a与 b分别是 m× n与 n× m矩阵 （ 二维数组 ）, 它
们均按行序存贮在一维结构中, 请分别用两种方法写
出计算 a× b的程序 。 这两种方法是,① 采用二维数组
的寻址公式访问元素； ② 不采用寻址公式访问元素,
而直接推算要访问的元素的存贮位置 。
85
4.6,分别推导出上三角矩阵按行与按列存贮的寻址公式
4.7,设 a与 b是 n× n的对称矩阵, 采用下三角压缩存贮 （ 只存
贮下三角 ）, 请分别按下列两种要求写出计算 a× b 的程
序,① 利用下三角按行存贮的寻址公式访问元素； ② 不利
用寻址公式, 直接推出要访问的元素的存贮位置 。
4.8,设对称矩阵按行序存贮下三角 (存贮在一维结构中 ),请
写一个程序, 根据任一元素的存贮位置 （ 相对位置 ） 求出
它所对应的行号与列号 。
4.9 设 a与 b是两个用三元组表存贮 （ 连续结构 ） 的稀疏矩阵,
请写出将 b 加到 a上的程序 。
4.10 设 a与 b是两个用三元组表存贮 （ 连续结构 ） 的稀疏矩阵,
请写出 a× b的程序,
4.11,写一个将用十字链表存贮的稀疏矩阵转置的程序,
2
§ 4.1 数组
? 数组是一种十分常用的结构
? 大多数程序设计语言都直接支持数组类型
? 数组的基本操作主要是元素定位
? 本节的主要内容是讨论数组的存贮映射方法
3
§ 4.1.1 数组的定义与运算
? 数组 是由一组类型相同的数据元素构成，每个
数据元素称为一个数组元素（简称元素）
? 每个元素受 n 个线性关系约束（ n≥ 1），若它
在第 1～第 n个线性关系中的序号分别为 i1、
i2……i n,则称它的 下标 为 i1,i2……i n，若该数
组的名为 A，则记下标为 i1,i2……i n,的元素为，
称该数组为 n维 数组。
4
§ 4.1.1 数组的定义与运算
? 数组 的另一个定义
? 数组定义为一个元素可直接按序号寻址的线性表
A=(A1,A2,…,Am)
若 Ai是简单元素（不是数组），则 A是一维数组；若 Ai是
（ k-1)维数组，则 A是 k维数组。
数组是从线性表的推广
而来
5
§ 4.1.1 数组的定义与运算
图 - 一个 3维数组的元素关系示意
1321 ?iiia
321,1 iiia ?
321,1 iiia ?
321 iiia
321,1 iiia ?
321,1 iiia ?
1321 ?iiia
6
§ 4.1.1 数组的定义与运算
? 一维数组的操作
– 给定一组下标, 读出相应的元素 。
– 给定一组下标，修改相应的元素。
7
§ 4.1.2 数组的存储结构与寻址问题
? 要求元素的存储地址能根据它的下标（即逻辑关系）
计算出来, 一般只采用顺序存储结构
? 偏移地址（相对地址）
– 选定一个基准（参考）存贮单元，问题中所涉及的地址值均
以此参考单元为基准（为起点）
– 设 i1,i2,…, in为某 n维数组中的一个元素的下标，则用
Loc(i1,i2,…,in)表示此元素的相对地址
? 可以将多维数组影射为一维结构，然后运用顺序存储
方式。
8
§ 4.1.3 一维数组的存贮与寻址
? 设一维数组为
A=(a0,a1,…,a n)
则它的元素 ai的相对地址为
Loc(i)=i · c
? 若数组下标范围为 闭区间 [l1,h1]内的整数，即
A=( )
则元素 ai的相对地址为
Loc(i)=(i-l1) · c
111,.,,,,1 hll aaa ?
9
§ 4.1.4 二维数组的存贮
? 二维数组的阵列形状
a11 a12 … a 1n
a21 a22 … a2n
A = ……
am1 am2 … a mn
? 常用的映射方法有两种,按行 与 按列
10
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 先行后列：先存贮行号较小的元素，行号相同者，先
存贮列号较小者。
a11 a12 … a1n a21 a22 … a2n …… am1 am2 … amn
────── ─────── ──────
第 1行元素 第 2行元素 第 m行元素
11
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 设二维数组的行下标与列下标变化范围分别为闭区间
[l1,h1]与 [l2,h2]，按行存储,任一元素 aij的相对地址计
算公式为
Loc(i,j) = ( (h2 - l2+1) (i-l1) + (j-l2) ) · c
12
§ 4.1.4 二维数组的存贮
? (一 ) 按行存贮
? 【 例 4.1】,设某二维数组的两个下标的范围分别为 [-1,2]
与 [0,1]，它的元素按行存贮的次序为（用 ai表示元素，
每个元素占两个单元）：
相对地址 0 2 4 6 8 10 12 14
元素 a-1,0 a-1,1 a0,0 a0,1 a1,0 a1,1 a2,0 a2,1
Loc(-1,1)＝ ( (1-0+1)(-1+1)+(1-0) )*2
＝ 2
13
§ 4.1.4 二维数组的存贮
? (二 )按列存贮
? 先列后行，即先存贮列号较小者，列号相同者先存贮
行号较小者
a11 a21 … am1 a12 a22 … am2 …… a1n a2n … amn
────── ─────── ──────
第 1列元素 第 2列元素 第 n列元素
? 任一元素 aij的相对地址计算公式为
Loc(i,j) = ( (j-l2) (h1 – l1+1) + (i-l1) ) · c
14
§ 4.1.5 多维数组的存贮
? (一 )按行存贮
?, 左, 下标优先的存贮方法
【 例 4.1】 设某三维数组的三个下标范围分别为
[2,4],[0,1],[1,3]
则它按行存贮的次序为
a201 a202 a203 a211 a212 a213 （ 接下行 ）
a301 a302 a303 a311 a312 a313 （ 接下行 ）
a401 a402 a403 a411 a412 a413
15
§ 4.1.5 多维数组的存贮
? (一 )按行存贮
?,设 n维数组第 k维的下标范围是 [lk,hk]，记
dk = hk - lk + 1,jk = ik - lk,k= 1,2,…,n
则 Loc(i1,i2,…,i n)＝ c·(j1d2d3…d n + j2d3…d n +…+j n-1dn + jn)
? 例如，三维数组的寻址公式为
Loc(i1i2i3)＝ c·(j1d2d3 + j2d3 + j3)
16
§ 4.1.5 多维数组的存贮
? (二 )按列存贮
? 右下标（最后一维下标为最右）优先的存贮映射方式
a201 a301 a401 a211 a311 a411 （ 接下行 ）
a202 a302 a402 a212 a312 a412 （ 接下行 ）
a203 a303 a403 a213 a313 a413
? n维数组按列存贮的寻址公式为
Loc(i1,i2 … i n) = c · (j1 + d1j2 + d1d2j3 + …+ d 1d2 …d n-1jn)
? 例如，对三维数组，按列存储寻址公式为
Loc(i1i2i3) ＝ c·( j1+d1j2 + d1d2j3 )
17
§ 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
18
§ 4.1.6 寻址公式的计算
? 此式可按下法计算
s=0;
k=1;
while (k<=n)
{
s = s*dk+jk ;
k = k+1;
}
19
§ 4.1.6 寻址公式的计算
longGetArrayElemAddress (longl[],longh[],long i[],long n,int c)
{
long k,s;
s=0;
for (k=1; k<=n; k++)
s = s*(h[k] – l[k] + 1) + (i[k] – l[k]);
return s;
}
20
§ 4.2 特殊数组
? 二维数组在形式上是矩阵
? 特殊矩阵, 元素分布具有一定规律
– 对称矩阵
– 上 /下三角矩阵
? 稀疏矩阵, 零元素 （ 或相同元素 ） 居多数的矩阵
21
§ 4.2.1 对称矩阵
? 若 n阶方阵元素满足
aij=aji （ i,j为任意的在下标范围内的数 ）
则称其为 对称矩阵 。
? 有近 1/2元素是相同的, 所以可只存贮不同元素
? 主对角线及其之下的元素为下三角元素, 主对角线及其之上元素为
上三角元素
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
22
§ 4.2.1 对称矩阵
1,按行存贮下三角
? 存贮次序为
a11 a21 a22 a31 a32 a33 a41 a42 a43 a44
? 寻址公式为
Loc(i,j) = ((i-l1)(i-l1+1) /2 +(j-l2)) ·c ………… 当 i≥j
Loc(i,j) = Loc(j,i) …………………… 当 i＜ j
23
§ 4.2.1 对称矩阵
2,按列存贮下三角
? 下三角按列存贮映射方法为：
a11 a21 a31 a41 a22 a23 a24 a33 a34 a44
? 这种存贮方式的寻址公式为
Loc(i,j) = ((j-l2)(2n-j+l2+1)/2 + (j-i+l1-l2))*c …… 当 i≥j
Loc(i,j) =Loc(j,i) ………………… 当 i＜ j
24
§ 4.2.2 下 /上三角矩阵
? 下 /上三角矩阵
矩阵主对线上方 /下方元素全为 0
? 存贮方式完全同对称矩阵
? 寻址,
– 对下三角, i<j时元素值为 0；
– 对上三角, i>j时元素值为 0,对 0值元素无需寻址 。
25
§ 4.3 稀疏矩阵
? 压缩存贮,不存贮零元素
? 必须显式地指出每个元素逻辑次
? 对每个非 0元素, 用如下形式的一个三元组表示：
（ 行号, 列号, 元素值 ）
? 各非 0元素对应的三元组构成的集合就是相应的
稀疏矩阵的逻辑表示
§ 4.3.1 稀疏矩阵的逻辑表示
26
?【 例 4.2】 稀疏矩阵
0 0 2 0 0 0
0 0 3 0 0 1
M = 1 0 0 0 0 0
0 0 0 0 0 0
4 0 5 0 0 0
的三元组集合为
M={(1,3,2),(2,3,3),(2,6,1),(3,1,1),(5,1,4),(5,3,5) }
§ 4.3.1 稀疏矩阵的逻辑表示
有二种表示方法：
三元组表表示法
十字链表表示法
27
? (一 ) 存贮方法
? 将稀疏矩阵视为由非 0元素的形如（行号，列号，
元素值）的三元组构成的线性表
? 表中三元组按行序（或列序）排列，采用连续
存贮结构
? 这种非 0 元素三元组线性表的连续存贮结构就称
为稀疏矩阵的 三元组表存贮法 。
§ 4.3.2 三元组表法
28
?(一 ) 存贮方法
?【 例 4.3】 上节例（ 【 例 4.2】 ）中的矩阵 M 的按行排列的线性表（顺
序存贮结构）如下所示
§ 4.3.2 三元组表法
行号 列号 元素值
5 6 6
1 3 2
2 3 3
2 6 1
3 1 1
5 1 4
5 3 5
0 0 2 0 0 0
0 0 3 0 0 1
1 0 0 0 0 0
0 0 0 0 0 0
4 0 5 0 0 0
29
?(二 )三元组对象描述
struct TTriTuple
{
long row,col;
float val;
operator ==( TTriTuple &i1)
{
return (row == i1.row && col==i1.col && val==i1.val);
}
§ 4.3.2 三元组表法
30
?(二 )三元组对象描述
TTriTuple& operator =( TTriTuple &i1)
{
this->row = i1.row;
this->col = i1.col;
this->val = i1.val;
return i1;
};
}; // TTriTuple
§ 4.3.2 三元组表法
31
?(二 )三元组对象描述
ostream& operator << (ostream& oo,TTriTuple &i1)
{
oo<<"("<<i1.row<<","<<i1.col<<","<<i1.val<<") ";
return oo;
}
§ 4.3.2 三元组表法
32
?(二 )三元组对象描述
class TTriTupleArray, public TLinearListSqu<TTriTuple>
{
long rows,cols;
float theZero; // 稀疏矩阵中相同元素的值, 一般是零
long AddNew (long i,long j,float x);
§ 4.3.2 三元组表法
33
?(二 )三元组对象描述
public:
TTriTupleArray( );
TTriTupleArray( long mSize);
float& Get ( long i,long j);
void Set ( long i,long j,float x);
longGetRowsCols ( long &r,long &c);
longAddNew ( long i,long j,float x);
float Delete ( long i,long j);
int Trans1( TTriTupleArray &tu);
int Trans2( TTriTupleArray &tu);
} ;
§ 4.3.2 三元组表法
34
?(二 )三元组对象描述
?相应的初始化函数为：
TTriTupleArray::TTriTupleArray ( ):TLinearListSqu<TTriTuple>()
{
rows=0;
cols=0;
theZero=0;
}
§ 4.3.2 三元组表法
35
?(二 )三元组对象描述
TTriTupleArray,,TTriTupleArray (long mSize):
TLinearListSqu <TTriTuple> (mSize)
{
rows=0;
cols=0;
theZero=0;
}
§ 4.3.2 三元组表法
36
? Get(i,j)----返回下标为（ i,j）的元素的值的引用。
? Set(i,j,x)----将下标为（ i,j）的元素的值置为 x
? Trans( )----将三元组所代表的矩阵转置
§ 4.3.3 三元组表的操作
37
?为了方便地动态获取三元组表矩阵的最大行号和列号，特设立
GetRowsCols(long &r,long &c)，它的源代码为：
longTTriTupleArray::GetRowsCols( long &r,long &c)
{
long k;
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;
}
return k; //返回非零元素个数
}
§ 4.3.3 三元组表的操作
38
?当一个元素由零变为非零时，需要在三元组表中增加新元素，该工
作由下列 AddNew函数完成
longTTriTupleArray::AddNew ( long i,long j,float x)
{
long k,kk;
k=len-1;
while (k>=0)
{
if (i < room[k].row) k--;
else break;
}
§ 4.3.3 三元组表的操作
39
while (k>=0 && room[k].row==i)
{
if (j < room[k].col) k--;
else break;
}
if (k>=0 && i==room[k].row&& j==room[k].col )
{ room[k].val=x; return k; }
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++;
return k+1;
}
40
?下面是具体的 Get和 Set函数的实现：
float& TTriTupleArray::Get ( long i,long j)
{
long k;
k=0;
while (k<len)
{
if (room[k].row==i)
if (room[k].col==j) break;
k++;
}
if (k==len) return theZero;
return room[k].val;
}
41
void TTriTupleArray::Set ( long i,long j,float x)
{
long k;
k=0;
while (k<len)
{
if (room[k].row==i)
{
if (room[k].col==j) break;
}
k++;
}
42
if( k==len)
{
if (x!=theZero)
AddNew(i,j,x);
}
else
{
if (x!=theZero) room[k].val = x;
else Delete(i,j);
}
}
43
? 若矩阵是用二维数组表示的, 转置过程可描述如下：
int a[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 转置操作
44
? 如果矩阵是用三元组表表示的，可以利用 Get和 Set
for (i=0; i<m; i++)
for (j=0; j<n; j++)
b.Set(j,i,a.Get(I,j) );
§ 4.3.4 转置操作
45
? 直接实现转置 的讨论：
? 显然的做法是：
– 将每个元素的行号和列号分别互换；
– 对三元组表排序，使其中元素按行序（或列序）排列。
? 时间复杂度 O(n)+O(nlog(n))
? 要降低时间复杂度，一个显然的做法是免去排序操作
§ 4.3.4 转置操作
46
? 使在进行元素的行号和列号互换的过程中，顺便实现
行序（列序）排列
– 将 a的每个元素从三元组表中取出，交换它们的行号值与列号
值；
– 将所取出的三元组元素存入目标三元组表 b中适当位置，使三
元组表 b保持行序 /列序。
§ 4.3.4 转置操作
47
?【 例 4.4】,这里给出一个稀疏矩阵 A与它的三元组形式 a以及它们的转
置形式 B与其三元组形式 b
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
020010
000000
002000
000003
005000
A
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00000
20000
00205
00000
10000
00030
B
行号 列号 元素值
1 4 5
2 1 3
3 4 2
5 2 1
5 5 2
行号 列号 元素值
1 2 3
2 5 1
4 1 5
4 3 2
5 5 2
转置
三元组 (行序 ) 三元组 (行序 )
转置
48
? (一 ) 转置算法 (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 转置操作
49
?(一 ) 转置算法 (I)
int TTriTupleArray::Trans1 (TTriTupleArray &tu)
{
long pa,pb,col;
long mCols,mRows;
if (len<1) return 0;
tu.ResizeRoom(len);
GetRowsCols(mRows,mCols);
pb=0;
§ 4.3.4 转置操作
50
?(一 ) 转置算法 (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;
return len;
}
§ 4.3.4 转置操作
51
? (二 )转置算法 (II)
? 该算法可概括为, 顺序取，直接存,
– 即依次从 a中第 1、第 2,…… 位置取元素，交换它们的行列位
置后放置在 b中适当位置
– 该过程可描述为：
for (pa=1; pa<=非 0元素个数 ; pa++)
{
为 a的 pa元素确定它在 b中应放位置 pb;
将 a的 pa元素行列值交换后存入 b中 pb位置 ;
}
§ 4.3.4 转置操作
52
? (二 )转置算法 (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 转置操作
53
? (二 )转置算法 (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 转置操作
54
?(二 )转置算法 (II)
?完整算法程序
int TTriTupleArray::Trans2 (TTriTupleArray &tu)
{
long pa,pb,col;
long mCols,mRows;
if (len<1) return 0;
tu.ResizeRoom(len);
GetRowsCols(mRows,mCols);
long *cnum,*cpos;
cnum=new long[mCols+1];
cpos=new long[mCols+1];
§ 4.3.4 转置操作
55
?(二 )转置算法 (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 转置操作
56
for (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;
return len;
}
57
§ 4.4十字链表
? 稀疏矩阵的一种链式表示
? 一切具有正交关系的结构，都可用十字链表存
储
58
§ 4.4.1 存贮方式
(a)稀疏矩阵中每个非 0元素对应一个十字链结点，每个
结点的结构为
(b)每行 /列设一个表头结点（结构同元素结点），以
down/right链构成循环链表
(c)设一个总头结点（结构同元素结点），令总头结点和
各个列 /行头结点，用 val字段按列 /行序构成一个循环
单链表。
row col val
down right
59
§ 4.4.1 存贮方式
(d) 令总头结点的 row,col与 val 分别表示矩阵 （ 或非 0元
素 ） 的最大行号, 列号与非 0元素个数, 而 down/right
指向第 1列 /行的头结点 。 该总头结点可作为整个十字
链表的代表 。
(e)由于行与列的头结点分别使用 right域与 down域 (不同时
使用 ),故第 i列与第 i 行头结点可合用同一个头结点
（ 对所有可能的 i）, 以节省存贮空间 。
(f)有时设置一个一维数组 headNodes[ ], 使 headNodes[i]
指向 i行 /列的头结点 。
60
§ 4.4.1 存贮方式
?【 例 4.5】 设有一个如下形式的矩阵：
?它所对应的十字链表如 下页：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
02010
00402
01001
00500
A
61
4 5 7 2 1 1 2 2 2 2 2 0 0
2 1 1 1 3 5
2 1 1 2 1 1 2 4 1
2 1 1 3 1 2 3 3 4
2 1 1 2 2 1 4 4 2
图 - 十字链表示意图
??
?
?
?
?
?
??
?
?
?
?
?
?
02010
00402
01001
00500
A
62
§ 4.4.2 十字链表对象
template <class TElem>
struct TCrossNode
{
long row,col;
union {
TElem val;
TCrossNode *next;
};
TCrossNode *down,*right;
63
§ 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;
return oo;
};
}
64
§ 4.4.2 十字链表对象
?我们将十字链表定义为包含指向十字链表总头结点的指针的对象 。
template <class TElem>
class TCrossLink
{
TCrossNode<TElem> *head;
longrows,cols;
int theZero;
void ReleaseAll ( void);
TCrossNode<TElem> *Insert ( TCrossNode<TElem> *pNode,long i,
longj);
int Insert ( TElem& x,long i,long j);
int Delete( long i,long j);
65
§ 4.4.2 十字链表对象
public:
longlen;
TCrossLink( );
TCrossLink( long rows,long cols);
~TCrossLink( );
TCrossNode<TElem>* Init ( long rows,long cols);
TElem& Get (long i,long j);
TCrossNode<TElem>* GetNode ( long i,long j);
TCrossNode<TElem> * Set ( long i,long j,TElem& x);
TCrossNode<TElem>* TCrossLink::GetHead ( long k);
int Print( );
} ;
66
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
? 该函数生成一个具有 rows1行和 cols1列的空的十字链表。
template <class TElem>
TCrossNode<TElem>* TCrossLink<TElem>::Init (long rows1,long cols1)
{
TCrossNode<TElem> *p,*h;
long rc;
rc=rows1;
if (rc<cols1) rc=cols1;
图 - 空十字链表
0 2 0 0 0 0 0 0 … …
67
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
if (head!=NULL) ReleaseAll();
h= new TCrossNode<TElem>;
if (h==NULL) throw TExcepComm(3);
h->next = h;
h->row=rows1;
h->col=cols1;
68
§ 4.4.3 基本操作的实现
?(一 ) 初始化操作
for (long i=0; i<rc; i++)
{
p = new TCrossNode<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;
return h;
}
69
§ 4.4.3 基本操作的实现
?(二 )插入操作
?两个插入版本，一个是将存在的链结点插入，另一个是已知元素值
进行插入，它通过调用前者实现。
template <class TElem>
TCrossNode<TElem> *TCrossLink<TElem>::
Insert (TCrossNode<TElem> *pNode)
{
long i,j;
TCrossNode<TElem> *p,*p0;
i=pNode->row;
j=pNode->col;
p0 = GetHead(i); //得到行 i的头结点 。 然后在行 i上插入 pNode
if (p0==NULL) throw TExcepComm(1);
p=p0;
70
§ 4.4.3 基本操作的实现
?(二 )插入操作
while (p->right!=p0 && p->right->col<j) //寻找插入位置 p
p = p->right;
pNode->right = p->right; //在 p后插入 pNode
p->right = pNode;
p0 = GetHead(j); //得到列 j的头结点 。 然后在列 j上插入 pNode
if (p0==NULL) throw TExcepComm(1);
p=p0;
while (p->down!=p0 && p->down->row<i) //寻找插入位置 p
p = p->down;
pNode->down = p->down; //在 p后插入 pNode
p->down = pNode;
len++;
return head;
} ;
71
§ 4.4.3 基本操作的实现
?(二 )插入操作
template <class TElem>
TCrossNode<TElem> *Insert (TElem& x,long i,long j)
{
TCrossNode<TElem> *p;
p = new TCrossNode<TElem>;
if (p==NULL) throw TExcepComm(3);
p->row=i;
p->col=j;
p->val=x;
Insert(p);
return p;
}
72
§ 4.4.3 基本操作的实现
?(三 )删除操作
留做练习 。
73
§ 4.4.3 基本操作的实现
? (四 ) Get类操作
? Get类操作实现按数组方式访问十字链表, 即已知行号
和列号求出元素值 。
? 有两个版本
– 第一个是已知行号和列号求对应元素结点的指针
– 第二个是是已知行号和列号求对应元素的值 。
– 后者可在前者基础上实现 。
– 实现方法是搜索给定行 （ 或列 ） 对应的链表, 查找列号 （ 或
行号 ） 为给定列号 （ 或行号 ） 的结点 。
74
§ 4.4.3 基本操作的实现
?(四 ) Get类操作
template <class TElem>
TCrossNode<TElem>* TCrossLink<TElem>::GetNode (long i,long j)
{
TCrossNode<TElem> *p,*p0;
p0 = GetHead(i);
if (p0==NULL) return NULL;
p=p0;
while (p->right!=p0 && p->right->col<j)
p = p->right;
if (p->right->col==j) return p->right;
else return NULL;
}
75
§ 4.4.3 基本操作的实现
?(四 ) Get类操作
template <class TElem>
TElem& TCrossLink<TElem>::Get (long i,long j)
{
TCrossNode<TElem> *p;
p= GetNode(i,j);
if (p==NULL) return (TElem)theZero;
else return p->val;
}
76
§ 4.4.3 基本操作的实现
? (五 ) Set类操作
? Get类操作实现按数组方式给元素置值
– 即已知行号和列号，给对应的元素置值。
? 需要先按给定的行号和列号查找对应的元素
? 查找到时，直接赋值即可，但当赋 0值时应删除对应的
结点
? 查不到时，要调用 Insert新插入一个结点
77
§ 4.4.3 基本操作的实现
?(五 ) Set类操作
template <class TElem>
TCrossNode<TElem> * TCrossLink<TElem>::Set ( long i,long j,TElem& x)
{
TCrossNode<TElem> *p,*p0;
if (x==0)
{
p=Delete(i,j);
if (p!=NULL)
{delete p;
return head;
}
else throw TExcepComm(1);
}
78
§ 4.4.3 基本操作的实现
?(五 ) Set类操作
p0 = GetHead(i);
if (p0==NULL) throw TExcepComm(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 = new TCrossNode<TElem>;
p->row = i;
p->col = j;
p->val = x;
Insert(p);
}
return p;
}
79
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 设有两个 m× n矩阵 A与 B，它们均按十字链表存贮。
? 现考虑操作 A←A+B,即将 B加到 A 上，两矩阵相加，就
是对应元素相加,aij+bij。
? 该操作的实现：
for (i=1; i<=B.rows; i++)
{
for (j=1; j<=B.cols; j++)
A.Set(i,j,A.Get(I,j)+B.Get(i,j));
}
80
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 下面考虑不借助 Get和 Set进行加法。
? 我们可以采用逐行相加的方法，即逐次将 B的各行加到 A
上
for (i=1; i<=m; i++)
{
pHB=B.GetHead(i); //求 B中第 i行头结点
将 B的第 i行加到 A的第 i行上 ;
}
81
§ 4.4.3 基本操作的实现
? (六 )十字链表相加法
? 问题就转化成了如何, 将 B的第 i行加到 A的第 i行上,
? 该项操作的实现与多项式加法十分类似，其过程可描述
为：
pHA = A.GetHead(i); //求得 A的第 i行头结点
pA=pHA->right; //pA指向 A中 i行上当前待处理的结点
pB=pHB->right; //pB指向 B中 i行上当前待处理的结点
pA0=pHA;
pB0=pHB; //pA0与 pB0分别为 pA与 pB的前趋
82
§ 4.4.3 基本操作的实现
while (pB->right!=pHB) //处理 B的 i行上各结点
{
if (pA->col < pB→col)
{
pA0=pA;
pA=pA→right ; //pA后移一步
}
else
if (pA->col > pB→col)
{
从 pB复制一结点 p；
将 p插入到 A的 i行链表中 pA之前,即 pA0前；
将 p插入到 A的 pB→col 列链表中适当位置；
pB0=pB;
pB=pB->right;
?}
83
else //pB->col==pA->col
{
pA->val = pA->val + pB->val;
if (pA->val !=0 )
{
pA0=pA;
pA=pA→right ;
pB0=pB;
pB=pB→right ;
} //pA与 pB分别后移一步
else
{
将 pA从十字链表中摘除 ;
释放 pA;
pA=pA0->right; //令 pA指向被删结点的下一结点
pB=pB→right ; //pB后移一步
}
}
} //while }
84
习 题 4
? 4.1 分别证明 n维数组的按行与按列存贮的寻址公式,
? 4.2,设 4维数组的 4个下标的范围分别为 [-1,0],[1,2]，
[1,3],[-2,-1],请分别按行序和按列序列出各元素 。
? 4.3对上题, 分别计算元素 a-1,2,2-2 的按行存贮与按列存
贮的相对地址 （ 设每个元素占 2个单元 ）
? 4.4,写出 n维数组按列存贮的寻址公式的计算函数,
? 4.5 设 a与 b分别是 m× n与 n× m矩阵 （ 二维数组 ）, 它
们均按行序存贮在一维结构中, 请分别用两种方法写
出计算 a× b的程序 。 这两种方法是,① 采用二维数组
的寻址公式访问元素； ② 不采用寻址公式访问元素,
而直接推算要访问的元素的存贮位置 。
85
4.6,分别推导出上三角矩阵按行与按列存贮的寻址公式
4.7,设 a与 b是 n× n的对称矩阵, 采用下三角压缩存贮 （ 只存
贮下三角 ）, 请分别按下列两种要求写出计算 a× b 的程
序,① 利用下三角按行存贮的寻址公式访问元素； ② 不利
用寻址公式, 直接推出要访问的元素的存贮位置 。
4.8,设对称矩阵按行序存贮下三角 (存贮在一维结构中 ),请
写一个程序, 根据任一元素的存贮位置 （ 相对位置 ） 求出
它所对应的行号与列号 。
4.9 设 a与 b是两个用三元组表存贮 （ 连续结构 ） 的稀疏矩阵,
请写出将 b 加到 a上的程序 。
4.10 设 a与 b是两个用三元组表存贮 （ 连续结构 ） 的稀疏矩阵,
请写出 a× b的程序,
4.11,写一个将用十字链表存贮的稀疏矩阵转置的程序,
