文档文本内容
本节内容
顺序表
定义
王道考研/CSKAOYAN.COM知识总览
a a a a a
1 2 3 4 5
王道考研/CSKAOYAN.COM顺序表的定义
设线性表第一个元素
的存放位置是 LOC (L)
内存
LOC 是 location 的缩写
线性表 L
LOC (L)
逻辑结构
a
1
LOC (L)+数据元素的大小
a
2
LOC (L)+2*数据元素的大小
a a a a a a
1 2 3 4 5 3
a
4
顺序表——用顺序存储的方式实现线性表 a
5
顺序存储。把逻辑上相邻的元素存储在物理
位置上也相邻的存储单元中,元素之间的关
系由存储单元的邻接关系来体现。
王道考研/CSKAOYAN.COM
……
每个数据元素所
占空间一样大
线性表是具有相同数据类型的n
(n≥0)个数据元素的有限 序列
ElemType 就是你
的顺序表中存放
的数据元素类型
如何知道一个数据元素大小?
typedef struct { C语言 sizeof(ElemType)
int num; //号数 Eg:
int people; //人数 sizeof(int) = 4B
} Customer; sizeof(Customer) = 8B顺序表的实现 静态分配
——
内存
#define MaxSize 10 //定义最大长度
typedef struct{
a1
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度 a2
}SqList; //顺序表的类型定义(静态分配方式)
a3
a4
Sq:sequence —— 顺序,序列
a5
给各个数据元素分配连
续的存储空间,大小为
MaxSize*sizeof(ElemType)
a a a a a
1 2 3 4 5
王道考研/CSKAOYAN.COM内存
本例中数据元素的
类型(ElemType)
是 int
②把各个数据元素的值
data[0]
设为默认值 (可省略)
data[1]
data[2]
data[3]
①在内存中分配存储顺
② data[4]
序表 L 的空间。包括:
data[5]
data[6] MaxSize*sizeof(ElemType)
③
data[7] 和 存储 length 的空间
data[8]
data[9]
①
length
③将 Length 的值设为0
王道考研/CSKAOYAN.COM内存
②把各个数据元素的值
内存中会 data[0]
设为默认值 (可省略)
有遗留的 data[1]
没有设置数据
“脏数据” data[2]
元素的默认值
data[3]
③
①在内存中分配存储顺
data[4]
序表 L 的空间。包括:
data[5]
data[6] MaxSize*sizeof(ElemType)
① data[7] 和 存储 length 的空间
data[8]
data[9]
length
③将 Length 的值设为0
这种访问方式也不够好, 思考:这一步
是否可省略?
更好的做法是使用基本操
作来访问各个数据元素
王道考研/CSKAOYAN.COM顺序表的实现 静态分配
——
内存
#define MaxSize 10 //定义最大长度
typedef struct{
a1
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度 a2
}SqList; //顺序表的类型定义
a3
a4
给各个数据元素分配连
a5
续的存储空间,大小为
a a a a a
1 2 3 4 5
MaxSize*sizeof(ElemType)
Q:如果“数组”存满了怎么办?
A:可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的)
思考:如果刚开始就声明一个很大的内存空间呢?存在什么问题?
王道考研/CSKAOYAN.COM顺序表的实现 动态分配
——
内存
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义(动态分配方式)
一整片连
续的存储
空间
malloc 函数返回一个指针,
Key:动态申请和释放内存空间
需要强制转型为你定义的
数据元素类型指针
C —— malloc、free 函数
L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);
C++ —— new、delete 关键字
malloc 函数的参数,指明要
分配多大的连续内存空间
王道考研/CSKAOYAN.COM内存
顺序表的实现 动态分配
——
malloc、free
函数的头文件
MaxSize
length
*data
data[0]
data[1]
……
data[9]
*p
data[0]
data[1]
......
data[9]
注:realloc 函数也可实现,但建议初学 ……
者使用 malloc 和 free 更能理解背后过程 data[14]
时间开销大
王道考研/CSKAOYAN.COM顺序表的实现
顺序表的特点:
代码实现:data[i-1];
①随机访问,即可以在 O(1) 时间内找到第 i 个元素。 静态分配、动态分配都一样
②存储密度高,每个节点只存储数据元素
③拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
④插入、删除操作不方便,需要移动大量元素
内存
LOC (L)
a
1
LOC (L)+sizeof(ElemType)
a
2
LOC (L)+2*sizeof(ElemType)
a
3
a
4
a
5
王道考研/CSKAOYAN.COM
……
顺序存储 链式存储
data[0]
存放指针
data[0]
data[1]
data[1]
……
data[9]
data[3]知识回顾与重要考点
动手写一写
理解原理
malloc、free
王道考研/CSKAOYAN.COM