数据结构教程李春葆第六版

同学们好，这一节呢，我们来学习数组的顺序存储结构， 那么咱们前面呢，学习了这个数组的抽象数据类型定义，那我们说了，嗯，要是 完成对某一种数据结构的这个操作，必须考虑他是怎么存储的，然后在这个存储结构上来实现他的操作。嗯，那么这个数组呢？我们说，嗯，很少采用链式存储结构， 为什么呢？就是跟数组的特点有关系的，嗯，数组啊，他的这个结构是固定的。结构，固定是什么意思啊？就是元素的个数是固定的，不会忽长忽短，嗯，忽长忽短，嗯，变化呢，也不大，所以呢，哎，我们就不需要链式存储结构了，嗯， 哎，他结构固定到底是几维，每一维有几个元素，嗯，都是固定的。另外呢，就是他的操作呢，嗯，也很少做这个插入和删除操作，嗯，不做这个操作， 哎，不是因为他元素各属固定的啊，元素各属固定的，插入了那么多了一个元素，那，那往哪放呀？是不是？哎，删除了，少了一个元素，那怎么弄啊？是不是？哎，所以我们说， 嗯，既然他的结构固定，行数，列数，嗯，每一维的这个，呃，长度，嗯，长度以及为数都固定了，所以呢，他不做这个插入和删除运算。 那么通常呢，只有，嗯，咱们介绍初始化呀，销毁啊，取某一个元素啊，或者是修改某个元素的值，正因为如此，嗯，正因为如此，咱们一般呢，这个存储 处数组都使用顺序结构来存储，哎，也就是呢，咱们如果用高级语言的话，就是用于这个叫做数组的这种东西来存储，嗯，来存储好了，那我们说数组呢，是可以多为的，嗯，是可以多为的， 二维数组啊，三位数组啊，哎，等等，或者更多维，嗯，更多维。但是呢，咱们存储空间这个内存单元的地址啊， 是一尾的，嗯，一尾的，也就说他的编号呢是线性的，嗯，我们就是从头编到尾，从零号单元一直到最后单元。 哎，那么我们说要存储数组，如果是多维的，那我们怎么把这个多维某一行某一列，嗯，这个他有这个，呃，多维性质的，这个元素怎么映射到这个依维 上去呢？哎，那么接下来咱们就重点来解决这个问题，因为你知道他怎么映射的，你才知道某一个元素到底存储到什么位置了。嗯， 那么首先呢，咱们先从一位数组来看，嗯，从一位数组，一位数组，懂了，那我们就可以理解二位数组，二位数组懂了，那么其他更高位的我们就好理解了。嗯， 好。比如说咱们现在呢，有一个数，因为数组 a 五，那个这个五呢？嗯，这个五呢，就表示他的第一维的长度是五，嗯，长度是五，我们怎么看出来他是一维的呢？ 他只有一个维度，嗯，只有一个。如果我们定义是这样的，有两个，有两个，嗯，比如说 a 三，五，那就表示他是二维的，嗯，他是二维的，第一维长度是三， 二维长度是五，那现在只有一个，那就是一维的长度是五，长度是五，什么意思呢？一共有五个元素，嗯，这五个元素呢是 a 零到 a 四，下边要从零开始，一直到四，是 a 零， 嗯，一直到 a 四，这样的五个元素。嗯，那么现在呢，假设我们现在存储每一个元素呢，需要四个字节， int， 嗯，在三十二为基里头呢，是四个字节，嗯， 存储每个元素需要四个字节。那么咱们这个 a 零元素呢，存储在两千号单元了，那么 a 三存在哪里呢？嗯， a 三的地址是哪里？ 哎，这个呢，咱们前面在学习顺序表的时候已经了解过了，嗯，已经了解过了，那我们再来看一下，那我说这个数组它的特点是什么呢？ 用一片连续的空间连续来存储，嗯，存储第一个元素 a 零之后呢，哎，就接着继续存储 a 一， a 一存储完了之后呢，接着继续存储 a 二，一，直到最后一个元素 a 四， 所以咱们画成示意图的话，就可以画成这个样子，嗯， a 零元素它的地址呢？是两千，嗯，是两千。然后呢，每个元素占四个字节， 那咱们说地址的时候，地址是两千，是表示他占的这一块空间的，嗯，第一个存储单元的，嗯，地址，嗯，那么这个 a 零呢，也就是占了两千到两千零三号这样的四个 的存储单元四个字节，那么那么我们的 a 一，它的地址 值是多少呢？嗯，他的地址是多少呢？哎，我们很容易就推算出来，嗯， a 零的是两千，那么他占据了，嗯，四个，也就是占据了 a 零，嗯，占据了两千，两千零一，两千零二，两千零三，所以 a 一呢，一定是从两千零四开始的， 嗯，同理。 a 二呢，嗯，就是看前面两个，前面两个，嗯，已经占了八个存储单元，嗯，占了八个存储单元，所以呢，他是从两千零八开始的，嗯，两千零八。那咱们 a 三呢？ 嗯，前面有三个元素，这三个元素呢？嗯，三四一十二，占了十二个存储单元，那么第一个在两千，嗯，第一个是两千，所以他一定是从两千这个，嗯，一 十二号，所以 a 三的地址呢？是二零一二，嗯，是二零一二，好，那我们说是这样呢，推算出来，那么任意的一个数组，任意的一个元素，咱们总不能每一个都画一个图，嗯，那我们说这个是怎么做出来的呢？其实很简单，我们只要知道第一个元素的地址， 第一个元素地址在哪？在数组名字里头，嗯，数组名字里头就存储的是第一个元素的地址，然后呢，我们知道每一个元素占多大一块空间，我们用大写 l 来表示的话，嗯，那么某一个元素它的存储位置是多少呢？ 哎，我们要算一下他们前面的所有元素，嗯，这个下标为三的这个元素前面有零一二这三个元素，所以下标为三。 这个元素前面有三个元素，嗯，有三个元素，那么这三个元素三，嗯，乘以四，总共是占了十二个，嗯，十二个存储单元。 然后呢？嗯，我们这个第一个，嗯，第一个是从两千号开始的，所以呢这个三号就是在这么多，嗯，二零 二零一二，他的地址呢？就是二零一二。那我们说任意的一个下标为 i 的元素，那我们怎么算呢？哎，我们首先数出来这个元素前面有多少个啊？前面有多少个元素，前面有多少个元素，那么下标为 i 的 前面呢？就是有 i 个元素，嗯，下标为三的前面有零一二三个元素，下标为四的前面有 零一二三四四个元素，所以我们数出来前面有几个呢？下标为 i 的，前面呢有 i 一个元素，然后呢我们乘上这个 l， 嗯，乘上来每一个元素需要四个字节，这么多元素占用了多少字节？ 然后再加上这个手地址，嗯，手地址加上这个 a 就可以了，这就是我们第二个元素的位置，嗯，第二个元素的位置，所以这个第二个元素存在哪呢？它的位置是， 嗯，前面有 i 个元素，每个元素占这么多，然后呢？再加上这个初始的值，嗯，初始我们从哪个单元开始的？嗯，那么第 i 个元素呢？就存在这个位置，嗯，这就是咱们计算一尾数组的这个任意一个下标为 i 的元 素，他的存储位置。下标，嗯，如果 i 等于零呢，那么他就存在这个，嗯，咱们的数组当中的数组名当中存放的是第一个元素的地址，嗯，哎，如果下标不是零， 其他元素存在哪呢？哎，就存在这里，嗯，就存在这里，这个跟这个一样的，嗯，就咱们推算出来的好了。这是什么呢？这是一维数组，嗯，那么二维数组我们又该怎么存呢？嗯，假设有这样的一个二位数组， 二位数组的特点是什么呢？两位，嗯，若干行，若干列。假如说咱们现在是 m 乘 n， 也就是 m 行 n 列，嗯， m 行，我们总共有 m 行，然后每一行呢有 n 个元素，嗯，有 n 个元素 m 行 n。 那我们说我们这个二位数组呢，可以看成是由若干个一位数组构成的，嗯，比如说，我可以将这个，嗯，二位数组呢看成是由 若干个行所构成的，每一行都是一个一维数组，嗯，每一行都是一个一维数组， 哎，一位数组，然后呢我也可以将它看成呢，是由若干列组成的，嗯，若干列， 哎，若干列，那么每一列呢都又是一个依维数组，嗯，依维数组，我们可以这样来，嗯，看， 所以呢，我们在存这个二维数组的时候就可以有两种方式了，嗯，有两种方式，一种呢是以行有先，我们一行一行的来存，我们先存第一行，再存， 存第二行，然后再存第三行，第四行等等。嗯，这种呢叫做行序为主席，行优先的，嗯，行优先的，哎，很多语言呢都是这种，嗯，包括咱们的 c， 包括这个扎瓦，嗯，都是行优先的， 嗯，行，就先一行一行的来存，存完第一行再存第二行。那么还有一种呢，就是我们一一列一列的来存，嗯，存完第一列，再存第二列，哎，最后存第 n 列，哎，这样的， 哎，这样的。就是以列为右线的，嗯，以列为右线的，好，那么我们咱们来看看啊， 这个以行为优先，以列为优先，他具体是怎么存的，嗯，具体是怎么存？比如说我们这样有若干行，若干列的一个二位数组，以行为优先呢，我们就先，嗯，存储第 一行，然后呢把第二行存在他的后头，然后呢把第三行再继续存在他的后头，这样呢就把二维的，嗯，二维的变成了一个一维的，线性的，嗯，线性的。这样。 那我们说我们要，嗯查找某一个元素，嗯，那我们就要对应的把它相应的位置上，嗯，相应的位置上，那我们怎么知道，嗯，某一个元素，某一个元素他被存到哪里去了呢？嗯，本来这是第一行第二个， 那我们存起来以后，编好号以后，一二三四，因为是线性的了吗？嗯，就没有第二维的，所以就是线性的，一二三四、五六七八这样数，嗯，这样数，哎，九十、十，一十二，那我们这个第二行的第三个元素，嗯， 这个第二行的第三个元素，那么被存在哪一个位置？我们怎么知道这个位置呢？哎，这就是咱们接下来要解决的问题。嗯，好， 这是咱们说的什么呢？嗯，要解的是什么问题呢？存储单元是一个一维的，嗯，一二三四五六这样编号的，嗯，而咱们的数组呢？数组呢？是一个多维的 啊，那我们用一维数组来存储这个多维的数据元素，那我们就有个次序的约定问题，那么这个行序为主，就一行一行的来存，那么同理呢，列序我们就一列一列的来存，存好第一列，然后第二列呢，跟在第一列的后头， 然后第三列再跟在第二列的后头，第四列呢，再跟在第三列的后头，我们是这样来存储的，所以这样呢，也有一个问题，本来 我们现在是，嗯，第三行的这个第一个元素，嗯，用这样的顺序存储了，他会被存在哪里呢？哎，这也是我们要解决的问题。嗯，要解决的问题。好嘞，那么怎么解决这个问题呢？我们来看一下。嗯，我们来看一下。 咱们刚才说了，二位数组呢，可以有两种存储方式，一种是以行序为主，一种是以列序为主。 以行序为主呢，咱们就是一行一行的来存，先存储第一行，然后再来存储第二行，然后再来存储第三行。嗯，所以呢，我们就对应，哎，假如说这个图就是内存，我们先把第一行，嗯，从 a 零零 到 a 零一，一直到 a 零 n 减一。因为总共有 n 列嘛，所以最后一个元素的下标，嗯，是 n 减一，嗯， n 减一。哎，我们把这 n 个元素这一行里头有 n 个元素存上，嗯，存好了以后呢，我们再来存第二行，又是 n 个元素，嗯，又是 n 个元素，再来存第二行，这 n 个元素 从里呢？再来存第三行，第四行，一直到最后一行。最后一行，我们这总共有多少行呢？ m 行，从零到 m 减一。嗯，从零到 m 减一，一共有 m 行，那我们最后呢？哎，再来存储 dm 行， dm 行也是有 n 个元素， 这样呢？嗯， m 乘 n 的，这样的二维就变成了这样的一个线性的一维的，嗯，那么这个一维是多少呢？从零到一共有 m 行 n 列，一共是 m 乘 乘 n， 所以 m 乘 n 减一。嗯， m 乘 n 减一。哎，这样的一个编号。好，这是以行序为主序，那么以列序为主序。那怎么存啊？那就是一列一列的来存，嗯，一列一列，我们先存第一列，嗯，先存第一列， 哎，这一列有多少个元素呢？我们总共有 m 行，所以呢，一共有 m 个元素，嗯，依次把它存进去。 好，那么接下来呢，我们再来存第二列，嗯，再来存第二列，哎，这又是 m 个元素，然后一直一直，总共有多少列呢？总共有 n 列， 最后一列我们存在最后面，嗯，这又是 m 个，总共有 m 乘 n 个元素，嗯，那第一个下标是零的话，那最后一个的下标呢？就是， 哎， m 这个，嗯，最后一个的下标呢？就是 m 乘 n 减一。嗯， m 乘 n 减一。好，这就是咱们列序为主序，嗯，列序优先，那么接下来呢，咱们就来看一下，嗯， 嗯，这个存储的时候，每一个元素，嗯，下标，嗯。为 i g 的那个元素，到底存储到什么位置去了？嗯，到底存储到什么位置去了？比如说我们现在呢要分析一下这个元素， 嗯，这个元素，我们现在呢以行序为主序，一行一行的来存啊，一行一行的来存。那么这一个元素，嗯，下标为 i j 的这个元素， 下标为 r a j 的元素，嗯，哎，这个 a i j， 那么他被存到哪里去了呢？嗯，我们说变成线性的了，嗯，从零号开始，然后一号、二号、三号、四号，哎，这样线性的，嗯，那我们就要假设这个，这个是， 嗯，这个 i g 存储在 d k 号单元了，那么这个 d k 号单元是多少？嗯，这个 d k 号单元是多少。 哎，那我们说这个怎么做呀？其实很简单，嗯，跟刚才一维数组是一样的。一维数组我们是怎么分析的？我们分析当前这个元素，嗯，他之前已经存了多少个元素了， 嗯，那么这一些元素呢，乘上这个 l 就是他总共占了多少空间？然后呢再加上手机纸，嗯，加上手 地址就是他的地址，所以呢咱们这个二维数组呢，也是一样的。嗯，比如说，比如说他，他第一个元素在哪里呢？在两千号单元，两千号单元，然后呢我们依次往里头，嗯，第一个呢就两千零 两千号到两千零四号，第二个两千零五号到两千零八号，哎，继续，嗯，两千零八号到二零一一，二零一三。我们一行一行的来，先把第一行的若干个存好，嗯，然后呢？再来存。第二行的若干个 啊，然后再来存。哎，所以呢，我们只要数清楚，在这个元素之前总共多少个元素啊？总共这是多少个元素？我们把这一块空间加上，嗯， 就可以了，加上就可以了。好，那么在某一个元素之前，他到底有多少个元素呢？我们分两步来算，嗯，首先我们说这个元素之前，我们分析一下总共有几行，嗯，总共有几行， 那么每一行呢？我们说这是 m 行， n 列啊，也是 n 列。 n 列，意思就是说每一行有 n 个元素啊，每一行有 n 个元素，我们用这个行数乘以 n， 就知道前面总共有多少个元素了。嗯，前面总共有多少个元素？ 好，那我们说这个任意一个下标的，比如说 a 二一，那前面有几行啊？前面肯定是有两行，嗯，也就是说，如果这个元素 a i j， 它的下标是 i j 的话，嗯，下标是 i j 的话，那么它前面 总共有多少行呢？总共有 i 行，这 i 行每一行都有 n 个元素，总共就 i 成 n 个元素。嗯，然后我们再数一下，他所在列前面有几个元素，这就是咱们的第二步了。嗯，所在列， 那么下标如果为 j 的话，那么前面有几列呢？前面就有 j 列，也就是有这个元素，这就是下标为 a i j 的这个元素前面总共有多少个元素？ 嗯，下标为 i j 的这个元素前面总共有多少个元素？那么这些元素总共占了多少空间呢？我们用它乘上一个 l， 这就是所占用的，嗯，空间。那我们再用手地址，嗯，第一个元素的地址，再加上他，那么这就是下标为 i j 的这个元素它的位置，所以以行序为主序，嗯，如果第一个元素存储在这，每个元素占用 l 的存储单元的话，那么 a i j 下标为 i j 的这个元素它存在什么位置呢？ 就存在这里，嗯，就是这么算的，就存在这里，那么其中这一部分是什么？就是在 ai 这一前面到底有多少个元素？ 那我们是怎么算呢？分两步，嗯，这个 i 这前面总共有几行？嗯，每一行有 n 个，所以呢？哎，前面总共有 i 行，嗯，前面总共有 i 行， 嗯，每一行有 n 个，所以是 i 乘 n， 嗯，然后呢，它所在的列，它所在的列，它下标是 j 的话，那么它在 j 加 一列，也就是他前面总共有这一列，这一列就是这个元素，嗯，也就是这就算出来了。这个 a i 这前面总共有多少个元素？每一个元素占这么多，总共占了这么一大块空间，哎，那么我们再加上他就可以求出来了，嗯，好，这是咱们 这个计算二维数组当中，嗯，某一个元素它的存储位置在哪里？嗯，那么同理，那么更高维的呢？三维，嗯，我们怎么存呢？嗯，跟二维一样。二维呢？我们是，呃，可以一行一行来存。三维呢？哎，就可以 这个可以一列一列存，三维呢？哎，咱们就可以这样分，嗯，哎，我们首先呢分若干液，不是三维了吗？就是由什么呢？若干个二维数 组构成，每一个二维数组呢，都是有 m 行 n 列，嗯，那么我们这样的呢，总共有 k 个 k 个二维数组，我们就可以理解成这个，嗯，理解成这样，那么其中这个每一维呢？我们可以， 嗯，这个每一个二位数组呢？我们可以理解成有 m 行 n 列啊， m 行 n 列。哎，那么这个总共有多少个呢？ 我们就可以理解成第三围，嗯，第三围。这个第三围呢，我们可以把它称作业，嗯，那么这个，嗯，一张一张的二维表，若干个二维表摞起来了，嗯， 这就是三维，所以三维呢，我们就考虑有三个维度，嗯，三个维度。那么第一第一维总共有多少页呢？从 l 一到 优异。嗯，第二位总共有多少行呢？从 l 二到 u 二。第三位，每一行有几个元素呢？是 l 三到 u 三，嗯， l 三到 u 三。 好嘞，那么在这种情况下我们可以什么呢？哎，我们可以一页一页的来存，嗯，我们一页一页的来存，这是咱们的第一个顺序。 那么美业怎么存呢？我们在行有先一行一行来存，嗯，每一行怎么存呢？哎，我们在一个一个元素从左到右来存， 嗯，这样来存储，这样来存储。那么同理，我们要想知道每一个元素啊，比如说这个元素他到底被存储在什么位置了啊？到底被存储在我们线性当中的什么位置了？我们还是同样的，嗯， 数出来，嗯，在存储的时候，他前面总共存了多少页？嗯，存前面总共存了多少页？哎，然后呢，再数出来他所在的页前面总共有多少行，然后再数出来他所在的行前面总共有多少个 啊？那我们就是这样来计算的，嗯，这样来计算，这就是咱们计算一个三维的三维的数组，嗯，如果他个维的下标是 i 一、 i 二、 i 三的话，那么这一个元素被存在哪里了呢？哎，这就是咱们说的，数出来，他前面，嗯。 i 一，因为这个页的编编号还是从零啊开始的，嗯，所以下边如果是 i 一的话，那前面总共有 i 一页，嗯，每一页都有，嗯，这么多个元素，这么多个元素，哎，我们算出来总共 有多少个元素？同理呢？他所在的页前面总共有挨二行，每一行有这么多个元素，嗯，这么多个元素，哎。再算出来他所在的行前面， 哎，总共有这么多个元素，这就是元素总数，嗯，这就是元素总数。总共有这么多个元素，那么每一个元素我们乘上一个 l， 乘上一个 l， 然后再加上手臂纸，那么如果用指针的话，嗯，那就不用乘 l， 直接就是 他直接移动这么多个，就只到这个元素了，嗯，只到元素了。好，这就是咱们三维的， 那么同理，我们就可以推广到 n 为了，嗯， n 为。那我们说 n 为的计算方法也是一样的，先计算出来，嗯，前 n 减一为，总共有多少个 元素，再加上第 n 为，嗯，他前面有多少个元素，这就是所有的元素个数啊，所有的元素个数，这就是，嗯。再加上这个手地址，这就是咱们这个，嗯。某一个元素他的位置，嗯。他的地址在哪里，嗯，他地址在哪里？ 好了，那么这个具体的公式呢？哎，同学们看一下。理解了，咱们就不详细的讲了，嗯，那么接下来呢，同学们看一个例子，嗯，看一个例子， 哎，我们把这个，嗯。这个元素的位置，嗯，到底在哪里？我们来看一下，嗯，假如说有一个数组， a， m， n， 嗯，这表示什么意思呢？ 就是 m 行 n 列，嗯， m 行 n 列，每一行呢有 n 个元素，总共有 m 行，嗯，那我们按行有弦，一行一行的来存储。 那么假设第一个元素 a 零零，他的存放位置呢？是六四四，嗯，这个地址呢？我们没有用二禁止表示，用的是十禁止表示的。这个角标表是用十禁止表示的，嗯，存储在六四四这号位置这个位置， 那么 a 二二呢？存储在这个六七六这个位置啊，六七六这个位置， 哎，那么请问这个 a 三三被存在哪里了？嗯， a 三三被存在哪里了？哎，好嘞，那咱们分析一下，嗯，咱们分析一下，我们说，嗯，我们说这个 这个二二维的，嗯，二维的，现在呢，要变成一维的，从下边零开始依次去存，嗯，依次去存。好，那我们说，嗯，这个 a 零零，嗯， a 零零被存在六四四了， a 二二被存在这了，那么这个 a 二二前面总共有多少个元素呢？ 嗯，这个 a 二二前面总共有多少个元素呢？哎，如果下标第一个下标是二的话，那么就表示，嗯，有零有一，他前面总共有多少行呢？有两行，嗯，有两行， 那么这两行每一行都有 n 个元素，所以前面总共有二，乘以 n 二 n 个元素， 那么他所在行，嗯，这个这个列坐标，如果是，呃，下标如果是二的话，那就表示他前面有零一两个元素。哎，所以呢，他总共是有这么多个，这么多个，嗯，那我们在 加上六四四，再加上六四四，那么这个就是他的地址，这个等于多少呢？等于六七六， 嗯，等于六七六。那么这样呢，我们算一下，就可以算出来这个 n 的值是多少？ n 的值就是什么每一行有多少个元素，嗯，每一行有多少个元素。好嘞，那我们说我们就这样算的，嗯，哎， 这样算，所以呢，我们就可以算出来 n 等于十五，每一行有十五个元素。那么知道了 n 以后，我们再求 a 三三，那就简单了。嗯，他前面总共有三行，每一行十五个元素， 然后再加上他所在行前面有三个元素，嗯，前面有三个元素，这四十五再加三，嗯，就等于四十八 八。哎，他前面的这些元素总共占了四十八个存储单元，嗯，四十八个，那么再加上手地址是六四四，嗯，手地址是六四四， 所以这个 a 三三存在哪里呢？六四四加上四十八，加上四十八。哎，是多少呢？是六九二， 嗯，六九二。所以呢，咱们这个，嗯， a 三三存储在哪呢？存储在下标为六九二的这个位置，嗯，这个位置。好了，这就是咱们如何计算？嗯，某一个元素他到底存储在哪里？嗯，到底存储在哪里？ 那么这个存储位置的公式呢？嗯，存储位置的公式呢？不需要同学们死 记硬背。嗯，你理解了这个公式从哪里来的？嗯，这个还代表的是什么意义，那你就很容易就算出来了。嗯，你要理解的这个是什么意义，你就很容易能够算出来这个元素在哪里。嗯，不要死记硬背，理解他。 好的，那么这一小节呢，关于这个数组的顺序存储，以及如何来计算数组当中某一个元素的存储位置，咱们就学习到这里。