04 顺序表的基本形式

简介: 04 顺序表的基本形式

图a表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元素)与存储单元大小(c)的乘积计算而得,即:

故,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。

如果元素的大小不统一,则须采用图b的元素外置的形式,将实际数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元素链接的存储位置,而后顺着链接找到实际存储的数据元素。注意,图b中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构。

目录
相关文章
|
存储 设计模式 安全
数据结构 - 2(顺序表10000字详解)
数据结构 - 2(顺序表10000字详解)
41 0
|
存储 Java 开发者
链表(链表数据转换为对象数组)|学习笔记
快速学习 链表(链表数据转换为对象数组)
305 0
|
C语言
C语言中二维数组a[3][4]行列元素互换,存到另一个数组中。
C语言中二维数组a[3][4]行列元素互换,存到另一个数组中。
287 0
|
10月前
指针的基础应用(数组的颠倒和排序,二维数组的表示)
指针的基础应用(数组的颠倒和排序,二维数组的表示)
43 0
|
10月前
|
C语言
【C语言】利用数组处理批量数据(一维数组和二维数组)
【C语言】利用数组处理批量数据(一维数组和二维数组)
104 1
|
10月前
|
算法
顺序表应用4-2:元素位置互换之逆置算法(数据改进)
顺序表应用4-2:元素位置互换之逆置算法(数据改进)
|
10月前
|
C语言
【C语言】数组元素:带方括号的下标形式和指针形式
【C语言】数组元素:带方括号的下标形式和指针形式
133 0
进一步理解指针:一维数组和二维数组转换
先看下列代码的输出是什么? int main() {     int m[5] = { 0,1,2,3,4 };     int* p = (int*)(&m+1);     printf("%d,%d\n", *(m+1), *(p-1));     return 0; } 要知道这个输出,最关键的是要理解指针操作的“加”和“减”,假设有一指针ptr,则“ptr”中的“1”是指ptr所指类型的大小。
815 0
|
C语言
C语言之输出一个二维数组中,求每列最大的元素,并存放在另一个数组中
C语言之输出一个二维数组中,求每列最大的元素,并存放在另一个数组中
190 0
|
存储 算法 Python
数据结构-顺序表的定义及python实现
数据结构-顺序表的定义及python实现
199 0
数据结构-顺序表的定义及python实现