武汉软件工程职业学院《数据结构讲义》第07讲 数组 - 图文

第七讲 数组

1．掌握数组的基本概念及数组的顺序存储结构。 2.了解并熟悉特殊矩阵的压缩存储。 3．掌握稀疏矩阵的三元存储。

? 教学重点：

1、 数组的概念及顺序存储结构。 2、 稀疏矩阵的转置矩阵。 ? 教学难点： 稀疏矩阵的转置矩阵 ? 授课内容

2.6 数组

2.6.1 数组的基本概念

数组是一种常用对数据结构，几乎所有的程序设计语言都把数组类型设定为固有类型。计算机系统的内存是连续的空间，为了方便的存取处理大量的相关性数据，我们定义一种“连续的存储区域”，并使用一个名称指向此区域的起点，通过名称及偏移的方式，可以很容易的存取到该区域内的数据，此即为数组。

数组 是由下标（index）和值（value）组成的序对（indexvalue pairs）集合。简单地讲，数组就是按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。我们经常使用数组来存放一连串数据类型相同的数据。因此，数组具有两个特性是：

1. 数组中的元素间的地址是连续的。 2. 数组中所有元素的数据类型是相同的。

数组的类型有一维数组A[10]、二维数组A[5][6]、三维数组A[3][5][5]、多维数组等。 数组元素 在数组中，对于每组有定义的下标，都存在一个与其相对应的值，这个值通常称为数组元素。

二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。在c语言中，其被定义为：

ELEMTP arrayname[row][col]；

在二维数组中，每个元素都受到行关系和列关系的约束，例如有一个而外数组A[m][n]，对于第i行第j列的元素A[i][j]，A[i][j+1]是该元素在行关系中的直接后继元素；而A[i]+1[j]是该元素在列关系中的直接后继元素。所以，可以把二维数组看成是一个一维数组，它有row个元素，每个数据元素又是一个col个数据元素的一维数组。

对数组一般讨论下面两种运算：

给定一组有定义的下标，存取相应的数据元素；

给定一组有定义的下标，修改相应数据元素（或其中的某个数据项）的值。

2.6.2 数组的顺序存储结构

数组是一顺序存储方式在计算机中的，而随机存取是顺序存储结构的主要特征。大部分高级语言采用以行序为主的存储方式，如图2-6-1（a）所示，（如PASCAL 、C等）；但在有的语言（如FORTRAN）中采用的是以列序为主的存储方式，如图2-6-1（b）所示。

在C语言中，数组中任一元素A[i][j]的存储位置可用下列公式计算：

LOC（A[i][j]）=LOC（A[0][0]）+（i*col+j）*L其中，LOC（A[0][0]）为数组的起始位置，L每个数据元素所占存储单元个数。

由于在定义数组时，LOC（A[0][0]）、L和col是已知的，因此可以根据上式计算出任一元素的存储地址，实现随机存取。

2.6.3 特殊矩阵的压缩存储

矩阵在科学与工程计算机中有广泛的应用。在用高级语言编程中，通常用二维数组来表示矩阵。这样，利用上面的地址计算公式可以快速访问矩阵中的每个元素。然而，实际应用中会遇到一些特殊的矩阵，所谓特殊矩阵，是指矩阵中值相同的元素或着零元素的部分有一定的规律。例如，对称矩阵、三角矩阵和三对角矩阵都是特殊矩阵。

若一个n阶矩阵A中的元素满足：Aij=Aij（1≤ i≤ n ，1≤ j ≤ n）则称A为对矩阵；当一个方阵的主对角线以上或以上的所有元素皆为零时，该矩阵为三角矩阵；除了主

对角线上和直接在主对角线上下方的对角线的元素外，其他所有元素皆为零的矩阵称为三角矩阵。图2-6-2是两种特殊矩阵的形式。

为了节省存储空间，可以对这些矩阵进行压缩存储。所谓压缩存储就是为多个值相同的元素只分配给一个存储空间，对零元素不分配存储空间。由于特殊矩阵中非零元素的分布有明显的规律，因此我们可将其压缩存储到一个一维数组中，并找到每个非零元素在一维数组中的对应关系。

2.6.4 稀疏矩阵的三元组存储

当一个m×n的矩阵A中有k个非零元素，若k<

