数据结构与算法之概念

allenxx / 2023-09-01 / 原文

1. 数据结构

存储、组织数据的方式包括数组、链表、堆、栈、队列、树、图等

同样的数据不同的组织方式就是数据结构。比如对老王的姓名、年龄、性别的描述：

　　列表方式：[老王,18,男]
　　字典方式:{name:"老王",age:18,sex:"男"}

而列表、字典存储了老外的数据并按照不同的方式存储在内存中。

分类

1. 线性结构：线性结构中的数据元素之间存在一对一的关系，即每个元素只有一个直接前驱和一个直接后继。常见的线性结构包括数组、链表、栈和队列等。

数组（Array）：一组具有相同类型的元素按照一定顺序排列，并通过索引访问。
链表（Linked List）：一组节点按照顺序连接而成的数据结构，每个节点包含数据和指向下一个节点的指针。
栈（Stack）：一种具有特殊操作限制的线性表，按照“先进后出”的原则进行插入和删除操作。
队列（Queue）：一种具有特殊操作限制的线性表，“先进先出”的原则进行插入和删除操作。

2. 树形结构：树形结构中的数据元素之间存在一对多的关系，即每个元素有且仅有一个直接前驱，但可以有多个直接后继。常见的树形结构包括二叉树、堆和哈夫曼树等。

二叉树（Binary Tree）：每个节点最多有两个子节点的树结构。
堆（Heap）：一种特殊的二叉树，每个节点的值都大于或小于其子节点的值，用于实现优先队列等应用。
哈夫曼树（Huffman Tree）：通过频率来构建的一种特殊二叉树，常被用于数据压缩。

3. 图形结构：图形结构中的数据元素之间存在多对多的关系，即每个元素可以与其他任意元素有关联。常见的图形结构包括有向图和无向图等。

有向图（Directed Graph）：图中的边具有方向性。
无向图（Undirected Graph）：图中的边没有方向性。

4. 散列结构：散列结构利用散列函数将数据元素映射到一个固定位置，常用于实现哈希表等。

以上只是数据结构的一些常见分类，实际上还有很多其他类型的数据结构，如集合、链表、树堆、图等。不同的数据结构适用于不同的场景和问题，选择合适的数据结构可以提高算法效率和程序性能。

1.1 数组

一组连续存储的相同类型元素的集合。连续存储说的是内存空间的使用情况，表示是一块连续内存空间。访问可以根据索引访问

1.2 链表

由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。在内存空间的表现是不连续，通过指针建立前后关系

1.3 堆

在计算机科学中，"堆"（Heap）是一种用于动态内存分配的数据结构。堆用于存储程序运行时分配和释放的数据，例如对象、函数的局部变量等。

它与栈（Stack）不同，栈用于存储函数调用的上下文和局部变量。

堆是一块大的内存区域，它的大小在程序运行时可以动态地增长或缩小，允许程序在需要时动态地分配内存。

在堆中分配的内存块通常由程序员手动分配和释放（java有垃圾回收机制），这需要一些管理工作以避免内存泄漏和悬挂指针等问题。

在堆中，数据存储的方式不是按照线性顺序，而是以一种更为灵活的方式进行组织。

对象和数据结构可以在堆中的不同位置分布，而且它们的大小不需要事先确定。这使得堆成为动态内存分配的理想选择，特别是在需要存储不同大小和不同生命周期的数据时。

值得注意的是，堆不仅仅用于动态内存分配，还用于存储在程序运行期间需要长时间存在的数据，如全局变量和动态分配的对象。

不同的编程语言和操作系统对于堆的管理方式可能会有所不同。

1.4 栈

一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。或者说先进后出

1.5 队列

一种先进先出的数据结构。

队列（Queue）遵循先进先出（First-In-First-Out，FIFO）的原则。在队列中，首先被添加到队列的元素也将首先被移除，类似于排队等候的概念。

队列有两个主要操作：入队（Enqueue）和出队（Dequeue）。入队操作将元素添加到队列的尾部，出队操作将队列的头部元素移除并返回。

队列常常用于模拟排队等待的场景，例如打印任务队列、计算机进程调度等。在编程中，队列的应用非常广泛，它可以帮助我们有效地管理和操作一系列数据。

1.6 树结构

1.7 图结构

有向图

无向图

1.8 哈希表

2. 数据类型

JAVA

Java常见的数据类型

列表、集合、字典/map都是以类存在的
Java是编译解释语言，也是强类型语言、静态类型语言
对于数据结构来说这些数据都可以存储。有1点特别注意：数组结构也可以存储数组这种数据（就是绕了点，说白了就是数组中的元素是数组）

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        Object [] array = new Object[2];
        array[0]=new int[]{1,2,3};
        array[1]=new int[]{3,4,5};
        System.out.println(Arrays.toString((int[]) array[0]));
        System.out.println(Arrays.toString((int[]) array[1]));
    }
}