[数据结构与算法]数组--数据结构

?

一、数组

基本知识

??数组(array)是具有相同类型的数据的集合，也就是说数组的所有元素的类型都是相同的，在所有的数据结构中，数组算是最常见也是最简单的一种数据结构，我们最常见的也就是一维数组，当然还有二维，三维……，数组需要先声明才能使用，数组的大小一旦确定就不可以在变了。
??数组中的每个数据元素都对应于一组下标(j₁，j₂，…，j_n)，每个下标的取值范围是0 <= j_i <= b_i-1，b_i称为第 i 维的长度(i=1，2，…，n)。显然，当 n=1 时，n 维数组就退化为定长的线性表。反之，n维数组也可以看成时线性表的推广。
??数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
?
?

存储方式及地址计算

??由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组是自然的事了。
??顺序存储结构特点：数据元素的存储对应一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素在存储器的相对位置来反映。

一维数组

??采用顺序存储结构表示数组，所以一维数组的存储方式就十分易懂了。数组地址顺序排列，邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

??我们看看C语言 int 数组的地址情况。定义一个 int 数组，大小为3，分别输出这三个元素的地址。可以发现三个元素地址是连续的，且间隔相同。

#include<stdio.h>

int main()
{
	int a[] = {1,2,3};
	printf("%p\n",a[0]);
	printf("%p\n",a[1]);
	printf("%p\n",a[2]);
	return 0;
}

?

地址计算

a[i]的存储地址：a+i*len （a是数组首地址，len是每个数组元素所占长度）

?
?

二维数组

??我们可以吧二维数组看成时这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如，一个二维数组，m行n列的矩阵形式。它可以看成是一个线性表

??????????A = (α₀，α₁，…，α_p) （p = m - 1 或 n - 1）

其中每个数据元素α_j是一列向量形式的线性表，如下图
??????????α_j = (α_0j，α_1j，…，α_m-1,j) （0 <= j <= n-1）

或者α_i是一个行向量形式的线性表，如下图
????????α_i = (α_i0，α_i1，…，α_i,n-1) （0 <= i <= m-1）

??对应地，对二维数组可有两种存储方式：一种以列序为主序的存储方式；一种是以行序为主序的存储方式。

??在扩展BASIC、PL/1、COBOL、PASCAL和C语言中，用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列序为主序的存储结构。
?
?

地址计算

按行存储：
　 a[i][j]的存储地址：a+(i*n+j)*len （a是数组首地址，len是每个数组元素所占长度，数组n行m列）

按列存储：
　 a[i][j]的存储地址：a+(j*m+i)*len （a是数组首地址，len是每个数组元素所占长度，数组n行m列）

int 占4位二进制位，以4行3列数组位例，查看C语言的地址。

#include<stdio.h>

int main()
{
	int a[4][3] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
	printf("int占2进制位：%d",sizeof(int));
	printf("16进制\n");
	printf("%p\n",a[0][0]);
	printf("%p\n",a[1][2]);
	printf("%p\n",a[3][2]);
	return 0;
}

?
?

二、特殊矩阵

??在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。
??假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。
?

对称矩阵

若 n 阶矩阵 A 中的元满足性质：a_ij = a_ji 1 <= i,j <= n 则称为 n 阶对称矩阵。
??对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将 n²个元压缩存储到 n(n+1)/2 个元的空间中。不失一般性，我们可以行序为主序存储其下三角（包括对角线）中的元。
??假设以一维数组 sa[n(n+1)/2] 作为 n 阶对称矩阵 A 的存储结构，则 sa[k] 和矩阵元 a_ij之间存在着一一对应的关系：

对于任意给定一组下标 (i，j) ，均可在 sa 中找到矩阵元 a_ij，反之，对所有的 k=0，1，2，…，n(n+1)/2 - 1，都能确定 sa[k] 中的元在矩阵中的位置 （i，j）。由此，称 sa[n(n+1)/2] 为 n 阶对称矩阵 A 的压缩存储。

这种压缩存储的方法同样也适用于三角矩阵。

?

地址计算

按行优先存储，并存储下三角： sa[k] 和 矩阵元素 a_ij之间的对应关系 （1 <= i,j <= n）

?
按行优先存储，并存储上三角： sa[k] 和 矩阵元素 a_ij之间的对应关系 （1 <= i,j <= n）

