第4章数组.ppt

文档介绍：数组(重点)
特殊矩阵的压缩存储
广义表
小结
第4章数组、特殊矩阵和广义表
2017/11/10
1页
本章学习目标
掌握多维数组的概念以及在计算机中的存储表示;
       掌握对称矩阵、三角矩阵、对角矩阵的压缩存储表示及地址运算公式;
        稀疏矩阵在计算机中的存储表示及基本运算的实现;
广义表的逻辑结构和基本运算。
2017/11/10
2页
数组 数组的基本概念
数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据,但属于同一数据类型,比如:一维数组可以看作一个线性表,二维数组可以看作“数据元素是一维数组”的一维数组,三维数组可以看作“数据元素是二维数组”的一维数组,依此类推。
数组的定义:
数组(array)是由下标(index)和值(value)组成的序对集合。
在C语言中,一维数组定义为:
ElemType arrayname[MAXSIZE];
2017/11/10
3页
下图一个m行n列的二维数组。它可以看成是由行向量组成的向量,也可以看成是由列向量组成的向量。
在数组中通常做下面两种操作:
(1)取值操作:给定一组下标,读其对应的数据元素。
(2)赋值操作:给定一组下标,存储或修改与其相对应的数据元素。
a00 a01 … a0,n-1
a10 a11 … a1,n-1
……… aij ………
am-1,0 am-1,1 … am-1,n-1
A=
m行n列的二维数组
与线性表的区别:在数组中不能进行插入、删除数据元素的操作。
2017/11/10
4页
数组的存储结构
一维数组在计算机内是存放在一组连续的存储单元中。因此,数组中任一元素A[i]的存储位置可用下列公式计算:
LOC(A[i])= LOC(A[0])+( i )×L
其中L是每个数据元素所占存储单元的个数。对于一维数组按下标顺序分配即可。
a00 a01 … a0,n-1
a10 a11 … a1,n-1
……… aij ………
am-1,0 am-1,1 … am-1,n-1
A=
m行n列的二维数组
二维数组的存储器,一般有两种存储方式:一是以行为主序的顺序存放,如BASIC、C等程序设计语言,即一行分配完了接着分配下一行。
2017/11/10
5页
C语言中,数组就是按行优先顺序存储的。
如,一个2×3的二维数组A2×3,以行为主序的分配顺序为:a00,a01,a02,a10,a11,a12。
以列为主序分配顺序为:a00,a10,a01,a11,a02,a12
a00 a01 a02
a10 a11 a12
A2×3=
2×3的二维数组
a00
a01
a02
a10
a11
a12
a00
a10
a01
a11
a02
a12
以行为主序
以列为主序
2017/11/10
6页
在C语言中,二维数组定义为:
ElemType arrayname[m] [n];
数组中任一元素A[i][j]的存储位置可用下列公式计算:
LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L
这是因为数组元素A[i][j]的前面有i行,每一行的元素个数为n,在第i行中A[i][j]的前面还有j个数组元素。L仍然是每个数据元素所占存储单元的个数。
例如2×3二维数组:
LOC(a12)= LOC(a00)+[(1)*3+2]* L
a00 a01 a02
a10 a11 a12
A=
2017/11/10
7页
【例4-1】选择题。设二维数组M的每个数据元素占6个存储单元,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要(Ⅰ)个字节;若M按行优先方式存储,元素M[8][5]的起始地址与当M按列优先方式存储时的(Ⅱ)元素的起始地址一致。
(Ⅰ)
(Ⅱ) [8][5] [3][10] [5][8] [0][9]
(1)二维数组M共有(8-0+1)×(10-1+1)=90个数据元素,所以共占 90×6=540个字节,即(Ⅰ)选D.
(2)M[8][5]的存储位置为:
LOC(M[8][5])= LOC(M[0][1])+504
在(Ⅱ):
LOC(M[3][10])= LOC(M[0][1])+504,因此(Ⅱ) 选B.
2017/11/10
8页
在科学与工程计算问题中,矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况,比如常见的一些特殊矩阵,如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。
对称矩阵