[数组](1)数组
之前记下的所有线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的，这次讨论的两种数据结构——数组和广义表可以看成是线性表在下述含义上的扩展，表中的数据元素本身也是一个数据结构
类似于线性表，抽象数据类型数组可形式的定义为：
ADT Array
{
数据对象：j(i) = 0,...,b(i) - 1, i = 1,2,...,n,
D = {a(j1,j2...jn) | n(> 0)称为数组的维数，b(i)是数组第i维的长度，
j(i)是数组元素的第i维下标，a(j1,j2...jn)属于ElemSet}
数据关系：R = {R1,R2,...,Rn}
R(i) = { <a(j1...ji...jn),a(j1,...ji...jn)> | 0 <= j(k) <= b(k) - 1,
1 <= k <= n 且k！ = i,0 <= j(i) <= b(i) - 2,
a(j1...ji...jn),a(j1...ji + 1...jn)数据D，i = 2,...,n }
基本操作：
InitArray(&A,n,bound1,...,boundn)
操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK
DestroyArray(&A)
操作结果：销毁数组A
Value(A,&e,index1,...,indexn)
初始条件：A是n维数组，e为元素变量，随后是n个下标值
操作结果：若各下标不越界，则e赋值为所指定的A的元素值，并返回OK
Assign(&A,e,index1,...,indexn)
初始条件：A是n维数组，e为元素变量，随后是n个下标值
操作结果：若下标不越界，则将e的值赋给所指定的A的元素，并返回OK
ADT Array这是一个C语言风格的定义，从上述定义可见，n维数组中含有∏(i=1,...,n)b(i)个数据元素，每个元素都受着n个关系的约束 ，在每个关系中，元素a(j1,j2,...,jn)(0<=j(i)<=b(i)-2)都有一个直接后继元素
因此，就其单个关系而言，这n个关系仍是线性关系，和线性表一样，所有的数据元素都必须属于同一数据类型，数组中每个数据元素都对应于一组下标(j1,j2,...jn).
每个下标的取值范围是0<=j(i)<=b(i)-1,b(i)称为第i维的长度(i=1,2,...,n)
显然，当n=1时，n维数组就退化为定长线性表，反之，n维数组也可以看成是线性表的推广，当n=1时候，n维数组就退化为定长的线性表，反之n维数组也可以看成线性表的推广，由此我们也可以从另一个角度来定义n维数组
我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表，例如，下图所示为一个二维数组，以m行n列的矩阵形式表示，它可以看成是一个线性表。
a图为矩阵形式表示
A=（a0，a1，...，ap） （p=m-1或n-1）
其中每个数据元素a(j)是一个列向量形式的线性表
a(j)=（a0(j),a1(j),...,a(m-1),j） （0<=j<=n-1）
其中每一个数据元素a(i)是一个行向量形式的线性表
在C语音中，一个二维数组类型可定义为其分量类型为一维数组类型的一维数组类型。也就是说
typedef ElemType Array2[m][n]
等价于
typedef ElemType Array1[n]
typedef Array[n] Array2[m]同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。
数组一旦被定义，它的维度和维界就不再改变，因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作
数组的顺序表示和实现
由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此，采用顺序存储结构表示数组是自然的事了
由于存储单元是一维的结构，而数组是多维的结构，则用一组连续的存储单元存放数组的数据元素就有个次序约定的问题。
例如上图A的二维数组可以看做如图C的一维数组，也可以看做图B的一维数组。
C语言和JAVA中用的都是以行序为主序的存储结构，而在FORTRAN语言中，用的是以列为主序的存储结构
由此，对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间，反之，只要给出一组下标便可求得相应的数组元素的存储位置，下面仅用以行序为主序的存储结构为例
假设每个数据元素占L个存储单元，则二维数组A中任一元素a(i,j)的存储位置可由下式确定
LOC(i,j)=LOC(0,0)+(b2*i+j)L
上述式子中，LOC(i,j)=LOC(0,0)是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。
由于计算各个元素存储位置的时间相等，所以存储数组中任一元素的时间也相等，我们称具有这一特点的存储结构为随机存储
下面是数组的顺序存储的表示和实现
#include<stdarg.h>//标准头文件，提供宏va_start、va_arg、va_end
#define MAX_ARRAY_DIM 8//假设数组最大维度为8
typedef struct
{
ElemType* base;//数组元素基址,由InitArray分配
int dim;//数组维数
int* bounds;//数组维界基址,由InitArray分配
int* coustants;//数组映像函数常量基址，由InitArray分配
}Array;
//-----基本操作函数说明-----
Status InitArray(Array* A, int dim, ...);
//若维度dim和随后各维长度合法，则构造相应的数组A，并返回OK
Status DestroyArray(Array* A);
//销毁数组A
Status Value(Array A, ElemType* e, ...);
//A是个n维数组，e为元素变量，随后是n个下标值
//若下标不超界，则将e的值赋给所指定的A的元素，并返回OK
Status InitArray(Array* A, ElemType e, ...);
//A是n维数组，e为元素变量，随后是n个下标值
//若下标不超界，则将e的值赋给所指定的A的元素值，并返回OK
/*-----基本操作的算法描述-----*/
Status InitArray(Array* A, int dim, ...)
//若维数dim和各维长度合法，则构造相应的数组A，并返回OK
{
if (dim<1 || dim>MAX_ARRAY_DIM)
{
return ERROR;
}
A->dim = dim;//将数组维度指定给数组内的维度值
A->bounds = (int*)malloc(sizeof(int) * dim);//存储各维度的维界
if (!A->bounds)
{
exit(ERROR);//若各维长度合法，则存入bounds中，并求出A的元素总数elemtotal
}
elemtotal = 1;
va_list ap;
va_start(ap, dim);
for (i = 0; i < dim; i++)
{
A->bounds[i] = va_arg(ap, int);
if (A->bounds[i] < 0)
{
return ERROR;
}
elemtotal *= A->bounds[i];
}
va_end(ap);
A->base = (ElemType*)malloc(sizeof(ElemType) * elemtotal);
if (!A->base)
{
exit(ERROR);
}
//求映像函数的常数C，并存入A.constants[i-1],i=1,...,dim
A->coustants = (int*)malloc(dim * sizeof(int));
if (!A->coustants)
{
exit(ERROR);
}
A->coustants[dim - 1] = 1;//L=1,指针的增减以元素的大小为单位
for (i = dim - 2; i >= 0; i--)
{
A->coustants[i] = A->bounds[i + 1] * A->coustants[i + 1];
}
return OK;
}上述包含着可变参数包，我找了很多教程讲的都不详细，后边觉得C参考手册内讲的蛮好，如下：
va_start：
va_arg
至于宏原理，说实话我弄不懂位运算，目前还没明白.....了解是如何实现的可以看下列视频：
简单来说，stdarg头文件包含的va_list va_start va_arg va_end 可以理解为：
- va_list是一个指针类型，里面存放的是变参
- va_start是指针从哪里开始，第一个参数是list指针类型，第二个参数变参前的一个固定参数
- va_arg是从list中取出一个参数，第一个参数是list类型，第二个参数是需要取出（返回）的元素类型
- va_end是消除list指针
然后关于：bounds(存储各个维度的维界基址，本身是一个int类型的一维数组，例如：num[2] [2]，这一维的维界为2，二维的维界为而，则bounds={2,2});
constants(存储每一维映射到内存上的常数，本身是一个int类型一维数组。
例如：二维数组A[3] [4]
bounds[] = [3,4];
constants[] = [4,1]:代表第0维上的数字每加一, 元素在线性结构L中的位置就增加了4; 而第一维上的数字每加一, 元素位置也是加一
详细请看大佬的博客：点击观看
有了这些上边的InitArray函数并不难理解，我们继续补充剩余的基本操作：
Status DestroyArray(Array* A)
//销毁数组A
{
if (!A->base)
{
return ERROR;
}
else
{
free(A->base);
A->base = NULL;
}
if (!A->bounds)
{
return ERROR;
}
else
{
free(A->bounds);
A->bounds = NULL;
}
if (!A->constants)
{
return ERROR;
}
else
{
free(A->constants);
A->constants = NULL;
}
}
Status Locate(Array A, va_list ap, int* off)
//若ap指示的各下标值合法，则求出该元素在A中相对地址off
{
off = 0;
for (i = 0; i < A.dim; i++)
{
ind = va_arg(ap, int);
if (ind < 0 || ind >= A.bounds[i])
{
return ERROR;
}
off += A.constants[i] * ind;
}
return OK;
}
Status Value(Array A, ElemType e, ...)
//A是n维数组，e为元素变量，随后是n个下标值
//若下标不超界，则e赋值为所指定的A的元素值，并返回OK
{
va_list ap;
va_start(ap, e);
if ((result = Locate(A, ap, off)) <= 0)
{
return result;
}
e = *(A.base + off);
return 0;
}
Status Assign(Array* A, ElemType e, ...)
//A是n维数组，e为元素变量，随后是n个下标值
//若下标不超界，则将e的值赋给所指定A的元素，并返回OK
{
va_list ap;
va_start(ap, e);
if ((result = Locate(A, ap, off)) <= 0)
{
return result;
}
*(A.base + off) = e;
}以上的数组基本操作测试代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
typedef struct Array
{
int* base;//数组基址
int dim;
int* dic;//维界
int* cont;//映射常数
}Array;
void ConnateArray(Array* A, int dim, ...);
void Lecoate(Array* A, va_list ap, int* off);
void Value(Array* A, int *e, ...);
void Assign(Array* A, int e, ...);
int main()
{
Array A;
int e = 10;
ConnateArray(&A, 3, 2, 2, 2);
Assign(&A, e, 1, 1, 1);
int a = 0;
Value(&A, &e, 1, 1, 1);
printf("%d\n", e);
system("pause");
return 0;
}
void ConnateArray(Array* A, int dim, ...)
{
if (dim < 0 || dim>8)
{
printf("错误\n");
return 0;
}
va_list ap;
va_start(ap, dim);
int elemtotal = 1;
A->dim = dim;
A->dic = (int*)malloc(sizeof(int) * dim);
for (int i = 0; i < dim; i++)
{
A->dic[i] = va_arg(ap, int);
elemtotal *= A->dic[i];
}
A->base = (int*)malloc(sizeof(int) * elemtotal);
A->cont = (int*)malloc(sizeof(int) * A->dim);
A->cont[dim - 1] = 1;
for (int i = dim - 2; i >= 0; i--)
{
A->cont[i] = A->cont[i + 1] * A->dic[i+1];
}
printf("构造成功\n");
va_end(ap);
}
void Lecoate(Array* A, va_list ap, int* off)//定位
{
int index = 0;
*off = 0;
for (int i = 0; i < A->dim; i++)
{
index = va_arg(ap, int);
if (index < 0 || index >= A->dic[i])
{
printf("越界\n");
exit(0);
}
*off += A->cont[i] * index;
}
}
void Value(Array* A, int* e, ...)//取
{
va_list ap;
va_start(ap, e);
int off = 0;
Lecoate(A, ap, &off);
*e = *(A->base + off);
va_end(ap);
}
void Assign(Array* A, int e, ...)//存
{
va_list ap;
va_start(ap, e);
int off = 0;
Lecoate(A, ap, &off);
*(A->base + off) = e;
va_end(ap);
}以上操作其实只要明白多维数组映射到线性结构中的规律即可明白，这点即为重要
矩阵的压缩存储
通常，用高级语言编制程序时，都是用二维数组来存储矩阵元素，有的程序设计语言还提供了各种矩阵运算，用户使用时都很方便
然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素，有时为了节省存储空间，可以对这类矩阵进行压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间
假若值相同的元素或零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵，反之，称为稀疏矩阵，下面分别讨论他们的压缩存储
特殊矩阵
若n阶矩阵A中的元满足下述性质
a[i][j]=a[j][i] 1<=i,j<=n
则称为n阶对称矩阵
对于对称举证，我们可以为每一对对称元分配一个存储空间，则可将n²个元压缩存储到n(n+1)/2个元的空间中，不失一般性，我们可以行序为主序存储其下三角（包括对称性中的元）
假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元a[i][j]之间存在着一一对应的关系：
- 当i>=j时：(i(i-1)/2)+j-1
- 当i<j时：(j(j-1)/2)+i-1
对于任意给定一组下标(i,j)，均可在sa中找到矩阵元a[i][j]，反之，对所有的k=0,1,2，...，(n(n+1)/2)-1，都能确定sa[k]中的元在矩阵中的位置(i,j)，由此，称sa[n(n+1)/2]为n阶对称矩阵A的压缩存储。
如下图所示：
还有三角矩阵，对称矩阵等详细请看老师视频：点击观看，重点在稀疏矩阵上。
稀疏矩阵
稀疏矩阵没有一个确切的定义，人们只是根据直觉来判断概念。
假设在m n的矩阵中，有t个元素不为零，零l=(mn)/t，称l为矩阵的稀疏因子，通常认为l<=0.05时称为稀疏矩阵，矩阵运算的种类很多，在下列抽象数据类型稀疏矩阵的定义中，值列举了几种常见的运算
抽象数据类型稀疏矩阵的定义如下：
ADT SparseMatrix
{
数据对象：D = {a[i][j] | i = 1,2...,m; j = 1,2,...,n };
a[i][j]属于ElemSet，m和n分别称为矩阵的行数和列数
数据关系：R = { Row，Col };
Row = { <a[i][j],a[i][j + 1]> | 1 <= i <= m,1 <= j <= n - 1 }
Col = { < a[i][j],a[i + 1][j] | 1 <= i <= m - 1,1 <= j <= n }
基本操作：
CreateSmatrix(&M);
操作结果：创建稀疏矩阵M
DestroySmatrix(&M);
初始条件：稀疏矩阵M存在
操作结果：销毁稀疏矩阵M
PrintSMatrix(M);
初始条件：稀疏矩阵M存在
操作结果：输出稀疏矩阵M
CopySMatrix(M, &T);
初始条件：稀疏矩阵M存在
操作结果：由稀疏矩阵M复制得到T
AddSMatrix(M, N, &Q);
初始条件：稀疏矩阵M与N的行数和列数对应相等
操作结果：求稀疏矩阵和Q = M + N
SubtMarix(M, N, &Q);
初始条件：稀疏矩阵M与N的行数和列数对应相等
操作结果：求稀疏矩阵的差Q = M - N
MultSMatrix(M, N, &Q)
初始条件：稀疏矩阵M的列数等于N的行数
操作结果：求稀疏矩阵的乘积Q=M*N
TransposeSMatrix(M,&T)
初始条件：稀疏矩阵M存在
操作结果：求稀疏矩阵M的转置矩阵T
}ADT SparseMatrix按照压缩存储的概念，只存储稀疏矩阵的非零元，因此，除了存储非零元的值之外，还必须同时记下它所在行和列的位置(i,j),反之，一个三元组(i,j,a[i] [j])惟一确定了矩阵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))，加上(6,7)这一对并可作为下图中M矩阵的另一种描述方式T
