扫码获取更多资源

●数组的顺序表示及操作实现

数组一般不做插入或删除操作。也就是说，一旦建立了数组，结构中的元素个数和元素 之间的关系就不再发生变动。因此，数组一般采用顺序存储的方式。

●数组顺序表的定义

数组的定义

把数组中的元素按照逻辑次序依次存放在一组地址连续的存储单元里的方式称为数组 的顺序存储结构，采用这种存储结构的数组称为数组顺序表(Array Sequential List) o

一维数组

一维数组(a。，少,…，a。—Q由n个元素组成，每个元素除具有相同类型的值外，还有一个 下标以确定元素的位置，显然一维数组就是一个线性表。一维数组在计算机内是存放在一 块连续的存储单元中，适合于随机查找。

一维数组(a。，…，有―)由n个元素组成，如果数组的每个元素占L个存储单元且从 地址A开始依次分配数组各元素，则数组A中任一元素街的存储地址可以由式(5-1)表示

二维数组的顺序存储

二维数组的每个元素含有两个下标，需要将二维关系映射为存储器的一维关系。常用 的映射方法有两种：按行优先和按列优先。例如,C/C++中的数组采用的是按行优先存储 方式,FORTRAN、PASCAL中的数组釆用的是按列优先存储方式。

(1)按行优先存储方式

按行优先存储方式是指先行后列，先存储行号较小的元素，行号相同者先存储列号较小 的元素。如果每个元素占L个存储单元且从地址A开始依次分配数组中各元素，则数组A 中任一元素a；J的存储地址可以由式(5-2)表示

按列优先存储方式

按列优先存储方式是指先列后行，先存储列号较小的元素，列号相同者先存储行号较小 的元素。如果每个元素占L个存储单元且从地址A开始依次分配数组各元素，则数组A 中任一元素ab的存储地址可以由式(5-3)确定，其分配情况如图5-4所示。

LOC(ajj) =LOC(a00) + (bL X j + i) X L (5-3)

其中：ie[0, b| — l],j£[O, b2-l]5 b.是数组A第一维的长度，b2是数组A第二维的长 度；LOC(aij)是的存储地址；LOC(aoo)是a。。的存储地址，即二维数组A的基地址。

第0列 第1列 第j列

300 … ％-1,0 301 … abl-l,l 刽 … ％ •- abi-l,b2-l

LOC(a()o) (b】xj+i)个元素 LOC^)

图5-4二维数组按列优先存储分配

多维数组的顺序存储

对于n(n>2)维数组，一般也釆用按行优先和按列优先两种存储方法。按行优先存储 的基本思想是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标 再变，……，最后是最左下标。按列优先存储的基本思想恰好相反：最左边的下标先变化， 即最左下标从小到大，循环一遍后，左边第二个下标再变，……，最后是最右下标。

设n维数组A第k维(iVkWn)的下标范围是[0,垃一1],如果每个元素占L个存储 单元且从地址A开始依次分配数组各元素，则数组A中下标为L j、・・・、jn的元素的按行优 先存储地址可以由式(5-4)确定。

联系我们：