第7周数组和稀疏矩阵第1讲-数组.pdf

《第7周数组和稀疏矩阵第1讲-数组.pdf》由会员分享，可在线阅读，更多相关《第7周数组和稀疏矩阵第1讲-数组.pdf（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 6.1.1 数组数组的基本概念的基本概念 从从逻辑结构逻辑结构上看上看，一维数一维数组组A是是n（n1）个相同类型数据）个相同类型数据 元素元素a1、 、a2、 、an构成的有限序列，其逻辑表示为：构成的有限序列，其逻辑表示为： A=（a1，a2，an） 其中，其中，ai（1in）表示数组）表示数组A的第的第i个元素。个元素。 一一个个m行行n列的列的二二维数维数组组A可以可以看作是每个数据元素都是相同看作是每个数据元素都是相同 类型的一维数组的一维数组类型的一维数组的一维数组。 由此由此看出，多维数组是线性表的推广。看出，多维数组是线性表的推广。 A= A1，A2，Am A1= a1,1，

2、a1,2，a1,n A2= a1,1，a2,2，a2,n Am= am,1，am,2，am,n A= a1,1a1,2a1,n a2,1a2,2a2,n am,1am,2am,n 数组的基本运算如下：数组的基本运算如下： 数组抽象数据类型逻辑结构基本运算（运算描述）数组抽象数据类型逻辑结构基本运算（运算描述） 将数组将数组的所有元素存储在一块地址连续的内存单元中的所有元素存储在一块地址连续的内存单元中，这是这是 一种一种顺序存储结构顺序存储结构。 6.1.2 数组数组的存储结构的存储结构 几乎所有的计算机语言都支持数组类型，以几乎所有的计算机语言都支持数组类型，以C/C+语言为例，语言为例，

3、其中数组数据类型具有以下性质：其中数组数据类型具有以下性质： 表明一表明一维数维数组具有组具有随机存储特性随机存储特性。 一一维数维数组：一旦组：一旦a1的存储地址的存储地址LOC(a1)确定，并假设每个数据元素确定，并假设每个数据元素 占用占用k个存储单元，则任一数据元素个存储单元，则任一数据元素ai的存储地址的存储地址LOC(ai)就可由以下就可由以下 公式求出：公式求出： LOC(ai)=LOC(a1)+(i- -1)*k(0in) 数组数组a：a1a2a3ai- -1aian 共共i- -1个元素个元素 对于一个对于一个m行行n列的二维数组列的二维数组Am n，存储方式： ，存储方式：

4、 以行序为主序的存储以行序为主序的存储 以列序为主序的存储以列序为主序的存储 a1,1， ，a1,2， ，a1,n 第第1行的元素行的元素 第第2行的元素行的元素 a2,1，a2,2，a2,n 第第m行的元素行的元素 ，am,1，am,2，am,n A= a1,1a1,2a1,n a2,1a2,2a2,n am,1am,2am,n 以行序为主序的存储方式以行序为主序的存储方式 a1,1，a1,2，a1,n，ai,1，ai,2，ai,j-1，ai,j， ai,n， 第第1行的元素行的元素第第i行的元素行的元素 1i- -1行，每行行，每行n个元素，个元素， 计计(i- -1) n个元素个元素 第

5、第i行中，行中，ai,j元素前元素前 有有j- -1个元素个元素 则则ai,j元素前元素前共有共有 (i- -1)n+j- -1个元素个元素 LOC(ai,j)=LOC(a1,1)+(i- -1)n+(j- -1) k 同理可推出在同理可推出在以列序为主序以列序为主序的计算机系统中有：的计算机系统中有： LOC(ai,j)=LOC(a1,1)+(j- -1)m+(i- -1)k 其中其中m为行数为行数。 所以，二维数组所以，二维数组采用顺序存储结构时采用顺序存储结构时，也，也具有具有随机存取特性随机存取特性。 是指给定序号是指给定序号i（下标），（下标），可以可以在在O(1) 的时间内找到相应

6、的的时间内找到相应的元素值。元素值。 同样，多维数组采用顺序存储时具有随机存储特性。同样，多维数组采用顺序存储时具有随机存储特性。 以列序以列序为主序的存储为主序的存储方式方式 6.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵的主要形式有特殊矩阵的主要形式有： 对称矩阵对称矩阵 上三角矩阵下三角矩阵上三角矩阵下三角矩阵 对角矩阵对角矩阵 它们都是它们都是方阵方阵，即行数和列数相同。，即行数和列数相同。 1、对称矩阵对称矩阵的压缩存储的压缩存储 若一个若一个n阶方阵阶方阵Ann中的元素满足中的元素满足ai,j=aj,i（0i，jn- -1），则称），则称 其为其为n阶阶对称矩阵对称矩阵

