数据结构| 数组

数组的定义

数组是由n个类型相同的数据元素组成的有限序列。其中，这n个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型，如整型、字符型、浮点型等，统称为一维数组；也可以是一个线性表，这种类型的数组称为二维数组。

数组的抽象类型定义如下：

ADT Array{
    数据对象；
    数据关系；

    基本操作：
        InitArray(Array &A,int dim,...)
            操作结果：若维数dim和随后的各维长度合法，则构造相应的数组A
        DestroyArray(Array &A)
            初始条件：存在数组
            操作结果：销毁数组A
        Value(Array A,ElemType &e,...)
            初始条件：存在数组
            操作结果：A是n维数组，e为元素变量，随后是n个下标值；若下表不超界，则将e赋值为所指定的A的元素
        Assign(Array &A,ElemType e,...)
            初始条件：存在数组
            操作结果：A是n维数组，e为元素变量，随后是n个下标值；若下表不超界，则将e赋值给所指定的A的元素
}

数组的顺序表示与实现

1.宏定义解释

#include<stdarg.h>   标准头文件，提供va_start、va_arg等
#define MAX_ARRAY_DIM 8  //假设数维数最大值为8

2.结构类型

typedef struct{
    ElemType *base;  //数组元素的基址
    int dim;  //数组维数
    int *bounds;  //数组维届基址
    int *constants;  //数组映像函数常量基址
}Array;

特殊矩阵的压缩存储

在矩阵的运算中往往会出现阶数很高的矩阵中存在许多相同的元素或者值为0的元素。为了节省空间需要将这些矩阵进行压缩存储。

1.对称矩阵的压缩存储

如果一个n阶矩阵A中的元素满足性质aij = aji，则称这样的矩阵为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角元素，使得对称的元素共享一个存储单元，这样就可以实现压缩的目的。

假设一维数组s存储对称矩阵A的上三角或者下三角元素，则一维数组s的下标k与n阶对称矩阵A的元素aij之间的对称关系为：

对称矩阵

其中当i>=j时表示的是下三角的情况，而i<j时表示的是上三角的情况。

2.三角矩阵的压缩存储

三角矩阵分为两种：上三角矩阵和下三角矩阵。其中，下三角元素均为常数或0的n阶矩阵称为上三角矩阵，反之则称为下三角矩阵。在三角矩阵中，重复元素可以用一个存储单元来进行存储，而其他的元素可以用对称矩阵的压缩存储方式来存储。

如果用一维数组来存储三角矩阵，则需要存储n* (n+1)/2+1个元素。一维数组的下标k与矩阵的下标(i,j)的对应关系为：

其中n*(n+1)/2这个位置是用来存放常数或者0元素的。

3.对角矩阵的压缩存储

对角矩阵就是所有的非0元素都集中在主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和其两边的对角线外，其他元素的值均为0。

对角矩阵

对角矩阵具有如下特点：

第一行和最后一行有2个非零元素，第2-n-1行有3个非零元素。
前i-1行有3*(i-1)-1个非零元素，第i行的非零元素个数为j-i+1当j<i时，j-i = -1当j>i时j-i=1。
使用一维数组存储，需要存储3*n-2个元素。
一维数组s[k]和A[i][j]的对应关系为：k = 2*i+j。

4.稀疏矩阵的压缩存储

稀疏矩阵是指在m x n矩阵中，有t个元素不为0，且t/(m+n)<=0.05，我们把这样的矩阵叫做稀疏矩阵。也就是说矩阵中存在大多数为0的元素，只有很少的非0元素，这样的矩阵就是稀疏矩阵。由于稀疏矩阵中的非0元素很少，因此稀疏矩阵也需要进行压缩存储。

稀疏矩阵的抽象类型定义如下：

ADT SparseMatrix{
    数据对象；
    数据关系；

    基本操作：
        CreateMatrix(&M)
            操作结果：创建稀疏矩阵
        DestroyMatrix(&M)
            初始条件：存在稀疏矩阵
            操作结果：销毁稀疏矩阵M
        PrintSMatrix(M)
            初始条件；存在稀疏矩阵
            操作结果：输出稀疏矩阵M
        CopyMatrix(M,&N)
            初始条件：存在稀疏矩阵
            操作结果：由稀疏矩阵M复制得到T
        TransposeSMatrix(M,&N)
            初始条件：存在稀疏矩阵
            操作结果：求稀疏矩阵M的转置矩阵T
}

