数据结构3.1线性表的推广——数组数据结构

数组（array）定义数组可看成一种特殊的线性表，其数据元素本身也是一个线性表。假设一个二维数组A（m*n）有m行n列，那么可以把这个二维数组看成一个线性表：
A = (a0,a1…am-1)
其中，每个元素ai是一个行向量组成的线性表：
ai = (ai 0,ai 1…ai n-1) (0<=i<=m-1)
也可以看作是一个由列向量组成的元素组成的线性表。
那么以此类推，一个n维数组可以看成是n-1维数组的线性表。
数组的基本操作因为数组一旦建立，数组的元素个数和元素关系就不能再改变，因此无元素插入删除操作，其基本操作主要是元素的读取和更新。
1->读取操作value(A,index1,index2,…,indexd)，其功能是返回由下标index1,index2,…,indexd确定的数组A的对应元素值
2->更新操作assign(A,e,index1,index2,…,indexd)，其功能是将e的值赋给数组A中下标为index1,index2,…,indexd的元素
3->输出操作list(A)，其功能是输出数组A的全部元素
数组存储结构由数组定义可知，用顺序存储结构最为理想。
而因次序约定问题又把二维数组的存储方式分为行优先存储方式以及列优先存储方式。
按以上两种存储方式存储的数组，只要知道起始结点的存放地址（基地址）、维数和每维的上下界，以及每个数组元素所占用的字节数，就能将数组元素的存放地址表示为其下标的线性函数。一旦规定了数组的维数和各维的长度，便可为他分配存储空间。
以行优先存储方式存储的数组举例,每个元素占L个字节，其ai j的地址计算公式为：
LOC(ai j) = LOC(a0 0) + (i * n + j) * L
推广得n维数组各维长度为bi，数组中每个数据元素对应于一组下标(j1,j2…jn)，(0<=ji<=bi - 1)(1<=i<=n)有：
LOC(aj1 j2…jn) = LOC(a0 0…0) + (b2 * … bn * j1 + b3 * … * bn * j2 + … + bn * jn-1 + jn) * L
矩阵的压缩存储 【数据结构3.1线性表的推广——数组】通常用二维数组来存储来存储矩阵。但对于一些高阶矩阵，其中含许多同值元素或零元素，若为其全部分配内存过于浪费，为节省空间，对其进行压缩存储，多个同值元素值分配一个存储空间，零元素不分配空间。
其中分为两类可压缩的矩阵：
同值元素或零元素在矩阵中的分布有规律——特殊矩阵
非零元素较少且分配没有规律——稀疏矩阵
特殊矩阵的压缩存储对称矩阵：ai j == aj i，因其元素关于主对角线对称，因此在存储时可只存储其上三角或下三角中的元素，使对称元素共享一个存储空间。
按行优先顺序存储存储下三角部分（包括对角线）元素，假设以一组数组a[n(n-1)/2]作为n阶对称矩阵A的存储结构，则矩阵A的任意元素aij和a[k]之间的对应关系为：
k = i(i-1)/2 + j (i >= j)
k = j(j-1)/2 + I (i < j)
三角矩阵：矩阵的下（上）三角（不包括主对角线）中的元素均为常数c。与对称矩阵的不同就是多开辟一个存储空间来存储常量c。
假设以一组数组a[n(n-1)/2 + 1]作为n阶对称矩阵A的存储结构，则三角矩阵A的任意元素aij和a[k]之间的对应关系为：
上三角矩阵：
k = i(2n - i + 1)/2 + j - i (i<=j)
k = n(n + 1)/2 (i < j)
下三角矩阵：
k = i(i + 1)/2 + j (i<=j)
k = n(n + 1)/2 (i < j)
其中a[n(n + 1)/2]用于存放常量c
对角矩阵：
所有非零元素集中在以主对角线为中心的带状区域中。
假设以行优先存储方式把n阶三角矩阵A存储到一维数组a[3n-2]中，则a[k]和aij的对应关系为：
k = 2i + j(| i - j | <= 1)
稀疏矩阵每一个非零元素由一个**三元组( i, j, aij)**唯一确定，因此可将其所有非零元素按一定次序排列构成一个三元组线性表。
三元组表的类型说明

#define MAXSIZE 100//定义三元组顺序表的最大长度 typedef int ElemType; typedef struct {int i; //行标 int j; //列标 ElemType e; //非零元素值 }tupletype; typedef struct {int rownum; //行数 int colnum; //列数 int nznum; //非零元素个数 tupletype data[MAXSIZE]; //非零三元组表 }table;

十字链表每个非零元用一个含五个域的结点表示，其中i,j,value三个域分别表示该非零元素所在的行列和非零元素值，向右域right用以链接同一行中下一个非零元素，向下域down用以链接同一列中下一个非零元素。
设置行列头结点和链表头结点，其中行列头结点的i，j域值均为-1，行的right值指向该链表的第一个结点，down域为空；列头结点的down值指向该列链表的第1个结点，他的right值为空。链表头结点的ij值为稀疏矩阵的行数列数。
十字链表的结点类型定义

#include #define M 3//矩阵行数 #define N 4//矩阵列数 #define MAX((M) > (N) ? (M) : (N))//矩阵行列最大值 typedef struct mtxn {int row; int col; struct mtxn *right,*down； union {int value; struct mtxn *link; }tag; }manode;