逻辑结构是从数据元素之间的逻辑关系上描述数据结构,它独立于数据的物理存储结构。逻辑结构主要分为线性结构和非线性结构。线性结构前面已经提到,如数组、链表、栈、队列等。这里我们主要讨论非线性结构中的树和图,并提供它们的简单Java实现。

1. 树 (Tree)

树是一种层次结构,它有一个根节点和若干个子树。每个子树也是一棵树,并且树中不存在环。

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

public class TreeDemo {
    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);

        // 前序遍历
        preOrderTraversal(root);
    }

    public static void preOrderTraversal(TreeNode node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }
}

2. 图 (Graph)

图是由顶点和边组成的集合。顶点表示对象,边表示对象之间的关系。图分为有向图和无向图。

import java.util.*;

class Graph {
    private int numVertices;
    private LinkedList<Integer> adjLists[];

    Graph(int vertices) {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];
        for (int i = 0; i < vertices; ++i) {
            adjLists[i] = new LinkedList();
        }
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
        // 如果是无向图,还需要添加反向边
        // adjLists[dest].add(src);
    }

    void printGraph() {
        for (int v = 0; v < numVertices; ++v) {
            System.out.println("Adjacency list of vertex " + v);
            System.out.print("head");
            for (Integer i : adjLists[v]) {
                System.out.print(" -> " + i);
            }
            System.out.println("\n");
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.printGraph();
    }
}

在上面的代码中,Graph 类使用邻接表来表示图。addEdge 方法用于添加边,printGraph 方法用于打印每个顶点的邻接表。注意,如果图是无向的,那么在添加边时,你需要同时添加正向和反向的边。

这些只是树和图的基本实现,实际应用中可能涉及更复杂的操作,如查找、遍历(深度优先遍历、广度优先遍历等)、最短路径算法等。在Java中,还可以使用集合框架(如HashSet, HashMap, ArrayList等)来实现更高效的图数据结构。

逻辑结构主要关注数据元素之间的关系,而物理结构(或存储结构)则关注数据如何在计算机内存中表示和访问。逻辑结构和物理结构是紧密相关的,但逻辑结构是更高级别的抽象,它独立于物理存储的细节。

Logo

DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