数组可以看成线性表的推广（特别是对于多维数组）
1.1 数组的基本概念
1.1.1 d维数组的抽象数据类型：
可以看出，数组除了初始化和销毁以外，在数组中通常只有下面两种操作：
· 读操作：给定一组下标，读取相应的数组元素。
· 写操作：给定一组下标，存储或修改相应的数组元素。
1.1.2 在C/C++中，数组的数据类型有以下性质：
（1）数据元素的数目固定，一旦定义了一个数组，其数据元素数目不再有变化。
（2）数据元素具有相同的数据类型。
（3）每个数据元素对应唯一一个下标。
（4）数组是一种随机存储结构，可以随机存取数组中的任意数据元素。
1.1.3 下面来体验一下数组的应用
用数组解决约瑟夫问题：设有n个人站成一圈其编号为1~n。从编号为1的人开始按顺时针方向“1，2，3，4···”循环报数，数到m的人出列，然后从出列者的下一个人重新开始报数，数到m的人又要出列，如此重复进行，直到n个人都出列为止，求出列顺序。
#约瑟夫问题void josephus(int n, int m){int p[MaxSize];int i, j, t;for(i = 0; i < n; i++) //构建初始序列p[i] = i+1;t = 0; //首次报数起始位置printf("出列顺序：");for(i = n; i >= 1; i--) //i为当前p数组的人数，出列一次，人数减1{t = (t+m-1) % i; //t为出列者的编号printf("%d,", p[t]);for(j = t+1; j <= i-1; j++) //后面的元素前移一个位置p[j-1] = p[j];}printf("\n");}
1.2 数组的存储结构
数组适合采用顺序存储结构来存储。
1.2.1 一维数组的存储结构
因为数组元素存储到一块地址连续的内存单元中，假设第一个元素a1的存储地址为LOC(a1)表示，每个元素用k个存储单元，则：
LOC(ai) = LOC(a1) + (i – 1) × k
1.2.2 二维数组的存储结构（简单理解）
有两种：按行优先存放、按列优先存放。
二维数组按行优先存放
二维数组按列优先存储
1.3 特殊矩阵的压缩存储（重点）
特殊矩阵主要形式有对称矩阵、对角矩阵等，他们都是方阵。
1.3.1 对称矩阵的压缩存储
图6.3对称矩阵的压缩存储
上述过程是对称矩阵采用行序优先存储对角线+下三角部分的元素，因为是对称矩阵，所以我们只需存储“对角线+下三角（或上三角）”就可以了，又因为数组可以看作一个线性表，因为不管是一维数组还是多维数组，他们一旦定义后，所占用的都是一块连续的存储地址。所以上图的数组B就是访问二维数组的一种相当于线性表的形式。
对于“对角线+下三角”的存储，其中元素所处的 i（行） >= 列 j（列），因为对于行下标为 i-1 的元素所处的行一共有 i 个元素（行下标从 0 开始）。所以这 i 行一共有 1+2+3+···+i = i(i+1)/2 个元素，又因为列下标为 j 的元素前面还有 j 个元素（列下标也从 0 开始），所以元素 a(i,j) 在对应B数组中的位置 k = i(i + 1)/2 +j (数组B中的元素下标也是从 0 开始)。
若存储的是“对角线+上三角”，有 i < j ，又因为 a(i,j) = a(j,i) ，所以它存放在数组B下标为 j(j+1)/2 +i 的位置。
综上有：
所以在访问或修改对称矩阵中的某个元素 a(i,j) 时，就可以根据上式计算出对应在线性表（数组）中位置，找到该元素。
总之就是在计算一个对称矩阵中元素 a(i,j) 在 B 中存储位置 k 时，首先要求出 a(i,j) 前面共存放多少个元素（设为m），再看 B 中存放元素的下标是从 0 开始还是从 1 开始（设 B 的初始下标为s），则 k = m+s。
1.3.2 上、下三角矩阵的压缩存储
这个不是我们所认为的下三角或上三角部分为 0 的上、下三角矩阵，而是为常数 c 的上下三角矩阵。
其压缩方式仍是采用以行序为主序存储其对角线或上三角（或下三角）部分的元素。另外用一个元素存储常数 c ，并将压缩结果存放在一维数组 B 中，B 中元素的个数为 n(n+1)/2 + 1，即用 B[0….n(n+1)/2] 存放 A 中的元素。
图6.4上三角矩阵的压缩存储
上面是对于存储“对角线+上三角”（i <= j）的一个图解，得出对于元素 a(i,j) 这 i 行一共有 n+(n-1)+(n-2)+······+(n-i+1) = i(2n-i+1)/2 个元素，在行下标为 i 的行中，元素 a(i,j) 的前面也存储了（j-i） 个元素。所以元素 a(i,j) 前面共存储了 i(2n-i+1)/2 +j-i 个元素，B数组的下标也是从零开始的，所以该元素对应数组 B 中的位置下标 k = i(2n-i+1)/2 +j-i 。
若 a(i,j) 是矩阵中的下三角部分也就是常数部分，有 i > j 。其值为常数c，用 B 的最后一个位置（即下标为 n(n+1)/2 的元素）存放常数c。
综上有：
对于“对角线+下三角”，类比对称矩阵有：
1.3.3 对角矩阵的压缩存储
这里的对角矩阵也不是简单的只是对角线为非 0 的对角阵，是指满足所有非零元素都集中在以对角线为中心的带状区域中。
半带宽：其主对角线上、下方各有 b 条非零元素构成的次对角线，则称 b 为矩阵的半带宽。
带宽：(2b+1) 为矩阵的带宽。
对角矩阵中 a(i,j) 对应到一维数组 B 中的下标位置 k = 2i + j 。（具体过程，百度吧，啊哈哈哈哈）
1.4 稀疏矩阵
稀疏矩阵：当一个矩阵中的非零元素个数 s 远小于矩阵元素总个数 t ，即 s << t 时，称该矩阵为稀疏矩阵。
1.4.1 稀疏矩阵的三元组表示
稀疏矩阵的压缩存储是只存储非零元素，但也必须同时存储非零元素对应的行下标、列下标和元素值。这个每一个非零元素由一个三元组（i, j, a(i,j)）唯一确定。其所有非零元素构成 三元组线性表。
若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为三元组顺序表，简称 三元组表。
· 三元组顺序表的数据类型声明如下：
#三元组顺序表的数据类型typedef int ElemType;#define M 6 //稀疏矩阵的行数#define N 6 //稀疏矩阵的列数#define MaxSize 10 //稀疏矩阵中非零元素最多的个数typedef struct{int r; //行号int c; //列号ElemType d; //元素值}TupNode; //三元组类型typedef struct{int rows; //行数int cols; //列数int nums; //非零元素的个数TupNode data[MaxSize]; // 结构体数组！}TSMatrix; //三元组顺序表类型
· 从一个二位稀疏矩阵创建其三元组表示 ：
#从一个二位稀疏矩阵创建其三元组表示void CreateMat(TSMatrix &t, ElemType A[M][N]){int i, j;t.rows = M;t.cols = N;t.nums = 0;for(i = 0; i < M; i++){for(j = 0; j < N; j++){if(A[i][j] != 0){t.data[t.nums].r = i;t.data[t.nums].c = j;t.data[t.nums].d = A[i][j];t.nums++;}}}}
· 三元组元素的赋值：
#三元组元素的赋值bool Value(TSMatrix &t, ElemType x, int i, int j){int k = 0, k1;if(i >= t.rows || j >= t.cols)return false;while(k < t.nums && i > t.data[k].r) //查找第i行的非零元素k++;while(k < t.nums && i == t.data[k].r && j > t.data[k].c)k++; //在第i行的非零元素中查找第j列if(t.data[k].r == i && t.data[k].c == j) //如果存在这样的非零元素，修改非零元素的值t.data[k].d = x;else{for(k1 = t.nums-1; k1 >= k; k1--) //若干元素均后移一位{t.data[k1 + 1].r = t.data[k1].r;t.data[k1 + 1].c = t.data[k1].c;t.data[k1 + 1].d = t.data[k1].d;}t.data[k].r = i; //插入非零元素xt.data[k].c = j;t.data[k].d = x;t.nums++;}return true;}
· 将指定位置的元素值赋值给变量：
#将指定位置的元素值赋值给变量bool Assign(TSMatrix t, ElemType &x, int i, int j){int k;if(i >= t.rows || j >= t.cols)return false;while(k < t.nums && i > t.data[k].r) //查找第i行的非零元素k++;while(k < t.nums && i == t.data[k].r && j > t.data[k].c)k++; //在第i行的非零元素中查找第j列if(t.data[k].r == i && t.data[k].c == j)x = t.data[k].d;elsex = 0;return true;}
· 输出三元组：
#输出三元组void DispMat(TSMatrix t){int k;if(t.nums <= 0)return; //因为函数为void 所以一个return就可以理解为返回空printf("\t%d\t%d\t%d\n", t.rows, t.cols, t.nums);// printf{"\n"};for(k = 0; k < t.nums; k++)printf("\t%d\t%d\t%d\n", t.data[k].r, t.data[k].c, t.data[k].d);}
· 稀疏矩阵的转置：
#稀疏矩阵的转置void TranTat(TSMatrix &t, TSMatrix &tb){int k, k1 = 0, v;tb.rows = t.rows;tb.cols = t.cols;tb.nums = t.nums;if(t.nums != 0){for(v = 0; v < t.cols; v++) //按列循环for(k = 0; k < t.nums; k++)if(t.data[k].c == v) //找到一个列号为v的元素{tb.data[k1].d = t.data[k].d;tb.data[k1].r = t.data[k].c;tb.data[k1].c = t.data[k].r;k1++;}}}
以上算法中含有两重for 循环,其时间复杂度为O(t.cols×t. nums)。最坏的情况是当稀疏矩阵中的非零元素个数t.nums和m×n同数量级时,时间复杂度为O(m×n^2),所以这不是一种高效的算法。
从以上可以看出,稀疏矩阵采用三元组顺序表存储后,当非零元素个数较少时会在一定程度上节省存储空间。如果用一个二维数组直接存储稀疏矩阵,此时具有随机存取特性,但采用三元组顺序表存储后会丧失随机存取特性。
1.4.2 稀疏矩阵的十字链表表示（类比图的十字链表）
十字链表(orthogonal list)是稀疏矩阵的一种链式存储结构(相应的,前面的三元组顺序表是稀疏矩阵的一种顺序存储结构)。有如下3行4列的稀疏矩阵:
创建稀疏矩阵 B 的十字链表的步骤如下:
(1）对于稀疏矩阵中每个非零元素创建一个结点存放它，包含元素的行号，列号和元素值。这里有 4 个非零元素，创建 4 个数据结点。
(2）将同一行的所有结点构成一个带头结点的循环单链表，行号为i的单链表的头结点为hr[i门。这里有 3 行，对应有 3 个循环单链表，头结点分别为hr[ 0 ]~hr[ 2 ]。hr[ i ] (0 ≤ i ≤ 2) 头结点的行指针指向行号为 i 的单链表的首结点。
(3）将同一列的所有结点构成一个带头结点的循环单链表，列号为j的单链表的头结点为hd[j] 。这里有 4 列，对应有 4 个循环单链表，头结点分别为 hd[0]~hd[3]。hd[j] (0 ≤ j ≤ 3) 头结点的列指针指向列号为 j 的单链表的首结点。
由此创建了 3十4=7 个循环单链表，头结点的个数也为 7 个。实际上，可以将 hr[ i ] 和 hd[ i ] 合起来变为h[ i ] ，即 h[ i ] 同时包含有行指针和列指针。h[ i ] (0 ≤ i ≤ 2) 头结点的行指针指向行号为i的单链表的首结点， h[ i ] (0 ≤ i ≤ 3) 头结点的列指针指向列号为i的单链表的首结点，这样头结点的个数为 MAX{3, 4} = 4 个。
(4）再将所有头结点h[ i ] (0 ≤ i ≤ 3) 连起来构成一个带头结点的循环单链表，这样需要增加一个总头结点 hm ，总头结点中存放稀疏矩阵的行数和列数等信息。
采用上述过程创建的稀疏矩阵B的十字链表如下图所示。每个非零元素就好比在一个十字路口，由此称为十字链表。
两种节点类型：
（a）数据结点结构 （b）头结点结构
设计稀疏矩阵的十字链表的节点类型 MatNode ：
#define M <稀疏矩阵的行数>#define N <稀疏矩阵的列数>#define Max ((M) > (N) ? (M) : (N)) //矩阵行列最大者typedef struct mtxn{int row;int col;struct mtxn *right, *down; //行列指针union{ElemType value;struct mtxn *link; //指向下一头节点}tag;}MatNode; //十字链表的结点类型
头结点 h[ i ] 的 h[ i ] ->right 指针可以逐行搜索行下标为i的所有非零元素。
h[ i ]-> down 指针可以逐列搜索列下标为i的所有非零元素。
转载请注明：XAMPP中文组官网 » 数组基本概念与存储结构