🚀前言

数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。

1. 数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
2. 链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
3. 栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
4. 队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
5. 哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
6. 树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
7. 堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
8. 图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。

🚀一、数据结构简介

🔎1.数据结构概述

数据结构是计算机科学中一个重要的概念，它是指用于组织和存储数据的一种方式，包括如何存储、访问、操作和管理数据的方法和算法。数据结构是计算机程序设计中的一种重要工具，它可以提高程序的效率和代码的可维护性。常见的数据结构包括数组、链表、栈、队列、树、图等。在计算机科学中，数据结构是构建算法和程序的基础。理解和掌握数据结构对于计算机科学的学习和应用都是至关重要的。

🔎2.数据结构分类

数据结构可以分类为逻辑结构和物理结构：

1. 逻辑结构：指数据元素之间的逻辑关系，包括线性结构、树形结构、图形结构等。
2. 物理结构：指数据元素在计算机内存中的存储方式，包括顺序存储结构和链式存储结构等。

顺序存储结构是指将数据元素存放在一段地址连续的存储单元中，例如数组；链式存储结构是指将数据元素存放在任意的存储单元中，通过指针来描述数据元素之间的逻辑关系，例如链表。需要注意的是，同一种逻辑结构可以有不同的物理结构实现，例如线性结构可以用数组或链表实现。

🦋2.1 逻辑结构

数据结构中的逻辑结构分为线性结构和非线性结构。

1. 线性结构

线性结构是指数据元素之间存在一对一的关系，即数据元素之间只有前后相互关联的关系，它是一种线性序列。线性结构包括以下几种：

• 数组：由n个数据元素组成的有限序列，其中每个元素具有唯一的前驱和后继。
• 栈：是一种特殊的线性表，其插入和删除操作只能在表的一端进行，该端称为栈顶。
• 队列：也是一种特殊的线性表，其插入操作在表的一端进行，删除操作在表的另一端进行，分别称为队尾和队头。
• 链表：由n个结点组成，每个结点包含数据域和指针域，指针域指向下一个结点。
• 哈希表：是一种以关键字为自变量，通过散列函数计算得到数据元素存储地址的结构。
• 非线性结构

非线性结构是指数据元素之间存在一对多或多对多的关系，即数据元素之间不仅有前后相互关联的关系，还有其他类型的关联。非线性结构包括以下几种：

• 树：是由n个结点组成的有限集合，其中有一个根节点，其他结点分为若干层次。
• 图：是由n个结点和m条边组成的有限集合，结点表示数据元素，边表示结点之间的关系。
• 堆：是一种特殊的树形结构，它满足任何一个非叶子节点的值，都不大于或不小于其左右孩子节点的值。
• 哈希表：是一种以关键字为自变量，通过散列函数计算得到数据元素存储地址的结构。

数据结构中的逻辑结构可以分为线性结构和非线性结构，不同的结构适用于不同的场景，选用适合的数据结构可以提高数据的处理效率。

非线性数据结构可以进一步被划分为树形结构和网状结构。

• 线性结构：数组、链表、队列、栈、哈希表，元素之间是一对一的顺序关系。
• 树形结构：树、堆、哈希表，元素之间是一对多的关系。
• 网状结构：图，元素之间是多对多的关系。

🦋2.2 物理结构

数据结构中的物理结构通常分为两种，即连续存储结构和离散存储结构。

连续存储结构指的是数据元素在物理空间上是连续排列的，即相邻的数据元素在内存中是相邻的。它的优点是对数据的访问速度较快，因为一旦知道了一个元素的起始地址，就可以通过偏移量来访问其它元素。而缺点是如果需要插入或删除一个元素，需要移动后面所有的元素，时间复杂度为O(n)，效率较低。常见的连续存储结构有数组和线性表。

离散存储结构指的是数据元素在物理空间上是离散排列的，即相邻的数据元素在内存中可以不相邻。它的优点是插入和删除元素时只需要改变指针的指向，时间复杂度为O(1)，效率较高。而缺点是访问元素时需要通过指针访问，速度比较慢。常见的离散存储结构有链表、树和图。

所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实

现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

• 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度 ≥ 3 的数组）等。
• 基于链表可实现：栈、队列、哈希表、树、堆、图等。

基于数组实现的数据结构也被称为“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构被称为“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。

🔎3.数字编码和字符编码

🦋3.1 数字编码

☀️3.1.1 原码、反码和补码

原码是二进制数表示法中最基本的表示方法，即最高位表示符号，0表示正数，1表示负数。

反码是原码的一种衍生表示方法，对于正数和0，其反码就是其原码本身；对于负数，反码是在原码的基础上，除符号位外，将其它位取反。

补码是二进制数的另一种表示方法，也是计算机中常用的一种表示方法。对于正数，其补码与其原码相同；对于负数，其补码是该数的反码加1。补码具有唯一性，而且加法运算可以统一用补码来进行，方便计算机的处理。

原码、反码和补码都是二进制数在计算机中的表示方式，其作用如下：

