- 存儲對象的集合
- 集合不同的類型有不同的查找方法
抽象數據類型（ADT）
把數據類型和數據類型上的運算捆在一起，進行封裝
常用的數據運算：
插入、刪除、修改、查找、排序
- 組織基本數據類型
int， float， chart - 內存
連續(xù)的存儲單元，一個字節(jié)會有一個地址標識
int：4個字節(jié)，char：1個字節(jié)
順序表
- 一種數據，相同類型
Loc[k] = Loc[0]+k*c - 不同類型
順序表存儲的是元素地址
順序表的結構與實現
- 元素存儲區(qū)的容量
- 當前表中已有的元素個數
表頭+ 數據
一體式結構和分離式結構
順序表的擴展，分離式比較方便
擴充的兩種策略
- 每次增加固定數目，線性增長
- 每次翻倍
順序表的操作
- 插入
- 尾端增加元素，時間復雜度O(1)
- 保證順序的元素插入O(n)
3.非保序的元素插入O(1)
*刪除
python中的順序表
List 特征
- 按下標位置索引 O(1)
- 任意加元素，分離式存儲，表頭不變
- 空列表，8個元素存儲區(qū)
- 4倍增長達到一定閾值后2倍增長
鏈表
將元素存放在通過鏈接構造起來的一系列存儲塊里
特點：可以充分利用計算機空間，實現靈活的內存動態(tài)管理
鏈表的實現
元素 = 數據區(qū)+鏈接區(qū)
單向鏈表
單鏈表的操作
python中地址表示
python中聲明的變量，保存的是地址
棧
特點：
- 只能在一端（top）輸入（push）和輸出（pop）
- 先進后出
棧結構的實現
棧的操作：
- Stack() 創(chuàng)建一個新的棧
- push(item) 添加一個新的元素item到棧頂
- pop() 彈出棧頂元素
- peek() 返回棧頂元素
- is_empty() 判斷棧是否為空
- size() 返回棧元素個數
隊列
特點：
- 一端添加，另一端取
- 先進先出
