揭秘郝斌数据结构精华：全面笔记助你轻松掌握核心要点

数据结构是计算机科学中的基础学科，对于理解和实现算法至关重要。郝斌的数据结构课程因其深入浅出的讲解和丰富的案例而受到许多学习者的喜爱。以下是对郝斌数据结构课程精华的全面笔记，旨在帮助读者轻松掌握核心要点。

第一章：数据结构概述

1.1 数据结构定义

数据结构是计算机存储、组织数据的方式。它包括数据的存储结构、数据的逻辑结构和数据的运算。

1.2 数据结构分类

数据结构主要分为两大类：线性结构和非线性结构。

• 线性结构：如数组、链表、栈、队列等。
• 非线性结构：如树、图等。

1.3 数据结构的重要性

良好的数据结构可以提高程序的效率和性能，降低时间复杂度和空间复杂度。

第二章：线性结构

2.1 数组

数组是一种基本的数据结构，用于存储一系列元素。

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 4;
        arr[4] = 5;
        
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

2.2 链表

链表是一种由节点组成的序列，每个节点包含数据和指向下一个节点的指针。

public class LinkedListExample {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        
        head.next = node1;
        node1.next = node2;
        
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }
    
    static class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

2.3 栈

栈是一种后进先出（LIFO）的数据结构。

public class StackExample {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
    
    static class Stack {
        private int[] elements;
        private int size;
        
        Stack() {
            elements = new int[10];
            size = 0;
        }
        
        public void push(int element) {
            if (size < elements.length) {
                elements[size++] = element;
            }
        }
        
        public int pop() {
            if (size > 0) {
                return elements[--size];
            }
            return -1;
        }
        
        public boolean isEmpty() {
            return size == 0;
        }
    }
}

2.4 队列

队列是一种先进先出（FIFO）的数据结构。

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        
        while (!queue.isEmpty()) {
            System.out.println(queue.dequeue());
        }
    }
    
    static class Queue {
        private int[] elements;
        private int front;
        private int rear;
        
        Queue() {
            elements = new int[10];
            front = 0;
            rear = 0;
        }
        
        public void enqueue(int element) {
            if ((rear + 1) % elements.length == front) {
                System.out.println("Queue is full");
            } else {
                elements[rear] = element;
                rear = (rear + 1) % elements.length;
            }
        }
        
        public int dequeue() {
            if (front == rear) {
                System.out.println("Queue is empty");
                return -1;
            }
            int element = elements[front];
            front = (front + 1) % elements.length;
            return element;
        }
        
        public boolean isEmpty() {
            return front == rear;
        }
    }
}

第三章：非线性结构

3.1 树

树是一种非线性结构，由节点组成，每个节点有零个或多个子节点。

public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

public class BinaryTreeExample {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        
        System.out.println("Pre-order traversal:");
        preOrderTraversal(root);
        
        System.out.println("In-order traversal:");
        inOrderTraversal(root);
        
        System.out.println("Post-order traversal:");
        postOrderTraversal(root);
    }
    
    static void preOrderTraversal(TreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }
    
    static void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }
    
    static void postOrderTraversal(TreeNode node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node.data + " ");
        }
    }
}

3.2 图

图是一种非线性结构，由节点和边组成。

public class GraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        graph.printGraph();
    }
    
    static class Graph {
        private int V;
        private LinkedList<Integer>[] adj;
        
        Graph(int V) {
            this.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);
            adj[w].add(v);
        }
        
        void printGraph() {
            for (int v = 0; v < V; ++v) {
                System.out.print(v + " -> ");
                for (Integer pCrawl : adj[v]) {
                    System.out.print(pCrawl + " ");
                }
                System.out.println();
            }
        }
    }
}

第四章：总结

通过以上对郝斌数据结构精华的全面笔记，读者可以系统地了解数据结构的基本概念、线性结构和非线性结构。在学习和实践过程中，建议读者多动手编写代码，加深对数据结构的理解和应用。