算法的设计取决于数据的逻辑结构,而算法的实现依赖于数据的存储结构。
数据的逻辑结构
元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,独立于计算机。
- 线性结构:元素一对一关系,常见如数组、链表、栈、队列。
- 树形结构:元素有层次关系,如树、二叉树、堆。
- 图形结构:任意连接关系,如图、网络。
数据的存储结构
存储结构是指数据的逻辑结构在计算机中的存储形式。数据是数据元素的集合,根据物理结构的定义,实际上就是如何把数据元素存储到计算机的存储器中。
数据的存储结构应正确反映数据元素之间的逻辑关系,即建立一种由逻辑结构到存储空间的映射。常用的基本存储映射方法如下:
- **顺序存储:**元素连续存放,访问快,插删慢。
- **链接存储:**通过指针连接,适合频繁插删。
- **索引存储:**建立索引表提高查找效率。
- **散列存储:**用哈希函数快速定位数据,查找快。
算法评估
1. 时间复杂度
2. 空间复杂度