1 / 13
为什么要学习数据结构？
在计算机科学中，数据结构是研究如何高效组织、管理和存储数据的学科。合理选择与设计数据结构不仅直接决定算法的效率和资源消耗，也是软件系统性能优化的核心之一。 举例来说，针对不同应用场景（如数据库索引、图像处理、路径规划等），应采用适合的数据结构以实现高效的数据查询、插入、删除与存储。
无论是开发高性能服务器、构建复杂的前端应用，还是实现底层操作系统功能，数据结构知识都是计算机程序员的基础能力。 只有扎实掌握常用数据结构及其适用场景，才能设计出健壮、高效与可扩展的软件系统。因此，数据结构被认为是计算机编程领域不可或缺的“基本功”。
什么是数据结构
在计算机的世界里，我们面对的是数字化的信息：数字、文字、图像、声音，以及各种复杂的对象。这些信息就像图书馆里的书籍一样，如果没有合适的组织方式，计算机就无法高效地处理它们。
核心概念
要理解数据结构，我们首先需要明确几个基本概念。假设我们有一个学生管理系统，这个系统里存储着每个学生的信息。数据就像是系统中记录的每一个学生的完整档案，它是我们要处理的原始材料，是计算机能够理解和操作的信息载体。
- 数据元素：每个具体的学生档案，比如张三的完整个人信息，它是数据的基本单位，通常作为一个整体来处理。
- 数据项：构成学生档案的具体信息片段，如姓名、学号、年龄、专业等等，这些是最小的、不可再分的信息单位。
- 数据对象：可以理解为所有计算机专业学生档案的集合，或者所有2020级学生档案的集合，它是具有相同性质的数据元素组成的群体。
现在我们理解了数据的各个层面，接下来就要探讨如何组织这些数据。这就涉及到数据结构的核心——“结构”。结构描述的是数据元素之间的关系模式，就像建筑师在设计房子时需要考虑房间之间的关系一样。 根据观察的角度不同，我们可以从两个层面来理解结构：逻辑结构告诉我们数据元素在概念上应该如何关联；物理结构则告诉我们这种关联在计算机内存中具体如何实现。
1. 逻辑结构
逻辑结构描述的是数据元素之间的抽象关系，就像描述人际关系的社会学理论一样，它不关心具体的技术实现，只关心关系的本质。让我们通过生活中的例子来理解四种基本的逻辑结构。
- 集合结构：就像一个装满各种颜色弹珠的袋子。这些弹珠都属于同一个袋子，但彼此之间没有特定的关系——没有先后顺序，没有上下级，也没有邻居关系。每颗弹珠都是独立的个体，它们唯一的共同点就是都在这个袋子里。
- 线性结构：就像我们日常生活中的排队。想象一下在银行办业务的队伍，每个人都有明确的前一位和后一位（除了队首和队尾）。这种“一对一”的关系形成了一条清晰的链条。
- 树形结构：就像一个家族的族谱或者公司的组织架构。在这种结构中，每个成员（除了族长或CEO）都有且仅有一个直接上级，但可能有多个下级。这种“一对多”的关系创造了层次分明的结构。
- 图形结构：最为复杂，就像现实世界中的社交网络。在这种结构中，任何两个元素之间都可能存在直接的关系，形成“多对多”的复杂网络。比如城市之间的交通路线、互联网的连接关系。
2. 物理结构
如果说逻辑结构是建筑师的设计图纸，那么物理结构就是工程师的施工方案。无论我们设计出多么优雅的逻辑关系，最终都要在计算机的内存中找到安身之所。物理结构，也被称为存储结构，决定了数据在计算机内存中的具体安排方式。
假设我们要在一栋公寓楼里安排一群朋友住宿。我们有两种基本的安排方案。
顺序存储结构：就像把朋友们安排在同一层楼的连续房间里。比如让小王住101，小李住102，小张住103，依此类推。
- 优点：如果我们知道小王住在101，我们马上就能算出小张住在103，不需要挨个房间去询问。这就是数组的存储方式——数据在内存中紧挨着排列，通过简单的数学运算就能快速定位任何元素。
- 缺点：如果小赵想要插队住在小王和小李之间，我们就得让小李搬到103，小张搬到104，以此类推。每次插入或删除都可能引起大规模的“搬家”行动。
链式存储结构：采用了完全不同的策略。朋友们可以住在楼里的任何地方——小王住301，小李住508，小张住207。为了保持联系，每个人都会保存下一个朋友的房间号码。
- 优点：虽然他们住得分散，但通过这些“线索”（指针），我们仍然能够按照正确的顺序找到每一个人。插入新朋友时只需要修改一下线索，不需要大规模搬家。
- 缺点：如果我们想直接找到第五个朋友，我们不能直接计算出他的房间号，必须从第一个朋友开始，一个一个地询问下去。
这就是数据结构设计的魅力所在：逻辑结构定义了“应该是什么样的关系”，物理结构决定了“如何在现实中实现这种关系”。就像同一个建筑设计可以用不同的材料和工艺来建造一样，同一个逻辑结构可以用不同的物理结构来实现。
计算机性能的影响
确实，现在的计算机性能比几十年前强大了几千倍，内存动辄几个GB，硬盘容量更是以TB计算。那么，我们还需要为了节省几个字节的内存或几毫秒的时间而费尽心思吗？
让我来讲一个故事。有两个程序员，小明和小华，他们都要开发一个社交软件，帮助用户找到朋友的朋友。
- 小明 觉得硬件这么强大，简单粗暴地把所有用户关系存在一个大数组里，每当用户要查找朋友的朋友时，就遍历整个数组进行匹配。刚开始用户不多的时候，这个方法工作得还不错。
- 小华 则仔细思考了数据的组织方式，用图的结构来表示用户关系，实现了高效的搜索算法。
几个月后，用户数量从几千增长到了几百万。小明发现他的程序变得越来越慢，用户查找一次朋友关系需要等待几分钟甚至更长时间，很多用户开始卸载他的应用。而小华的程序依然运行如飞，甚至在用户数量达到千万级别时，查找速度仍然保持在毫秒级别。
从上面的例子我们不难看出数据结构的重要性。接下来，本课程将带领我们系统地学习各种核心的数据结构。我们将按照一条精心设计的路径，从简单到复杂，从基础到高级，逐步深入这个精彩的世界！