顺序存储结构-《计算机导论》简明指南

2023-11-18 理论教育版权反馈

【摘要】：顺序存储结构就是先向系统申请一块地址连续的存储单元，然后把数据按照某种次序存入这块内存单元的相应位置中。顺序存储结构的最大优点是使用方法简单，最大缺点是必须预先分析估计出所需定义数组的最大个数。

顺序存储结构就是先向系统申请一块地址连续的存储单元，然后把数据按照某种次序存入这块内存单元的相应位置中。

所有高级语言都支持数组，在8.2.2节中曾讨论过，数组是一种构造数据类型，数组是相同数据类型的集合。在使用高级语言的程序设计中，定义一个数组要求具体给出该数组的数据类型和大小。在高级语言程序编译时，如果用户定义了数组，系统将分配用户希望的内存单元空间给相应的运行程序，这样该程序在运行时，就可以把数据存放在这些内存单元中。

例如，下面的C语言语句就定义了一个int数据类型，包括100个数据元素的数组v。

int v[100]

数组的数据类型不仅可以是基本数据类型，也可以是任何一个用户自己定义的结构体类型。例如，下面的C语言语句就首先定义了图书管理软件设计需要的结构体数据类型，然后定义了该结构体类型的包括1000个数据元素的数组b。

struct book

{

char bookNo[20]； //书号

char bookName[40]；书名

char authorName[10]；作者名

int status； //状态

}；

book b[1000](www.chuimin.cn)

定义数组时之所以需要给出数组元素的数据类型和大小个数，是因为数据类型确定了每个数据元素需要占用的内存空间大小（即字节个数），系统为用户程序数组分配的内存空间大小是：每个数组元素需要占用的内存空间乘以数组总个数。

系统分配给用户程序数组的内存首地址由数组名指示。这样，有了数组在内存中的首地址和每个数组元素占用的内存字节个数，系统就可以计算出任意一个数组元素在内存中的地址。例如，已知int为4个字节，系统为上述数组v分配的内存首地址是1000，则第一个数组元素v[0]的内存地址就是1000，v[10]的内存地址就是1000＋4*10＝1040，最后一个数组元素v[99]的内存地址就是1000＋4*99＝1396。数组v的内存示意图如图8-5所示。

图8-5 数组Ⅴ的内存示意图

设系统为数组a分配的内存首地址为a0，数组的下标起始序号从0开始计数，每个数组元素占用的字节个数为k，则数组a中第i个数组元素的内存单元地址计算公式如下：

a[i]的内存地址＝a0＋i*k

我们在8.1节讨论了图书管理问题，图书管理问题的数据模型是一个线性表，线性表的顺序存储结构是使用一个数组存储所有线性表元素。图书管理问题线性表的数组定义方法是：

（1）定义图书管理问题要使用的数据元素结构体，如前面定义的结构体book。

（2）分析估计实际可能的最大图书数量，设最大图书数量为m。

（3）定义数据类型为book、个数为m的数组a。

这样，在程序运行时，首先把已有的所有图书的数据元素调入内存，然后根据用户需要进行图书数据元素的插入、删除、修改等操作。

顺序存储结构的最大优点是使用方法简单，最大缺点是必须预先分析估计出所需定义数组的最大个数。如果估计的数组的最大个数大大超过实际使用的数据元素个数，将造成内存资源的浪费；如果估计的数组的最大个数小于实际使用的数据元素个数，将导致程序运行失败。