谁教你这么剪的 | 游戏开发中的数据结构和算法

合集 · 英雄哥的游戏开发之路 (29)

Description
很多人问我，数据结构和算法 同 人工智能 中的那些算法有什么区别，两者有联系也有区别，前者是基础，每个学计算机的同学都应该掌握，在工作中会帮助你更好的理解问题，剖析原理。后者相对较难，如果不是将来要从事相关工作，可能基本用不到它。
      为什么很多人学不好数据结构？
      原因就是没有从本质去理解数据结构的概念，任何一种算法都会对应一种数据结构。例如二分查找对应的是顺序表（因为不可能在链表上执行二分查找）、递归对应的是树、最短路对应的是图。
      而核心的数据结构就只有三种：线性表、树、图。
      再抽象一点，其实只有一种数据结构，就是图。
      图就是由 顶点 和 边 构成的网络，像这样。如果一个图中任意两点间都可达，就叫连通图。从一个点经过若干的不重复边，回到自己，我们叫它圈，没有圈的图，实际上就是一棵树。
       我们适当调整它的位置，就成了我们现实中的树，而把树的枝干剪掉，就变成了一个线性的结构，这就成了线性表。平时上课的时候都是从 线性表 讲到 图，而当我们逆向思考发现，所有的数据结构，本质都是图。并且所有的数据结构按照存储方式，既可以用顺序的方式进行存储，也可以用链式的方式进行存储。
        而 栈 和 队列 是两种线性表；树则根据分叉数量，可以是 二叉树、三叉树、四叉树、... ，其中 二叉树最为常见，二叉搜索树必须掌握，并且自己能够手写它的常见遍历；平衡二叉树是效率最高的二叉搜索树，平时没遇到是因为很多库都给你封装好了，像 C++ 中的 map 底层实现红黑树就是一种平衡二叉树，哈希表在冲突时拉链也有可能转化成平衡二叉树；堆则是一种完全二叉树，应用在优先队列中，如 C++ 中的 priority_queue；图主要分为有向图、无向图，其上的算法有很多，比较经典的是最短路和最小生成树。不是很明白的话，可以看我前几期的Python教程：
《Python入门》第一课(输入输出)：https://www.bilibili.com/video/BV1ny4y197dC
《Python入门》第二课(基础语法)：https://www.bilibili.com/video/BV11x4y1j7gK/
《Python入门》第三课(数据结构)：https://www.bilibili.com/video/BV1AY411r78C/
《Python入门》第四课(基础循环)：https://www.bilibili.com/video/BV1ps4y1m75J/
《Python入门》第五课(基础排序)：https://www.bilibili.com/video/BV1Zs4y1X7mN/