7、。 ai,i（0in- -1） 主对角线主对角线 ai,j（ij） 下三角下三角 ai,j（ij） 上三角上三角 a0,0a0,1a0,n-1 a1,0a1,1a1,n-1 an-1,0an-1,1an-1,n-1 以以行序为主序存储其下三行序为主序存储其下三角角+主对角线主对角线的元素。的元素。 a0,0，a1,0，a1,1，an-1,0，an-1,1， ，an-1,n-1 B=（b0， b1， b2， ， ，bs） 下三角下三角+主对角线主对角线 a0,0a0,1a0,n-1 a1,0a1,1a1,n-1 an-1,0an-1,1an-1,n-1 n(n+1)/2个元素个元素 ij ai,

8、j bk k = ? k= 当当 ij时（下时（下三角三角+主对角线的元素主对角线的元素） 当当ij时（时（ai,j=aj,i） i(i+1) 2 +j j(j+1) 2 +i B=(a0,0,a1,0,a1,1,ai-1,0, ,ai-1,i-1，ai,0, , ai,j-1, ai,j, , an-1,n-1) 1个个 元素元素 2个个 元素元素 i个元素个元素j个元素个元素 共计共计i(i+1)/2+j个元素个元素 bk n2个个元素元素n(n+1)/2个元素个元素 A0.n- -1,0.n- -1 B0.n(n+1)/2- -1 aij bk k= 当当 ij时时 当当ij时时(ai,

9、j=aj,i) i(i+1) 2 +j j(j+1) 2 +i 对于对于对称矩阵对称矩阵A，采用一维数组，采用一维数组B存储，并提供存储，并提供A的所有的所有 运算。运算。 a0,0a0,1a0,n-1 a1,0a1,1a1,n-1 an-1,0an-1,1an-1,n-1 上三角矩阵：上三角矩阵： 2、 三角矩阵的压缩存储三角矩阵的压缩存储 B=（a0,0,a0,1, , a0,n-1,a1,1, , ai-1,n-1, ,ai-1,i-1, , ai-1,n-1,ai,i, ,ai,j-1,ai,j, ） ai,j bk k= 当当ij时时 当当ij时时 存放常量存放常量c i(2n- -

10、i+1) 2 +j- -i n(n+1) 2 c n个元素个元素n- -1个元素个元素n- -i+1个元素个元素j- -i个元素个元素 共计共计i(2n- -i+1)/2+j- -i个元素个元素 ij 下三角矩阵下三角矩阵 B=（a0,0，a1,0，a1,1，an-1,0，an-1,1， ，an-1,n-1） ai,j bk 存放一个常量存放一个常量c k= 当当 ij时时 当当ij时时 i(i+1) 2 +j n(n+1) 2 a0,0a0,1a0,n-1 a1,0a1,1a1,n-1 an-1,0an-1,1an-1,n-1 c ij 【例例6- -1】若将若将n阶上三角矩阵阶上三角矩阵A

11、按列按列优先顺序压缩存放在一维优先顺序压缩存放在一维 数组数组B1.n(n+1)/2中，中，A中第一个非零元素中第一个非零元素a1,1存于存于B数组的数组的b1中，则中，则 应存放到应存放到bk中的非零元素中的非零元素ai,j（ij）的下标）的下标i、j与与k的对应关系的对应关系 是是。 A. i(i+1)/2+jB. i(i- -1)/2+j C. j(j+1)/2+iD. j(j- -1)/2+i a1,1a1,2a1,n a1,0a2,2a2,n an-1,0an-1,1an,n ij c 按按行行还是按还是按列列 初始下标从初始下标从0还是从还是从1开始开始 1j- -1列的元素个数：列的元素个数：j(j- -1)/2 第第j列列aij之前的元素个数：之前的元素个数：i- -1 k=j(j- -1)/2+i- -1+1= j(j- -1)/2+i 3、对角矩阵对角矩阵的压缩存储的压缩存储 半带宽为半带宽为b的对角矩阵的对角矩阵 b条条 0 0 b条条 AB aij bk 当当b=1时称为时称为三对角矩阵三对角矩阵 其压缩地址计算公式如下：其压缩地址计算公式如下： k = 2i + j 0 0 对角矩阵对角矩阵压缩存储压缩存储 本讲完本讲完