ds05

数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表

5.1 数组的定义和特点

( )( )( )( )a00a01......a0,n1( )( )a10a11......a1,n1( )...............( )am1,0am1,1......am1,n1–数组特点

•数组结构固定

•数据元素同构

Amn–数组运算（基本操作）

•给定一组下标，存取相应的数据元素•给定一组下标，修改数据元素的值

2

( )–定义

抽象数据类型数组

5.2 数组的顺序存储结构按列序为主序存放按行序为主序存放•次序约定–以行序为主序–以列序为主序a00 a01……..a0,n-1a00 a01 …….. a0,n-1•类C表示和实现P93a10 a11 ……..a1,n-1a10 a11 …….. a1,n-1………………….………………….am-1,0am-1,1……..am-1,n-1am-1,0 am1 …….. am-1,n-1Loc(aij)=Loc(a)+(j*m+i)*L00Loc( aij)=Loc(a00)+(i*n+j)*L0011n-1m-1mnm*n-1m*n-1a00a1001…….am-1,00,n-1a01 10 a11…….. am-1,1 1,n-1 ……….a0,n-1 m-1,0 a1,n-1m-1,1…….. am-1,n-135.3 矩阵的压缩存储

•对称矩阵

a11 a12….… ….. a1n

a21a22…….. ……. a2n

………………….

an1an2…….. ann

按行序为主序：

a11a21a22a31a32…...an1…...ann

k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1

存放位置

i(i1)/2j1，ijkj(j1)/2i1,ij下三角阵上三角阵

4

•三角矩阵

a11 0 0…….. 0

a21 a22

0…….. 0

…………………. 0

an1 an2 an3…….. ann

按行序为主序：a11a21a22a31a32… aij

... an1 ...ann

k=0 1 2 3 4 i(i-1)/2+(j-1) n(n-1)/2 n(n+1)/2-1 i(i-1)

Loc(aij)=Loc(a11)+[ +(j-1)]*L2

5

•对角矩阵

a00a01 0 …………… . 0a10 a11a120…………… 00a21 a22a230……… 0……………………………0

0… an-2,n-3 an-2,n-2an-2,n-1 0

k与i，j转换？k=3i-1+j-(i-1)=2i+j ;i=(k+1)/3j=k-2i=…

0

0……… …an-1,n-2 an-1,n-1

按行序为主序：

a00a01a10a11a12…...aij …...an-1,n-2an-1,n-1k=0 1 2 3 4 2i+j 3n-4 3n-3 Loc(aij)=Loc(a00)+(2i +j)*L

6

•稀疏矩阵

–定义：非零元少，且分布没有规律的矩阵，稀疏因子–压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值

0012900003000M002400180015007000000140000000000670M由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24),

(5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数（6,7）唯一确定

7

•稀疏矩阵的压缩存储方法–顺序存储结构01290#define M 20

0000•三元组表

typedef structM3000{ int i,j;

00240行列下标

非零元值

ElemType e;01800}Triple;

15007i j eTriple ma[M];06

7 8typedef struct {

1

1 2 12 Triple data[M+1];int mu, nu, tu;21 3 9 } TSMatrix;

33 1 -3 43 6 14 54 3 24 65 2 18 ma[0].i,ma[0].j,ma[0].e分别存放76 1 15 矩阵行列维数和非零元个数8

6 4 -7 三元组表所需存储单元个数为3(t+1)ma

其中t为非零元个数

000000014000000000067•带辅助行向量的二元组表（修改的行逻辑链接顺序表）

增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元个数(i2)列下标和NRA[0]不用或NRAj e非零元值存矩阵行数061780122 12 13矩阵列数和333 9 2非零元个数451 -3 3566 14 4673 24 501290002 18 6000000二元组表需存储单元M3000014个数为2(t+1)+m+11 15 700240004 -7 80180000ma

150070000000067•伪地址表示法

00M3001590000024000伪地址：本元素在矩阵中（包括零元素再内）

按行优先顺序的相对位置

伪地址

addr e非零元值0

6

7

矩阵行列维数

12 12 2

3 9 000015 -3 00003420 14 001400000524 24 00006

30 18 伪地址表示法需存储单元个数70007

36 15 为2(t+1)

678

39 -7 ma

10

1218–求转置矩阵

问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析

一般矩阵转置算法：

for(col=0;colfor(row=0;rown[col][row]=m[row][col];T(n)=O(mn)

11

0012900003000M002400180015007i j v010000001400000000006700129T0000012031500018000240000007000000140000000076i j v0067 876 8

mb

1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 ma2345678?3456786 4 -7 6 3 14 解决思路：只要做到

将矩阵行、列维数互换

将每个三元组中的i和j相互调换

重排三元组次序，使mb中元素以T的行(M的列)为主序

方法一：按M的列序转置

即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序

算法5.1描述：

13

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){ // 算法5.1

// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.mu = M.nu; T.nu = M.mu; T.tu = M.tu;if (T.tu) {q = 1;

for (col=1; col<=M.nu; ++col)for (p=1; p<=M.tu; ++p)if (M.data[p].j == col) {T.data[q].i=M.data[p].j;T.data[q].j =M.data[p].i;

T.data[q].e =M.data[p].e; ++q; }

算法分析：T(n)=O(M的列数n非零元个数t)}2T(n)O(mn)若t 与mn同数量级，则return OK;

} // TransposeSMatrix

i j e0

67 8p1

1 2 12 pp21 3 9 pp33 1 -3 pp4

3 6 14 pp54 3 24 pp65 2 18 pp76 1 15 pp8

6 4 -7 mapcol=1

col=2

i j e0

7 68

q1

1 3 -3 q2q1 6 15 32 1 12 q4

2 5 18 q53 1 9 63 4 24 74 6 -7 8

6 3 14 mb方法二：快速转置

即按ma中三元组次序转置，转置结果放入b中恰当位置

此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组

num[col]：表示矩阵M中第col列中非零元个数

cpot[col]：指示M中第col列第一个非零元在mb中位置显然有：cpot[1]=1;

cpot[col]=cpot[col-1]+num[col-1]; (2col ma[0].j)

0012900003000M002400180015007000000140000000000670colnum[col]cpot[col]

1223

32

417

508

618

709

21

5

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {

// 算法5.2 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.mu = M.nu; T.nu = M.mu; T.tu = M.tu;if (T.tu) {

for (col=1; col<=M.nu; ++col) num[col] = 0;

for (t=1; t<=M.tu; ++t) // 求M 中每一列所含非零元的个数++num[M.data[t].j];cpot[1] = 1;

// 求M 中每一列的第一个非零元在b.data 中的序号for (col=2; col<=M.nu; ++col)

cpot[col] = cpot[col-1]+num[col-1];for (p=1; p<=M.tu; ++p) {

col = M.data[p].j; q = cpot[col];

T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i;T.data[q].e =M.data[p].e; ++cpot[col]; } // for

算法分析：T(n)=O(M的列数n+非零元个数t)} // if

若t 与mn同数量级，则T(n)=O(mn)return OK;

} // FastTransposeSMatrix

