数据结构和算法

苏丙榅2024-05-042024-06-21

1. 概述

1.1 概念

数据结构和算法是计算机科学中的一组重要概念。先看一下官方对这两个概念的定义：

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
算法：是指解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个步骤。

为了方便理解，上述概念可以再说的直白一些：

数据结构就是指一组数据的存储方式
算法就是操作数据的一组方法

1.2 为什么要学习数据结构和算法

为什么要学习数据结构和算法呢?

想要通关大厂面试，千万别让数据结构和算法拖了后腿
业务开发工程师，不能做一辈子 CRUD（增删改查）
基础架构研发工程师，写出达到开源水平的框架才是目标
对编程还有追求？不想被行业淘汰？那就不要只会写凑合能用的代码

学习数据结构具有多重好处：

提高问题解决能力： 数据结构是组织和存储数据的方式，学习数据结构可以帮助你更好地理解问题的本质，并能够有效地设计和实现解决方案。
提升编程能力： 数据结构是编程的基础，掌握了数据结构可以让你写出更高效、更健壮的代码，提升编程技能和代码质量。
优化算法效率： 数据结构和算法是紧密相关的，选择合适的数据结构可以大幅提升算法的效率，从而更快地解决问题。
应对面试挑战： 许多技术面试都会考察数据结构和算法的知识，掌握了这些知识可以帮助你在面试中更好地应对各种挑战。
为工程实践打下基础： 在实际的软件开发中，经常需要处理各种数据，了解不同的数据结构可以为你在工程实践中选择合适的工具提供指导。

掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。因为这样的你，就像是站在巨人的肩膀上，拿着生存利器行走世界。数据结构与算法，会为你的编程之路，甚至人生之路打开一扇通往新世界的大门。

1.3 数据结构和算法的关系

数据结构和算法是密切相关的，它们之间有着互相依存的关系：

数据结构为算法服务： 数据结构提供了存储和组织数据的方式，为算法提供了操作数据的基础。选择合适的数据结构可以使得算法更加高效、简洁。
算法作用于数据结构： 算法是解决问题的方法和步骤，而这些问题通常涉及对数据的操作。算法通过对数据结构进行操作，实现了对数据的处理、查找、排序等功能。
相辅相成： 数据结构和算法相辅相成，优秀的算法需要建立在合适的数据结构之上，而高效的数据结构也需要结合适当的算法来实现其功能。
优化效率： 选择合适的数据结构可以优化算法的效率，而设计高效的算法也需要考虑数据结构的特点，以实现更快速、更节省资源的操作。

总的来说，数据结构和算法是计算机科学中的两大基础，它们相互促进、相互支撑，共同构建了解决问题的框架和方法。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

2. 数据结构

数据结构可以根据逻辑结构和物理结构进行分类：

逻辑结构：数据对象中数据元素之间的相互关系
- 集合结构：数据元素同属于一个集合，但是元素之间没有任何关系，这和数学中的集合类似。
- 线性结构： 线性结构是数据元素之间存在一对一的逻辑关系，包括数组、链表、栈和队列等。
  - 数组（Array）： 数组是一种线性数据结构，它由相同类型的元素组成，并以连续的内存地址存储。数组的特点是可以通过索引快速访问任何元素，但插入和删除操作可能会比较耗时，需要移动其他元素。
  - 链表（Linked List）： 链表也是一种线性数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。链表的特点是插入和删除操作效率较高，但访问元素需要从头节点开始逐个遍历。
  - 栈（Stack）： 栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。栈通常用于实现函数调用、表达式求值等场景。
  - 队列（Queue）： 队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队首删除元素。队列通常用于实现任务调度、消息传递等场景。
- 非线性结构： 非线性结构是数据元素之间存在一对多或多对多的逻辑关系，包括树和图等。
  - 树（Tree）： 树是一种非线性数据结构，它由节点组成，每个节点可以有零个或多个子节点。树的特点是可以用于表示层次关系，如文件系统、组织结构等。
  - 图（Graph）： 图是一种非线性数据结构，它由节点（顶点）和边组成，用于表示元素之间的关系。图的特点是可以表示各种复杂的关联关系，如社交网络、网络拓扑等。
物理结构：数据在计算机中的存储形式
- 顺序存储结构： 顺序存储结构是指数据元素在内存中占据一段连续的空间，例如数组。
- 链式存储结构： 链式存储结构是指数据元素在内存中非连续存储，而是通过指针相互连接，例如链表。

逻辑关系主要描述数据元素之间的逻辑连接方式，而物理关系描述数据元素在内存中的存储结构。选择合适的逻辑关系和物理关系可以更好地组织和操作数据，在算法设计和实现时起到重要作用。

3. 算法

3.1 算法的特性

算法具有5个基本特性：输入、输出、有穷性、确定性、可行性。

输入输出
- 算法具有零个或多个输入，比如：键盘输出、参数等
- 算法至少有一个或多个输出，比如：打印输出、返回值等
有穷性

算法在执行有限的步骤后会自动结束，而不会出现死循环，并且每一个步骤都可以在可以接受的时间内完成。
确定性

算法的每个步骤都有具体确定的含义，不会出现二义性。
可行性

算法的每一个步骤都是可行的，也就是说，每一步都能够通过执行有限的次数完成。

3.2 算法的设计要求

在编写算法的时候，我们一般用什么标准来评判它的优劣呢？主要有三个方面：

正确性

算法的正确性大体上可以分为四个层次：
- 算法程序没有语法错误
- 算法程序对于合法的输入数据，能够得到满足要求的输出结果
- 算法程序对于非法的输入数据，能够产生满足规格说明的结果
- 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
可读性

写代码的目的，一方面是让计算机执行，还有另一个重要的目的就是便于他人阅读、理解和交流。
健壮性

当输入的数据不合法时，算法也能够做出相应的处理，而不是产生异常或者莫名其妙的结果。

3.3 算法效率的度量方法

我们都知道，数据结构和算法本身解决的是 “快” 和 “省” 的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量编写的算法代码的执行效率呢？

算法效率的评估一般有两种方式：

3.3.1 事后统计法

通过设计好的测试程序和数据，把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。最后对不同算法的运行结果进行比较，就能得到算法效率的高低了。

通过上述方式评估算法的执行效率肯定是正确的，但是，这种统计方法有非常大的局限性。

测试结果非常依赖测试环境
- 处理器性能不同得到的结果也不同，比如：i5和i7
- 处理器指令集架构不同，对结果影响很大
  - CISC（复杂指令集计算机）：在硬件上提供了乘法器
  - RISC（精简指令集计算机）：通过加法指令来实现乘法指令
测试结果受数据规模的影响很大
- 量大 VS 量小
- 无限接近有序的数据 VS 极度混乱的数据
编写测试程序成本高
- 花费大量精力编写的测试程序，但是测出的结果是算法效率很低，竹篮打水一场空