文章目录一、什么是程序二、什么是数据结构1. 数据结构是什么2. 为什么会有不同的数据结构三、什么是算法四、数据结构和算法有什么关系1. 为什么两种方式会有差别2. 可以实际验证一下五、为什么要学习数据结构与算法1. 从“能运行”到“运行得更好”2. 不只是会用 list 和 dict3. 写代码之前先想清楚数据4. 很多计算机知识都会回到这些基础六、总结七、参考一、什么是程序计算机科学中有一句非常经典的话程序 数据结构 算法这句话也对应了 Niklaus Wirth 的经典著作《Algorithms Data Structures Programs》。一个程序想要解决实际问题通常离不开两个核心问题数据应该怎样组织和存储这些数据应该怎样被处理前者对应数据结构后者对应算法。可以简单理解为数据结构解决“数据怎么组织”算法解决“数据怎么处理”。比如一个学生管理系统需要保存学生的姓名、学号、成绩等信息同时还需要完成查询、添加、删除、修改、排序等操作。这里既涉及数据如何组织和存储也涉及如何对这些数据进行处理。真正写程序时数据结构和算法往往是结合在一起的。程序数据结构算法数据怎么组织数据怎么处理解决实际问题二、什么是数据结构在理解数据结构之前先来看什么是数据。例如一个学生管理系统中姓名张三 学号20260001 年龄20 成绩90姓名、学号、年龄、成绩这些都属于数据。当学生数量从几个人增加到几千、几万甚至更多时仅仅把数据保存下来已经不够了还需要考虑怎样组织这些学生信息怎样通过学号找到某个学生怎样添加或删除学生怎样修改学生信息怎样按照成绩进行排序这时候数据的组织方式就开始变得重要。1. 数据结构是什么数据结构是数据在计算机中的组织、存储以及数据之间关系的表示方式。通俗一点说就是研究数据应该怎么组织。例如可以使用 Python 的列表保存学生姓名students[张三,李四,王五]这些数据按照一定顺序组织在一起。也可以通过学号组织学生信息students{20260001:张三,20260002:李四,20260003:王五}虽然保存的仍然是学生信息但组织方式已经不同。数据怎样组织会影响后续查找、插入、删除等操作的实现方式和效率。2. 为什么会有不同的数据结构因为现实中的数据关系并不完全相同。有些数据是按照顺序排列的有些具有明显的层级关系还有一些数据之间存在复杂的连接关系。因此计算机中形成了许多不同的数据结构例如数组、链表、栈、队列、哈希表、树、堆、图等。它们本质上都是在用不同的方式组织数据以适应不同的问题和操作需求。例如一组连续的数据 → 数组 先进先出的任务 → 队列 具有上下级关系的数据 → 树 相互连接的节点 → 图这里真正需要关注的不是这些名字而是不同的问题需要的数据组织方式可能并不相同。三、什么是算法有了数据以后还需要对数据进行处理。例如现在有一组数字nums[5,2,9,1,7]要求找出其中最大的数字。可以这样做max_numnums[0]fornuminnums:ifnummax_num:max_numnumprint(max_num)运行结果9整个过程实际上就是先把第一个数字作为当前最大值 ↓ 依次与后面的数字比较 ↓ 如果发现更大的数字就替换 ↓ 继续比较直到结束 ↓ 得到最大值这就是一种算法。算法是解决某个问题的一系列明确步骤和方法。比如查找一个数据对一组数字进行排序计算两个城市之间的最短路线判断一个字符串是否满足某种条件。这些问题都需要相应的算法。算法并不一定意味着复杂的数学公式。像前面的“依次比较并保留当前最大值”本身就是一种非常基础的算法。真正值得关注的是为什么要按照这样的步骤解决问题有没有更合适的方法四、数据结构和算法有什么关系数据结构和算法经常放在一起是因为两者本身就有很强的联系。数据怎么组织会直接影响数据应该怎么处理。假设现在有三个用户users[{id:1001,name:张三},{id:1002,name:李四},{id:1003,name:王五}]现在需要找到 ID 为1003的用户。一种直接的方法是从第一个用户开始依次查找foruserinusers:ifuser[id]1003:print(user)数据很少时这种方式没有什么问题。但如果用户数量变成几十万甚至几百万就需要开始考虑查找效率。如果换一种方式组织数据users{1001:{name:张三},1002:{name:李四},1003:{name:王五}}查找时可以直接通过 ID 获取print(users[1003])同样是在完成“根据 ID 查找用户”这个任务但数据的组织方式不同处理方式和效率也随之发生变化。1. 为什么两种方式会有差别列表中的数据是按顺序保存的。如果不知道目标在哪就可能需要第 1 个 → 不是 第 2 个 → 不是 第 3 个 → 不是 …… 直到找到目标假设一共有n条数据最坏情况下可能需要检查接近n次。这种查找通常记作O(n)而 Python 的dict底层使用的是哈希表。根据 key 查找时并不是简单地从第一条数据开始逐个比较而是会通过哈希值定位到相应位置。在平均情况下它的查找复杂度通常可以看作O(1)简单对比如下数据组织方式查找方法平均查找复杂度列表list从前往后逐个比较O(n)字典dict根据 key 进行哈希定位O(1)这里暂时不需要深入研究时间复杂度。只需要知道O(n)数据越来越多需要进行的操作通常也会随之增加O(1)平均情况下操作次数不会随着数据规模线性增长。这也说明了一个很重要的问题选择什么样的数据结构本身就可能影响程序的效率。2. 可以实际验证一下如果想直观看看这种差别可以用 Python 的timeit做一个简单测试importtimeit users_list[{id:i,name:fuser{i}}foriinrange(100000)]users_dict{i:{name:fuser{i}}foriinrange(100000)}target99999deffind_from_list():foruserinusers_list:ifuser[id]target:returnuserdeffind_from_dict():returnusers_dict[target]list_timetimeit.timeit(find_from_list,number100)dict_timetimeit.timeit(find_from_dict,number100)print(list:,list_time)print(dict:,dict_time)不同电脑、不同 Python 版本得到的具体数字会有差异因此这里没有必要死记某个耗时结果。更值得观察的是当数据规模逐渐增大时逐个遍历列表的耗时会越来越明显而按照 key 查询字典通常仍然能够保持较高的查找效率。这就是“数据结构影响算法和程序效率”的一个非常直观的例子。一个实际问题通常可以逐渐拆成现实问题确定数据选择数据结构设计处理方法算法得到结果选择什么样的数据结构会影响算法怎么写而需要完成什么操作也会反过来影响数据结构的选择。五、为什么要学习数据结构与算法平时写代码时我们其实已经在不断使用数据结构和算法。比如students[张三,李四,王五]或者student{name:张三,score:90}甚至像forstudentinstudents:print(student)这些代码可能早就已经写过很多次。很多时候我们知道“这样写可以实现。”却不一定清楚“为什么要这样写”为什么有时候使用list有时候更适合使用dict为什么某些写法在十几条数据时几乎没有区别到了几十万条数据以后差距却越来越明显为什么set经常用来判断一个元素是否存在这也是学习基础知识很重要的原因知其然更要知其所以然。学习数据结构与算法不只是记住某种语法而是逐渐从“知道怎么写”走向“理解为什么这样写”。1. 从“能运行”到“运行得更好”刚开始写程序时最先考虑的通常是代码能不能运行结果是不是正确这是最基本的要求。但随着程序规模和数据量增大还需要继续考虑运行速度怎么样占用多少内存数据规模扩大以后还能不能正常工作有没有更合适的数据结构或算法两个程序可能都能得到正确答案但实现方式并不一定相同。一个可能需要进行上百万次操作另一个可能只需要很少的操作。所以代码能运行只代表问题被解决了怎么解决则决定了程序能不能在更大的规模下继续工作。2. 不只是会用list和dict平时使用 Python 时我们可能已经非常熟悉nums[1,2,3,4]或者student{name:张三,score:90}这些写法本身并不难。但继续往下看就会出现更多问题为什么dict根据 key 查找通常很快为什么判断元素是否存在时经常使用set什么情况下适合使用list为什么有些操作换一种数据结构会更加合适当开始理解这些问题时我们就不再只是调用 Python 提供好的工具而是在逐渐理解这些工具背后的设计。3. 写代码之前先想清楚数据面对一个需求时很容易直接进入“这个功能怎么写”但真正决定程序结构的往往是更前面的问题。比如要做一个任务管理系统需要先考虑有哪些数据数据之间是什么关系哪些操作最频繁查询多还是修改多数据规模大不大应该怎样组织这些数据这些问题的答案不同最后写出来的程序结构也可能完全不同。写程序并不只是把语法拼起来。更重要的是把现实中的问题抽象成计算机能够处理的数据再设计合适的方法处理这些数据。4. 很多计算机知识都会回到这些基础很多常见技术背后都能看到数据结构和算法。例如函数调用 → 栈 任务调度 → 队列、堆 数据库索引 → 树 文件目录 → 树 地图导航 → 图 快速查找 → 哈希表 搜索 → 查找算法比如文件目录本身就具有明显的层级关系D: └── Code ├── project1 ├── project2 └── project3这种结构可以很自然地看成一棵树。地图导航也是类似的道理。城市、路口可以看成节点道路可以看成节点之间的连接。当整个道路网络被抽象成图以后接下来才是在图上通过相应算法寻找路线。数据结构和算法还会不断出现在操作系统、数据库、编译原理、计算机网络、搜索、人工智能等领域中。越往后学习越容易发现一些表面上完全不同的技术最后都会重新遇到这些基础概念。六、总结程序解决问题时通常既要考虑数据如何组织也要考虑数据如何处理。再次回到最开始的公式程序 数据结构 算法其中数据结构关注数据怎么组织算法关注数据怎么处理、问题怎么解决。平时写代码时我们可能早就在使用各种数据结构和算法只是更多停留在“这样写可以用”。学习这些基础知识的意义就是逐渐从我知道这样写能用。走向我知道为什么这样写也知道什么时候应该换一种写法。面对新的问题时可以多想一步有哪些数据 ↓ 数据之间是什么关系 ↓ 应该怎样组织这些数据 ↓ 需要完成哪些操作 ↓ 怎样处理更合理、更高效这也是后面继续学习数组、链表、栈、队列、哈希表、树、图以及各种算法时可以一直带着的问题。七、参考Python 官方文档 - Data Structures