《数据结构》课件第4章

第4章数组和矩阵4.1数组4.2特殊矩阵本章小结习题四实训4-1建立稀疏矩阵的十字链表

【教学目标】数组是比较熟悉的一种数据类型，几乎所有的高级程序设计语言都支持数组这种数据类型，各种数据结构的顺序存储结构都是用一维数组来描述的。实际上，数组本身也是一种数据结构，它可以看做是线性表的推广。4.1数组4.1.1数组的定义数组是由n(n≥1)个相同类型的数据元素a0,a1,…,ai,…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。因此，数组的定义类似于采用顺序存储结构的线性表。一维数组可以用下列形式表示：A[n]=(a0,a1,…,ai,…,an-1)其中，n为数组A中数据元素的个数，ai为数组A的第i+1个数据元素，i(0≤i≤n-1)叫做下标。如果把下标看做是数据元素在数组中的序号，则一维数组就是一个线性表，不过，数组中的下标是从0开始，而线性表中的元素排列序号是从1开始的。如果一维数组中的每个元素都是数据类型相同的行向量或列向量，则这样的一维数组就扩展成了二维数组，二维数组也就是矩阵。一个m行n列的二维数组A，可用图4.1所示的m × n阶矩阵表示。其中，aij为数组的第i行第j列元素，i为二维数组的行下标，j为二维数组的列下标。为描述方便，设数组行、列下标均从1开始，m为行下标的最大值，n为列下标的最大值。矩阵Am×n可以看成n个列向量的线性表A=(α1,α2,…,αj,…,αn)，其中每个数据元素αj是一个列向量形式的线性表，如图4.2所示。图4.1Am×n的二维数组

图4.2矩阵Am×n看成n个列向量的线性表同样，矩阵Am×n可以看成m个行向量的线性表B=(β1,β2,…,βi…,βm)，其中每个数据元素βi是一个行向量形式的线性表，如图4.3所示。图4.3矩阵Am×n看成m个行向量的线性表4.1.2数组的顺序表示和实现图4.4一维数组的顺序存储表示由于数组的数据元素存储在一块地址连续的内存单元中，因此，数组的存储方式一般采用顺序存储结构。对于一维数组A[n]，假设该数组的每一个元素占有一个存储单元，数组的起始地址为Loc(a[0])，则第i(0≤i≤n-1)个元素ai的存储地址为Loc(a[i])=Loc(a[0])+i，如图4.4所示。若数组A[n]中的每一个元素占用d个存储单元，则第i(0≤i≤n-1)个元素ai的存储地址为Loc(a[i])=Loc(a[0]) + i × d。对于一个m行n列的二维数组，必须先确定m × n个元素的排列顺序，然后才能根据不同的排列顺序确定每个元素在内存中的物理位置。数组的顺序存储结构有两种：一种是按行序存储，如高级语言中的BASIC、COBOL和PASCAL语言都是以行序为主；另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主。以行序为主的顺序存储是将数组的元素一行接一行地顺序存储到一块地址连续的存储空间中，即先存储第一行的每个元素，再存储第二行的每个元素，以此类推，每行的元素从左至右顺序存储。显然，二维数组A[m][n]以行序为主的存储序列为a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn以列为主的顺序存储则是将数组的元素一列接一列地顺序存储到一块地址连续的存储空间中，则以列为主的存储序列为a11,a21,…,am1，a12,a22,…,am2,…a1n,a2n,…,amn假设数组A[m][n]以行序为主顺序存储，且每个数据元素占d个存储单元，Loc(a11)为第一个元素a11在存储器中的地址，则数组中任一元素aij前面共有i-1行，每行n个元素，第i行中aij前面还有j-1个元素，所以aij在存储器中的地址是：Loc(a[i][j]) = Loc(a11)+((i-1) × n + (j-1)) × d1≤i≤m,1≤j≤n同样，假设数组A[m][n]以列序为主顺序存储，则aij在存储器中的地址是：Loc(a[i][j]) = Loc(a11)+((j-1) × m + (i-1)) × d1≤i≤m,1≤j≤n在C语言中，一维数组可定义为#defineMAXN /*数组的元素个数*／Elemtypea[MAXN];二维数组可定义为#defineMAXN1 /*数组的最大行数*／#defineMAXN2 /*数组的最大列数*／Elemtypea[MAXN1][MAXN2];通常，数组一旦被建立，则数组中的元素个数和元素之间的逻辑关系就不再发生变动，即它们的逻辑结构就固定下来了。因此，对数组不能进行插入和删除操作，一般只讨论下列两种运算：

(1)获得特定位置的元素值。

