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 树结构

树结构（Tree）是一种的非线性数据结构，它由节点（Node）组成，节点之间通过边（Edge）相连接。

树的第一个节点称为根节点（Root），它没有父节点；其他节点都有一个父节点，可以有零个或多个子节点。

树结构的一个重要特性是它的层次性，节点之间有明确定义的层级关系。

树结构的核心概念：

1. 根节点（Root）： 树的起始节点，没有父节点。
2. 父节点（Parent）： 有子节点的节点。
3. 子节点（Child）： 直接连接到父节点的节点。
4. 叶子节点（Leaf）： 没有子节点的节点。
5. 兄弟节点（Sibling）： 具有相同父节点的节点。
6. 祖先节点（Ancestor）： 某节点的父节点、父节点的父节点等等。
7. 后代节点（Descendant）： 某节点的子节点、子节点的子节点等等。

树结构的示例（二叉树）

下面是一个简单的二叉树的示例，其中包含了整数值作为节点的数据：

• 根节点是 10。
• 10 的左子节点是 5，右子节点是 15。
• 5 的左子节点是 3，右子节点是 7。
• 15 的左子节点是 12，右子节点是 20。

分类

树结构（Tree）在计算机科学中具有多种不同的分类，它们适用于不同的应用和问题。以下是一些常见的树结构分类和详细解释：

1. 二叉树（Binary Tree）：
   • 二叉树是一种树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。左子节点通常存储比父节点小的值，右子节点存储比父节点大的值。
   • 特殊的二叉树包括满二叉树（每个节点要么没有子节点，要么恰好有两个子节点，满二叉树的节点数量可以用公式计算：N = 2^H – 1，其中 N 表示节点数量，H 表示树的高度。满二叉树的高度是固定的，取决于节点数量）和完全二叉树（除了最后一层，其他层都是满的，而且最后一层的节点都尽量靠左排列。高度可以根据节点数量进行计算，通常为 log2(N)（向上取整），N是节点数。不要求每个节点都有两个子节点，但是如果某个节点有子节点，它的子节点一定是从左到右依次添加的，不会有空缺的位置。）。
2. 二叉搜索树（Binary Search Tree，BST）：
   • 二叉搜索树是一种二叉树，它具有以下性质：
     • 左子树中的所有节点的值都小于根节点的值。
     • 右子树中的所有节点的值都大于根节点的值。
     • 左右子树都是二叉搜索树。
   • BST 可以用于高效的查找、插入和删除操作。
3. 平衡二叉树（Balanced Binary Tree）：
   • 平衡二叉树是一种特殊的二叉搜索树，它确保树的高度平衡，避免出现极端不平衡的情况。平衡树的操作效率更稳定。
4. 红黑树（Red-Black Tree）：
   • 红黑树是一种自平衡二叉搜索树，它通过规定节点的颜色和旋转操作来保持平衡。红黑树的高度永远不会超过 2 倍的最短路径。
5. B树（B-Tree）：
   • B树是一种多叉树（每个节点可以有多个子节点），通常用于数据库和文件系统中。它具有平衡性和高度可调性，能够存储大量数据。
6. 堆（Heap）：
   • 堆是一种特殊的树结构，通常是一个完全二叉树。堆分为最小堆和最大堆两种类型，用于高效地查找最小值或最大值。
7. Trie（前缀树）：
   • Trie 是一种树结构，用于高效存储和检索字符串集合。它的每个节点代表一个字符，从根节点到叶子节点的路径构成一个字符串。
8. AVL树：
   • AVL树是一种自平衡二叉搜索树，确保树的高度平衡。它在插入和删除操作时会自动执行旋转操作以维持平衡。
9. 伸展树（Splay Tree）：
   • 伸展树是一种自适应树结构，它通过伸展操作将最近访问的节点移到根节点位置，以提高最近访问节点的访问效率。

这些是一些常见的树结构分类，每种树结构都有自己的特点和适用场景。根据具体的问题和需求，选择合适的树结构可以提高算法和数据结构的效率。

满二叉树和完美二叉树区别：