?
按列优先存储，并存储下三角： sa[k] 和 矩阵元素 a_ij之间的对应关系 （1 <= i,j <= n）

?
按列优先存储，并存储上三角： sa[k] 和 矩阵元素 a_ij之间的对应关系 （1 <= i,j <= n）

?
?

三、稀疏矩阵

??假设在m×n得矩阵中，有 t 个元素不为零。令 δ = t / (m×n)，称 δ 为矩阵的稀疏因子。通常认为 δ <= 0.05 时称为稀疏矩阵。
?

三元组

??压缩存储的概念，只存储稀疏矩阵的非零元。所以，除了存储非零元的值之外，还必须同时记下它所在行和列的位置 (i,j)。反之，一个三元组(i,j,a_ij)唯一确定了矩阵 A 的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

三元组：( (1,2,12) , (1,3,9) , (3,1,-3) , (3,6,14) , (4,3,24) , (5,2,18) , (6,1,15) , (6,4,-7) )
?

三元组顺序表

//稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE 12500 //假设非零元素个数的最大值为12500 
typedef struct{
	int i,j;//该非零元的行下标和列下标 
	ElemType v;//非零元值 
}Teiple;
typedef struct{
	Triple data[MAXSIZE + 1];//非零元三元组，data[0]未用 
	int mu, nu, tu;//矩阵的行数、列数和非零元个数 
}TSMatrix;

data域中表示非零元的三元组是以行序为主序顺序排列的。

我们看看转置矩阵三元组顺序表的对比。以上面的矩阵M和矩阵T为例。

我们可由发现两者的差异：（1）将矩阵的行列值相互交换；（2）将每个三元组中的 i 和 j 相互调换；（3）重排三元组之间的次序便可实现矩阵的转置。

?

稀疏矩阵转置算法

算法一

1. 由 M 的行数、列数以及非 0 元素数可以直接得到 T 的列数、行数和非 0 元素数。
2. 对 M 中的数据进行遍历，即依次扫描第 0 列、第 1 列、……、最后一列，扫描过程交换行和列的顺序，并存储到 T 中对应的位置即可。

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
	//采用三元组表存储表示，求稀疏矩阵M的转置矩阵T 
	T.mu = M.nu;	T.nu = M.mu;	T.tu = M.tu;
	if(T.tu){
		q = 1;
		for(col=1; col<=M.nu; col++)//n是列数 
			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].v = M.data[p].v;
					q++;
				}
	}
}

??两重循环，算法时间复杂度：O(nu * tu)，即和 M 的列数及非零元的个数的乘积成正比。
??当非零元的个数 tu 和 mu×nu 同数量级时，时间复杂度就为 O(mu×nu²)，这样时间复杂度就较大了，所以该算法仅适用于 tu?mu×nu 的情况。
?
?

算法二

1. 由 M 的行数、列数以及非 0 元素数可以直接得到 T 的列数、行数和非 0 元素数。
2. 要想扫描一次 M 就能得到 T，必须每次扫描到一个三元组就直接将其放到 b 中相应的位置上，因此，需要知道 M 中的元素在 T 中的存储位置，这就要预先确定矩阵 M 的每一列的第一个非 0 元素在 T 中相应的位置。为此，需要附设两个数组，num 和cpot，分别用于存储矩阵 M 中每一列的非 0 元素个数和矩阵 M 中每一列第 1 个非0 元素在 T 中的存储位置。

显然，有如下的公式成立：

• cpot[0] = 1
• cpot[col] = cpot[col - 1] + num[col -1] 2<= col <= a.nu

矩阵 M的 num 和 cpot 的值，如下表：

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
	//采用三元组表存储表示，求稀疏矩阵M的转置矩阵T
	T.mu = M.nu;	T.nu = M.mu;	T.tu = M.tu;
	if(T.tu){
		for(col=1; col<= M.mu; col++)
			num[col] = 0;
		for(t=1; t<=M.tu; t++)
			num[M.data[t].j]++;	//求M中每一列含非零元个数 
		cpot[1] = 1;
		//求第col列中第一个非零元在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].v = M.data[p].v;
			cpot[col]++;
		}
	}
} 

??时间复杂度：O(nu+tu)。
??三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。