3.1-数据结构

数据结构

逻辑结构

数据结构揭示数据与元素之间的关系，主要可以分为两类

• 线性：数组、链表、栈、队列、哈希表（一对一），元素之间为一对一的顺序关系
• 非线性数据结构：树、堆、图、哈希表（一对多）
  • 树形结构：树，堆，哈希表，元素之间为一对多
  • 图，元素之间为多对多

物理结构

算法运行时，正在处理的数据主要存储在内存中，系统通过内存地址来访问目标位置的数据

实际内存的工作机制比较复杂，涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。

内存是所有程序的共享资源，某个模块被程序占用，通常无法被其它程序同时使用。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如算法所占用的内存不应超过系统剩余空闲内存。如果缺少连续的内存空间，所选数据结构必须能存储在分散的内存空间内。

比如数组和链表的存储方式不同

• 连续空间存储（数组）占用空间比链表小
• 分散空间存储（链表）占用空间比数组大

所有数据结构都是基于数组、链表，或者两者的组合实现的

基本数据类型

基本数据类型是 CPU 可以直接进行运算的类型，主要包括以下几种

• 整数类型：byte、short、int、long
• 浮点数类型：float、double，表示小数
• 字符类型：char 表示各种语言的字母，标点甚至是表情
• 布尔类型：bool，表示 是 或者 否

基本数据类型以二进制的形式存储在计算机中。

• 整数类型 byte 占用 字节 = 比特 ，可以表示 个数字。
• 整数类型 int 占用 字节 = 比特 ，可以表示 个数字。