数据结构——常见数据结构和应用
数据结构是计算机科学中的一个基本概念，它涉及数据的组织、管理和存储方式。以下是对数据结构的详细解释：
一、定义与组成
- 数据：描述事物的符号记录，是计算机程序的输入和输出。它可以以多种形式存在，如数字、文字、图像、声音等。数据是信息的载体，具有可识别性、可存储性、可处理性和可传输性等特点。
- 数据对象：必须由软件理解的复合信息表示。它可以是外部实体、事物、偶发事件或事件、角色、组织单位、地点或结构等的抽象表示。数据对象具有独立性、意义性和封装性等特点，只封装数据，没有对数据的操作。
- 数据元素：数据的基本单位，也叫做结点或记录。在计算机程序中，数据元素通常作为一个整体进行考虑和处理。数据元素由数据项组成，数据项是构成数据元素的不可分割的最小单位。
- 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。这些关系定义了数据元素之间的逻辑结构和存储结构，以及可以对这些数据元素执行的操作。
二、逻辑结构
逻辑结构与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。常见的逻辑结构包括：
- 集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系。
- 线性结构：数据结构中的元素存在一对一的相互关系。典型的线性表有链表、栈和队列。它们共同的特点就是数据之间的线性关系，除了头结点和尾结点之外，每个结点都有唯一的前驱和唯一的后继，也就是所谓的一对一的关系。
- 树形结构：数据结构中的元素存在一对多的相互关系。每个节点有0个或多个子节点，没有父节点的节点称为根节点，每一个非根节点有且只有一个父节点。除了根节点外，每个子节点可以分为多个不相交的子树。
- 图形结构：数据结构中的元素存在多对多的相互关系。
三、存储结构
存储结构依赖于计算机，是数据的物理视图。常见的存储结构有：
- 顺序存储：用一段物理地址连续的存储单元依次存储数据元素的线性结构。特点为空间连续，支持随机访问，但中间或前面部分的插入删除时间复杂度较高，且增容的代价比较大。
- 链式存储：一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。包括无头单向非循环链表、带头双向循环链表等。特点为插入和删除操作的时间复杂度为O(1)，但需要额外的存储空间来保存指针；查找元素需要遍历整个链表，耗时较长。
- 索引存储：通过索引表来存储数据元素。索引表由若干索引项组成，每个索引项至少包含两个内容：关键字和该关键字所在数据的物理地址。
- 哈希存储：根据关键码值（key-value）直接访问的数据结构。特点为查找、插入和删除操作的时间复杂度通常为O(1)，但需要额外的存储空间来保存哈希函数和哈希表。
四、运算
运算是定义在数据的逻辑结构上的一组操作，用于对数据元素进行处理以实现特定功能。每种数据结构都有一个运算的集合，如搜索、插入、删除、更新、排序等。
五、分类
数据结构可以根据其逻辑结构和存储结构的不同进行分类，例如：
- 线性数据结构：如数组、链表（单链表、双向链表、循环链表）、栈和队列（）等。
- 非线性数据结构：如树（包括二叉树、平衡二叉树、红黑树等）、图（包括有向图和无向图）和堆（包括最大堆和最小堆）等。
六、常见数据结构及其应用
- 数组：用于存储和管理有序集合的数据，如列表。
public class ArrayExample { public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; // 访问数组元素 System.out.println(array[0]); // 输出 1 // 修改数组元素 array[0] = 10; System.out.println(array[0]); // 输出 10 } } - 链表：同样用于存储和管理有序集合的数据，如队列、栈等。链表允许在任意位置进行插入和删除操作，具有灵活性。
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } public class LinkedListExample { Node head; public void add(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; } } public void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } public static void main(String[] args) { LinkedListExample list = new LinkedListExample(); list.add(1); list.add(2); list.add(3); list.printList(); // 输出 1 2 3 } } - 栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。特点为后进先出（LIFO），通常用于递归调用、函数调用栈等场景。
public class StackExample { private int maxSize; private int[] stackArray; private int top; public StackExample(int size) { this.maxSize = size; this.stackArray = new int[maxSize]; this.top = -1; } public void push(int value) { if (isFull()) { System.out.println("Stack is full"); return; } stackArray[++top] = value; } public int pop() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } return stackArray[top--]; } public boolean isEmpty() { return (top == -1); } public boolean isFull() { return (top == maxSize - 1); } public static void main(String[] args) { StackExample stack = new StackExample(3); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // 输出 3 System.out.println(stack.pop()); // 输出 2 } } - 队列：一种先进先出的线性表，允许在一端进行插入操作（入队），在另一端进行删除操作（出队）。特点为先进先出（FIFO），常用于缓冲区、任务调度等场景。
public class QueueExample { private int front, rear, size; private int capacity; private int[] queue; public QueueExample(int capacity) { this.capacity = capacity; this.front = this.size = 0; this.rear = capacity - 1; this.queue = new int[capacity]; } private boolean isFull() { return size == capacity; } private boolean isEmpty() { return size == 0; } public void enqueue(int item) { if (isFull()) return; rear = (rear + 1) % capacity; queue[rear] = item; size = size + 1; } public int dequeue() { int item = -1; if (isEmpty()) return item; item = queue[front]; front = (front + 1) % capacity; size = size - 1; return item; } public int front() { if (isEmpty()) return -1; return queue[front]; } public int rear() { if (isEmpty()) return -1; return queue[rear]; } public static void main(String[] args) { QueueExample queue = new QueueExample(5); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(queue.dequeue()); // 输出 10 System.out.println(queue.front()); // 输出 20 System.out.println(queue.rear()); // 输出 40 } } - 树：由n（n≥1）个有限节点组成的一个具有层次关系的集合。常用于表示层次结构，如文件系统、组织结构图等。
class TreeNode { int data; TreeNode left, right; TreeNode(int item) { data = item; left = right = null; } } // 二叉树的基本操作（如插入、遍历等）需要额外实现 - 图：一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。图用于表示网络结构，如社交网络、交通网络等。
import java.util.*; class Graph { private int V; // 顶点数 private LinkedList<Integer> adj[]; // 邻接表 // 构造函数 Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList(); } // 添加边 void addEdge(int v, int w) { adj[v].add(w); // 添加w到v的列表 } // 打印图（用于调试） void printGraph() { for (int v = 0; v < V; ++v) { System.out.print("\n Adjacency list of vertex " + v); for (Integer n : adj[v]) System.out.print(" -> " + n); System.out.println(); } } public static void main(String args[]) { Graph g1 = new Graph(5); g1.addEdge(0, 1); g1.addEdge(0, 4); g1.addEdge(1, 2); g1.addEdge(1, 3); g1.addEdge(1, 4); g1.addEdge(2, 3); g1.addEdge(3, 4); g1.printGraph(); } } - 堆：一种特殊的完全二叉树结构，分为最大堆和最小堆。最大堆中每个节点的值都大于或等于其子节点的值；最小堆中每个节点的值都小于或等于其子节点的值。常用于实现优先队列等场景。
import java.util.Arrays; public class MaxHeap { private int[] heap; private int size; private int capacity; // 构造函数，初始化堆 public MaxHeap(int capacity) { this.capacity = capacity; this.heap = new int[capacity]; this.size = 0; } // 堆化一个数组以构建最大堆 public MaxHeap(int[] array) { this.capacity = array.length; this.heap = new int[capacity]; this.size = capacity; System.arraycopy(array, 0, heap, 0, capacity); for (int i = size / 2 - 1; i >= 0; i--) { heapifyDown(i); } } // 插入一个新元素 public void insert(int value) { if (size == capacity) { throw new IllegalStateException("Heap is full"); } heap[size] = value; size++; heapifyUp(size - 1); } // 获取堆顶元素（最大值） public int getMax() { if (size == 0) { throw new IllegalStateException("Heap is empty"); } return heap[0]; } // 移除堆顶元素 public int extractMax() { if (size == 0) { throw new IllegalStateException("Heap is empty"); } int maxValue = heap[0]; heap[0] = heap[size - 1]; size--; heapifyDown(0); return maxValue; } // 上滤操作，用于插入新元素后维护堆的性质 private void heapifyUp(int index) { while (index > 0) { int parentIndex = (index - 1) / 2; if (heap[parentIndex] < heap[index]) { swap(parentIndex, index); index = parentIndex; } else { break; } } } // 下滤操作，用于移除堆顶元素后维护堆的性质 private void heapifyDown(int index) { int largest = index; int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; if (leftChild < size && heap[leftChild] > heap[largest]) { largest = leftChild; } if (rightChild < size && heap[rightChild] > heap[largest]) { largest = rightChild; } if (largest != index) { swap(index, largest); heapifyDown(largest); } } // 交换堆中两个元素的位置 private void swap(int index1, int index2) { int temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } // 打印堆的内容 public void printHeap() { System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size))); } // 主方法，用于测试 public static void main(String[] args) { MaxHeap maxHeap = new MaxHeap(10); maxHeap.insert(3); maxHeap.insert(1); maxHeap.insert(6); maxHeap.insert(5); maxHeap.insert(2); maxHeap.insert(4); maxHeap.printHeap(); // 输出堆的内容 System.out.println("Max: " + maxHeap.getMax()); // 输出最大值 System.out.println("After extracting max:"); maxHeap.extractMax(); maxHeap.printHeap(); // 输出移除最大值后的堆内容 } } - 散列表：也叫哈希表，是根据键和值（key和value）直接进行访问的数据结构。通过key和value来映射到集合中的一个位置，从而可以很快找到集合中的对应元素。常用于实现快速查找、缓存等场景。
import java.util.HashMap; import java.util.Map; public class HashTableExample { public static void main(String[] args) { // 创建一个HashMap实例 Map<String, Integer> hashMap = new HashMap<>(); // 插入键值对 hashMap.put("apple", 1); hashMap.put("banana", 2); hashMap.put("orange", 3); // 访问元素 System.out.println("Value for key 'apple': " + hashMap.get("apple")); // 检查键是否存在 if (hashMap.containsKey("banana")) { System.out.println("Key 'banana' exists in the map."); } // 移除键值对 hashMap.remove("orange"); // 遍历HashMap for (Map.Entry<String, Integer> entry : hashMap.entrySet()) { System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()); } } }