稀疏矩阵的表示与实现

为了实现压缩存储，可以只存储稀疏矩阵中的非0元素。在存储稀疏矩阵中的非0元素时，还必须存储非0元素对应的行和列的位置(i,j)。也就是说，存储一个非0元素需要存储元素的行号列号和元素的值。在这里我们可以采用三元组的方式来进行存储。

1.宏定义解释

#define MaxSize 200  //三元组的个数
#typedef DataType int;  //定义为int类型

2.结构类型

typedef struct{
    int i;  //行号
    int j;  //列号
    DataType e;  //值
}Triple;
//定义矩阵
typedef struct{
    Triple data[Maxsize];  
    int m;  //矩阵的行数
    int n;  //矩阵的列数
    int len;  //非0元素的个数
}TriSeqMatrix;

3.基本操作的实现
（1）创建稀疏矩阵CreatMatrix

int CreatMatrix(TriSeqMatrix *M){
    int i,m,n;
    DataType e;
    int flag;  //设置标志位
    cout<<"Enter the number of rows, columns, and non-zero elements:"<<endl;  //输入行数、列数和非0元素的个数
    cin>>M->m;
    cin>>M->n;
    cin>>M->len;
    if(M->len>Maxsize){  //如果超过最大容量则返回0
        return 0;
    }
    for(i=0;i<M->len;i++){  //开始输入
        do{
            cout<<"Enter the number of rows,columns and values for the NO."<<i+1<<"number"<<endl;  //输入每一个非0元素的行数列数与数值
            cin>>m;
            cin>>n;
            cin>>e;
            flag=0;  //初始化标志位
            if(m<0||m>M->m||n<0||n>M->n){  //如果输入错误，则标志位为0
                flag=0;  
            }
            if(i>0&&m<M->data[i-1].i||m==M->data[i-1].i&&n<=M->data[i-1].j){
                flag=1;
            }
        }while(flag)
        M->data[i].i=m;
        M->data[i].j=n;
        M->data[i].e=e;
    }
    return 1;
}

（2）销毁稀疏矩阵DestroyMatrix

void DestroyMatrix(TriSeqMatrix *M){
    M->m=M->n=M->len=0;  //全部置为零
}

（3）矩阵的复制CopyMatrix

void CopyMatrix(TriSeqMatrix M,TriSeqMatrix *N){
//稀疏矩阵M复制得到另一个矩阵N
    int i;
    N->len = M.len;
    N->m = M.m;
    N->n = M.n;
    for(i=0;i<M.len;i++){
        N->data[i].i=M.data[i].i;
        N->data[i].j=M.data[i].j;
        N->data[i].e=M.data[i].e;
    }
}

（4）矩阵的转置TransposeMatrix

void TransposeMatrix(TriSeqMatrix M,TriSeqMatrix *N){
    int i,k,col;
    N->m=M.n;
    N->n=M.m;
    N->len=M.len;
    if(N->len){
        k=0;
        for(col=0;col<M.n;col++){  //按照列号开始扫描三元组
            for(i=0;i<M.len;i++){
                if(M.data[i].j==col){  //如果列号是当前的列，则进行转置
                    N->data[k].i=M.data[i].j;
                    N->data[k].j=M.data[i].i;
                    N->data[k].e=M.data[i].e;
                    k++;
                }
            }
        }
    }
}

稀疏矩阵的十字链表表示与实现

稀疏矩阵的十字链表表示就是采用链式存储的方式来进行的，链表中的每个结点存储稀疏矩阵中的每个非0元素。每个结点包含5个域：3个数据域和2个指针域。其中3个数据域分别表示非0元素的行号、列号以及元素值；2个指针域是right域和down域，right指向同一行中的下一个非0元素，down指向同一列的非0元素。