当前位置:主页 > java教程 > Java数据结构之链表、栈、队列、树的实现方法示例

Java中链表、栈、队列、树的数据结构用法实例总结

发布:2019-06-08 13:35:39 164


本站精选了一篇Java数据结构相关的编程文章,网友卢永贞根据主题投稿了本篇教程内容,涉及到Java、数据结构、链表、栈、队列、树、Java数据结构之链表、栈、队列、树的实现方法示例相关内容,已被410网友关注,相关难点技巧可以阅读下方的电子资料。

Java数据结构之链表、栈、队列、树的实现方法示例

本文实例讲述了Java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考,具体如下:

最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查。

一、线性表(链表)

1、节点定义

/**链表节点定义
 * @author colonel
 *
 */
class Node {
 public int data;
 Node next=null;
 public Node(int data){
 this.data=data;
 }
}

2、链表操作类

/**链表操作类
 * @author colonel
 *
 */
public class operateClass {
 public Node headNode=null;
 /*给链表添加界节点
 * @param data 链表节点数据
 */
 public Node addNode(int data){
 Node newNode=new Node(data);
 if (headNode==null) {
  headNode=newNode;
  newNode.next=null;
  return headNode;
 }
 Node tempNode=headNode;
 while (tempNode.next!=null) {
  //tempNode=headNode;
  tempNode=tempNode.next;
 }
 tempNode.next=newNode;
 return headNode;
 }
 /**删除节点
 * @param 删除节点的位置
 *
 */
 public boolean delNode(int index){
 if (index<1||index>length()) {
  return false;
 }
 if (index==1) {
  headNode=headNode.next;
  return true;
 }
 Node preNode=headNode;
 Node curNode=preNode.next;
 int count=2;
 while (curNode!=null) {
  if (count==index) {
  preNode.next=curNode.next;
  return true;
  }
  preNode=curNode;
  curNode=curNode.next;
  count++;
 }
 return true;
 }
 /**取链表的长度
 * @return返回链表的长度
 */
 public int length(){
 int length=0;
 Node temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.next;
 }
 return length;
 }
 /**按照值域对链表数据排序
 * @return 返回排序后的链表头节点
 */
 public Node orderList(){
 Node nextNode=null;
 int temp=0;
 Node curNode=headNode;
 while (curNode.next!=null) {
  nextNode=curNode.next;
  while (nextNode!=null) {
  if (curNode.data>nextNode.data) {
  temp=curNode.data;
  curNode.data=nextNode.data;
  nextNode.data=temp;
  }
  nextNode=nextNode.next;
  }
  curNode=curNode.next;
 }
  return headNode;
 }
 /**
 * 去除链表中值域重复的元素
 */
 public void redRepeat(){
 if (length()<=1) {
  return;
 }
 Node curNode=headNode;
 while (curNode!=null) {
  Node insidNode=curNode.next;
  Node insidPreNode=insidNode;
  while (insidNode!=null) {
  if (insidNode.data==curNode.data) {
   insidPreNode.next=insidNode.next;
   //return;
  }
  insidPreNode=insidNode;
  insidNode=insidNode.next;
  }
  curNode=curNode.next;
 }
 }
 /**倒序输出链表中所有的数据
 * @param hNode 链表头节点
 */
 public void reversePrint(Node hNode){
 if (hNode!=null) {
  reversePrint(hNode.next);
  System.out.println(hNode.data);
 }
 }
 /**
 * 从头节点开始到为节点结尾打印出值
 */
 public void printList(){
 Node tmpNode=headNode;
 while (tmpNode!=null) {
  System.out.println(tmpNode.data);
  tmpNode=tmpNode.next;
 }
 }
}

二、栈

1、该栈使用数组实现,具体的栈操作类

class MyStack<E>{
 private Object[] stack;
 int top=-1;
 public MyStack(){
 stack=new Object[10];
 }
 public boolean isEmpty(){
 return top==0;
 }
 /**弹出栈顶元素(不删除)
 * @return
 */
 public E peek(){
 if (isEmpty()) {
  return null;
 }
 return (E) stack[top];
 }
 /**出栈站顶元素
 * @return 栈顶元素
 */
 public E pop(){
 E e=peek();
 stack[top]=null;
 top--;
 return e;
 }
 /**压栈
 * @param item 待压元素
 * @return 返回待压元素
 */
 public E push(E item){
 //ensureCapacity(top+1);
 stack[++top]=item;
 return item;
 }
 /**栈满扩容
 * @param size
 */
 public void ensureCapacity(int size){
 int len=stack.length;
 if (size>len) {
  int newLen=10;
  stack=Arrays.copyOf(stack, newLen);
 }
 }
 /**返回栈顶元素
 * @return
 */
 public E getTop(){
 if (top==-1) {
  return null;
 }
 return (E) stack[top];
 }
}

三、队列

该队列使用链式实现

1、队节点定义

/**
 * @author colonel
 *队节点定义
 * @param <Elem>
 */
class queueNode<Elem>{
 queueNode<Elem> nextNode=null;
 Elem data;
 public queueNode(Elem data){
 this.data=data;
 }
}

2、队列操作类

/**
 * @author colonel
 *队列操作类
 * @param <Elem>
 */
