04 顺序表的基本形式

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

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

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

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

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

目录
相关文章
|
9月前
|
C语言
【C语言】利用数组处理批量数据(一维数组和二维数组)
【C语言】利用数组处理批量数据(一维数组和二维数组)
100 1
|
8月前
|
存储 算法 安全
C++一分钟之-数组与指针基础
【6月更文挑战第19天】在C++中,数组和指针是核心概念,数组是连续内存存储相同类型的数据,而指针是存储内存地址的变量。数组名等同于指向其首元素的常量指针。常见问题包括数组越界、尝试改变固定大小数组、不正确的指针算术以及忘记释放动态内存。使用动态分配和智能指针可避免这些问题。示例代码展示了安全访问和管理内存的方法,强调了实践的重要性。
63 3
|
8月前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
|
9月前
指针的基础应用(数组的颠倒和排序,二维数组的表示)
指针的基础应用(数组的颠倒和排序,二维数组的表示)
41 0
|
9月前
|
机器学习/深度学习 算法 C++
C++系列之一维数组内容与应用
C++系列之一维数组内容与应用
|
9月前
|
存储 算法 Java
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
110 0
|
9月前
|
C语言
【C语言】数组元素:带方括号的下标形式和指针形式
【C语言】数组元素:带方括号的下标形式和指针形式
125 0
|
算法
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
数据结构单链表之查找链表的长度(迭代和递归) | 第七套
114 0
|
存储 C++
数据结构单链表之将链表表示的两个数字相加 | 第十四套
数据结构单链表之将链表表示的两个数字相加 | 第十四套
50 0
|
存储 设计模式 安全
数据结构 - 2(顺序表10000字详解)
数据结构 - 2(顺序表10000字详解)
41 0