手撕408|数据结构之顺序表(2)

通知：冷月目前提供免费408 1对1辅导，有需要的同学可以加我微信：lengyue408。  

“ 顺序表其实就是数组，其逻辑上连续，物理上也要连续。”

手撕408系列之数据结构之顺序表，冷月出品必是精品，大家好，我是学长冷月。

补充：线性表

在介绍顺序表之前，首先需要补充一下线性表的相关知识。之前我们有讲过，在学习一个新的数据结构时，要从它的三要素入手。

逻辑结构

定义：具有相同数据类型的n个（n≥0）数据元素的有限序列。

除了表头元素之外（第一个元素），有且仅有一个直接前驱；除表尾元素（最后一个元素）之外，有且仅有一个直接后继。满足这样定义的一个数据结构称为线性表。

物理结构

顺序存储：顺序表。线性表采用顺序存储，又叫顺序表（数组）

链式存储：链表。线性表采用链式存储，又叫链表。

顺序表

在补充完线性表的相关知识后，我们知道顺序表其实就是线性表的一种物理(存储)实现方式，是一种物理结构，那么我们对它下一个定义。

定义：顺序表也就是数组，用一组地址连续的存储单元依次存放数据元素。逻辑上相邻，物理上也相邻。

顺序表的实现

1、静态分配：直接静态定义一个数组，其结构体定义如下图：

2、动态分配：在C语言中是利用malloc函数，在堆中分配一组地址连续的空间，其结构体定义如下图：

C语言实现法：

首先利用malloc函数来动态分配空间：(ElemType * )malloc(sizeof(ElemType)  * InitSize)，再讲data指向这片空间完成定义。

特点

1、地址连续（系统分配的内存空间地址连续）

2、随机存取（数组可以利用下标进行随机存取，时间复杂度为O(1)）

3、顺序存储（每一个元素按照顺序依次存储）

明天别忘了来打卡！

关注下方“学长冷月”可获得更多408答题技巧及资料。

请帮冷月点一下旁边的在看，再点一个赞,一键三连支持一下！您的每一次点击都是对冷月莫大的鼓励，谢谢！！

点“在看”给我一朵小黄花