• 满二叉树的每个节点要么没有子节点，有子节点必须有两个子节点，高度是固定的。
• 完全二叉树的高度可以根据节点数量计算，最后一层节点从左到右排列，不会有空缺。

满二叉树：

 完美二叉树：

树结构的应用：

1. 二叉树（Binary Tree）： 每个节点最多有两个子节点，左子节点和右子节点。常用于搜索、排序和表示层次关系等任务。
2. 二叉搜索树（Binary Search Tree，BST）： 一种特殊的二叉树，左子树中的节点值小于根节点，右子树中的节点值大于根节点。用于高效的查找、插入和删除操作。
3. 平衡二叉树（Balanced Binary Tree）： 一种特殊的二叉搜索树，确保树的高度平衡，以提高性能。
4. 堆（Heap）： 用于高效地找到最大或最小元素，常用于优先队列、堆排序等。
5. 树表达式（Expression Tree）： 用于表示数学表达式，如算术表达式或布尔表达式，方便求值。
6. 文件系统（File System）： 文件和目录可以表示为树结构，其中根目录是根节点，子目录是父目录的子节点。
7. HTML DOM（Document Object Model）： 用于表示网页文档的树结构，方便操作和修改网页内容。

 树结构的深度

树结构的深度（Depth）是指树中从根节点到某个节点的最长路径的长度。深度也可以表示树的层数，即树中最深的节点所在的层级。

下面来详细解释树结构的深度：

1. 树的根节点深度为 0： 根节点是树的起始点，因此它的深度为 0。
2. 子节点的深度是父节点深度加 1： 在一棵树中，每个子节点的深度都是其父节点深度加 1。
3. 树的深度是最深节点的深度： 一棵树的深度等于其中最深的节点的深度。
4. 深度与层级： 深度也可以表示为树的层数。根节点所在的层级是第 0 层，树的深度等于最底层叶子节点所在的层级。

深度的概念在树的操作和遍历中非常重要，因为它决定了你可以在树中搜索的范围。在深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）等算法中，深度是一个关键参数。

下面是一个示例树结构，让我们计算树中各个节点的深度:

• 节点 A 的深度为 0。
• 节点 B 和节点 C 的深度为 1。
• 节点 D、节点 E 和节点 F 的深度为 2。

在这个示例中，树的深度是 2，因为最深的节点（D、E、F）位于第 2 层。了解树的深度可以帮助你确定树的结构，以及如何在树中进行搜索和操作。

1.7 图结构

图结构（Graph）用于表示对象之间的关系。

图由节点（Node）和边（Edge）组成，节点表示对象，边表示对象之间的关系。

图可以用于解决各种实际问题，如社交网络分析、路由算法、关系数据库等。

基本概念：

1. 节点（Node）：
   • 节点也称为顶点（Vertex），表示图中的对象或实体。节点可以存储任何类型的数据。
   • 节点之间可以有连接，也可以没有。
2. 边（Edge）：
   • 边表示节点之间的关系，它可以是有向的或无向的。
   • 有向边从一个节点指向另一个节点，具有方向性。
   • 无向边没有方向，表示节点之间的双向关系。
3. 路径（Path）：
   • 路径是节点和边的序列，连接图中的节点。路径可以为空（长度为 0），或者包含一个或多个节点和边。
4. 有向图和无向图：
   • 有向图（Directed Graph）包含有向边，其中边从一个节点指向另一个节点。
   • 无向图（Undirected Graph）包含无向边，边没有方向，表示节点之间的对等关系。
5. 权重（Weight）：
   • 对于加权图（Weighted Graph），每条边都关联一个权重或成本，用于表示边的属性或距离。

分类

1. 无向图（Undirected Graph）：
   • 无向图中的边没有方向，节点之间的关系是对等的。
2. 有向图（Directed Graph，Digraph）：
   • 有向图中的边具有方向，表示节点之间的单向关系。
3. 加权图（Weighted Graph）：
   • 加权图中的边具有权重，通常用于表示距离、成本等。
4. 稀疏图和稠密图：
   • 稀疏图具有较少的边，节点之间的连接相对较少。
   • 稠密图具有大量的边，节点之间的连接相对较多。

 

图的应用：

