数据结构与数据类型
分类
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图,它们可以从“逻辑结构”和“物理结构”两个维度进行分类。
逻辑结构:线性与非线性
逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中,数据按照一定顺序排列,体现了数据之间的线性关系;而在树中,数据从顶部向下按层次排列,表现出“祖先”与“后代”之间的派生关系;图则由节点和边构成,反映了复杂的网络关系。
逻辑结构可分为“线性”和“非线性”两大类。线性结构比较直观,指数据在逻辑关系上呈线性排列;非线性结构则相反,呈非线性排列。
线性数据结构:数组、链表、栈、队列、哈希表,元素之间是一对一的顺序关系。
数据结构:树、堆、图、哈希表。
非线性数据结构可以进一步划分为树形结构和网状结构。
树形结构:树、堆、哈希表,元素之间是一对多的关系。
网状结构:图,元素之间是多对多的关系。
物理结构:连续与分散
**当算法程序运行时,正在处理的数据主要存储在内存中。**展示了一个计算机内存条,其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格,其中每个单元格都可以存储一定大小的数据。
**系统通过内存地址来访问目标位置的数据。**如图 3-2 所示,计算机根据特定规则为表格中的每个单元格分配编号,确保每个内存空间都有唯一的内存地址。有了这些地址,程序便可以访问内存中的数据。
内存是所有程序的共享资源,当某块内存被某个程序占用时,则通常无法被其他程序同时使用了。因此在数据结构与算法的设计中,内存资源是一个重要的考虑因素。比如,算法所占用的内存峰值不应超过系统剩余空闲内存;如果缺少连续大块的内存空间,那么所选用的数据结构必须能够存储在分散的内存空间内。
物理结构反映了数据在计算机内存中的存储方式,可分为连续空间存储(数组)和分散空间存储(链表)。物理结构从底层决定了数据的访问、更新、增删等操作方法,两种物理结构在时间效率和空间效率方面呈现出互补的特点。
值得说明的是,所有数据结构都是基于数组、链表或二者的组合实现的。例如,栈和队列既可以使用数组实现,也可以使用链表实现;而哈希表的实现可能同时包含数组和链表。
基于数组可实现:**栈、队列、哈希表、树、堆、图、矩阵、张量(维度 的数组)**等。
基于链表可实现:栈、队列、哈希表、树、堆、图等。
链表在初始化后,仍可以在程序运行过程中对其长度进行调整,因此也称“动态数据结构”。数组在初始化后长度不可变,因此也称“静态数据结构”。值得注意的是,数组可通过重新分配内存实现长度变化,从而具备一定的“动态性”。
基本数据类型
基本数据类型是 CPU 可以直接进行运算的类型,在算法中直接被使用,主要包括以下几种。
整数类型 byte、short、int、long 。
浮点数类型 float、double ,用于表示小数。
字符类型 char ,用于表示各种语言的字母、标点符号甚至表情符号等。
布尔类型 bool ,用于表示“是”与“否”判断。
基本数据类型以二进制的形式存储在计算机中。一个二进制位即为
比特。在绝大多数现代操作系统中, 1字节(byte)由 8比特(bit)组成。
基本数据类型的取值范围取决于其占用的空间大小。下面以 Java 为例
整数类型 byte 占用 1字节 = 8 比特 ,可以表示 2^8 个数字。
整数类型 int 占用 4字节 = 32 比特 ,可以表示 2^32 个数字。
在 Python 中,整数类型 int 可以是任意大小,只受限于可用内存;浮点数 float 是双精度 64 位;没有 char 类型,单个字符实际上是长度为 1 的字符串 str 。
C 和 C++ 未明确规定基本数据类型的大小,而因实现和平台各异。表 3-1 遵循 LP64 数据模型,其用于包括 Linux 和 macOS 在内的 Unix 64 位操作系统。
字符 char 的大小在 C 和 C++ 中为 1 字节,在大多数编程语言中取决于特定的字符编码方法,详见“字符编码”章节。
即使表示布尔量仅需 1 位(0 或 1),它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常将 1 字节作为最小寻址内存单元。
那么,基本数据类型与数据结构之间有什么联系呢?我们知道,数据结构是在计算机中组织与存储数据的方式。这句话的主语是“结构”而非“数据”。
如果想表示“一排数字”,我们自然会想到使用数组。这是因为数组的线性结构可以表示数字的相邻关系和顺序关系,但至于存储的内容是整数 int、小数 float 还是字符 char ,则与“数据结构”无关。
换句话说,**基本数据类型提供了数据的“内容类型”,而数据结构提供了数据的“组织方式”。**例如以下代码,我们用相同的数据结构(数组)来存储与表示不同的基本数据类型,包括 int、float、char、bool 等。
class ListNode:
"""链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 后继节点引用
"""Driver Code"""
if __name__ == "__main__":
# 使用多种基本数据类型来初始化数组
numbers = [0] * 5
decimals = [0.0] * 5
# Python 的字符实际上是长度为 1 的字符串
characters = ['0'] * 5
bools = [False] * 5
# Python 的列表可以自由存储各种基本数据类型和对象引用
data = [0, 0.0, 'a', False, ListNode(0)]
数字编码
原码、反码和补码
首先需要指出,数字是以“补码”的形式存储在计算机中的。在分析这样做的原因之前,首先给出三者的定义
**原码:**我们将数字的二进制表示的最高位视为符号位,其中 0 表示正数,1 表示负数,其余位表示数字的值。
**反码:**正数的反码与其原码相同,负数的反码是对其原码除符号位外的所有位取反。
**补码:**正数的补码与其原码相同,负数的补码是在其反码的基础上加 1 。
浮点数编码
字符编码
在计算机中,所有数据都是以二进制数的形式存储的,字符 char 也不例外。为了表示字符,我们需要建立一套“字符集”,规定每个字符和二进制数之间的一一对应关系。有了字符集之后,计算机就可以通过查表完成二进制数到字符的转换。
ASCII 字符集
ASCII 码是最早出现的字符集,其全称为 American Standard Code for Information Interchange(美国标准信息交换代码)。它使用 7 位二进制数(一个字节的低 7 位)表示一个字符,最多能够表示 128 个不同的字符。如图 3-6 所示,ASCII 码包括英文字母的大小写、数字 0 ~ 9、一些标点符号,以及一些控制字符(如换行符和制表符)
然而,ASCII 码仅能够表示英文。随着计算机的全球化,诞生了一种能够表示更多语言的 EASCII 字符集。它在 ASCII 的 7 位基础上扩展到 8 位,能够表示 256 个不同的字符。
在世界范围内,陆续出现了一批适用于不同地区的 EASCII 字符集。这些字符集的前 128 个字符统一为 ASCII 码,后 128 个字符定义不同,以适应不同语言的需求。
GBK字符集
后来人们发现,EASCII 码仍然无法满足许多语言的字符数量要求。比如汉字有近十万个,光日常使用的就有几千个。中国国家标准总局于 1980 年发布了 GB2312 字符集,其收录了 6763 个汉字,基本满足了汉字的计算机处理需要。
然而,GB2312 无法处理部分罕见字和繁体字。GBK 字符集是在 GB2312 的基础上扩展得到的,它共收录了 21886 个汉字。在 GBK 的编码方案中,ASCII 字符使用一个字节表示,汉字使用两个字节表示。
Unicode 字符集
随着计算机技术的蓬勃发展,字符集与编码标准百花齐放,而这带来了许多问题。一方面,这些字符集一般只定义了特定语言的字符,无法在多语言环境下正常工作。另一方面,同一种语言存在多种字符集标准,如果两台计算机使用的是不同的编码标准,则在信息传递时就会出现乱码。
那个时代的研究人员就在想:如果推出一个足够完整的字符集,将世界范围内的所有语言和符号都收录其中,不就可以解决跨语言环境和乱码问题了吗?在这种想法的驱动下,一个大而全的字符集 Unicode 应运而生。
Unicode 的中文名称为“统一码”,理论上能容纳 100 多万个字符。它致力于将全球范围内的字符纳入统一的字符集之中,提供一种通用的字符集来处理和显示各种语言文字,减少因为编码标准不同而产生的乱码问题。
自 1991 年发布以来,Unicode 不断扩充新的语言与字符。截至 2022 年 9 月,Unicode 已经包含 149186 个字符,包括各种语言的字符、符号甚至表情符号等。在庞大的 Unicode 字符集中,常用的字符占用 2 字节,有些生僻的字符占用 3 字节甚至 4 字节。
Unicode 是一种通用字符集,本质上是给每个字符分配一个编号(称为“码点”),但它并没有规定在计算机中如何存储这些字符码点。我们不禁会问:当多种长度的 Unicode 码点同时出现在一个文本中时,系统如何解析字符?例如给定一个长度为 2 字节的编码,系统如何确认它是一个 2 字节的字符还是两个 1 字节的字符?
对于以上问题,一种直接的解决方案是将所有字符存储为等长的编码。如图 3-7 所示,“Hello”中的每个字符占用 1 字节,“算法”中的每个字符占用 2 字节。我们可以通过高位填 0 将“Hello 算法”中的所有字符都编码为 2 字节长度。这样系统就可以每隔 2 字节解析一个字符,恢复这个短语的内容了。
UTF-8 编码
除了 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 。
编程语言的字符编码
参考
hello算法第3章
原文地址:https://blog.csdn.net/weixin_44006060/article/details/144170354
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!