- 存储对象的集合
- 集合不同的类型有不同的查找方法
抽象数据类型(ADT)
把数据类型和数据类型上的运算捆在一起,进行封装
常用的数据运算:
插入、删除、修改、查找、排序
- 组织基本数据类型
int, float, chart - 内存
连续的存储单元,一个字节会有一个地址标识
int:4个字节,char:1个字节
顺序表
- 一种数据,相同类型
Loc[k] = Loc[0]+k*c - 不同类型
顺序表存储的是元素地址
顺序表的结构与实现
- 元素存储区的容量
- 当前表中已有的元素个数
表头+ 数据
一体式结构和分离式结构
顺序表的扩展,分离式比较方便
扩充的两种策略
- 每次增加固定数目,线性增长
- 每次翻倍
顺序表的操作
- 插入
- 尾端增加元素,时间复杂度O(1)
- 保证顺序的元素插入O(n)
3.非保序的元素插入O(1)
*删除
python中的顺序表
List 特征
- 按下标位置索引 O(1)
- 任意加元素,分离式存储,表头不变
- 空列表,8个元素存储区
- 4倍增长达到一定阈值后2倍增长
链表
将元素存放在通过链接构造起来的一系列存储块里
特点:可以充分利用计算机空间,实现灵活的内存动态管理
链表的实现
元素 = 数据区+链接区
单向链表
单链表的操作
python中地址表示
python中声明的变量,保存的是地址
栈
特点:
- 只能在一端(top)输入(push)和输出(pop)
- 先进后出
栈结构的实现
栈的操作:
- Stack() 创建一个新的栈
- push(item) 添加一个新的元素item到栈顶
- pop() 弹出栈顶元素
- peek() 返回栈顶元素
- is_empty() 判断栈是否为空
- size() 返回栈元素个数
队列
特点:
- 一端添加,另一端取
- 先进先出
网友评论