数据结构之 逻辑结构
逻辑结构是从数据元素之间的逻辑关系上描述数据结构,它独立于数据的物理存储结构。逻辑结构主要分为线性结构和非线性结构。线性结构前面已经提到,如数组、链表、栈、队列等。这里我们主要讨论非线性结构中的树和图,并提供它们的简单Java实现。
逻辑结构是从数据元素之间的逻辑关系上描述数据结构,它独立于数据的物理存储结构。逻辑结构主要分为线性结构和非线性结构。线性结构前面已经提到,如数组、链表、栈、队列等。这里我们主要讨论非线性结构中的树和图,并提供它们的简单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等)来实现更高效的图数据结构。
逻辑结构主要关注数据元素之间的关系,而物理结构(或存储结构)则关注数据如何在计算机内存中表示和访问。逻辑结构和物理结构是紧密相关的,但逻辑结构是更高级别的抽象,它独立于物理存储的细节。
DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐

所有评论(0)