数据结构与算法--python版-01

基本概念

程序 = 数据结构 + 算法
数据结构数据的存储物理结构及相互间的关联关系(逻辑结构)

1. 线性表顺序表、链表、队列、栈一个前驱一个后继
2. 树二叉树、B树、B+树、红黑树一个前驱多个后继
3. 图多个前驱多个后继

算法 处理问题的逻辑方式

数据存储方式

数据在内存中有如下两种存储方式

1. 顺序存储内存块地址连续通过相对位置offset表示数据间的逻辑关系
   通过索引(偏移量)随机存取
   插入、删除依次移动多个元素最坏复杂度O(n)
   如python中的列表

2. 链式存储内存块地址不连续通过指针表示数据间的逻辑关系
   结点包含后继结点的地址信息空间利用率低
   必须顺序存取 不可以随机存取
   插入、删除方便时间复杂度O(1)

求解问题面向问题抽象出合适的逻辑结构面向机器选择合适的存储结构。

 

算法

算法是解决某一问题的方法步骤。可以是自然语言或者计算机语言。

算法特性

1. 有穷性操作步骤有限、合理
2. 确定性每一步必须有确定的含义
3. 可行性

案例

1. 100W个词语设计最快查询速度的存储方式
   哈希结构 二进制转为十进制对应的数值作为索引存入数组

2. n个城市的连线最小费用问题
   图结构