1. 原码：最基本的表示方式，用于表示有符号整数，但在运算时需要考虑符号位的影响，不便于计算机进行加减运算。
2. 反码：在原码的基础上，将负数的表示方式统一，便于计算机进行加减运算，但依然存在加减运算溢出的问题。
3. 补码：补码的优点在于可以用同一个加法器对有符号数和无符号数进行加减运算，且不存在加减运算溢出的问题。因此，补码是计算机中最常用的二进制表示法，同时也是计算机中的基础概念之一。

原码、反码和补码都是计算机中用于表示有符号整数的基础概念，它们在计算机中的作用是方便计算机进行加减运算和表示负数。

☀️3.1.2 浮点数编码

浮点数编码是一种用来表示实数的二进制数字编码方式，可以用来表示包括小数等非整数在内的任意实数。浮点数编码按照一定的规范将一个实数转换成一个二进制序列，其中会包括指数和尾数两部分信息。不同的浮点数编码规范会有不同的实现方式和精度要求，例如IEEE浮点数标准就是一种广泛采用的浮点数编码方式。浮点数编码在计算机科学和计算机应用领域广泛使用，例如在计算机图形学、数值计算、科学计算等领域中都会使用到浮点数编码。

浮点数编码的作用是在计算机中表示实数。由于计算机是基于二进制的，无法准确地表示所有实数。因此，浮点数编码使用科学计数法的形式来表示实数，其中数值和指数以二进制表示。这种编码方式可以更有效地利用计算机中有限的位数来表示实数，同时也避免了精度丢失的问题。浮点数编码在科学计算、图像处理、计算机图形学等领域都有广泛的应用。

🦋3.2 字符编码

☀️3.2.1 ASCII 字符集

ASCII（American Standard Code for Information Interchange）字符集，是美国制定的一种字符编码方式，用于将字符映射到数字。它包括128个字符，其中包括数字、字母、标点符号和一些控制字符。每个字符都用一个7位二进制数表示，即可以用一个字节（8位二进制数）进行编码。

ASCII字符集最早是为了在不同的计算机和设备之间传输文本而设计的。由于ASCII字符集是固定的，因此它的局限性很大，无法表示其他国家和地区的语言和文字。因此，一些国家和地区制定了自己的字符集，例如GB2312、ISO-8859、GBK、Unicode等等。但是，ASCII字符集仍然被广泛使用，特别是在计算机和网络领域中作为基础字符集。

☀️3.2.2 GBK 字符集

GBK（Guo Biao Ku）是中华人民共和国国家标准的简体中文字符集，包含了21,913个汉字。它是在GB2312字符集的基础上进行了扩展，增加了汉字和符号。和GB2312一样，GBK是双字节字符集，每个汉字占用两个字节，每个英文字符和标点占用一个字节。GBK可以向下兼容GB2312，也可以与Unicode互相转换。在中国大陆和台湾地区广泛使用。

☀️3.2.3 Unicode 字符集

Unicode 字符集是一种标准化的字符编码系统，用于表示世界上所有语言和文字的字符。它包含了超过13万个字符，包括了字母、数字、标点符号、符号、表情符号等等。Unicode 字符集的设计是为了实现跨语言、跨平台、通用的字符编码方案。这样，在不同的计算机、操作系统、应用程序和网络之间传输字符时，可以保证字符的正确性和一致性。

☀️3.2.4 UTF‑8 编码

UTF-8是一种用来表示Unicode字符集的编码方式。Unicode是一个包含了世界上所有字符集的标准，UTF-8则是其中一种最普遍的编码方式。UTF-8使用1到4个字节来表示不同的字符，其中ASCII字符（0-127）只需要1个字节表示，而其他字符则需要使用多个字节。UTF-8的优点是可以兼容ASCII编码，并且可以表示世界上大部分语言的字符，因此被广泛应用于网络和计算机系统中。

除了 UTF‑8 之外，常见的编码方式还包括以下两种。

• UTF‑16 编码：使用 2 或 4 个字节来表示一个字符。所有的 ASCII 字符和常用的非英文字符，都用 2 个 字节表示；少数字符需要用到 4 个字节表示。对于 2 字节的字符，UTF‑16 编码与 Unicode 码点相等。
• UTF‑32 编码：每个字符都使用 4 个字节。这意味着 UTF‑32 会比 UTF‑8 和 UTF‑16 更占用空间，特 别是对于ASCII 字符占比较高的文本。

从存储空间的角度看，使用 UTF‑8 表示英文字符非常高效，因为它仅需 1 个字节；使用 UTF‑16 编码某些非英文字符（例如中文）会更加高效，因为它只需要 2 个字节，而 UTF‑8 可能需要 3 个字节。

从兼容性的角度看，UTF‑8 的通用性最佳，许多工具和库都优先支持 UTF‑8 。

☀️3.2.5 编程语言的字符编码

编程语言通常使用Unicode字符集来表示字符编码。Unicode是一种标准化的字符编码系统，可以表示世界上所有语言的字符。在计算机中，Unicode字符集的字符通常是以UTF (Unicode Transformation Format)编码的形式存储和传输的，包括UTF-8、UTF-16和UTF-32。不同的编程语言支持不同的字符编码方式，比如Java使用UTF-16编码，Python默认使用UTF-8编码。在处理字符编码时，需要注意不同编码方式之间的转换和字符集的兼容性问题。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！