引言¶
数据结构是计算机中组织和存储数据的方式,存储的内容可以是整数浮点数字符等各种类型的数据,而算法是在有限时间内解决特定问题的一组指令或操作步骤。
类比1
数据类型 ≈ 不同材料的积木,比如塑料、木头、金属等
数据结构 ≈ 积木组织形式,包括形状、大小、连接方式等
算法 ≈ 把积木拼成不同模型的一系列操作步骤
类比2
数据类型 ≈ 不同类别的书籍,比如期刊、小说、教辅等
数据结构 ≈ 书籍的整理方式,比如书架、抽屉、台子等
算法 ≈ 获取书籍的方式
数据结构¶
根据逻辑结构分类¶
逻辑结构描述了数据元素之间的逻辑关系
根据物理结构分类¶
物理结构描述了数据在计算机内存中的存储方式,决定了数据的增删改查等操作方法
所有数据结构都是基于「数组」和「链表」,或者其组合实现的,比如,哈希表的底层是数组,其中每一个桶槽位可能包含一个值,但也可能包含一个链表或一棵树。
基于数组实现的数据结构也称静态数据结构,这意味着此类数据结构在初始化后长度不可变。(动态数组或者说列表比较特殊)
相对应地,基于链表实现的数据结构也称动态数据结构,这类数据结构在初始化后,仍可以在程序运行过程中对其长度进行调整。
算法¶
计算机科学研究的正是算法,计算机只是工具,解决问题的过程以及解决方案,可能存在也可能不存在,存在即为可计算。
算法并不一定涉及复杂的数学,而是更多的依赖基本逻辑,这些逻辑在我们的日常中随处可见。
搜索算法 searching_algorithm¶
- 暴力搜索
- 线性搜索
- 广度优先搜索:从初始节点开始逐层搜索,由近及远地访问各个节点
- 深度优先搜索:从初始节点开始,沿着一条路径走到头,再回溯并尝试其他路径,直到遍历完整个数据结构
- 自适应搜索(查找算法)
- 二分查找 binary_search
- 哈希查找
- 树查找
思想¶
- 分治
- 贪心,一条路走到黑,就一次机会,只能哪边看着顺眼走哪边
- 回溯,一条路走到黑,无数次重来的机会,还怕我走不出来 (Snapshot View)
- 动态规划,Dynamic Programming,简称 DP,拥有上帝视角,手握无数平行宇宙的历史存档 (Versioned Archive View),同时发展出无数个未来,存在递推关系,可以使用动态规划求解