logseq-1/pages/数据结构.md

数据结构的分类

- [[数组与链表]]
- [[栈与队列]]
- ### 逻辑结构
- 线性结构
	- [[数组]]
	- [[链表]]
	- [[栈]]
	- [[队列]]
	- [[哈希表]]，元素之间一对一
- 非线性结构
	- [[树]]
	- [[堆]]
	- [[图]]
	- 哈希表
- 树形结构
	- 树
	- 堆
	- 哈希表，元素之间一对一
- 网状结构
	- 图，元素之间多对多
- ### 物理结构
- [[算法]]运行时，处理的数据主要存储于内存中
- 系统通过内存地址来访问目标位置的数据
- 数据结构与算法的设计中，内存是一个重要的考虑因素
- 物理结构反映了数据在内存中的存储发昂是
	- 连续空间存储（数组）
	- 分散空间存储（链表）
- > 所有数据结构都是基于数组、链表或二者的组合实现的
- 基于数组
	- 栈、队列、哈希表、树、堆、图、矩阵、张量（维度大于等于3 的数组）
- 基于链表
	- 栈、队列、哈希表、树、堆、图

• 基本数据类型

  • 基本数据类型是CPU可以直接进行运算的类型

  • 整数类型
    • byte
    • short
    • int
    • long
  • 浮点数类型
    • float
    • double
  • 字符类型
    • char
  • 布尔类型
    • bool
  • 基本数据类型的占用空间和取值范围
    • 
  • 基本数据类型提供了数据的”内容类型“，而数据结构提供了数据的组织方式

• 数字编码

  • 数字是以”补码“的形式存储在计算机中的

  • 原码
    • 数字的二进制最高为视为符号位，0正1负，其余表示数字的值
  • 反码
    • 对原码除符号位外所有数字取反
  • 补码
    • 正数的补码与原码相同，负数的补码是在反码的基础上加1
  • 浮点数 32bit
    • 符号位S：1bit
    • 指数位E：8bit
      • E=0表示零
      • E=255表示无穷大 NaN
    • 分数位N：23bit
  • float 的表示方式包含指数位，导致其取值范围远大于 int
  • id:: 6659374d-dfae-436f-af1d-3d1fdf513b37

    尽管浮点数 float 扩展了取值范围，但其副作用是牺牲了精度

• 字符编码

  • ASICC字符集
    • 共128个字符，仅能表示英文
  • GBK字符集
    • GB2312字符集，6763个汉字
    • GBK字符集，21886个汉字
    • ASICC一个字节表示，汉字两个字节表示
  • Unicode字符集
    • 多种语言，同一语言也有多种字符集
    • 当多种长度的 Unicode 码点同时出现在一个文本中时，系统如何解析字符？
      • 一种直接的解决方案是将所有字符存储为等长的编码
  • UTF-8编码
    • 可变长编码，使用1-4字节表示一个字符
    • 向下兼容ASICC编码
    • UTF-16，使用2-4字节表示一个字符
    • UTF-32，每个字符都使用4个字节表示
  • 编程语言的字符编码
    • 使用UTF-16或UTF-32编码
    • 字符串可看成数组表示
      • 随机访问
      • 字符计数
      • 字符串操作