《小白学数据结构》课件——第四章 数组、串和广义表.pptx
品
T
学数据结构
知识讲堂
主讲教师：
C(
UUL
C(
UUL
C(
UUL
线性数据存储结构
存储逻辑关系为一对
一的数据
存储的数据元素不可分
线性数据存储结构
可以包含多种“一对
一的逻辑关系
存储的数据元素可分
数组
数组的定义
KC(
包含的元素具有“一对一”的逻辑关系
4个序列也具有“一对一”的逻辑关系
数组的定义
28
id4
C
一对一
对一
特点1:数组中的数据元素的数据类型相同
特点2:数组是一种随机存取结构，只要给定一组下标，就可
以访问与其对应的数组元素
特点3:数组中数据元素的个数是固定的
定义：数组是由n(n1)个具有相同数据类型的数据元素ao,a₁,a₂,…,an-1组
成的有限序列，记作A={ao,a₁,a₂,…,an-1}。
数组的定义
UU
U0
一维数组
二维数组
n维数组
C(
数组
一维数组是所有数据元素属于同一类型、固定长度的线性表。
例如，一维数组A是由1,7,9,10,四个数据元素组成，数
组长度就为4,且数据元素都是整型。
数组的定义
C
二维数组中的数据元素是一维数组中
的一维数组
C(
UU
U0
一对一
382d
即即即
al
a2
a3
a4
b2
b3
b4
通用国言用用自准着容信准间自面准
对一
UUL
00
数组的表现形式
C(
例：二维数组的不同表示
二维数组的不同表示形式
(a)m×n矩阵形式表示
(a)m×n矩阵形式表示(b)列向量的一维数组
Am×n=((a₀oa₀1…a₀,n-1),(a₁0a₁…a1,n-1),...,(am-1,0am-1,1…am-1,n-1))
(c)行向量的一维数组
例：二维数组的不同表示
二维数组的不同表示形式
C(
UUL
数组被建立起来，数据元素个数及元素之间
的对应关系就不再发生改变。
C(
顺序存储结构
链式存储结构
UU
U0
C(
UUL
UU
0
数组顺序存储结构特性
无论数组的维度是多少，数组中的数
据类型都必须一致
数组一旦建立，它的维度将不再改变
数组存储结构不会对内部的元素做插
入和删除操作
C(
UU
00
初始化数组
销毁数组
取数组中的元素
修改数组中的元素
C(
常见的
操作
UU
U0
一维数组的存储结构
一维数组的存储结构，采用内存中一段连续的
存储单元进行存储。一维数组
例如，一维数组a[n]={ao,a1,…,an-1}的存储
结构如图所示：
ao
a₁
…
an-1
C(
UU
U0
一维数组的存储结构
对于一维数组a[n],如果给定第一个元素a₀的
存储地址为Loc(a₀),设定每个数据元素所占
的存储单元为k,则一维数组任意数据元素a的
存储单元地址可用公式求出：
Loc(a;)=Loc(ao)+1#k(0≤in)
C(
UU
U0
多维数组的存储结构
以二维数组存储为例说明：
AB
C(
以列序为主序
以行序为主序
一个m行n列的数组Am×n,可以转换成以行
序为主序，和以列序为主序存储结构。
C(
a0.0
a01
·
aon-1
a10
a₁1
…
a₁n-1
…
…
…
·
am-1.0
am-1.1
…
am-1.n-1
UU
U0
二维数组的存储结构
a₀0a₀1…ao,n-1a₁0a₁1…a₁m1aam1,0am-1,1am-1m1
共存储m个一维数组的数据元素
对应任一数据元素的存储单位地址，可以通过这个公式求出：
Loc(aij)=Loc(aoo)+(i*n+j)*k(0≤im,0≤jn)
CC
茶以行序为主序的存储结构
第1行Loc(a;j)
Loc(a。)第0行
第m-1行
共存储n个一维数组的数据元素
对应任一数据元素的存储单位地址，可以通过这个公式求出：
Loc(ai;)=Loc(aoo)+(j*m+i)*k(0≤im,0≤jn)
CC
杂以列序为主序的存储结构
Loc(a)第0列第1列Loc(a;)第m-1列
a0a10am-10Xao1a