第2课数据结构_分类
热度🔥:42 免费课程
授课语音
数据结构分类
1. 介绍
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆和图，分为逻辑结构和物理结构。
1.1 逻辑结构
逻辑结构描述了数据之间的关系和组织方式，主要分为线性结构和非线性结构。
线性结构
线性结构中的数据元素按顺序排列，每个元素有且只有一个前驱和一个后继。主要包括：
数组（Array）：一组相同类型的元素，按顺序存储在内存中。支持随机访问，但插入和删除操作较慢，因为可能需要移动大量元素。
链表（Linked List）：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的变体包括：
- 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
- 双链表（Doubly Linked List）：每个节点有两个指针，分别指向前一个节点和下一个节点。
- 循环链表（Circular Linked List）：链表的尾节点指向头节点，形成一个环。
栈（Stack）：遵循“后进先出”（LIFO）原则的数据结构。主要操作有推入（push）和弹出（pop）。
队列（Queue）：遵循“先进先出”（FIFO）原则的数据结构。主要操作有入队（enqueue）和出队（dequeue）。它的变体包括：
- 双端队列（Deque）：可以在两端进行插入和删除操作的队列。
- 优先队列（Priority Queue）：每个元素都有一个优先级，按照优先级顺序进行操作。
非线性结构
非线性结构中的数据元素没有线性排列的顺序，元素间的关系更加复杂。主要包括：
树（Tree）：一种分层的数据结构，包含节点和边。每个节点可以有零个或多个子节点。常见的树结构包括：
二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）。
- 完全二叉树（Complete Binary Tree）：除了最后一层外，每层的节点都完全填满，最后一层的节点从左到右依次填充。
- 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
- 平衡二叉树（Balanced Binary Tree）：每个节点的左右子树的高度差不超过某个阈值（通常为1）。
二叉搜索树（Binary Search Tree, BST）：二叉树的一种，其中左子树的值小于根节点的值，右子树的值大于根节点的值。
- AVL平衡树（Balanced Tree）：自平衡的二叉搜索树，任意节点的左右子树高度差不超过1。
- 红黑树（Red-Black Tree）：自平衡的二叉搜索树，节点颜色限制。
B树（B Tree）：自平衡的多路搜索树，适合存储和检索。每个节点可以有多个子节点，每个节点包含多个键（keys）和子节点指针。
B+树（B+ Tree）：B树的变体，所有键值都存储在叶子节点中，内部节点仅存索引。
堆（Heap）：一种特殊的完全二叉树，用于实现优先队列。分为最大堆（根节点最大）和最小堆（根节点最小）。
图（Graph）：由节点（顶点）和连接节点的边组成的结构。图可以是：
- 无向图（Undirected Graph）：边没有方向，连接两个节点。
- 有向图（Directed Graph）：边有方向，从一个节点指向另一个节点。
- 加权图（Weighted Graph）：边有权值，表示连接的代价或距离。
- 无权图（Unweighted Graph）：边没有权值，只有连接关系。
哈希表 是一种非常重要的数据结构，用于实现高效的插入、删除和查找操作。它通过哈希函数将数据映射到数组中的特定位置，以便在常数时间内完成这些操作。
图示
1.2 物理结构
物理结构描述了数据如何在计算机内存中实际存储。主要分为内存连续结构和内存分散结构。
内存连续结构：数据在内存中是连续存储的。主要包括：
- 数组（Array）：数据元素在内存中连续存储，支持快速随机访问。
内存分散结构：数据在内存中不是连续存储的，而是通过指针或引用连接起来。主要包括：
- 链表（Linked List）：节点在内存中分散存储，每个节点包含数据和指向下一个节点的指针（或双向链表中还包含指向前一个节点的指针）。
所有的数据结构都是基于数组、链表或两者的组合实现的。
2. 代码案例
import java.util.*;
// ====================== 线性结构 ===========================
// 1. 数组（Array）类
class ArrayStructure {
private int size; // 数组大小
private int[] array; // 数组数据
// 构造函数，初始化数组
public ArrayStructure(int size) {
this.size = size;
array = new int[size]; // 初始化数组，默认值为 0
}
// 设置指定索引的值
public void set(int index, int value) {
if (index >= 0 && index < size) {
array[index] = value;
} else {
throw new IndexOutOfBoundsException("Index out of bounds"); // 索引越界错误
}
}
// 获取指定索引的值
public int get(int index) {
if (index >= 0 && index < size) {
return array[index];
} else {
throw new IndexOutOfBoundsException("Index out of bounds"); // 索引越界错误
}
}
// 打印数组内容
public void print() {
for (int item : array) {
System.out.print(item + " "); // 输出数组元素
}
System.out.println();
}
}
// 2. 链表（Linked List）
// 2.1 单链表（Singly Linked List）节点类
class Node {
public int data; // 节点数据
public Node next; // 指向下一个节点的指针
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 单链表（Singly Linked List）类
class SinglyLinkedList {
private Node head; // 链表头节点
public SinglyLinkedList() {
head = null; // 初始化空链表
}
// 向链表末尾添加新节点
public void append(int data) {
Node newNode = new Node(data); // 创建新节点
if (head == null) {
head = newNode; // 如果链表为空，直接将头指针指向新节点
} else {
Node last = head;
while (last.next != null) { // 找到链表的最后一个节点
last = last.next;
}
last.next = newNode; // 将最后一个节点的指针指向新节点
}
}
// 打印链表内容
public void print() {
Node current = head;
while (current != null) { // 遍历链表
System.out.print(current.data + " -> "); // 输出节点数据
current = current.next;
}
System.out.println("None"); // 输出链表结束标志
}
}
// 2.2 双链表（Doubly Linked List）节点类
class DoublyNode {
public int data; // 节点数据
public DoublyNode next; // 指向下一个节点的指针
public DoublyNode prev; // 指向前一个节点的指针
public DoublyNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// 双链表（Doubly Linked List）类
class DoublyLinkedList {
private DoublyNode head; // 双链表头节点
public DoublyLinkedList() {
head = null; // 初始化空链表
}
// 向双链表末尾添加新节点
public void append(int data) {
DoublyNode newNode = new DoublyNode(data); // 创建新节点
if (head == null) {
head = newNode; // 如果链表为空，将头指针指向新节点
} else {
DoublyNode last = head;
while (last.next != null) { // 找到链表的最后一个节点
last = last.next;
}
last.next = newNode; // 将最后一个节点的指针指向新节点
newNode.prev = last; // 设置新节点的前向指针
}
}
// 打印双链表内容
public void print() {
DoublyNode current = head;
while (current != null) { // 遍历双链表
System.out.print(current.data + " <-> "); // 输出节点数据
current = current.next;
}
System.out.println("None"); // 输出链表结束标志
}
}
// 2.3 循环链表（Circular Linked List）节点类
class CircularNode {
public int data; // 节点数据
public CircularNode next; // 指向下一个节点的指针
public CircularNode(int data) {
this.data = data;
this.next = null;
}
}
// 循环链表（Circular Linked List）类
class CircularLinkedList {
private CircularNode head; // 循环链表头节点
public CircularLinkedList() {
head = null; // 初始化空链表
}
// 向循环链表末尾添加新节点
public void append(int data) {
CircularNode newNode = new CircularNode(data); // 创建新节点
if (head == null) {
head = newNode; // 如果链表为空，将头指针指向新节点
newNode.next = newNode; // 新节点的 next 指向自己，形成循环
} else {
CircularNode last = head;
while (last.next != head) { // 找到链表的最后一个节点
last = last.next;
}
last.next = newNode; // 将最后一个节点的 next 指向新节点
newNode.next = head; // 新节点的 next 指向头节点，完成循环
}
}
// 打印循环链表内容
public void print() {
if (head == null) { // 如果链表为空
System.out.println("Empty List");
return;
}
CircularNode current = head;
do { // 遍历循环链表
System.out.print(current.data + " -> "); // 输出节点数据
current = current.next;
} while (current != head); // 循环直到回到头节点
System.out.println("(back to head)"); // 输出回到头节点的标志
}
}
// 3. 栈（Stack）类
class Stack {
private List<Integer> items; // 栈内存储的元素
public Stack() {
items = new ArrayList<>();
}
// 压栈操作
public void push(int item) {
items.add(item);
}
// 弹栈操作
public int pop() {
if (isEmpty()) {
throw new NoSuchElementException("pop from empty stack"); // 栈空时弹栈错误
}
int top = items.get(items.size() - 1); // 获取栈顶元素
items.remove(items.size() - 1); // 弹出栈顶元素
return top;
}
// 查看栈顶元素
public int peek() {
if (isEmpty()) {
throw new NoSuchElementException("peek from empty stack"); // 栈空时查看栈顶错误
}
return items.get(items.size() - 1); // 返回栈顶元素
}
// 判断栈是否为空
public boolean isEmpty() {
return items.size() == 0;
}
// 获取栈的大小
public int size() {
return items.size();
}
}
// 4. 队列（Queue）类
class Queue {
private List<Integer> items; // 队列内存储的元素
public Queue() {
items = new ArrayList<>();
}
// 入队操作
public void enqueue(int item) {
items.add(item);
}
// 出队操作
public int dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("dequeue from empty queue"); // 队列空时出队错误
}
int front = items.get(0); // 获取队首元素
items.remove(0); // 移除队首元素
return front;
}
// 判断队列是否为空
public boolean isEmpty() {
return items.size() == 0;
}
// 获取队列的大小
public int size() {
return items.size();
}
}
// ====================== 非线性结构 ===========================
// 1. 二叉树（Binary Tree）节点类
class TreeNode {
public int data; // 节点数据
public TreeNode left; // 左子节点
public TreeNode right; // 右子节点
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// 二叉树（Binary Tree）类
class BinaryTree {
private TreeNode root;
// 根节点
public BinaryTree() {
root = null; // 初始化为空树
}
// 插入节点
public void insert(int data) {
root = insertRec(root, data); // 从根节点开始插入
}
// 递归插入节点
private TreeNode insertRec(TreeNode node, int data) {
if (node == null) {
return new TreeNode(data); // 如果节点为空，创建新节点
}
if (data < node.data) {
node.left = insertRec(node.left, data); // 如果数据小于当前节点，递归插入左子树
} else {
node.right = insertRec(node.right, data); // 如果数据大于当前节点，递归插入右子树
}
return node;
}
// 中序遍历
public void inorder() {
inorderRec(root); // 从根节点开始中序遍历
System.out.println();
}
// 递归中序遍历
private void inorderRec(TreeNode node) {
if (node != null) {
inorderRec(node.left); // 遍历左子树
System.out.print(node.data + " "); // 输出节点数据
inorderRec(node.right); // 遍历右子树
}
}
}
// 2. 堆（Heap）类
class MinHeap {
private List<Integer> heap; // 存储堆元素
public MinHeap() {
heap = new ArrayList<>();
}
// 向上调整堆
private void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap.get(index) < heap.get(parent)) {
swap(index, parent); // 如果当前元素小于父节点，交换
index = parent; // 更新当前索引
} else {
break;
}
}
}
// 向下调整堆
private void heapifyDown(int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int smallest = index;
if (leftChild < heap.size() && heap.get(leftChild) < heap.get(smallest)) {
smallest = leftChild; // 左子节点更小
}
if (rightChild < heap.size() && heap.get(rightChild) < heap.get(smallest)) {
smallest = rightChild; // 右子节点更小
}
if (smallest != index) {
swap(index, smallest); // 交换当前节点与最小子节点
heapifyDown(smallest); // 继续调整
}
}
// 交换堆中两个元素的位置
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
// 插入元素
public void insert(int value) {
heap.add(value); // 将元素添加到堆末尾
heapifyUp(heap.size() - 1); // 调整堆
}
// 删除最小元素
public int extractMin() {
if (heap.isEmpty()) {
throw new NoSuchElementException("Heap is empty"); // 堆为空错误
}
int minValue = heap.get(0); // 获取最小值
heap.set(0, heap.get(heap.size() - 1)); // 将堆尾元素移到堆顶
heap.remove(heap.size() - 1); // 移除堆尾元素
heapifyDown(0); // 调整堆
return minValue;
}
}
// 3. 图（Graph）类
class Graph {
private Map<Integer, List<Integer>> adjList; // 图的邻接表表示
public Graph() {
adjList = new HashMap<>();
}
// 添加边
public void addEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v); // 添加 u -> v 边
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // 添加 v -> u 边（无向图）
}
// 打印图的邻接表
public void printGraph() {
for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
System.out.print(entry.getKey() + " -> ");
for (Integer neighbor : entry.getValue()) {
System.out.print(neighbor + " "); // 输出邻接节点
}
System.out.println();
}
}
}
// 主程序，测试各种数据结构
public class Main {
public static void main(String[] args) {
// ====================== 测试数组 =======================
ArrayStructure arr = new ArrayStructure(5);
arr.set(0, 10);
arr.set(1, 20);
arr.print();
// ====================== 测试单链表 =======================
SinglyLinkedList sll = new SinglyLinkedList();
sll.append(1);
sll.append(2);
sll.append(3);
sll.print();
// ====================== 测试栈 =======================
Stack stack = new Stack();
stack.push(10);
stack.push(20);
System.out.println(stack.pop());
// ====================== 测试队列 =======================
Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
System.out.println(queue.dequeue());
// ====================== 测试二叉树 =======================
BinaryTree bt = new BinaryTree();
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.inorder();
// ====================== 测试堆 =======================
MinHeap minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(1);
System.out.println(minHeap.extractMin());
// ====================== 测试图 =======================
Graph g = new Graph();
g.addEdge(1, 2);
g.addEdge(1, 3);
g.printGraph();
}
}
解释：
- 集合类型：在 Java 中使用
ArrayList和HashMap。 - 异常处理：Java 中使用
NoSuchElementException。 - 方法和成员命名：Java 使用小写字母的方式（例如
set,get））。
3. 总结
本文概述了常见的数据结构及其分类，分别介绍了逻辑结构和物理结构，并通过代码示例展示了各种数据结构的基本实现。掌握这些数据结构将有助于高效地处理和存储数据。
系列课程：
📱 下载客户端
小程序
安卓APP
iOS APP
📚 视频课程
- Java入门教程 86
- Python入门教程 33
- JavaScript入门教程 35
- C++入门教程 45
- Go入门教程 38
- 数据结构与算法 30
- 设计模式入门 23
- SQL入门教程 29
- C语言入门教程 25
- TypeScript入门教程 19