数据结构

• 存储对象的集合
• 集合不同的类型有不同的查找方法

抽象数据类型（ADT）

把数据类型和数据类型上的运算捆在一起，进行封装
常用的数据运算：
插入、删除、修改、查找、排序

• 组织基本数据类型
  int， float， chart
• 内存
  连续的存储单元，一个字节会有一个地址标识
  int：4个字节，char：1个字节

顺序表

• 一种数据，相同类型
  Loc[k] = Loc[0]+k*c
• 不同类型
  顺序表存储的是元素地址

顺序表的结构与实现

• 元素存储区的容量
• 当前表中已有的元素个数
  表头+ 数据

一体式结构和分离式结构

顺序表的扩展，分离式比较方便
扩充的两种策略

• 每次增加固定数目，线性增长
• 每次翻倍

顺序表的操作

• 插入

1. 尾端增加元素，时间复杂度O(1)
2. 保证顺序的元素插入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() 返回栈元素个数

队列

特点：

• 一端添加，另一端取
• 先进先出