数据结构-使用C语言 朱战立 第5章数组

1、第第5 5章章 数组数组 1 5.1 数组数组 5.2 动态动态数组数组 5.3 特殊特殊矩阵矩阵的压缩存储的压缩存储 5.4 稀疏稀疏矩阵矩阵的压缩存储的压缩存储 5.1 5.1 数组数组 2 一、数组的定义一、数组的定义 数组：它是数组：它是n（n1)个个相同数据类型相同数据类型的数据元的数据元 素素a0,a1,a2,an-1构成的占用一块构成的占用一块地址连续的地址连续的内存内存 单元的有限序列。单元的有限序列。 数组的下标：数组元素的位置。数组的下标：数组元素的位置。 注意注意 (1)C语言的数组定义下标从语言的数组定义下标从0开始。开始。 (2) 数组的处理相比其它复杂的结构要简单。

2、数组的处理相比其它复杂的结构要简单。 数组中各元素具有统一的类型；数组中各元素具有统一的类型； 数组元素的下标一般具有固定的上界和下界，即数数组元素的下标一般具有固定的上界和下界，即数 组一旦被定义，它的组一旦被定义，它的维数维数和和维界（静态数组）维界（静态数组）就不再就不再 改变。改变。 数组的基本操作比较简单，除了结构的初始化和销数组的基本操作比较简单，除了结构的初始化和销 毁之外，只有存取元素和修改元素值的操作。毁之外，只有存取元素和修改元素值的操作。 (3)一个二维数组可以看作每个数据元素是一个一维数组一个二维数组可以看作每个数据元素是一个一维数组 的一维数组。二维数组是两维的，内存

3、单元是一维的，的一维数组。二维数组是两维的，内存单元是一维的， 存在向内存存储时二维数组中数据元素的存储方法问存在向内存存储时二维数组中数据元素的存储方法问 题，题，C语言采用以行序为主序的方法存储。语言采用以行序为主序的方法存储。 3 问题：数组与线性表的区别与联系问题：数组与线性表的区别与联系 4 相同之处：相同之处： 它们都是若干个相同数据类型的数据元素它们都是若干个相同数据类型的数据元素a a0 0,a,a1 1,a,a2 2, ,，a an-1 n-1 构成的有限序列。构成的有限序列。 不同之处：不同之处： (1)(1)数组要求其元素占用一块数组要求其元素占用一块地址连续的地址连续的

4、内存单元空间，而内存单元空间，而 线性表无此要求；线性表无此要求； (2)(2)线性表的元素是逻辑意义上不可再分的元素，而数组中线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组；的每个元素还可以是一个数组； (3)(3)数组的操作主要是向某个下标的数组元素中存放数据和数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素，这与线性表的插入和删除操作不同。取某个下标的数组元素，这与线性表的插入和删除操作不同。 二、数组的实现机制二、数组的实现机制 5 、一维数组（一维数组（n n个元素）中任一元素个元素）中任一元素aiai的内存单元地址的内存单元地址

5、LOC(aLOC(ai i)=LOC(a)=LOC(a )+i )+i* *k (0k (0i i n)n) 、一个、一个m m行行n n列的二维数组列的二维数组 LOC(aLOC(aij ij)=LOC(a )=LOC(a00 00)+(i )+(i* *n+j)n+j)* *k (0k (0i im， 0 0j jn)n) 注：注：C C语言中数组元素采用行主序的存放方法，即语言中数组元素采用行主序的存放方法，即行优先顺序行优先顺序。 a 的内存单元地址 的内存单元地址 每个元素所需的字节个数每个元素所需的字节个数 每个元素所需的字节个数每个元素所需的字节个数 a 0的内存单元地址 的内存

6、单元地址 一个一个mn的二维数组可以的二维数组可以 看成是看成是m行的一维数组，或行的一维数组，或 者者n列的一维数组。列的一维数组。 a0,0 a0,1 a0,n-1 a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 Amn= 注：只要知道以下三要素便可随时求出任一元素的地址（意义：注：只要知道以下三要素便可随时求出任一元素的地址（意义： 数组中的任一元素可随机存取）数组中的任一元素可随机存取） 开始结点的存放地址（即基地址）；开始结点的存放地址（即基地址）； 维数和每维的上、下界；维数和每维的上、下界； 每个数组元素所占用的单元数每个数组元素所占用的单元数 6

