1.专题 存储结构和逻辑结构
1. 存储结构
软件完成对象抽象，需要分配一定的内存资源。
根据对象对内存使用的特征，可以把数据存储的特征划分为：
- 顺序存储
- 链接存储
- 索引存储 和 散列存储
1.1 顺序存储
对象占用的资源表现为一段连续的内存存储
图示如下：
MAX_SIZE表示数组容量
ele_lenth 表示元素个数
1.2 链接存储
对象占用的内存资源表现为一段内存和另一段内存单点间的链接
图示如下：
单向(循环)链接，左侧节点为 FIRST
双向链接，左侧为left end，右侧为right end
只包含有一个节点的链表存储
1.3 索引存储
[table]是一个指针数组，容量使用[MAX_SIZE]表示
指针表中有效指针个数表示为[lenth]
比如下图：
1.4 散列存储
散列映射特征值/关键字 为一个整形数字：pos
pos表示一个指针数组的索引号，该指针可能指向一个数组，一个链表或其他数据结构：如果用户要求的数据存在，那么就应该存储在这个数据结构里
1.4.1 散列+箱子
示例：68或者88作为key，pos计算出来都是8;
hash table取出index为8的表项，这个结构体中可能存储着key68或者key 88的数据；
如果对应的结构体，key字段是88，那么就是key 88需要的数据。
但是因为箱子当中只能存储一个数据，这样key 68应该存储在哪里呢？我们定一个规则：当没有位置存放key68时，把key68存放到紧邻的下一空表项
- 查找
f(key)计算pos，查看pos是否命中直到：
01表项key 命中
02表项未命中，向下查找，找到空表项，返回没有元素
03表现回到pos，返回没有元素 - 添加
f(key)计算pos，查看pos是否被占用直到：
01 表项没有被占用 ，写入数据（返回成功）
02 表项已经被占用，写入下一个空表项（返回成功）
03 没有找到空表项，返回溢出状态
1.4.2 散列+链表
示例：使用key68或者key88计算出pos = 8，那么如果两个key的数据存在，一定存在于pos = 8的链表上
1.5 总结
对象内存 的 存储结构是设计对象时首先要考虑的事情
2. 逻辑结构
2.1 综述
- 逻辑结构 表示构成对象的子元素之间的关系
2.2 数据表
如果对象间元素没有时间上的关系，那么他们构成的组合是一张表，供使用者存储和查询用。
此意义上数据表可以使用顺序存储、链接存储、索引存储、散列存储均可
2.3 时间序: 队列 FIFO（先进先出）
2.3.1 数组描述
规则A：front位置永远为0
规则B：front位置小于rear位置
2.3.2 链表描述
[rear]和[front]分别为一个指针,两种描述类型复杂度相近
2.4 时间序：栈 LIFO（后入先出）
2.4.1 数组描述
[top] 最后放入的数据
[bottom] 最先放入的数据
2.4.2 链表描述
