栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

基本数据结构 (java 实现)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

基本数据结构 (java 实现)


 主要是自己总结使用,写的比较笼统 -_-

数据结构
      • 数组
      • 双端队列
      • 栈
      • 树
      • 图
      • 堆
      • 字典


数组

  介绍:

     逻辑上是一种线性表,存储上内存可以是连续的和离散的

  题目:

  实现:

  1. Java

  (1) 最原始的数组:[ ], 内存连续 // 比较底层, java的业务代码不推荐使用

	//一维数组
	E[] array =  new E[array_size];     // 创建长度为 array_size 数据类型为 E的数组
	
	for(int i = 0; i < length; i++){
		array[i] = new E();		// 为数组中的每个引用new出一个对象
	}
	
	array[i]  	// invoke ...调用

   (2) ArrayList : 可变长度数组,实质是对 [] 的封装, 它的内存是连续的,频繁的插入删除请不要使用

	import  java.util.ArrayList;
	//一维数组
	ArrayList arr =  new ArrayList();    
	
	// 增
	arr.add(element : E);	// 数组末尾添加       		
    arr.add(idx : int, element : E) / / index 处添加   //  避免了繁琐的往后移动数组的操作
	
	// 删
	arr.remove(idx :index);    //删除索引处的元素
	arr.remove(element : E);    // 删除数组中所有  element 元素, element 元素可以为空
	
	//改
	arr.set(idx: int, element:E);	// 将索引idx处的对象更改为E
	
	//查
	arr.get(idx : int);    //查找 idx 处的元素
	
	// more
	arr.size();     // 返回数组元素个数
	
	arr.isEmpty();  // 数组是否为空

	arr.contain(element : E);  // 判断某个元素在数组中是否存在 

	arr.clear();   //清空所有数组;

  (3) LinkedList :数组, 内存离散(基于链表实现),频繁插入删除请使用;

   // 搞不懂为啥官方不提供一个 Array 的接口,并提供两种实现, 估计只有内存连续的才被定义为数组
   import java.util.LinkedList;
   LinkedList arr = new LinkedList();
   

双端队列

  介绍:

     可以从队列两端插入、删除、查询元素

  题目:

  实现:

  1. Java :队列(双端)
	import java.util.Deque;
    import java.util.ArrayList;
	
	Deque deq = new ArrayDeque();  // 创建一个双端队列
	
	que.isEmpty() -> true/false; // 判断队列是否为空
	
	// 入队
	que.offerFirst(element : E) -> true/false; // 从队首入队,如果队列空间不够返回 null
	que.offerLast(element : E) -> true/false; //  从队尾入队,如果队列空间不够返回 null
	
	//查询
	que.peekFirst()-> element : E; // 查询队首元素
	que.peekLast()-> element : E; // 查询队尾元素
	
	//出队
	que.pollFirst()-> element : E; // 从队首出队
	que.pollLast() -> element : E; // 从队尾出队

栈

  介绍:

    先入后出、函数调用

  题目:

  实现:

  1. Java 实现 :(Java支持的 Stack 类过旧, 官方推荐使用双端队列实现)
 	import java.util.Deque;
    import java.util.ArrayList;
    
    Deque stk = new ArrayDeque();  // 使用一个双端队列创建一个栈
    stk.isEmpty() -> true/false;	// 判断栈是否为空
    stk.offerFirst(element : E) ;  //入栈;
    stk.peekFirst() -> element : E;   // 得到栈首元素, 如果栈为空返回null
    stk.pollFirst();  -> return element : E   // 得到栈首元素并移除,如果栈为空返回null

树

  介绍:

    各种各样的树,但是这里只介绍二叉树

  题目:

  实现:

  1. Java 实现 :java中并没有现成的类(这里写一种构造方法)
 class Node {			// Tree Node
     E item;
     Node left;
     Node right;
     Node(E element) { this.item = element;}
 }
 Node root = new Node<>()
 
 Node  newNode = new Node<>();  // construct  newNode
 root.left  = newNode; 
 
 Node  newNode = new Node<>();  // construct  newNode
 root.right  = newNode; 
 //   需要注意 java 中left, right 会被自动初始化为null, 其他语言需手动

