文档介绍：数据结构 数组
第一页，共38页
● 数组的基本概念
数组可以看成是线性表的一种扩展，表中的元素本身也是一种数据结构，但所有的元素都属于同一类型。
第二页，共38页
● 数组的定义及逻辑结构
例如：二维数组可以看成“数组元素是一维数组”的一维数组，三维数组可以看成“数组元素是二维数组”的一维数组，依次类推。一个m行×n列的二维数组。
a11
a12
…
a1n
a21
a22
…
a2n
…
…
…
…
am1
am2
…
amn
Am×n＝
第三页，共38页
数组是一个固定格式和数量的数据有序列，每个数组元素用惟一的一组下标标识。
数组的基本操作:
⑴取值操作：给定一组下标，读其对应的数组元素。
⑵赋值操作：给定一组下标，存储或修改与其相对应的数组元素。
● 数组的定义及逻辑结构
第四页，共38页
● 数组的顺序存储结构
在内存中,数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
对于一维数组按下标顺序分配即可。
对于多维数组的分配，要把它的元素映像在一维存储器中，一般有两种存储方式，即“以行(序)为主(序)”的映象方法和“以列(序)为主(序)”的映象方法。
“以行为主”的存储结构: 将数组中的数据元素“按行依次排放”在存储器中；
“以列为主”的存储结构: 将数组中的数据元素“按列依次排放”在存储器中。
第五页，共38页
● 数组的顺序存储结构
LOC(A1 (1) )=LOC(a11)
a11
a12
…
a1n
LOC(A2 (1) )=LOC(a21)
a21
a22
…
a2n
…
LOC(Am(1) )=LOC(am1)
am1
am2
…
amn
LOC(A1 -(1) )=LOC(a11)
a11
a21
…
am1
LOC(A2 -(1) )=LOC(a12)
a12
a22
…
am2
…
LOC(An-(1) )=LOC(a1n)
a1n
a2n
…
amn
A1 (1)
A2 (1)
Am(1)
A1 -(1)
A2 -(1)
An -(1)
(a) 以行为主序
(b) 以列为主序
第六页，共38页
由下标计算数组元素的存储位置:
假设每个数据元素占L个存储单元
⒈ 一维数组A(n)
任意元素ai的存储位置
LOC(ai)=LOC(a0)+i*L /*假设数组下标界从0开始*/
第七页，共38页
● 数组的顺序存储结构
⒉ 二维数组A(m×n)
一个2×3的二维数组，其逻辑结构和内存映像如下。
a11
a12
a13
a21
a22
a23
2×3数组的逻辑结构
a11
a12
a13
a21
a22
a23
a11
a21
a12
a22
a13
a23
以行为主序内存映像
以列为主序内存映像
第八页，共38页
假设二维数组 A[m][n] 中每个数据元素占L个存储地址，并以 LOC(aij) 表示下标为 (i,j) 的数据元素的存储地址，则数据元素在“以行为主”的顺序映象中的存储地址为：
LOC(aij) =
在C语言中，数组中每一维下标界定义为0，则
LOC(aij) = /*假设数组下标界从0开始*/
● 数组的顺序存储结构
LOC(a11) + ((i-1)*n+j-1)*L /*假设数组下标界从1开始*/
LOC(a00) + (i*n+j)*L
第九页，共38页
*
练****br/>已知二维数组A[1..3,1..5]的存储首地址为100，它采用以行为主的顺序存储，且每个元素占用4个字节
LOC (a2，4 )=
100+[（2-1）*5+4-1]*4
= 132
第十页，共38页