大家好。
数据结构与算法这一讲，我们开始第十二章高级数据结构的学习。
其实我们分为两大部分，第一部分呢就是高级线性结构。 我们有一些高级的树形结构。
在高级线性结构里面，首先我们来看多维数组。
那数组呢它在我们计算机里面，
它表示的是一些元素类型是固定的数据的组合，
而且呢它的数量其实我们也固定，这样我们就
可以固定一些存储区域，然后来存放这些很有规律的数据。
那静态数组呢，我们是在申明的时候就要规定它的大小。
在动态数组呢我们可以根据程序运行情况才能分配。
那这个呢在不同的语言环境是不一样的。
多维数组其实可以看作是一维数组的扩展。
那也就是说，向量的向量，那就变成二维数组，
然后我们如果是这个数组里面的元素，它本身就是二维数组。 那我们就是，
那我们二维数组串起来，又变成三维数组，依次推广，那我们就可以定义多维的数组。
那这个多维数组呢，我们在很多语言里面可能
其实你可以定义数组的每一维，它们的起始的这个上下界。
那这个起始的上下界呢，在某些语言里面，甚至它都不要求是
这种连续的整数值，你可以是每一矩形的。
那我们这些维，我们每一维所占用的这个
上下界它的一个大小的区域，那我们合起来呢，
整个数组块就占这么大的一个区域。 在计算机里面，其实我们本质上所有的存储，
它都是线性的。 那我们来看一下这个数组，它的一个空间的这么一个示意。
对于二维数组来说，其实我们可以就看作一个平面的这种表格结构。
那每一个数组元呢，就是它里面某一个格子。
那就对应到我们，这样一个数组的元素。
那我们如果是三维数组，那你可以想像成一个三维的空间向量。
当然因为我们计算机喜欢就是把这个维度小的，从上面然后再往下面放。
所以我们是这样的一个结构。那我们来看一下，
数组的这个存储表示。
因为在计算机里面，我们必须给它线性化的存储。
所以这些数据，我是这么一行行地来，
从左到右给它摆放呢，还是我们一列列地从上到下摆放呢。 那其实在不同的语言里面有不同的处理方式。
那在c和pascal里面都是行优先存储的。
那所谓行优先呢，其实就是说我一行一行的这样的存放。
那我们来看看这个数组下标的这样一个变化呢。
其实就是说，我们这个下标是从我这几维里面的，
最右那一维开始变，前面呢先固定，
然后变完这一大块以后呢，我们下一大块那我们再变的时候，你可以看到，
我们这时候在变化的呢，就是这个数组维度里面的我们
右边往左边数的这个第二个维度，然后依次去这样变化。
那另外一些呢，就是另外一种变化的规律。
那我们可以看到呢，从这个数组的下标来说，
我首先呢，就是固定的这个右边的几个维度，
然后最开始从最左边，变化起，
然后再接着变左边的这个第二个维度，然后继续往下面变化。 那我们来看，
在c里面呢我们这样一个数组的它的存储位置的计算公式。
那我们知道，数组元素，它每一个这一个元素都是同类型的。
那就是非常整齐划一的，那也就是说我每一个数组元素，
它的这个存储区域大小都是固定的。
假设就是d，那我的整个这个数组，
它的起始元素，就是a01,02,一直到0。
那么这么一个存储地址我也是能获得的。
其实那我们运输这样一个数组的存储地址呢，它返回的那个首地址，
就是这个最前面的，那个a0000元这么一个地址。
然后我们在计算某一个元素的地址的时候，娜假设我们
计算这个j1,j2一直到jn，就是在每维上，
它是有这么一个它的下标值，
那我们计算的时候呢，其实你可以这么来看。 就是说我首地址，
然后再加上d，就是每一个元素的地址。
那再加上它在整个数组里面的一个线性划分的区域。
那在，我们怎么来看这个区域呢？因为我是按照行优先来划分的。
首先我是变化最左边的那一大块。 那我们是分成若干块，
就是这个比如说对于第一这个维度，我们总共有第一个块。
那我们在寻找的时候呢，我首先定义到这个个具体的这一块里。 在我们找这个元素a112的时候，
我首先就是d0块我们越过去，
我们找到的是d1块，
那我就是这个起始的地址呢我们要再加上这里有一整大块，
所以就是加上1乘以d2乘d3，是这个方块里面的元素个数。
然后呢我们在这个块里面呢，我又找到它的第几行。
因为我们是a112，那我们就是第0行第1行。
那找到这一行，这里面行的出现有一行的数据。
所以有呢d3这样一个数值。
然后我再找到这一行里面具体的这个列，
然后这个列我们从它的首位呢开始偏移呢，
是前面有两个，所以我们加上两个这个偏移。
那计算的时候呢就是用这样的方法，
首先分最大的一个块，然后在第二个维度再去分这里面的子块。
在第三个维度，最后到最后那一个维度， 我们再看它的偏移有多少。那，我们有一些特殊的矩阵。
就是比如说像三对角矩阵啊，然后还有像对称矩阵啊这些，
因为我们对稀疏矩阵呢我们有一些特殊的存储。
那我们来看这样一个下三角矩阵，
所谓下三角矩阵，其实对应到我们前面说过的图结构，
那就是我们的这个无项图的存储呢，
其实我就可以只需要一个下三角矩阵或者是上三角矩阵就可以了。
那当然这个它并不对应于无项图啊，
因为这里它在对角线上头有数值。
那我们对这个矩阵呢，我也是可以给他线性化。
哪这个线性化的规律呢，就是我们这个元素i键呢，在线性化里它对应到
这个i平方加i然后括号除以2再加上j这样的一个位置。
那还有像这个对称矩阵
就是我们刚才说的这个无向图的向型矩阵的情况
那我们对这个对称矩阵呢，我也是只需要存一半的这样一个元素，
然后另外一半我可以推算出来， 那，
我们其实在这里，我就是只存它的下三角， 那我也是可以根据它的下标的这样一个对应关系，
可以给它推出来，那我就是要看这个i 和j的一个大小，
那其实这个公式跟前面的下三角公式是相应的。
只是说在这个在i,j不同的时候，我们用不同的这样一个公式来计算。
那还有一些特殊的矩阵，我们像这个矩阵就是一个对角矩阵，
我们有这个三条这个斜线，它这上头有数据，其他的元素呢都是0。 当然你也可以自己定义，比如说你有五条这样的一个斜线。
那，呃，这也是非常有规律的。这，这种矩阵呢，我也可以呃，
给出它的一个相应的呃线性化以后的下标计算公式。
呃，对于稀疏矩阵这样的一种特殊情况，
那我们经常有一些特殊的存储处理。
那所谓稀疏矩阵呢就是，在这样的一个矩阵里面呢，它的非零元呢非常非常少。
呃，那零元是大量存在的。那如果是用这样的一个原来的矩阵去存呢，
那，呃，第一我空间是浪费的， 第二呢我时间还浪费。因为我要在这里面大海捞针一样
去捞出这样的非零元，我要逐个逐个看，
要浪费我很多的这样的计算时间。那，呃，当我们这个呃非零元的比例
在整个矩阵里面只占到不到百分之五的时候呢，我们可以认为
它是一个稀疏的矩阵。对于稀疏矩阵呢，我们往往啊去呃存储它这些
额么非零元，而对零元呢，我抛掉。那我怎么存储呢？显然我就是
拉链。
那有一种呃方法呢，就是三元组的方法。那这种方法，我们往往
只用在输入输出的处理里面。也就是说，我把这些非零元
它的i，j下标我给你表示出来。
那这样就是非常清晰地表示出这个矩阵的 它的这样的一个结构。
现在我们一般不用这种三元组的方法来进行内存的这个组织和计算。
那在内存里面，我们对于这种稀疏矩阵呢，我最常见的一个表示方法 就是十字链的形式。
所谓十字链呢，就是我把它的这个每一行这些非零元呢，我给它串起来。
对每一列的非零元呢，我也给它串起来。那我们每一个这个
元素呢，它既在这个行里面出现，也在列里面出现。
那因此呢，我们对每个元素要存储它的这个 行的下标、列下标以及元素值。
另外呢，我在这个行里面出现和在列里面出现呢，它都会是
有这样的一个链接的信息。所以我们起码是有五个域。
如果你还需要呃往前面找，也就是说，在同一行里面谁是我的
前区，呃，在同一列里面谁是我的这个非零的前区，那我还需要
这个拉双向链。那就是说有四个指针域。那这里我们表达的 是最简单的情况下，只从前往后面去拉链。
那对于这样一个呃矩阵乘法，
我们来看一下稀疏矩阵怎么来表示它。
那我们经典的这个矩阵乘法的话，那就是说，这两个矩阵，假设它们的
呃，这个维度呢是，A矩阵是c1到d1，然后c3到d3。
然后B呢是c3到d3，还有c2到呃d2。
那我们这么一个结果矩阵呢，它就会是c1到d1，然后c2到d2。
那我们这个经典的一个矩阵的乘法呢， 它其实是一个三层的
这么一个循环。这个循环呢就是我们对这个结果矩阵的
每一行每一列，我们对应到这个呃，
A矩阵和B矩阵里面就是A矩阵那里面的
同一行和B矩阵那里面的相应的那一列。
然后我们进行一个叉乘的一个运算。然后我们啊，
把这个结果呢再加到这个
位置上头。那我们呃来看这个稀疏矩阵的表示情况下呢。
那我们呃， 相应的来说呢，我就是，比如说对这个呃结果里面的c[0,0]，
我就是这个A里面的第0行和B里面的第0列。
然后我对应的来相乘，那我们呃这个c[0,0]呢，它得的结果是0。
然后，呃，c[0,1]它得的结果是6。然后我们相应的
这样进行。那我们想象如果是说这个A矩阵很稀疏，然后，
这个B矩阵也很稀疏的情况呢，那我们通过这个稀疏矩阵的一个运算，
用原来在这样的两个数组表示的矩阵运算里面呢，
理论上我们是可以节省一点时间的。当然这是要绝对稀疏的情况下。
那我们看一下它的这样一个时间的分析。那如果这个
A是pxm的矩阵，然后B呢是mxn的矩阵，
那乘得的结果就是pxn的一个矩阵。那呃，
呃，如果是矩阵A里面的这个行向量
它的非零元素是ta。然后，这个呃，
B里面的列向量的这个非零元素呢最多是tb。那我们总的时间
就会是（ta+tb）xpxn。
那如果是这个，呃， ta+tb它比那个m要小很多的情况下，或者说ta+tb 本身就非常非常小，可能就等于几，是相当于一个常数的情况下，
Prof. Ming Zhang 张铭教授
