数据结构（10）— 数组、稀疏矩阵
(mi6236)
一、数组
数组是具有相同类型的变量，其中各个元素共用一个数组名，但是有不同的下标来访问。对于二维数组来说，给定维数和下标，如何得到数组元素存储位置？设每个数组占用1个内存单元，则二维数组Amn按行优先顺序(下标从1开始)，aij的地址为：LOC(aij)=LOC(a11)+((i-1)*n+(j-1))*1。二维数组Amn按列优先顺序(下标从1开始)，aij的地址为：LOC(aij)=LOC(a11)+((j-1)*n+(i-1))*1。在C语言中，二维数组是按行优先存储的，数组float a[4][5]的存储顺序为a[0][0],a[0][1],…,a[0][4],…,a[3][0],…,a[4][5]
,(下标从0开始)，a[2][3]的地址为a+((2－0)*5+(3-0))*4(单个元素存储空间)。
二、稀疏矩阵
1、稀疏矩阵的三元组线性表示
在计算机中存贮矩阵的一般方法是采用二维数组，其优点是可以随机访问每一个元素，因而较容易地实现矩阵的各种运算。但当一个矩阵中非零元素的个数远远少于零元素的个数(即称之为稀疏矩阵)时，这种存贮方法既浪费大量的存贮单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的，一种较方法是：只考虑存贮占元素极少数的非零元素。
对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这三元组(i,j,aij)来表示。若把所有的三元组按照行号从小到大的顺序；对于行号相同的三元组再按照列号从小到大的顺序排列，则就构成了一个表示稀疏矩阵的三元组线性表。
稀疏矩阵M= (无法显示)
对应的三元组线性表((1,1,3),(1,4,5),(2,3,-2),(3,1,1)(3,3,4),(3,5,6),(5,3,-1))。
2、稀疏矩阵的顺序存贮
稀疏矩阵的顺序存贮就是对其相应的三元组线性表进行顺序存贮。设一个稀疏矩阵具有i行和j列，其非零元素的个数为max，则它的顺序存贮可定义为：
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 8 /*系数矩阵非零元素的最大个数*/
typedef int ElemType;
typedef struct{ /*第i行，第j列的元素值为e*/
int i,j;
ElemType e;
}Triple;
typedef struct{
Triple data[MAXSIZE];
int mu,nu,tu; /*矩阵的行数、列数和非零元数*/
}TSMatrix;
对于矩阵am*n转置为an*m,使a[i,j]=b[j,i],其中，1<=i<=n,1<=j<=m,其实现步骤为：
1、将矩阵的行、列数互换。2、将每个三元组中的i和j互换。3、重排三元组之间的次序。
按a.data中的三元组的次序进行转置，将转置后的三元组置入b中恰当的位置，如能预先确定M中每一列的第一个非零元在b.data中的相应位置，则转置时可直接放入b.data恰当的位置。先求每一类非零元的个数，设num,cpot两个向量，num[col]表示M中第col列非零元个数，cpot[col]的初值表示M中第col列第一个非零元在b.data中的位置。
/*WINXP+VC6.0环境测试*/
void Show(TSMatrix TSM) /*打印稀疏矩阵*/
{
int i,j;
ElemType **temp=(ElemType **)malloc(TSM.mu*(sizeof(ElemType))); /*定义一个动态二维数组，注意是sizeof(ElemType)而不是sizeof(ElemType*)*/
if (temp==NULL)
return;
for(i=0;i<TSM.mu;i++)
temp[i]=(ElemType *)malloc(TSM.nu*(sizeof(ElemType))); /*为数组分配空间,注意mu,nu的位置，切勿颠倒*/
for(i=0;i<TSM.mu;i++) /*空间换时间，为临时数组赋值*/
for(j=0;j<TSM.nu;j++)
temp[i][j]=0;
for(i=0;i<TSM.tu;i++)
{
temp[TSM.data[i].i][TSM.data[i].j]=TSM.data[i].e; /*生成稀疏矩阵*/
}
for(i=0;i<TSM.mu;i++)
{
for(j=0;j<TSM.nu;j++)
{
printf("%d%c",temp[i][j],' ');
}
printf("/n",' ');
}
for(i=0;i<TSM.mu;i++) /*释放动态数组*/
{
free(temp[0]);
temp[i]=NULL;
}
free(temp);
temp=NULL;
/* for(i=0;i<TSM.mu;i++)
{
for(j=0;j<TSM.nu;j++)
{
if(TSM.data[k].i==i && TSM.data[k].j==j && k<MAXSIZE)
{
printf("%d%c",TSM.data[k].e,' ');
k++;
}
else
{
printf("%d%c",0,' ');
}
}
printf("/n",' ');
}
*/
}
TSMatrix Transpose(TSMatrix a) /*稀疏矩阵元素置换*/
{
TSMatrix b;
b.mu=a.nu;
b.nu=a.mu;
b.tu=a.tu;
if(a.tu!=0)
{
for(int k=0;k<MAXSIZE;k++)
{
b.data[k].j=a.data[k].i;
b.data[k].i=a.data[k].j;
b.data[k].e=a.data[k].e;
}
}
return b;
}
int main()
{
TSMatrix BTranspose= /*结构赋值*/
{
{
{0,1,12},
{0,2,9},
{2,0,-3},
{2,5,14},
{3,2,24},
{4,1,18},
{5,0,15},
{5,2,-7}
},
6,7,8
};
TSMatrix ATranspose;
Show(BTranspose);
ATranspose=Transpose(BTranspose); /*稀疏矩阵置换*/
printf("/n/n");
Show(ATranspose);
return 0;
}
2、稀疏矩阵的十字链表
十字链表存储就是既带行指针又带列指针向量的链接存储。这种链接存储中，每个三元组结点既处于同一行的单链表中，又处于同一列的单链表中，既处于所在的行单链表和列单链表的交点处。
链式存储可方便插入与删除。十字链表为每行和每列的非零元链成循环链表，每个非零元用一个结点表示，其形式如下：
row,col分别表示该数组每非零元素的行、列值，e表示该非零元素的值。Down指向该行的下一行具有相同列的非零元素，right指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。
十字链表结点结构和头结点的数据结构可定义如下：(无法显示)
typedef struct mtxn{
int row;
int col;
struct mtxn *right, *down;
union{
int value;
struct mtxn *link;
}tag;
}natnode;