数据结构与算法基础——第02周-线性表的顺序表示和实现(2.4.1)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 线性表的顺序存储表示

  • 线性表的顺序表示又称为顺序存储结构或顺序映像
  • 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
  • 简言之，逻辑上相邻，物理上也相邻
  • 线性表的第1个数据元素a1的存储位置，称作线性表的起始位置或基地址
1
2
3
线性表：(a1,a2,...ai-1,ai,ai+1,...,an)
        |  |      |   |    |      | 
数组：  a1,a2,... ai-1,ai,ai+1,...an

二 顺序存储结构

2.1 线性存储结构示例

线性表(1,2,3,4,5,6)的存储结构表示如下：

1 2 3 4 5 6
说明：
  • 上图是一个典型的线性表顺序存储结构
  • 依次存储，地址连续——中间没有空出存储单元

2.2 非线性存储结构

1 2 3 4 5 6

说明：

  • 上图不是一个线性表顺序存储结构
  • 地址不连续——中间存在空的存储单元

2.3 总结

  • 线性表顺序存储结构占用一片连续的存储空间。
  • 知道某个元素的存储位置就可以计算其他元素的存储位置

三 顺序表中元素存储位置的计算

3.1 问题提出

a1 a2 ... ai-1 ai ai+1 ... an

如果每个元素占用8个存储单元，ai存储位置是2000单元，则ai+1存储位置是？2008单元

3.2 说明

假设线性表的每个元素需占L个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系

LOC(ai+1)=LOC(ai)+L

有此，所有元素的存储位置均可由第一个数据元素的存储位置得到

LOC(ai)=LOC(ai)+(i-1)xL

其中，LOC(ai)是基地址