数据结构与算法设计（第二版）课件 第5章数组.pptx

第五章数组

数组—逻辑结构数组是我们很熟悉的一种数据结构，可以把数组看做是线性表的推广。数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。一维数组

二维数组三维数组数组—逻辑结构从小事做起，学会“积累”，学习也是一个积累的过程。使学生明白“积少成多”，能力才能螺旋式上升。

数组—逻辑结构数组的特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，一维数组可以看做是一个线性表；（a1a2…aj…an）二维数组可以看做是“数据元素是一维数组”的一维数组；三维数组可以看做是“数据元素是二维数组”的一维数组。a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……

m行n列的二维数组看成n个列向量的线性表推广：n维数组—每个数据元素受n个关系的约束，每一单个关系，仍是线性关系。也可看成m个行向量的线性表B=(βiβ2β1βm……a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……A=(α1α2…αj…αn)每一个数组元素aij在第i行，第j列，受到两个线性关系的约束，就是行和列关系。数组—逻辑结构

一般来说，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。从数组的特殊结构可看出，数组中的每个元素由一个值和一组下标来描述。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..数组—逻辑结构

由于对数组一般不做插入、删除操作；一旦建立了数组，数据元素个数和元素之间的关系就不再发生变动；采用顺序存储结构表示数组；由于存储单元是一维的结构，而数组是多维的结构，则采用一组连续存储单元存放数组元素就有个次序约定问题。一般有两种存储方式：一是以行为主序(即先行后列)的顺序存放，一行存储完了接着存储下一行。二是以列为主序(即先列后行)的顺序存放，一列存储完了接着存储下一列。数组—存储结构

数组—存储结构第一行第二行第一列第二列第三列a11a12a13a21a22a232×3数组的逻辑状态a11a12a23a21a22a23以行为主序a11a21a12a22a13a23以列为主序

采用以行为主序的方法存放，则存放顺序为：a111，a112，a121，a122，…，a331，a332，a341，…；采用以纵为主序的方法存放，则顺序为：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342。假设有一个3?×?4?×?2的三维数组，共有24个元素。三维数组元素的下标由三个数字表示，即行、列、纵三个方向。A231表示第2行、第3列、第1纵的元素。数组—存储结构

数组的顺序存储是一种随机存取的结构。如果已知多维数组的维数，以及每维的上、下界，就可以方便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出数组中某个数组元素在存储器中的位置。设有m?×?n二维数组Amn，假设下标从1开始，以“以行为主序”的分配为例。设数组中的a11存储地址为Loc(a11)，每个数组元素占据L个地址单元，那么aij的物理地址可计算出来：Loc(aij)?=?Loc(a11)?+?((i?-?1)×n?+?j?-?1)?×?L这是因为数组元素aij的前面有i-1行，每一行的元素个数为n，在第i行中它的前面还有j-1个数组元素。数组—存储结构

同理，可得到三维数组Amnp中任意元素aijk的存储地址的计算公式：Loc(aijk)?=?Loc(a111)?+?((i?-?1)?×?n?×?p?+?(j?-?1)?×?p?+?k?-?1)?×?L数组元素的存储位置是其下标的线性函数，一旦数组下标确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结