class MyQueue<Elem>{
 private queueNode<Elem> headNode=null;
 private queueNode<Elem> tailNode=null;
 private queueNode<Elem> lastNode=null;
 /**判断该队列是否为空
 * @return 返回true or false
 */
 public boolean isEmpty(){
 return headNode==tailNode;
 }
 /**入队操作
 * @param data 节点元素值
 */
 public void put(Elem data){
 queueNode<Elem> newNode=new queueNode<Elem>(data);
 if (headNode==null&&tailNode==null) {
  headNode=tailNode=newNode;
  //tailNode=headNode.nextNode;
  lastNode=tailNode.nextNode;
  return;
 }
 tailNode.nextNode=newNode;
 tailNode=newNode;
 lastNode=tailNode.nextNode;
 //tailNode=tailNode.nextNode;
 }
 /**出队操作
 * @return 返回出队元素
 */
 public Elem pop(){
 if (headNode==lastNode) {
  return null;
 }
 queueNode<Elem> tempNode=headNode;
 Elem statElem=tempNode.data;
 headNode=tempNode.nextNode;
 return statElem;
 }
 /**返回队列长度
 * @return 长度
 */
 public int size(){
 if (isEmpty()) {
  return 0;
 }
 int length=0;
 queueNode<Elem> temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.nextNode;
 }
 return length;
 }
}

四、二叉树

1、节点定义

/**树节点定义
 * @author colonel
 *
 */
class TreeNode{
 public int data;
 public TreeNode leftNode;
 public TreeNode rightNode;
 public TreeNode(int data){
 this.data=data;
 this.leftNode=null;
 this.rightNode=null;
 }
}

2、二叉树操作类

/**二叉排序树操作类
 * @author colonel
 *
 */
class OperateTree{
 public TreeNode rootNode;
 public OperateTree(){
 rootNode=null;
 }
 /**元素插入二叉排序树
 * @param data 待插节点数据
 */
 public void insert(int data){
 TreeNode newNode=new TreeNode(data);
 if (rootNode==null) {
  rootNode=newNode;
 }else {
  TreeNode current=rootNode;
  TreeNode parent;
  while (true) {
  parent=current;
  if (data<current.data) {
   current=current.leftNode;
   if (current==null) {
   parent.leftNode=newNode;
   return;
   }
  } else {
   current=current.rightNode;
   if (current==null) {
   parent.rightNode=newNode;
   return;
   }
  }
  }
 }
 }
 /**构建二叉排序树
 * @param item 元素数组
 */
 public void buildTree(int[] item){
 for (int i = 0; i < item.length; i++) {
  insert(item[i]);
 }
 }
 /**
 * 先序遍历二叉树
 */
 public void preOrder(TreeNode root){
 if (root!=null) {
  System.out.println(root.data);
  preOrder(root.leftNode);
  preOrder(root.rightNode);
 }
 }
 /**中序遍历
 * @param root
 */
 public void inOrder(TreeNode root){
 if (root!=null) {
  inOrder(root.leftNode);
  System.out.println(root.data);
  inOrder(root.rightNode);
 }
 }
 /**后序遍历
 * @param root
 */
 public void afterOrder(TreeNode root){
 if (root!=null) {
  afterOrder(root.leftNode);
  afterOrder(root.rightNode);
  System.out.println(root.data);
 }
 }
 /**
 * 层序遍历二叉排序树
 */
 public void layerTrave(){
 if (this.rootNode==null) {
  return;
 }
 Queue<TreeNode> myQueue=new LinkedList<>();
 myQueue.add(rootNode);
 while (!myQueue.isEmpty()) {
  TreeNode tempNode=myQueue.poll();
  System.out.println(tempNode.data);
  if (tempNode.leftNode!=null) {
  myQueue.add(tempNode.leftNode);
  }
  if (tempNode.rightNode!=null) {
  myQueue.add(tempNode.rightNode);
  }
 }
 }

 


参考资料

相关文章

  • Java实现国产加密算法SM4的示例详解

    发布:2023-04-20

    这篇文章主要为大家详细介绍了Java如何实现国产加密算法SM4(ECB和CBC两种模式),文中的示例代码讲解详细,感兴趣的小伙伴可以了解一下


  • JavaScript高级程序设计笔记分享

    发布:2019-08-09

    这篇文章主要介绍了Ajax高级笔记 JavaScript高级程序设计笔记,需要的朋友可以参考下


  • Java中final关键字和final的四种用法实例

    发布:2023-04-12

    final关键字代表最终的、不可改变的,下面这篇文章主要给大家介绍了关于Java中final关键字和final的四种用法实例,文中通过图文以及实例代码介绍的非常详细,需要的朋友可以参考下


  • 分享JavaScript中数组及对象合并方法示例代码

    发布:2020-03-01

    这篇文章主要介绍了JavaScript中的数组合并方法和对象合并方法,通过代码的形式给大家介绍的非常详细,需要的朋友可以参考下


  • java数据结构实现AI机器人行走实例分享

    发布:2020-01-06

    这篇文章主要为大家详细介绍了java数据结构实现机器人行走,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


  • Java Char的简单工具类CharUtil分享

    发布:2023-01-18

    给大家整理了关于Java的教程,下面小编就为大家分享一篇Java Char的简单工具类CharUtil,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧


  • java中TCP实现回显服务器及客户端

    发布:2023-04-13

    本文主要介绍了java中TCP实现回显服务器及客户端,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧


  • Java AbstractQueuedSynchronizer源码分析

    发布:2020-03-26

    这篇文章主要为大家详细介绍了Java并发系列之AbstractQueuedSynchronizer源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


网友讨论