从表到图：Java常用数据结构

Java数据结构

一.稀疏数组

当一个二维数组有许多相同的默认值，记录了许多没有意义的数据，可将该数组转换为稀疏数组

实现思路：

原数组总行数	原数组总列数	原数组有效值个数
有效值1所在行	有效值1所在列	有效值1
有效值2所在行	有效值2所在列	有效值2
有效值n所在行	有效值n所在列	有效值n

public class main { public static void main(String[] args) { int a[][] = new int[8][8]; //8*8数组 a[2][2] = 5; //3行3列，值5 a[4][6] = 9; //5行7列，值9 a[5][7] = 12; //6行8列，值12 int value = 0; //统计有效值个数 System.out.println("原始数组："); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[0].length; j++) { if (a[i][j]!=0){ value++; } System.out.printf("%d\t",a[i][j]); } System.out.println(); } System.out.println("-------------------------------------"); //原始数组转换稀疏数组 int b[][] = new int[value+1][3];//创建稀疏数组，大小为有效值+1行和3列 b[0][0] = a.length; //原数组总行数 b[0][1] = a[0].length; //原数组总列数 b[0][2] = value; //原数组有效值个数 int row = 1; //稀疏数组有效数据行行数，记录有效值 for (int i = 1; i < a.length; i++) { for (int j = 0; j < a[0].length; j++) { if (a[i][j]!=0){ b[row][0] = i; //第一列：有效值所在行 b[row][1] = j; //第二列：有效值所在列 b[row][2] = a[i][j]; //第三列：有效值 row++; //记录完一行跳转下一行 } } } System.out.println("稀疏数组："); for (int[] hang : b) { for (int i : hang) System.out.printf("%d\t",i); System.out.println(); } System.out.println("-------------------------------------"); //稀疏数组还原 int c[][] = new int[b[0][0]][b[0][1]]; //创建数组 for (int i = 1; i < b.length; i++) { for (int j = 0; j < b[1].length; j++) { //在b[i][0]行，[b[i][1]列添加有效值：b[i][2] c[b[i][0]][b[i][1]] = b[i][2]; } } System.out.println("还原数组："); for (int[] hang : c) { for (int i : hang) System.out.printf("%d\t",i); System.out.println(); } } } 

二.链表

链表是一种物理存储单元上非连续、非顺序的存储结构，元素的逻辑顺序是通过链表中的指针链接次序实现的

链表由一个个节点组成，每个节点都指向下一个节点，最后一个节点的下个节点指向null

public class main { public static void main(String[] args) { Student student1 = new Student(1, "小A"); Student student2 = new Student(2, "小B"); Student student3 = new Student(3, "小C"); Student student4 = new Student(4, "小D"); Student student5 = new Student(5, "小E"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(student1); singleLinkedList.add(student2); singleLinkedList.add(student3); singleLinkedList.add(student4); singleLinkedList.add(student5); System.out.println("学生链表"); singleLinkedList.list(); //修改节点 Student newStudent = new Student(3, "小明"); singleLinkedList.update(newStudent); System.out.println("修改后："); singleLinkedList.list(); //删除节点 singleLinkedList.del(4); singleLinkedList.del(7); System.out.println("删除后："); singleLinkedList.list(); } } class SingleLinkedList { //初始化头节点 private Student head = new Student(0, ""); public void add(Student student) { //移动遍历 Student temp = head; //遍历链表，找到最后 while (true) { //找到链表的最后 if (temp.next == null) { break; } //如果没有找到最后, 将temp后移 temp = temp.next; } //将最后这个节点的next指向新的节点 temp.next = student; } public void update(Student newStudent) { Student temp = head; while (true) { if(temp.next==null){ System.out.println("找不到该元素"); break; } //找到要修改的元素 if (temp.num == newStudent.num) { temp.name = newStudent.name; break; } //如果没有找到最后, 将temp后移 temp = temp.next; } } public void del(int num) { Student temp = head; while (true) { if(temp.next==null){ System.out.println("找不到该元素"); break; } if (temp.next.num == num) { //将待删除的节点替换为它的下一个节点 temp.next = temp.next.next; break; } temp = temp.next; //temp后移，遍历 } } public void list() { Student temp = head; while (true) { //判断是否到链表最后 if (temp.next == null) { break; } System.out.println(temp.next); //将temp后移 temp = temp.next; } } } class Student { public int num; public String name; public Student next; //指向下一个节点 public Student(int num, String name) { this.num = num; this.name = name; } @Override public String toString() { return "Student [编号=" + num + ", name=" + name +"]"; } } 

三.队列(Queue)

队列是一个有序列表，可用数组和链表实现，遵循先入先出原则

队列在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。rear端称为队尾，front端称为队头

public class main { public static void main(String[] args) { Queue<String> queue = new LinkedList<String>(); Scanner scanner = new Scanner(System.in); for (int i = 0; i < 5; i++) { queue.offer(scanner.next()); } System.out.println(queue); for (int i = 0; i < 2; i++) { System.out.println("poll元素："+queue.poll()); } System.out.println(queue); System.out.println("element元素："+queue.element()); System.out.println(queue); for (int i = 0; i < 2; i++) { System.out.println("再次添加："+queue.offer(scanner.next())); } System.out.println(queue); } }

四.栈(Stack)

栈是一个有序列表，可用数组和链表实现，遵循先入后出原则

栈中的元素只允许在同一端进行插入和删除，能进行增删的一端为栈顶（top），固定的一端为栈底（bottom）

public class main { public static void main(String[] args) { Stack<String> stack = new Stack<String>(); Scanner scanner = new Scanner(System.in); for (int i = 0; i < 5; i++) { stack.push(scanner.next()); } System.out.println(stack); for (int i = 0; i < 2; i++) { System.out.println("弹出元素："+stack.pop()); } System.out.println(stack); for (int i = 0; i < 2; i++) { System.out.println("加入元素："+stack.push(scanner.next())); } System.out.println(stack); } }

五.哈希表(Hash table)

根据关键码值(Key value)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

哈希表是由一块地址连续的数组空间构成的，其中每个数组都是一个链表，数组的作用在于快速寻址查找，链表的作用在于快速插入和删除元素，因此，哈希表可以被认为就是链表的数组

public class main { public static void main(String[] args) { //创建哈希表 HashTab hashTab = new HashTab(7); String key = ""; Scanner scanner = new Scanner(System.in); while(true) { System.out.println("add:  添加员工"); System.out.println("list: 显示员工"); System.out.println("find: 查找员工"); System.out.println("del: 删除员工"); key = scanner.next(); switch (key) { case "add": System.out.println("输入添加id和名字"); int id = scanner.nextInt(); String name = scanner.next(); Emp emp = new Emp(id, name); hashTab.add(emp); break; case "list": hashTab.list(); break; case "find": System.out.println("输入查找id和名字"); int id1 = scanner.nextInt(); String name1 = scanner.next(); Emp emp1 = new Emp(id1, name1); hashTab.findEmpById(emp1); break; case "del": System.out.println("输入删除id和名字"); int id2 = scanner.nextInt(); String name2 = scanner.next(); Emp emp2 = new Emp(id2, name2); hashTab.del(emp2); break; } } } } //创建HashTab class HashTab { //创建员工链表数组，管理多条链表 private EmpLinkedList[] empLinkedList; private int size; //表示有多少条链表 //构造器 public HashTab(int size) { this.size = size; //初始化empLinkedListArray empLinkedList = new EmpLinkedList[size]; //初始化每个链表 for(int i = 0; i < size; i++) { empLinkedList[i] = new EmpLinkedList(); } } //添加雇员 public void add(Emp emp) { //使用散列函数确定添加哪条链表 int List_id = hashFun(emp.id); empLinkedList[List_id].add(emp); } //遍历所有的链表 public void list() { for(int i = 0; i < size; i++) { empLinkedList[i].list(i); } } //根据输入的信息,查找员工 public void findEmpById(Emp emp) { //使用散列函数确定到哪条链表查找 int List_id = hashFun(emp.id); Emp emp_f = empLinkedList[List_id].findEmpById(emp); if(emp_f != null) { System.out.printf("第%d条链表，id=%d，name=%s\n", List_id+1,emp_f.id,emp_f.name); }else{ System.out.println("在哈希表中，没有找到该员工"); } } //根据输入信息删除员工 public void del(Emp emp){ int List_id = hashFun(emp.id); empLinkedList[List_id].del(emp); } //散列函数 public int hashFun(int id) { //return id % size;   除法散列法 //这里表示id为几就插入哪条链表 return id-1; } } //创建EmpLinkedList链表 class EmpLinkedList { //头节点 Emp head = new Emp(0,"",null); //添加员工 public void add(Emp emp) { //定义移动节点，从头节点开始 Emp curEmp = head; while(true) { //循环后移节点，找到链表末端跳出 if(curEmp.next == null) { break; } curEmp = curEmp.next; } //此时curEmp为链表最后一个员工，将新员工赋值给curEmp的下个节点 curEmp.next = emp; } //遍历链表的员工信息 public void list(int no) { if(head.next==null) { //说明链表为空 System.out.println("第 "+(no+1)+" 链表为空"); return; } System.out.print("第 "+(no+1)+" 链表的信息为"); //定义移动节点，头节点为空，从第二个节点开始 Emp curEmp = head.next; while(true) { System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name); if(curEmp.next == null) {//遍历到末端 break; } curEmp = curEmp.next; //后移 } System.out.println(); } //根据id查找 public Emp findEmpById(Emp emp) { //定义移动节点，从头节点开始 Emp curEmp = head; while(true) { if(curEmp.name.equals(emp.name)) {//找到指定员工 break; } if(curEmp.next == null) {//遍历当前链表没有找到该员工 curEmp = null; break; } curEmp = curEmp.next;//后移 } return curEmp; } public void del(Emp emp){ //定义移动节点，从头节点开始 Emp curEmp = head; while(true) { if (curEmp.next == null){ System.out.println("找不到该员工"); break; } //循环后移节点，找到待删除节点 if(curEmp.next.name.equals(emp.name)) { //将待删除的节点替换为它的下一个节点 curEmp.next = curEmp.next.next; break; } curEmp = curEmp.next; } } } //员工类 class Emp { public int list_id; public int id; public String name; public Emp next; public Emp(int id, String name,Emp next) { this.id = id; this.name = name; this.next = next; } public Emp(int id, String name) { this.id = id; this.name = name; } }

六.二叉树(Binary tree)

有序数组的优势在于二分查找，链表的优势在于数据的插入和删除。但是在有序数组中插入数据很慢，在链表中查找数据效率很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势

二叉树是n个有限元素的集合，由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树

存储方式有顺序存储、链式存储

public class main { public static void main(String[] args) { //创建二叉树，添加节点 BinaryTree binaryTree = new BinaryTree(); StudentNode root = new StudentNode(1, "AA"); StudentNode node2 = new StudentNode(2, "BB"); StudentNode node3 = new StudentNode(3, "CC"); StudentNode node4 = new StudentNode(4, "DD"); StudentNode node5 = new StudentNode(5, "EE"); StudentNode node6 = new StudentNode(6, "FF"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node3.setLeft(node5); node3.setRight(node6); //添加根节点 binaryTree.setRoot(root); System.out.println("前序遍历"); // 1,2,4,3,5,6 binaryTree.preOrder(); System.out.println("中序遍历"); binaryTree.infixOrder(); // 4,2,1,5,3,6 System.out.println("后序遍历"); binaryTree.postOrder(); // 4,2,5,6,3,1 //前序遍历，查找5次 System.out.println("前序遍历查找"); StudentNode resNode1 = binaryTree.preOrderSearch(5); if (resNode1 != null) { System.out.printf("num=%d name=%s", resNode1.getNum(), resNode1.getName()); } else { System.out.printf("没有找到%d号学生", 5); } //中序遍历，查找4次 System.out.println("中序遍历查找"); StudentNode resNode2 = binaryTree.infixOrderSearch(5); if (resNode2 != null) { System.out.printf("num=%d name=%s", resNode2.getNum(), resNode2.getName()); } else { System.out.printf("没有找到%d号学生", 5); } //后序遍历，查找3次 System.out.println("后序遍历查找"); StudentNode resNode3 = binaryTree.postOrderSearch(5); if (resNode3 != null) { System.out.printf("num=%d name=%s", resNode3.getNum(), resNode3.getName()); } else { System.out.printf("没有找到%d号学生", 5); } //删除结点 System.out.println("删除前,前序遍历"); binaryTree.preOrder(); //  1,2,4,3,5,6 binaryTree.delNode(5); System.out.println("删除后，前序遍历"); binaryTree.preOrder(); //1,2,4,3,6 } } //定义BinaryTree二叉树 class BinaryTree { private StudentNode root; public void setRoot(StudentNode root) { this.root = root; } //删除结点 public void delNode(int num) { root.delNode(num); } //前序遍历 public void preOrder() { this.root.preOrder(); } //中序遍历 public void infixOrder() { this.root.infixOrder(); } //后序遍历 public void postOrder() { this.root.postOrder(); } //前序遍历查找 public StudentNode preOrderSearch(int num) { return root.preOrderSearch(num); } //中序遍历查找 public StudentNode infixOrderSearch(int num) { return root.infixOrderSearch(num); } //后序遍历查找 public StudentNode postOrderSearch(int num) { return this.root.postOrderSearch(num); } } //先创建StudentNode 结点 class StudentNode { private int num; private String name; private StudentNode left; //默认null private StudentNode right; //默认null public StudentNode(int num, String name) { this.num = num; this.name = name; } public int getNum() { return num; } public void setNum(int num) { this.num = num; } public String getName() { return name; } public void setName(String name) { this.name = name; } public StudentNode getLeft() { return left; } public void setLeft(StudentNode left) { this.left = left; } public StudentNode getRight() { return right; } public void setRight(StudentNode right) { this.right = right; } @Override public String toString() { return "StudentNode{" + "num=" + num + ", name='" + name + '}'; } //递归删除结点 //如果删除的节点是叶子节点，则删除该节点 //如果删除的节点是非叶子节点，则删除该子树 public void delNode(int num) { //如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) if(this.left != null && this.left.num == num) { this.left = null; return; } //如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) if(this.right != null && this.right.num == num) { this.right = null; return; } //左子树递归删除 if(this.left != null) { this.left.delNode(num); } //右子树递归删除 if(this.right != null) { this.right.delNode(num); } } //前序遍历实现 public void preOrder() { //输出父结点 System.out.println(this); //递归向左子树前序遍历 if(this.left != null) { this.left.preOrder(); } //递归向右子树前序遍历 if(this.right != null) { this.right.preOrder(); } } //中序遍历实现 public void infixOrder() { //递归向左子树中序遍历 if(this.left != null) { this.left.infixOrder(); } //输出父结点 System.out.println(this); //递归向右子树中序遍历 if(this.right != null) { this.right.infixOrder(); } } //后序遍历实现 public void postOrder() { //递归向右子树后序遍历 if(this.left != null) { this.left.postOrder(); } //递归向右子树后序遍历 if(this.right != null) { this.right.postOrder(); } //输出父结点 System.out.println(this); } //前序遍历查找实现 //前序遍历顺序：1，2，4，3，5，6 //1开始，按照遍历顺序依次对比 public StudentNode preOrderSearch(int num) { System.out.println("查找中......"); //this表示当前节点(父节点)，对比目标节点，是则返回this if(this.num == num) { return this; } StudentNode resNode = null; //遍历左子树 if(this.left != null) { resNode = this.left.preOrderSearch(num); } if(resNode != null) { return resNode; } //遍历右子树 if(this.right != null) { resNode = this.right.preOrderSearch(num); } return resNode; } //中序遍历查找 //中序遍历顺序：4，2，1，5，3，6 //1开始，找到4，按照遍历顺序依次对比 public StudentNode infixOrderSearch(int num) { StudentNode resNode = null; //遍历左子树 if(this.left != null) { resNode = this.left.infixOrderSearch(num); } if(resNode != null) { return resNode; } System.out.println("查找中......"); //this表示当前节点(父节点)，对比目标节点，是则返回this if(this.num == num) { return this; } //遍历右子树 if(this.right != null) { resNode = this.right.infixOrderSearch(num); } return resNode; } //后序遍历查找 //后序遍历顺序：4，2，5，6，3，1 //1开始，找到4，按照遍历顺序依次对比 public StudentNode postOrderSearch(int num) { StudentNode resNode = null; //遍历左子树 if(this.left != null) { resNode = this.left.postOrderSearch(num); } if(resNode != null) { return resNode; } //遍历右子树 if(this.right != null) { resNode = this.right.postOrderSearch(num); } if(resNode != null) { return resNode; } System.out.println("查找中......"); //this表示当前节点(父节点)，对比目标节点，是则返回this if(this.num == num) { return this; } return resNode; } }

七.图(Graph)

图是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都可能相关

图可以用邻接矩阵或邻接表表示

public class main { public static void main(String[] args) { //顶点的个数 int n = 8; //顶点值数组 String Vertexs[] = {"A", "B", "C", "D", "E", "F", "G", "H"}; //创建图对象 Graph graph = new Graph(n); //循环添加顶点 for(String vertex: Vertexs) { graph.insertVertex(vertex); } //定义各个边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1); //显示图基本信息 graph.showGraph(); System.out.println("深度优先："); graph.dfs(); // 1->2->4->8->5->3->6->7 System.out.println(); System.out.println("广度优先："); graph.bfs(); // 1->2->3->4->5->6->7->8 System.out.println(); //显示邻结矩阵 graph.showEdges(); } } //定义图的属性 class Graph{ private ArrayList<String> vertexList; //存储顶点集合 private int[][] edges; //存储图对应的邻结矩阵 private int numOfEdges; //表示边的数目 private boolean[] isVisited; //记录某个结点是否被访问 //构造器 public Graph(int n) { //初始化邻结矩阵和顶点集合 edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; } //插入结点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 public void insertEdge(int v1, int v2, int weight) { //设置邻接矩阵值，可以直接两个相连的顶点weight为1 edges[v1][v2] = weight; edges[v2][v1] = weight; //统计边数 numOfEdges++; } //显示图的基本信息 public void showGraph(){ System.out.println("顶点总数："+vertexList.size()); System.out.println("边总数："+numOfEdges); } //显示图对应的邻接矩阵 public void showEdges() { System.out.println("邻接矩阵："); for(int[] hang : edges) { for (int lie : hang) System.out.printf("%d\t",lie); System.out.println(); } } //返回结点i(下标)对应的数据 public String getValueByIndex(int i) { return vertexList.get(i); } //深度优先遍历算法 private void dfs(boolean[] isVisited, int i) { //首先我们访问该顶点,输出 System.out.print(getValueByIndex(i) + "->"); //将顶点设置为已经访问 isVisited[i] = true; //查找顶点i的第一个邻接顶点w int w = getFirstNeighbor(i); while(w != -1) {//找到第一个邻接顶点w //如果w顶点未被访问，继续递归查找它的第一个邻接顶点 if(!isVisited[w]) { dfs(isVisited, w); } //如果该顶点已经被访问过，将i，w传过去，查找i的第二个邻接顶点 w = getNextNeighbor(i, w); } } //对dfs进行一个重载, 遍历我们所有的顶点，并进行dfs public void dfs() { isVisited = new boolean[vertexList.size()]; //遍历所有的顶点，进行dfs[回溯] for(int i = 0; i < vertexList.size(); i++) { if(!isVisited[i]) { dfs(isVisited, i); } } } //广度优先遍历算法 private void bfs(boolean[] isVisited, int i) { int u ; // 表示队列的头顶点对应下标 int w ; // 邻接顶点w //队列，记录顶点访问的顺序 LinkedList queue = new LinkedList(); //访问顶点，输出顶点信息 System.out.print(getValueByIndex(i) + "->"); //标记为已访问 isVisited[i] = true; //将顶点加入队列 queue.addLast(i); while( !queue.isEmpty()) { //取出队列的头顶点下标 u = (Integer)queue.removeFirst(); //得到第一个邻接顶点的下标 w w = getFirstNeighbor(u); while(w != -1) {//找到第一个邻接顶点w //如果w顶点未访问 if(!isVisited[w]) { //输出 System.out.print(getValueByIndex(w) + "->"); //标记已经访问 isVisited[w] = true; //入队 queue.addLast(w); } //以u为前驱点，找w后面的下一个邻接顶点 w = getNextNeighbor(u, w); } } } //遍历所有的结点，都进行广度优先搜索 public void bfs() { isVisited = new boolean[vertexList.size()]; for(int i = 0; i < vertexList.size(); i++) { if(!isVisited[i]) { bfs(isVisited, i); } } } //获取顶点的第一个邻接顶点 public int getFirstNeighbor(int v1) { for(int j = 0; j < vertexList.size(); j++) { if(edges[v1][j] > 0) { return j; } } return -1; } //根据前一个邻接顶点的下标来获取下一个邻接顶点 public int getNextNeighbor(int v1, int v2) { for(int j = v2 + 1; j < vertexList.size(); j++) { if(edges[v1][j] > 0) { return j; } } return -1; } } 

本文地址：https://blog.csdn.net/gugfjj/article/details/108041686