(2)修改特定位置的元素值。4.2特殊矩阵矩阵是很多科学与工程计算问题中研究的对象，在高级程序设计语言中一般用二维数组来表示矩阵，因此，矩阵的存储方式就可以采用二维数组的存储方式。即对于一个m行n列的矩阵可以用m × n个地址连续的存储单元来存储，但是，当一个矩阵的阶数很高(即m × n的值很大)，且矩阵中有许多相同的元素或者零元素时，如果仍用m × n个存储单元来存储每个元素，显然会浪费大量的存储空间。有时，为了节省存储空间，对这类矩阵进行压缩存储。所谓压缩存储，是指只存储矩阵中的值不相同的非零元素，对多个值相同的元素只分配一个存储单元，对值为零的元素不分配存储空间。4.2.1三角矩阵图4.5下三角矩阵A三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。对于一个n阶矩阵An×n来说，若当i < j时，有aij = 0，则称此矩阵为下三角矩阵(如图4.5所示)；若当i > j时，有aij = 0，则称此矩阵为上三角矩阵；若矩阵中的所有元素均满足aij = aji，则称此矩阵为对称矩阵。对于下三角矩阵的压缩存储，只存储下三角的非零元素，零元素则不存。如果按照“行序为主序”进行存储，得到的序列是a11,a21,a22,a31,a32,a33,…,an1,an2,…,ann。由于下三角矩阵的元素个数为n(n+1)/2，即所以可压缩存储到一个大小为n(n+1)/2的一维数组C中，如图4.6所示。

图4.5下三角矩阵A图4.6下三角矩阵的压缩形式下三角矩阵中元素aij(i > j)在一维数组A中的位置为：Loc［i,j］=Loc［1,1］+(前i-1行非零元素个数)+(第i行中aij前非零元素个数)其中：前i-1行非零元素个数 = 1 + 2 + 3 + 4 + … + (i-1) = i(i-1)/2，第i行中aij前非零元素个数 = j-1，所以有Loc［i,j］= Loc［1,1］+i(i-1)/2+j-1同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n + 1)/2的一维数组C中。其中元素aij(i<j)在数组C中的存储位置为Loc［i,j］=Loc［1,1］+j(j-1)/2+i-1对于对称矩阵，因其元素满足aij = aji，故可以为每一对相等的元素分配一个存储空间，即只存下三角(或上三角)矩阵，从而将n2个元素压缩到n(n + 1)/2个空间中。4.2.2稀疏矩阵图4.7稀疏矩阵在一个阶数很高的矩阵Am×n中，如果非零元素的个数k远远小于m×n时，则称矩阵Am×n为稀疏矩阵。至于非零元素少到多少才算稀疏，没有一个确切的定义。图4.7就是一个稀疏矩阵。对于稀疏矩阵，可以采用压缩存储的方法，只存储其中的非零元素。图4.7稀疏矩阵由于稀疏矩阵中非零元素的分布没有任何规律，因此在存储非零元素值的同时还必须存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素就需要用一个三元组(i，j，aij)唯一确定，并将每个三元组按照行号的递增顺序(同一行按列号的递增顺序)排列，构成一个稀疏矩阵的三元组线性表。线性表中的每一个数据元素对应着稀疏矩阵的一个非零元素。图4.7所示的稀疏矩阵用三元组线性表可表示为((1，1，5)，(1，4，1)，(2，3，2)，(3，1，8)，(4，5，7)，(5，4，4))稀疏矩阵的三元组线性表的存储方法主要有两种：稀疏矩阵的顺序存储和稀疏矩阵的链式存储。

1.稀疏矩阵的顺序存储稀疏矩阵的顺序存储就是对其相应的三元组线性表进行顺序存储。可用一维数组表示三元组表，称为三元组数组。一般来说，具有t个非零元素的稀疏矩阵可以用t+1个三元组表示，其中用第一个三元组表示稀疏矩阵的行数、列数及非零元素的个数。图4.8是图4.7的稀疏矩阵所对应的三元组数组。图4.8稀疏矩阵的三元组表示如果在一个1000 × 1000稀疏矩阵中只有1000个非零元素，则该矩阵共需存储1001个三元组，假如每个三元组需占用3个存储单元，则共计需占用3003个存储单元，显然比采用非压缩存储所需占用1000 × 1000个存储单元要少得多。三元组线性表的结点用C语言定义如下：#defineElemtypeint /*此处假定数据元素为int型*/#defineMAXSIZE100

/*MAXSIZE为非零元素的最大个数*/typedefstructxnode{inti,j; /*i和j分别表示非零元素的行下标和列下标*/Elemtypev; /*非零元素的值*/}XNode;顺序存储的稀疏矩阵用C语言可定义如下:typedefstructsmatrix /*定义一个稀疏矩阵*/{introws,cols; /*稀疏矩阵的行数和列数*/intterms; /*稀疏矩阵非零元素个数*/XNodedata[MAXSIZE]; /*顺序存储的三元组表*/}SMatrix;对稀疏矩阵的基本操作主要有：建立稀疏矩阵、查找稀疏矩阵元素、求稀疏矩阵的转置矩阵、两个稀疏矩阵相加、两个稀疏矩阵相乘等。下面讨论在顺序存储方式下求稀疏矩阵的转置矩阵的算法。例4.1

