数据结构：密矩阵

　　一般来说，矩阵的每个元在计算机内存中逐个储存，这种数据结构通常叫做密矩阵（dense matrix）．由于在计算机内存中所有数据都是按顺序排成一行，所以在储存矩阵时我们就有两种选择，一是把矩阵所有行首尾相接，叫做行主序（row-major），二是把矩阵所有列首尾相接，叫列主序（column-major）．例如对于 $2 \times 2$ 的矩阵 $ \boldsymbol{\mathbf{A}} $，列主序下，矩阵元在内存中的顺序依次 $A_{11}, A_{21}, A_{12}, A_{22}$，而在行主序下顺序为 $A_{11},A_{12},A_{21},A_{22}$．

　　在 fortran 和 Matlab 中¹，语言自带的矩阵都是列主序，而在 C/C++ 中如果用指针的指针（或数组的数组）来表示矩阵，得到的将会是行主序．当然，由于 C++ 的灵活性，我们完全可以创造行主序和列主序两种不同的矩阵类．由于 C++ 的数组的指标从 0 开始，那么矩阵的行标和列表也习惯从 0 开始．

　　在我们用双索引寻找矩阵元时，我们需要先将其转换为单索引．假设矩阵尺寸为 $N_1 \times N_2$，那么

\begin{equation} \begin{aligned} &\begin{cases} n = i + N_1 j &\text{（列主序）}\\ n = N_2 i + j &\text{（行主序）} \end{cases}\\ &(i = 0, 1, \dots, N_1-1,\quad j = 0, 1, \dots, N_2-1) \end{aligned} \end{equation}

　　行主序和列主序也可以延申至高维矩阵，如果使用列主序，那么当我们在内存中按顺序读取数据的时候，第 1 个索引（index）将变化得最快，第 2 个索引变化得第二快，最后得索引变化得最慢．行主序则相反，最后的索引变化得最快，而第一个最慢．例如 4 维数组的多索引变为单索引的公式为

\begin{equation} \begin{cases} n = i_1 + N_1 i_2 + N_1 N_2 i_3 + N_1 N_2 N_3 i_4 &\text{（列主序）}\\ n = N_2 N_3 N_4 i_1 + N_3 N_4 i_2 + N_4 i_3 + i_4 &\text{（行主序）} \end{cases} \end{equation}

从性能角度来看，单索引要比多个索引要快．

　　若要由单索引计算多索引，我们可以用整数除法（向下取整）/ 和求余运算 %，例如对列主序的矩阵有

\begin{equation} \begin{cases} i = n \% N\\ j = n / N \end{cases} \end{equation}

1. ^ Matlab 最初就是由 fortran 编写的．