数据结构- 案例5

向量与矩阵在许多科学和工程技术应用中，数组用于表示数学对象向量和矩阵。本节我们将学习如何在C中表示向量和矩阵，以及如何编写C函数实现对这些对象的操作。向量的表示向量是由一个数的序列（向量的分量）构成的数学对象。若向量由N个分量构成，则称向量是N维的。遗憾的是，“维”在C中的含义与向量的标准数学术语不一致。图88中的数组C是一维（在C的术语中）的，而它所表示的向量却是三维（在数学术语中）的。一个N一维向量在C中表示为一个长度为N的一维数组。也许你会注意到向量分量的符号标识与C中也不尽相同。向量X的第三个分量（4）在数学中记为X3，但它在C中被称为X2,因为C数组的下标总是从0开始的。C数组X0X1X2X向量的X1X2X3分量图88向量在C中的表示C数组X；向量X标量积分量个数相同的两个向量可以相乘，将对应分量的乘积求和，所得结果为标量（点或内）积。因此，若X且W,它们的标量积为123XW12234112通常，若X与W是两个N维的向量，则它们的标量积为KNKX1式中，XK与WK分别表示向量X和W的第K个分量。编写计算两个N维向量X和W的程序很简单。需要一个循环计数器逐一遍历各个分量，变量SUM_PROD用于累加求和。计算标量积的C程序如下SUM_PROD0FORK0K21321210MN矩阵A和N维向量X相乘计算VI的数学通项公式是VIAIKXKN1将求和公式转化为C语句，并根据组下标从零开始的规定适当调整，计算VI的代码如下VIAIKXK掌握了矩阵中的一个元素的计算方法，编程计算整个向量就是一件轻而易举的事情了。我们所要做的就是把一个元素VI的计算嵌入到一个FOR的循环中，I充当循环变量。图812的C函数MAT_VEC_PROD希望调用自己的函数能够提供空间用来存储结果向量。我们一贯采用大写字母表示数组的行数和列数，暗示已经把它们定义为常量。虽然我们的函数可以允许M行数的变化，但考虑到列数必须为常数，两个维数我们均选择使用常数。/计算MN矩阵A与N维向量X的乘积。结果存储在输出变量V，一个M维向量中。/VOIDMAT_VEC_PRODDOUBLEV,/输出M维乘积向量/DOUBLEAMN/输入M行N列矩阵/DOUBLEX/输入N维向量/INTI,KFORI1IM,IVI0FORK0KNKVIAIKXK图812计算矩阵与向量乘积的函数的MAT_VEC_PROD矩阵乘法矩阵与向量相乘仅是矩阵与矩阵相乘的一种特例，因为一个N维向量可以看作是一个N行1列的矩阵。我们现在来编写两个矩阵相乘，返回值为乘积矩阵的C函数。两个矩阵A和B相乘，将产生一个新的矩阵CAB,只要A的列数与B的行数相同。我们说符合这一条件的矩阵A和B是“适合”相乘的，若A是一个MN的矩阵，B是一个NP的矩阵，则乘积矩阵C就是一个MP的矩阵。这个结果与我们讨论过的矩阵（MN）与向量（N1）相乘结果为新向量（M1）是一致的。再计算两个矩阵的乘积时，首先考虑一个一般性元素是如何计算的。例如，乘积矩阵C中的一个一般性元素是位于I行J列的一个元素，记为CIJ。一旦我们知道如何计算CIJ，那么计算矩阵的其余元素就轻而易举了。我们只需要将CIJ的计算嵌入到适当的循环机制中，令和已辞去有关数值即可FORI1；IMIFORJ0JPJ计算CIJ现在我们分析乘积矩阵CAB中通项CIJ的计算。元素CIJ恰是A的第I行B的第J列的标量积。图813所示的两个方阵A和B的相乘（若矩阵的行数与列数相同则称之为方阵）。例如，在计算图813中的C的彩色元素是将A（可视为一个向量）中彩色的一列相乘。将A的第I行B的第J列相乘计算CIJ的C语句如下CIJ0FORK0KNKCIJAIKBKJ将上述计算嵌入到一个适当的嵌套FOR的循环结构，即可得到整个矩阵相乘的计算结果。如图814函数MAT_PROD所示。图814中采用运算符，因为它既简洁又高效。在任何ASNSIC的实际环境中，必须确保执行语句CIJAIKBKJ时只计算一次CIJ的内存地址。相比之下，下面的语句则需计算两次CIJCIJAIKBKJAB813矩阵A与矩阵B相乘/矩阵A与矩阵B相乘，结果为矩阵C/VOIDMAT_PRODDOULECMP,/输出M行P烈矩阵/DOUBLEAMN/输入M行N列矩阵/DOUBLEBNP/输入N行P列矩阵/INTI,J,KFORI1IM,IFORJ0JPJCIJ0FORK0KNKCIJAIKBKJ图8。14两个矩阵相乘的函数MAT_PROD84线性方程组的求解在83节我们看到矩阵A132与向量X12右乘时，结果为向量Y294现在我们来考虑下面的问题。假设我们知道矩阵A和向量Y，但不知道向量X。我们想知道哪个向量X与矩阵A右乘时能得到向量Y。这个问题就是求出下面方程中的三个未知数X1,X2和X3,AXY13232X94要计算X1,X2,和X3的值，我们必须求解包含三个未知数的三个线性方程组。为了说明这个问题，我们来看在下面的式子中向量Y的每一个分量是如何由矩阵A和未知向量X计算的Y1A1,1X1A1,2X2A1,3X3将数值代入矩阵元素AIJ,我们即可得到含三个未知数的X1，X2和X3的三个线性方程所构成的方程组X1X2X342X13X2X39X1X2X32这样的方程组可以用于描述很多类问题。例如，假设一艘飞船由三个助