7、 例例软考题软考题：一个二维数组：一个二维数组A A，行下标的范围是，行下标的范围是1 1到到6 6，列下标的范围是，列下标的范围是0 0到到 7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，存储器按字节编址。那么，这个数个字节存储，存储器按字节编址。那么，这个数 组的体积是组的体积是 个字节。个字节。 答：答： Volume=mVolume=m* *n n* *L=(6-1+1)L=(6-1+1)* *(7- 0 +1)(7- 0 +1)* *6=486=48* *6=2886=288 例例 设数组设数组aa60, 60, 7070的基地址为的基地址为20482048，每

8、个元素占，每个元素占2 2个存储单元，个存储单元， 若以行序为主序顺序存储，则元素若以行序为主序顺序存储，则元素a32,58a32,58的存储地址的存储地址 为为 。 答：根据行优先公式答：根据行优先公式 LOC(aLOC(aij ij)=LOC(a )=LOC(a00 00)+(i )+(i* *n+j)n+j)* *k (0k (0i im，0 0j jn)n) 得：得：LOC(aLOC(a32,58 32,58)=2048+(32 )=2048+(32* *70+58)70+58)* *2 266446644 288 三、三、数组抽象数据类型数组抽象数据类型 7 数据集合：数据集合： a

9、0,a1,a2,an-1 每个数据类型为抽象数据元素类型每个数据类型为抽象数据元素类型 操作集合操作集合: :(1)(1)求求数组元素个数数组元素个数 ArrayLength(D)ArrayLength(D) 函数返回数组函数返回数组D D的元素个数的元素个数 (2) (2)存数组元素存数组元素Storage(D,i,x)Storage(D,i,x) 把数据元素把数据元素x x存入下标为存入下标为i i的数组的数组D D中，其约束条件中，其约束条件 为为0=i=ArrayLength(D)-10=i=ArrayLength(D)-1 (3) (3)取数组元素取数组元素Get(D,i,x)Get

10、(D,i,x) 取出下标为取出下标为i i的数组的数组D D中的元素赋给参数中的元素赋给参数x x，其约束，其约束 条件为条件为0=i=ArrayLength(D)-10=i=ArrayLength(D)-1 5.2 5.2 动态数组动态数组 8 一、动态数组的设计方法一、动态数组的设计方法 1 1、动态数组的概念、动态数组的概念 动态数组：它是在需要存储单元空间时才给出数组的具体动态数组：它是在需要存储单元空间时才给出数组的具体 个数。个数。 C C语言提供的支持函数有：语言提供的支持函数有： malloc( )malloc( )、calloc( )calloc( )、free( )free

11、( ) 例例5-15-1定义有定义有1010个元素的整数类型一维数组个元素的整数类型一维数组a a，先分别给，先分别给 数组元素赋数据数组元素赋数据1,21,2，1010，然后显示数组中的数值，然后显示数组中的数值 9 例：编写一个定义和使用二维例：编写一个定义和使用二维3 3行行4 4列动态列动态 数组的一个完整程序。数组的一个完整程序。 10 11 二、动态数组和静态数组对比二、动态数组和静态数组对比 12 1 1、从使用方法上来说，动态数组和静态数组除向系统申、从使用方法上来说，动态数组和静态数组除向系统申 请内存空间的方法不同外，数组的使用方法完全相同。请内存空间的方法不同外，数组的使

12、用方法完全相同。 静态数组采用数组定义语句向系统申请内存空间；静态数组采用数组定义语句向系统申请内存空间； 动态数组采用函数动态数组采用函数malloc( )malloc( )来向系统申请内存空间。来向系统申请内存空间。 2 2、从性能上来说，静态数组必须确切指定数组元素个数，、从性能上来说，静态数组必须确切指定数组元素个数， 这样的指定在程序运行后不能改变；动态数组虽然也这样的指定在程序运行后不能改变；动态数组虽然也 要确切指定数组元素个数，但因为这样的指定是在程要确切指定数组元素个数，但因为这样的指定是在程 序运行时通过调用函数实现的，可以改变其元素个数。序运行时通过调用函数实现的，可以改

13、变其元素个数。 5.3 5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵特殊矩阵: :指有许多值相同的元素或有许多零元指有许多值相同的元素或有许多零元 素、且值相同的元素或零元素的分布有一定规素、且值相同的元素或零元素的分布有一定规 律的矩阵。律的矩阵。 特殊矩阵的存储方法：只存储特殊矩阵中数值不特殊矩阵的存储方法：只存储特殊矩阵中数值不 相同的数据元素。相同的数据元素。 读取被压缩掉矩阵元素的方法：利用特殊矩阵压读取被压缩掉矩阵元素的方法：利用特殊矩阵压 缩存储的数学映射公式找到相应的元素缩存储的数学映射公式找到相应的元素 13 14 1 1、n n阶对称矩阵阶对称矩阵 在一个在一个n