图结构在许多领域中都有广泛的应用，包括但不限于：

• 社交网络分析：用于表示社交网络中的用户和关系。
• 路由算法：用于网络路由和路径规划。
• 数据库：用于关系数据库中的表与表之间的关系。
• 编译器设计：用于表示源代码的语法结构。
• 地理信息系统（GIS）：用于地图和地理空间数据的表示。

图是一种非常强大的数据结构，可以用于解决各种复杂的问题，但也需要谨慎使用，因为图算法的复杂度通常较高。

示例

考虑一个社交网络中的图结构，其中表示了一些用户之间的关系。

在这个图中，每个节点代表一个用户，边代表用户之间的关系，例如友谊关系。这是一个无向图，因为友谊关系是双向的。

解释：

• 节点（Vertices）：
  • A、B、C、D、E、F 分别代表六个用户。
• 边（Edges）：
  • 边表示用户之间的友谊关系。
  • 例如，A 与 B 之间有一条边，表示 A 和 B 是朋友。
  • 同样，B 与 C、C 与 E、E 与 D 都有边表示他们之间是朋友关系。
• 无向图（Undirected Graph）：
  • 这是一个无向图，因为边没有方向。如果 A 与 B 是朋友，那么 B 与 A 也是朋友。
• 路径（Paths）：
  • 路径是从一个节点到另一个节点经过的边的序列。例如，从 A 到 D 可以通过节点 B 和节点 E 获得路径：A -> B -> E -> D。
• 连通性（Connectivity）：
  • 图中的节点和边形成一个连通组件，也就是说，从任何一个节点出发，都可以到达图中的其他节点。
  • 例如，在这个图中，每个节点都与其他节点相连通。

这个图示例展示了一个简单的社交网络，其中用户之间的友谊关系表示为图的边。

图结构可以用于模拟和分析各种复杂的关系网络，包括社交网络、网络路由、组织结构等。图的节点和边的组织方式可以根据具体的应用和问题而变化。

1.8 哈希表

哈希表（Hash Table），也称为散列表，是一种常用的数据结构，用于高效地存储和检索数据。

哈希表基于哈希函数将数据存储在数组中，并通过哈希函数将键映射到数组的特定位置，从而实现快速的数据访问。

以下是哈希表的详细解释以及一个示例：

基本概念：

1. 哈希函数（Hash Function）：
   • 哈希函数是一个算法，它接受输入（例如键）并将其转换为固定大小的哈希值（散列码）。
   • 好的哈希函数应该具有以下特性：
     • 一致性：对于相同的输入，始终生成相同的哈希值。
     • 均匀性：尽量避免哈希冲突，即不同的输入应该映射到不同的哈希值。
     • 快速计算：哈希函数应该快速计算哈希值。
2. 哈希表数组（Hash Table Array）：
   • 哈希表通常是一个包含固定数量桶或槽的数组，每个桶用于存储数据。
   • 哈希函数将键映射到数组的特定索引位置。
3. 哈希冲突（Hash Collision）：
   • 当两个不同的键被哈希函数映射到相同的索引位置时，发生哈希冲突。
   • 解决哈希冲突的方法包括链地址法和开放地址法等。

哈希表的示例：

考虑一个简单的哈希表示例，用于存储学生的成绩信息。每个学生有一个唯一的学号作为键，对应的成绩作为值。

 1 # 创建一个哈希表
 2 hash_table = [None] * 10  # 使用长度为 10 的数组作为哈希表
 3 
 4 # 哈希函数示例：将学号取模来计算索引位置
 5 def hash_function(student_id):
 6     return student_id % len(hash_table)
 7 
 8 # 插入数据
 9 def insert_score(student_id, score):
10     index = hash_function(student_id)
11     if hash_table[index] is None:
12         hash_table[index] = []
13     hash_table[index].append((student_id, score))
14 
15 # 查找数据
16 def lookup_score(student_id):
17     index = hash_function(student_id)
18     if hash_table[index] is not None:
19         for item in hash_table[index]:
20             if item[0] == student_id:
21                 return item[1]
22     return None
23 
24 # 插入学生成绩
25 insert_score(101, 95)
26 insert_score(102, 88)
27 insert_score(103, 78)
28 
29 # 查找学生成绩
30 print("Student 101's score:", lookup_score(101))  # 输出：Student 101's score: 95
31 print("Student 102's score:", lookup_score(102))  # 输出：Student 102's score: 88
32 print("Student 104's score:", lookup_score(104))  # 输出：Student 104's score: None

