三、数据结构描述数据的结构1. 基本概念程序 数据结构 算法2. 时间复杂度O(c) O(logn) O(n) O(nlogn) O(n^2) .. O(2^n)在程序运行中我们希望无论数据量是否增长程序运行时间维持恒定随着数据量的增长程序运行时间增长两者之间呈现的函数关系称为时间渐进复杂度函数简称为时间复杂度3. 空间复杂度随着数据的增长程序所占空间与数据量增长所呈现的比例函数关系称为空间复杂度4. 数据结构1 数据的逻辑结构线性结构表状结构 一对一关系树形结构 一对多关系图形结构 多对多关系2数据的存储结构顺序结构链式结构散列存储索引存储5. 数据结构内容顺序表访问元素方便存放方式简单链式表单向链表双向链表双向循环链表内核链表顺序栈链式栈顺序队列链式队列二叉树哈希表常见的排序和查找的算法3.1 顺序表概念顺序存放的表状结构3.2链式表1.单向链表数组和链表各自的优缺点数组1. 空间连续访问元素方便2. 元素必须有上限无法做到无限个元素3. 插入删除效率低链表1. 空间不需要连续访问元素不太方便2. 增大存储空间3. 主要空间足够元素可以没有上限4. 插入、删除效率高