《数据结构》课程教学课件（讲稿，C语言描述）第5章 数组和广义表

第5章数组和广义表数据结构（C描述)

第5章 数组和广义表 数据结构（C描述）

目录5.1多维数组5.23多维数组的存储结构5.3特殊矩阵及其压缩存储5.4稀疏矩阵5.5广义表退出

5.5 广义表 5.1多维数组 5.2 多维数组的存储结构 5.3 特殊矩阵及其压缩存储 5.4 稀疏矩阵 退出 目 录

5.1 多维数组5.1.1多维数组的概念1. 一维数组一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。2. 二维数组二维数组可以看成是向量的推广

5.1 多维数组 5.1.1多维数组的概念 1．一维数组 一维数组可以看成是一个线性表或一个向量（第 二章已经介绍），它在计算机内是存放在一块连 续的存储单元中，适合于随机查找。这在第二章 的线性表的顺序存储结构中已经介绍。 2．二维数组 二维数组可以看成是向量的推广

例如，设A是一个有m行n列的二维数组，则A可以表示为：aooao1aon-1a1oailain-1A=am-1 0am-1 1am-1 n-1在此，可以将二维数组A看成是由m个行向量[XX,,., Xm-JT组成，其中,X-(aio, ail,.,ain-1),0<i<m-1；也可以将二维数组A看成是由n个列向量[yoY,.,yn-]组成,其中 y,-(aoi, aii,..,am-I),O<i<n-

a00 a01 . a0n-1 a10 a11 . a1n-1 . am-1 0 am-1 1 . am-1 n-1 A= 例如，设A是一个有m行n列的二维数组，则A可以 表示为： 在此，可以将二维数组A看成是由m个行向量[X0， X1， .，Xm-1 ] T组成，其中，Xi =( ai0, ai1, .,ain-1 )， 0≤i≤m-1；也可以将二维数组A看成是由n个列向量[y0 , y1 , .,yn-1 ]组成，其中 yi =(a0i, a1i, .,am-1i)， 0≤i≤n-1

由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。3.多维数组同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构

由此可知二维数组中的每一个元素 最多可有二个直接 前驱和两个直接后继（边界除外），故是一种典型的 非线性结构。 3．多维数组 同理，三维数组最多可有三个直接前驱和三个直接后继， 三维以上数组可以作类似分析。因此，可以把三维以上的 数组称为多维数组，多维数组可有多个直接前驱和多个直 接后继，故多维数组是一种非线性结构

5.1.2多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。5.2多维数组的存储结构由于数组一般不作插入或册删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析

5.1.2 多维数组在计算机内的存放 怎样将多维数组中元素存入到计算机内存中呢？由于 计算机内存结构是一维的（线性的），因此，用一维 内存存放多维数组就必须按某种次序将数组元素排成 一个线性序列，然后将这个线性序列顺序存放在存储 器中 。 5.2 多维数组的存储结构 由于数组一般不作插入或删除操作，也就是说，一旦建 立了数组，则结构中的数组元素个数和元素之间的关系 就不再发生变动，即它们的逻辑结构就固定下来了，不 再发生变化。因此，采用顺序存储结构表示数组是顺理 成章的事了。本章中，仅重点讨论二维数组的存储，三 维及三维以上的数组可以作类似分析

多维数组的顺序存储有两种形式：5.2.1行优先顺序1．存放规则行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Amxn二维数组，可用如下形式存放到内存：aoo'aol, ... aon-1' aio' all' ...,， am-10，am-11’ain-lam-ln!。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）

多维数组的顺序存储有两种形式： 5.2.1 行优先顺序 1．存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下 标。具体实现时，按行号从小到大的顺序，先将第一行 中元素全部存放好，再存放第二行元素，第三行元素， 依次类推 . 在BASIC语言、 PASCAL语言、 C/C++语言等高级语言 程序设计中，都是按行优先顺序存放的。例如，对刚才 的Am×n二维数组，可用如下形式存放到内存：a00， a01, . a0n-1，a10，a11，.， a1 n-1，.，am-1 0 ， am-1 1，.， am-1 n-1。即二维数组按行优先存放到内存后，变成了一 个线性序列（线性表）

因此，可以得出多维数组按行优先存放到内存的规律最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。2.地址计算由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其它元素的内存地址？我们可以将它们的地址排列看成是一个等差数列假设每个元素占1个字节，元素a：的存储地址应为第一个元素的地址加上排在a：前面的元素所占用的单元数，而的前面有i行(0~i-1)共iXn个元素，而本行前面又有i个a.元素，故a.的前面一共有iXn+i个元素，设ao的内存地址为LOC(aoo)，则a:的内存地址按等差数列计算为LOC(a.)=LOC(aoo)+（iXn+j）Xl。同理，三维数组Amxnxp按行优先存放的地址计算公式为：LOC(aik)-LOC(aooo)+(iX n X p+j × p+k)Xl

因此，可以得出多维数组按行优先存放到内存的规律： 最左边下标变化最慢，最右边下标变化最快，右边下 标变化一遍，与之相邻的左边下标才变化一次。因此， 在算法中，最左边下标可以看成是外循环，最右边下 标可以看成是最内循环。 2．地址计算 由于多维数组在内存中排列成一个线性序列，因此，若 知道第一个元素的内存地址，如何求得其它元素的内存 地址？我们可以将它们的地址排列看成是一个等差数列， 假设每个元素占l个字节，元素aij 的存储地址应为第一个 元素的地址加上排在aij 前面的元素所占用的单元数，而 aij 的前面有i行(0~i-1)共i×n个元素，而本行前面又有j个 元素，故aij的前面一共有i×n+j个元素，设a00的内存地 址为LOC(a00)，则aij的内存地址按等差数列计算为 LOC(aij)=LOC(a00)+ （ i×n+j ） ×l 。 同 理 ， 三 维 数 组 Am×n×p 按 行 优 先 存 放 的 地 址 计 算 公 式 为 ： LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×l

5.2.2列优先顺序1．存放规则列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时，按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元素，第三列元素依次类推在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前面提到的Amxn二维数组，可以按如下的形式存放到内存：ao’aio.，am-10’ao1’a'即二维数组按列2mao m-!' aim-1' ..,am-I n-!°.优先存放到内存后，也变成了一个线性序列（线性表）

5.2.2 列优先顺序 1．存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下 标。具体实现时，按列号从小到大的顺序，先将第一列 中元素全部存放好，再存放第二列元素，第三列元素， 依次类推 . 在FORTRAN语言程序设计中，数组是按列优先顺序存 放的。例如，对前面提到的Am×n二维数组，可以按如下 的形式存放到内存：a00， a10.， am-10， a01，a11， .， am-1 1，.， a0 m-1，a1m-1，.， am-1 n-1。 即二维数组按列 优先存放到内存后，也变成了一个线性序列（线性表）

因此，可以得出多维数组按列优先存放到内存的规律最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。2.地址计算同样与行优先存放类似，若知道第一个元素的内存地址则同样可以求得按列优存放的某一元素a.的地址对二维数组有：LOC(a;)-LOC(aoo）+(jXm+i)×1对三维数组有LOC(aik)-LOC(aoo0)+(k X m X n+j X m+i) X1

因此，可以得出多维数组按列优先存放到内存的规律： 最右边下标变化最慢，最左边下标变化最快，左边下 标变化一遍，与之相邻的右边下标才变化一次。因此， 在算法中，最右边下标可以看成是外循环，最左边下 标可以看成是最内循环。 2．地址计算 同样与行优先存放类似，若知道第一个元素的内存地址， 则同样可以求得按列优存放的某一元素aij的地址。 对二维数组有：LOC(aij)=LOC(a00）+(j×m+i)×l 对三维数组有： LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×l