colnum[col]cpot[col]

12123

22

3

41

50

6189

709

2567

345

78

i j e0

i j e0123467867 87 68

pppppppp1231 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 1 3 -3 1 6 15 2 1 12 456782 5 18 53 1 9 3 4 24 4 6 -7 6 3 14 5 2 18 6 1 15 6 4 -7 mamb–链式存储结构

•带行指针向量的单链表表示

每行的非零元用一个单链表存放

设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义typedef struct Node{ int col;

5 7^1 3int val;

3 -1^struct Node *link;

2 -2^1 -1}Node;

typedef struct Node *TD;

003010A1200000000700000020^4 2^需存储单元个数为3t+m

–十字链表

设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义

30typedef struct OLNode

jei{ int i, j, e;05Adownright00struct node *down, *right;

} OLNode, *OLink;80040043typedef struct {

OLink *rhead, *chead;int mu, nu, tu;} CrossList;

113^2^^252^34^418^^Status CreateSMatrix_OL (CrossList &M) { // 算法5.4// 创建稀疏矩阵M。采用十字链表存储表示。if (M) free(M);

scanf(&m, &n, &t ); // 输入M的行数、列数和非零元个数M.mu=m; M.nu=n; M.tu=t;

if (!(M.rhead = (OLink *)malloc((m+1)*sizeof(OLink)))) exit(OVERFLOW);if (!(M.chead = (OLink *)malloc((n+1)*sizeof(OLink)))) exit(OVERFLOW);

for(int a=1;a<=m;a++) M.rhead[a]=NULL;// 初始化行列头指针向量；各行列链表为空链表for(int b=1;b<=n;b++) M.chead[b]=NULL;

for ( int c=1; c<=t; c++) { // 按任意次序输入非零元

scanf(&i,&j,&e); if (!(p = (OLNode *)malloc(sizeof(OLNode)))) exit(OVERFLOW); p->i=i; p->j=j; p->e=e; p->down=NULL; p->right=NULL; // 新结点if (M.rhead[i] == NULL || M.rhead[i]->j > j) {p->right = M.rhead[i]; M.rhead[i]= p; } else { // 寻查在行表中的插入位置

for (q=M.rhead[i]; (q->right) && (q->right->jright);p->right = q->right; q ->right = p; } // 完成行插入

if (M.chead[j] == NULL || M.chead[j]->i > i) {p->down = M.chead[j]; M.chead[j]= p; } else { // 寻查在列表中的插入位置

for ( q=M.chead[j]; (q->down) && q->down->i down );p->down = q->down; q->down = p;

算法分析：T(n)=o(ts)} // 完成列插入

} // for其中：t——非零元个数return OK;

} // CreateSMatrix_OLs= max(m,n)

m=4,n=31,1,32,2,52,3,44,1,82,1,7113^72^252^3^21^^^4^418^^