求稀疏矩阵的转置矩阵。算法分析：转置是矩阵中最简单的一种运算。对于一个m × n的矩阵A，它的转置矩阵B是一个n × m的，且B[i][j]=A[j][i],0≤i＜n,0≤j＜m。如果用三元组表来表示稀疏矩阵，那么将A转置为B的过程如下：将表示矩阵中非零元素的三元组(i,j,aij)的行号和列号对调，可得到转置后的非零元素(j,iaij),再将(j,iaij)插入到转置后的三元组数组的适当位置上，即可完成转置运算。将A转置为B的方法有两种，一是按照A的列序进行转置，二是按照A的行序进行转置。下面讨论按列序进行转置的具体步骤。设矩阵A的三元组数组为a.data，转置后的矩阵B的三元组数组为b.data。首先在a.data中查找列号为0的所有元素，将它们作为b.data中行号为0的元素，依次插入b.data中；然后在a.data中查找列号为1的所有元素，把它们作为b.data中行号为1的元素，依次插入b.data中……下面是用C语言编写的求A的转置矩阵的算法：voidtranspose(SMatrixa){

SMatrixb;

/*b为a的转置*/

intm,n=0,col,i;

b.rows=a.cols;

b.cols=a.rows;

b.terms=a.terms;

if(b.terms>0)

{for(col=0;col<a.cols;col++) /*按列号扫描*/for(m=0;m<a.terms;m++) /*对三元组扫描*/if(a.data[m].j==col) /*进行转置*/{b.data[n].j=a.data[m].i;b.data[n].i=a.data[m].j;

b.data[n].v=a.data[m].v;

n++;}}printf("\nThesmatrixafterturn:\n");for(i=0;i<a.terms;i++)/*输出转置后的三元组结果*/printf("%5d%5d%5d\n",b.data[i].i,b.data[i].j,b.data[i].v);}main(){

inti;SMatrixa;/*输入稀疏矩阵的行、列数及非零的个数*/

printf("\ninputrowscolsterms:\n");scanf("%d%d%d",&a.rows,&a.cols,&a.terms);/*输入转置前的稀疏矩阵的三元组*/printf("\ninputsmatrixbeforeturn:\n");for(i=0;i<a.terms;i++)

scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v);

transpose(a);

/*调用转置算法*/}该算法的执行时间主要用在二重循环上，算法的时间复杂度为O(a.cols × a.terms)，如果不采用压缩存储的方法，则m × n阶矩阵的转置算法的时间复杂度为O(m × n)。由于一般的稀疏矩阵中非零元个数a.terms远大于行数m，故采用压缩存储进行转置运算，虽然节省了存储单元，但增大了时间复杂度，故此算法仅适用于非零元素个数远远小于m × n的情形。

2.稀疏矩阵的链式存储与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算时间比经典算法还少。但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A = A + B，将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。对稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储，它是一种既带行指针又带列指针的链接存储结构。链表中的每一个结点表示一个非零元素的三元组，稀疏矩阵中同一列的所有非零元素通过down指针链接成一个列链表，同一行中的所有非零元素通过right指针链接成一个行链表。因此，对稀疏矩阵中的每一个非零元素来说，它既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，即每个结点都处于所在行的单链表和所在列的单链表的交点处，整个稀疏矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row，col，value)以外，还要有以下两个链域：

right：用于链接同一行中的下一个非零元素；

down：用于链接同一列中的下一个非零元素。十字链表的结点结构如图4.9所示。图4.9十字链表中结点的结构示意结点类型用C语言定义如下：typedefstructlinkXNode /*定义十字链表的一个结点*/{

introw;

intcol;

structlinkXNode*down;

structlinkXNode*right;

Elemtypevalue;}LinkXNode;为了便于访问十字链表，还要设置两个指针型数组，一个用来存放每个行链表的表头指针，另一个用来存放每个列链表的表头指针，这样对稀疏矩阵的访问，既可在行链表上进行，也可以在列链表上进行。例4.2对于稀疏矩阵M，它的十字链表存储结构可用图4.10来表示。图4.10稀疏矩阵的十字链表存储结构本章小结一维数组也是线性表，而多维数组是一维数组的推广，矩阵又是一个二维数组,它是一个比较复杂的线性表。二维数组的存储分为行序为主和列序为主两种。对数组不能进行插入和删除操作，其操作主要是查找和修改。对特殊矩阵一般采用压缩存储，即只存储矩阵中的值不相同的非零元素，对多个值相同的元素只分配一个存储单元，对值为零的元素不分配存储空间。对于一个n阶矩阵A来说，若当i＜j时，有aij=0，则称其为下三角矩阵；若当i＞j时，有aij=0，则称其为上三角矩阵；若矩阵中的所有元素均满足aij=aji，则称其为对称矩阵。稀疏矩阵是非零元素个数特别少的一种矩阵，为了节省存储空间，一般用一个三元组表来表示稀疏矩阵。对稀疏矩阵的存储也就是对三元组表的存储，存储方法主要有顺序存储和链式存储，链式存储的三元组表就是一个十字链表。习题四一、填空题