例如，式（２.６.１）所示的矩阵Ｍ和它的转置矩阵Ｎ，在３０个元素中只有７个非零元素，显然是一个稀疏矩阵。

5 0 0 12 0 0 5 0 8 0 0 0 0 16 0 0 0 0 0 0 0 0 M= 8 0 11 0 27 0 N= 0 16 11 0 4 0 0 0 0 0 0 12 0 0 0 0 0 0 4 0 0 0 0 0 27 0 0 0 0 0 0 0 按照压缩存储概念，只需存储稀疏矩阵的非零元素。但是，为了实现矩阵的各种运算，除了存储非零元素外，还必须同时记下它所在的行和列。这样，一个三元组（ｉ,ｊ,Ａij）便唯一的确定了矩阵的一个非零元素，其中ｉ、ｊ分别表示非零元素的行号和列号，Ａij表示非零元素值。

下列７个三元组表示了式（２.６.１）中的矩阵Ｍ的７个非零元素：

（１,１,５）（１,４,１２）（２,３,１６）（３,１,８）（３,３,１１）（３,５,

２７）（５,３,４）

1、 三元组顺序表

假设以顺序存储结构来表示三元组表（triple table）,则可得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。

其结构描述如下： Typedef struct{ int i,j; ELEMTP v; }TripleTp ; Typedef struct{

TripleTp elem[MAXSIZE]; int m,n,t;

}SpmaTp; 在此，elem域中表示非零元素的三元组是按以行为主的顺序排列的。假设a和b是SpMatTp型的变量，分别表示稀疏矩阵Ｍ和Ｎ，则图２-６-４表示了稀疏矩阵Ｍ和Ｎ中elem域的排列情况。显然，在矩阵足够稀疏情况下，这种表示法，对存储空间的需求量比通常的方法少得多。

２.稀疏矩阵的转置运算

