二维数组是元素为一元数组的一维数组。

数组一般采取顺序存储，最常见的两种操作是查找与修改。

二维数组元素的位置计算问题：假设有二维数组a[m][n]，数组从a[0][0]开始存储，问a[i][j]是数组中第几个元素？

分析：m表示a的行数，n表示a的列数，且每行有n个元素，每列有m个元素。

a[i][j]表示的是数组a中第i+1行第j+1个元素，那么：

Amn即为一个矩阵的逻辑表示，在数据结构中，可以用一个二维数组来存储。

矩阵的转置

对于一个m×n的矩阵A[m][n]，其转置矩阵是一个n×m的矩阵B[n][m]，且有B[i][j]=A[j][i]，0 for (int j = 0; j for (int i = 0; i C[i][j] = A[i][j] + B[i][j]; } } }

矩阵相乘

设A为m×n的矩阵，B为n×p的矩阵，那么称 的矩阵C为矩阵A与B的乘积，且只有在A矩阵的列数和B的行数相同时才有意义。矩阵C中的第i行第j列元素可以表示为：

那么自然地，C的大小为m×p：

假设有一个4阶的稀疏矩阵A如下图所示：

里面含有5个非0元素，将其转换为三元组表示法即为：

可以看到，5个元素我们用了6个三元组结点，因为默认第1个结点的val存储非零元素的个数，i存储原矩阵的行数，j存储原矩阵的列数。以A[0][4]元素1为例，它的值为1，行坐标为0，列坐标为3，那么:

伪地址法即元素在矩阵中按照行优先或者列优先存储的相对位置。（第几个元素的意思）

伪地址法存储时每个元素只需要两个变量，即：值和伪地址。

比如上述矩阵A的最后一个非零元素2，按照行优先的规则它在矩阵中的位置就是i*4+j+1，即3*4+1+1=14。

对于一个m*n的稀疏矩阵a，a[i][j]的伪地址计算方法为（行优先）：n*i+j+1。

最常见的稀疏矩阵的链式存储方法就是：邻接表法和十字链表法。

邻接表法就是将矩阵中的每一行的非零元素串成一个链表，每个链表结点中含有两个分量，一个是元素值，一个是列号。

在稀疏矩阵的十字链表存储结构中，矩阵的每一行用一个带头结点的链表表示， 每一列也用 一个带头结点的链表表示， 这种存储结构中的链表结点都有5个分量： 行分量、 列分量、数据域分量、指向下方结点的指针、指向右方结点的指针。

广义表： 表元素可以是原子或者广义表的一种线性表的扩展结构。

广义表的长度： 为表中最上层元素的个数

广义表的深度： 为表中括号的最大层数

表头 (Head) 和表尾 (Tail)：当广义表非空时， 第 个元素为广义表的表头， 其余元素组成的表是 广义表的表尾。

举例说明：

A=( ), A 是个空表，长度为 0，深度为 1。

B=(d, e), B 的元素全是原子，即 d 和 e，长度为 2，深度为 1。

C=(b, (c, d)), C 有两个元素，分别是原子 b 和另一个广义表(c, d)，长度为 2，深度为 2。

4)D=(B, C), D 的元素全是广义表，即 B 和 C， 长度为 2， 深度为 3。

由此可见，一个广义表的子表可以是其他已经定义的广义表的引用。

5)E=(a, E), E 有两个元素，分别是原子 a 和它本身，长度为 2。

由此可见，广义表可以是递归定义的，展开E可以得到(a,(a, (a, (a, · · ·)))) ，是无限深的广义表。

其中，对于广义表结点来说，

图5-7展示了1)到5)中广义表的头尾链表存储结构的存储情况：

，其中也有两种结点，即原子结点和广义表结点。

原子结点有3个域：标记域、数据域和尾指针域；

广义表结点也有3个域：标记域、头指针域与尾指针域。

其中，标记域区分当前结点是原子（用0来表示），还是广义表（用1来表示）。

扩展线性表存储结构类似带头结点的单链表存储结构，每一个子表都有一个不存储信息的头结点来标记其存在。

头尾链表存储结构类似于不带头结点的单链表存储结构。

图5-8展示了1)到5)中广义表的扩展线性表存储结构的存储情况：

设数组A[0, ···, n-1]的n个元素中有多个零元素，设计一 个算法，将 A 中所有的非零元素依次移动到A数组的前端。

关于浮点型数组A[0, ···, n-1], 试设计实现下列运算的递归算法。

(1) 求数组A中的最大值。 (2) 求数组中n个数之和。 (3) 求数组中n个数的平均值。

试设计一 个算法，将数组 A [0, · · ·, n-1]中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。