在这个示例中，我们使用一个长度为 10 的数组作为哈希表。

我们定义了一个哈希函数来计算学生的学号对应的索引位置。

然后，我们可以插入学生成绩和查找学生成绩，通过哈希函数将学号映射到数组中的索引位置，实现了高效的数据存储和检索。

哈希表是一种非常强大且高效的数据结构，常用于解决数据存储和查找的问题。但需要注意的是，良好的哈希函数设计对于减少哈希冲突非常重要。

2.  数据类型

JAVA

Java常见的数据类型

1. 列表、集合、字典/map都是以类存在的
2. Java是编译解释语言，也是强类型语言、静态类型语言
3. 对于数据结构来说这些数据都可以存储。有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]));
    }
}

 输出：

1 2	[1, 2, 3] [3, 4, 5]

 1 # 归并排序函数
 2 def merge_sort(arr):
 3     if len(arr) <= 1:
 4         return arr
 5 
 6     # 分
 7     mid = len(arr) // 2
 8     left = arr[:mid]
 9     right = arr[mid:]
10 
11     # 递归地解决子问题
12     left = merge_sort(left)
13     right = merge_sort(right)
14 
15     # 合并子问题的解
16     return merge(left, right)
17 
18 # 合并函数
19 def merge(left, right):
20     result = []
21     i = j = 0
22 
23     while i < len(left) and j < len(right):
24         if left[i] < right[j]:
25             result.append(left[i])
26             i += 1
27         else:
28             result.append(right[j])
29             j += 1
30 
31     result.extend(left[i:])
32     result.extend(right[j:])
33     return result
34 
35 # 示例用法
36 arr = [38, 27, 43, 3, 9, 82, 10]
37 sorted_arr = merge_sort(arr)
38 print(sorted_arr)  # 输出：[3, 9, 10, 27, 38, 43, 82]

 1 # 阶乘计算的递归函数
 2 def factorial(n):
 3     # 基本情况
 4     if n == 0:  # 3：函数递归调用终止
 5         return 1
 6     # 递归调用
 7     else:
 8         return n * factorial(n - 1)  # 1&2： 函数里调用自己并建立此次调用与下次调用关系
 9 
10 # 示例用法
11 result = factorial(5)
12 print(result)  # 输出：120

 1 '''
 2 考虑一个找零钱的问题，假设有以下面额的硬币：1元、5元、10元、25元，以及一个顾客需要找零 n 元的需求。我们的目标是找零的硬币数量尽可能少。
 3 '''
 4 
 5 
 6 def greedy_coin_change(n, coins):
 7     coins.sort(reverse=True)  # 将硬币按面额降序排序
 8     change = []  # 存储找零的硬币列表
 9 
10     for i in range(0, len(coins), 1):  # range(start, stop, step),实践到stop-1
11         coin = coins[i]
12         print(coin)
13         while n >= coin:  # 每次都贪心，就想要大面额的硬币
14             n -= coin
15             change.append(coin)
16 
17     if n == 0:
18         return change
19     else:
20         return "无法找零"
21 
22 
23 def greedy_coin_change2(n, coins):
24     coins.sort(reverse=True)  # 将硬币按面额降序排序
25     change = []  # 存储找零的硬币列表
26 
27     for coin in coins:  # python、javascript for-each是按照列表的顺序顺序遍历的，但java不是，java是随机的
28         while n >= coin:
29             n -= coin
30             change.append(coin)
31 
32     if n == 0:
33         return change
34     else:
35         return "无法找零"
36 
37 
38 # 示例用法
39 n = 49
40 coins = [1, 5, 10, 25]
41 change = greedy_coin_change(n, coins)
42 print(change)  # 输出：[25, 10, 10, 1, 1, 1, 1]