图

  介绍:

    图吗,几个节点之间互相连接

  题目:

  实现:

  1. Java 实现 :java没有提供图的官方api呦,@_@, 这里手动实现
    (1)邻接矩阵 : 适合用于实现稠密图
 	// 使用  java 自带的二维数组实现
 	// 节点
    int numNode = ?;
    int numEdge = ?;
    
    String [] nodes = new String[];    
 
    class Edge{
   
    		int src;
    		int dst;
    		int cost;
    }
    Edge edgs = new Edge[numEdge]; 
    
    //创建表
 	E[][] graph = new E[numNode][numNode];    // 创建邻接矩阵
    
    int src, dst;
    for(Edge e : edges){
    		src = e.src;
    		dst = e.dst;
    		graph[src][dst] = e.cost;	//有向图

 			// 若为无向图, 还需添加
 			graph[dst][src] = e.cost;	//有向图
    }

(2)邻接表:使用于稀疏矩阵

 // 使用 LinkedList 实现
    int numNode = ?;
    int numEdge = ?;
    
    String [] nodes = new String[];    
 
    class Edge{
   
    		int src;
    		int dst;
    		int cost;
    }
    
    Edge edgs = new Edge[numEdge]; 
   
  class GraphNode{
  		
 		int dst;
   		int cost;
   		GraphNode(int dst, int cost){
 			this.dst = dst;
 			this.cost = cost
 		}
   }
  
 	
    LinkedList> graph= new  LinkedList>();        // 创建邻接表;
   
    for(int i = 0; i < numNode; i++){					/
   		graph.add(new LinkedList());
    }
   
    for(Edge e: edges){
    		src = graph.get(e.src);
    		src.add(new GraphNode(e.dst, e.cost))
    }
   // 当然也可以自定义链表实现

堆

  介绍:

    实质是优先队列 (大顶堆:当前节点的值大于左右孩子的值 / 小顶堆当前节点的值小于左右孩子的值)

  题目:

  实现:

  1. Java 实现 :
   import java.util.PriporityQueue;  			// 需要添加可比较元素,默认升序
   import java.util.Comparator
   PriporityQueue heap = new  PriporityQueue();
   heap.offer(element : E);      // 向堆中添加元素
   heap.peek(element : E):    //  检索头部
   heap.poll(element : E);   //检索头部并删除
   heap.size(); //返回队列元素数目;
   heap.isEmpty();    //是否为空;
   heap.clear();    // 清空;
 
   // 对于E是任意类的情况, 需要定义比较器
   // 如果 E 是一个 雇员类 employee
   class Employee{
 		int id;
 	}
    //  按照员工 id 排序,比较器可以这样定义
   Comparator compareById = (Employee o1, Employee o2) -> o1.id.compareTo( o2.id);
   PriporityQueue heap = new  PriporityQueue(compareById);  // 定义带有比较器的堆

字典

  介绍: 本质是散列表, 常用于暂存数据库中取出来的数据;

   

  题目:

  实现:

  1. Java 实现 :
   import java.util.HashMap;
   HashMap dict = new HashMap ();	//创建一个HashMap
   dict.put(key:T, vaule:E);    // 字典中添加元素, 或者更改某键处的值
   dict.get(key:T);    //访问元素
   dict.remove(key:T);  // 删除元素
   dict.containsKey(key:T) ;   //是否包含某个键值 K
   dict.size(); 
   dict.isEmpty();
  
 // 字典遍历
 Iterator> iterator = dict.entrySet().iterator();   // 创建迭代器
 while(iterator.hasNext){
 	Map.Entry entry = iterator.next();
 	entry.getKey();   
 	entry.getValue();
 }	
 

   参考自菜鸟教程

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975927.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号