1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是

。

2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是

。

二、单选题

1.常对数组进行的两种基本操作是

。

A.建立与删除 B.索引和修改

C.查找和修改 D.查找与索引

2.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，存放该数组至少需要的单元数是。

A. 80 B. 100

C. 240

D. 270

3.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为

。

A. SA+141 B. SA+144

C. SA+222

D. SA+225

4.稀疏矩阵一般的压缩存储方法有两种，即

。

A.二维数组和三维数组B.三元组表和散列

C.三元组表和十字链表D.散列和十字链表

三、算法描述题假设稀疏矩阵Am×n和Bm×n都采用三元组表表示，编写一个函数计算C=A+B，要求C也采用三元组表表示。实训4-1建立稀疏矩阵的十字链表【实训目的】

1.加深对矩阵压缩存储知识的理解。

2.掌握稀疏矩阵十字链表的应用。【实训内容】采用十字链表存储结构，创建并输出稀疏矩阵。【实训要求】

1.要求矩阵大小、非零元素个数、非零元素从键盘录入。

2.分别按行序为主和列序为主形式输出。【算法分析】

1.按输入的矩阵行、列数，生成行、列头指针向量，并初始化，使各行、列链表为空链表。

2.将t个非零元素依次插入十字链表：

(1)输入行i、列号j及值e，如行、列号不合法则要求重新输入。

(2)从第i行表头元素开始，通过比对列号，查找正确插入位置，将新元素插入行链表。

(3)从第j列表头元素开始，通过比对行号，查找正确插入位置，将新元素插入列链表。

(4)重复步骤(1)，直到所有t个非零元素全部插入。

3.以行序为主，输出各行链表数据。

4.以列序为主，输出各列链表数据。

5.建立十字链表算法的时间复杂度为O(t×s)，s=max(m，n)。【程序清单】#defineElemtypeint#include<stdio.h>typedefstructOLNode{

introw,col; /*非零元素的行和列下标*/

Elemtypevalue;

structOLNode*right,*down; /*非零元素所在行表、列表的后继链域*/}OLNode,*OLink;typedefstruct{

OLink*row_head,*col_head;

/*行、列链表的头指针向量*/

intm,n,len;

/*稀疏矩阵的行数、列数、非零元素的个数*/}CrossList;CreateCrossList(CrossList*M)/*采用十字链表存储结构，创建稀疏矩阵M*/{

intm,n,t,i,j,e;OLNode*p,*q;if(M!=NULL)free(M);printf("输入M的行数,列数和非零元素的个数:\n");scanf("%d%d%d",&m,&n,&t);

M->m=m;M->n=n;M->len=t;

if(!(M->row_head=(OLink*)malloc((m+1)*sizeof(OLink))))

exit(-1); /*生成行链表头指针向量*/if(!(M->col_head=(OLink*)malloc((n+1)*sizeof(OLink))))exit(-1); /*生成列链表头指针向量*//*初始化行、列头指针向量，各行、列链表为空链表*/for(i=0;i<M->m;i++)

M->row_head[i]=NULL;for(i=0;i<M->n;i++)

M->col_head[i]=NULL;/*建立十字链表*/for(t=1;t<=M->len;t++){printf("输入非零元素行号、列号、值\n");scanf(“%d%d%d”,&i,&j,&e); /*输入非零元素行号、列号、值*/if(i<0||i>=M->m||j<0||j>=M->n){printf("行列号不合法，请重新输入！\n");t--;continue;}

if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(-1);

/*生成结点*/p->row=i;p->col=j;p->value=e;p->right=NULL;p->down=NULL;/*新元素插入行链表*/if(M->row_head[i]==NULL)/*第i行原来没有非零元素*/

M->row_head[i]=p;else{

q=M->row_head[i];

/*从头开始寻找行表中的插入位置*/

/*该行中新元素列号最小，插入在最前面*/

if(q->col>j){

p->right=q;

q=p;

}

else{/*查找插入位置q，插入在q之后*/while(q->right&&q->right->col<j)

q=q->right;p->right=q->right; /*完成插入*/q->right=p;}}/*新元素插入列链表*/if(M->col_h