14、 n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： a aij ij=a =aji ji （1i,jn1i,jn）注意：矩阵下标从注意：矩阵下标从1 1开始开始 则称则称A A为为n n阶对称矩阵。如下图是一个阶对称矩阵。如下图是一个5 5阶对称矩阵。阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 an2 an3 a nn 对称矩阵 n n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上

15、三 角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样， 能节约近一半的存储空间。不失一般性，我们按能节约近一半的存储空间。不失一般性，我们按“行优先行优先顺序顺序”存储主存储主 对角线（包括对角线）以下的元素。对角线（包括对角线）以下的元素。 15 i(i-1)/2+j-1 i(i-1)/2+j-1 当当i ij j j(j-1)/2+i-1 j(j-1)/2+i-1 当当i ij j k= 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i i个元素，元素总数为个元素，元素总数为n(n+1)/2n(n+1

16、)/2，这，这 样就可将样就可将n n2 2个数据元素压缩存储在个数据元素压缩存储在n(n+1)/2n(n+1)/2个存储单元中。个存储单元中。 假设以一维数组假设以一维数组vava作为作为n n阶对称矩阵阶对称矩阵A A的压缩存储单元，的压缩存储单元，k k为一维数组为一维数组vava 的下标序号的下标序号，a aij ij为 为n n阶对称矩阵阶对称矩阵A A中中i i行行j j列的数据元素列的数据元素( (其中其中1i,jn 1i,jn ），）， 其数学映射关系为：其数学映射关系为： 例题：已知数组例题：已知数组A88A88为对称矩阵，数组下标从为对称矩阵，数组下标从0 0开始存储，其中

17、每一开始存储，其中每一 个元素占个元素占5 5个单元。现将其下三角部分按行优先次序存储在起始地址为个单元。现将其下三角部分按行优先次序存储在起始地址为 100100的连续的内存单元中，则元素的连续的内存单元中，则元素A45A45对应的地址为多少？对应的地址为多少？ K=K= j(j-1)/2+i-1 j(j-1)/2+i-1 元素元素A45A45存储在矩阵中应该是存储在矩阵中应该是A56A56 i=5,j=6 k=(6-1)6/2+5-1=19i=5,j=6 k=(6-1)6/2+5-1=19 1919* *5+100=1955+100=195 16 2 2、n n阶三角矩阵阶三角矩阵 以主对

18、角线划分，以主对角线划分， n n阶三角矩阵有阶三角矩阵有n n阶上三角矩阵和阶上三角矩阵和n n阶下三角矩阵两阶下三角矩阵两 种。种。 n n阶上三角矩阵如图阶上三角矩阵如图5.2(a)5.2(a)所示，它的下三角（不包括主对角线）中所示，它的下三角（不包括主对角线）中 的元素均为的元素均为0 0（或常数）。（或常数）。n n阶下三角矩阵正好相反，它的主对角线上方均阶下三角矩阵正好相反，它的主对角线上方均 为为0 0（或常数），如图（或常数），如图5.2(b)5.2(b)所示。所示。 注：在大多数情况下，注：在大多数情况下， n n阶三角矩阵常数为零。阶三角矩阵常数为零。 a11 a12 a

19、 1n a11 c c c a22 a 2n a21 a22 c . c c a nn an1 an2 an n (a) (a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵 图图5.2 5.2 三角矩阵三角矩阵 17 i(i-1)/2+j-1 i(i-1)/2+j-1 当当i ij j n(n+1)/2 （或空）（或空） 当当i imd = da.nd; /db-md = da.nd; /* *行数值转为列数值行数值转为列数值* */ / db-nd = da.md; /db-nd = da.md; /* *列数值转为行数值列数值转为行数值* */ / db-td = da.td;d

20、b-td = da.td;/ /* *非零元个数不变非零元个数不变* */ / if (da.td=0)if (da.td=0)return;return; elseelse q = 0;q = 0; / /* *q q为为b-list b-list 的下标值的下标值* */ / for (v=1;v=da.nd;v+) for (v=1;v=da.nd;v+) for(p = 0; p da.td; p+)/ for(p = 0; p listq.i = a.listp.j; / b-listq.i = a.listp.j; /* *列号转为行号列号转为行号* */ / b-listq.j = a.listp.i; / b