矩阵的转置运算就是变换元素的位置，即把位于（ｉ,ｊ）的元素换到（ｊ,ｉ）位置上。对于一个m×n的矩阵Ｍ，它的转置矩阵是一个ｎ×ｍ的矩阵Ｎ，且Ｎ[ｉ][ｊ]＝Ｍ[ｉ][ｊ]，其中，１≤ｉ≤ｎ，１≤ｊ≤m。例如，式（２.６.１）中的矩阵Ｎ就是矩阵Ｍ的转置矩阵。矩阵Ｎ也是一个稀疏矩阵，其非零元素的排列情况如图２-６-４(b）所示。在三元组表的存储形式下，求稀疏Ｍ的转置矩阵Ｎ，实际上就是有图２-６-４（ａ）求的图２-６-４（b）。

图2-6-4 表示矩阵M和N的elem域 i j v i j v i j v 1 1 5 1 1 5 1 1 5

1 3 8 4 4 15 1 4 12

3 2 16 3 2 16 2 3 16

3 3 11 1 3 8 3 1 8

3 3 5 3 5 3 11 27 4 3 4 5 5 1 3 4 12 27 3 5 3 3 3 5 11 27 4 （a）a．elem （b）b.elem 图2-6-5 b’.elem 可以采用下列的两种方法实现 (1) 矩阵M的列序进行转置

这种方法需要对a.elem进行n次扫描（n为M的列数）才能完成。

具体地说，第一次扫描把a.elem中所有j值等于1（即列号为1）所在的三元组（即对应N中第一行的非零元）按序存b.elem中；第二次扫描把a. elem中所有j值等于2（即列号为2）所在的三元组按序存入b.elem中；依次类推。

具体算法描述如下：

void TransMat(SpMatTp *a, SpMatTp *b) { b->m=a->n;b->n=a->m;b->t=a->t; if(a->t!=0){ q=0;

for(col=l;col<=a->n;col++) for (p=0;pt;p++)

if (a->elem[p].j= =col){

b->elem[q].i=a->elem [p].j; b->elem[q].j=a->elem [p].i;

b->elem[q].v=a->elem [p].v;

q ++; } }

分析这个算法

除少数附加空间，例如p,q,和col外，它需要的存储量仅为两个三元组表a、b所需要的空间。因此，当

非零元素个数t

(2)按照a.elem中三元组的次序进行转置 要实现对a.elem扫描一次就能得到b.elem，必须每扫描一个元素就直接将它放到b.elem中应有的位置上。

因此，首先要知道a.elem中的元素在b.elem中的存储位置。这就要预先确定矩阵M中每一列（即N中每一行）的第一个非零元素在b.elem中应有的位置。为此，需要设置两个数组num[1..n]和pot[1..n]，分别存放在矩阵M 中每一列的非零元素个数和每一列的第1个非零元素在b.elem中的位置，即

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

Pot[col]的初值表示M中第col列的第1个非零在b.elem中的位置。显然有： pot[1]=0；

pot[col]=pot[col-1]+num[col-1] （2<=col<=n)

对于式（2.6.1）中的矩阵M ，其num和pot的值如表2-6-1所示。

col 1 2 3 4 5 6

num[col] 2 0 3 1 1 0

pot[col] 0 2 2 5 6 7

表2-6-1式(2.6.1)中的矩阵M的num和pot值 算法2.11

Void FastTran(SpMatTp *a, SpMatTp *b)

{ b->m=a->n;b->n=a->m;b->t=a->t; if(a->t ！=0){

for(col=1;col<=a->n;col++) num[col]=0; for(k=0;kt;k++) num[a->elem[k].j]++; pot[1]=0;

for(col=2;col<=a->n;col++)

pot[col]=pot[col-1]+num[col-1]; for(p=0;pt;p++){

col=a->elem[p].j;q=pot[col]; b->elem[q].i=a->elem[p].j; b->elem[q].j=a->elem[p].i; b->elem[q].v=a->elem[p].v; pot[col]++; 算法分析

此算法比前一个算法多用了两个辅助数据。但从时间上看，算法中有4个并列的循环语句，它们分别执行n,t,n-1和t次，因此算法的执行时间为O（n+1）。当t和m×n等数量级时，该算法的执行时间为O（m×n），但是在t<

3.稀疏矩阵的十字链表存储

当矩阵非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构。例如，我们要作运算

A=A+B，即将矩阵B加到矩阵A上，则会产生大量的数据元素的移动。此时，采用链表存储结构更为恰当。下面介绍十字链表的存储方法。

在十字连表中，每个非零元素可用含有五个域的结点表示，其中col,row和val三个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个单链表，同一列的非零元通过down域链接成一个单链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个链表构成一个十子交叉的链表，故称这样的存储结构为十子链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。例如，对于如式（2.6.1）所示的5*6阶稀疏距阵M 的十字链表如图2-6-6所示。

(2)建立稀疏矩阵的十字链表 十字链表的结构描述如下：

#define MAXR 100/*稀疏矩阵可能的最大行数*/ #define MAZC 100 /*稀疏矩阵可能的最大行数*/ typedef struct OLNode{

int col, row; /*该非零元的行、列下标*/ ELMTP val; /*该非零元的值*/

struct OLnode *right,*down; /*该非零元所在行、列表的后继链域*/ }OLNode ； typedef struct{

OLnode *rhead[MAXR+1],*chead[MAXC+1];/*行、列链表头指针向量*/ int mu ,nu,tu ; {CrossList;

建立稀疏矩阵的十字 链表的算法如下； 算法2.12

Void creat _LinkMat(CrossList *M ) /*建立稀疏矩阵M 的十字链表*/

{scanf(&m,&n,&t);/*输入矩阵的行列数、列数和非零元个数*/ M ->mu=m; M ->nu=n; M ->tu =t;

for(k=0;k<=m;k++) M->rhead[k]=NULL; for(k=0;k<=n;k++) M->chead[k]=NULL;

for(scanf(&i,&j,&v);i!=0;scanf(&I,&j,&v)){ p=(OLNode * ) malloc (sizeof(OLNode)); p->row=i;p->col=j;p->val=v; p->right=p->down = NULL

if(M - > rhead[i] = = NULL) M - > rhead[i] = p; else{ / * 寻找行表中的插入位置 * /

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

if(M->chead[j]==NULL) M->chead[j]=p; else{

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

对于m行n列且有t个非零元的稀疏矩阵，算法的执行时间为O（t×s），其实s=MAX{m，n}，这是因为每建立一个非零元素的结点时都要寻找它在行表和列表中的插入位置，此算法对非零元输入的先后次序没任何要求。

本文来源：https://www.bwwdw.com/article/1so5.html