溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

Java數(shù)據(jù)結(jié)構(gòu)之鏈表、棧、隊(duì)列、樹(shù)的實(shí)現(xiàn)方法示例

發(fā)布時(shí)間：2020-10-13 07:56:04 來(lái)源：腳本之家 閱讀：188 作者：0colonel0 欄目：編程語(yǔ)言

本文實(shí)例講述了Java數(shù)據(jù)結(jié)構(gòu)之鏈表、棧、隊(duì)列、樹(shù)的實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

最近無(wú)意中翻到一本書(shū)，閑來(lái)無(wú)事寫幾行代碼，實(shí)現(xiàn)幾種常用的數(shù)據(jù)結(jié)構(gòu)，以備后查。

一、線性表（鏈表）

1、節(jié)點(diǎn)定義

/**鏈表節(jié)點(diǎn)定義
 * @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;
 /*給鏈表添加界節(jié)點(diǎn)
 * @param data 鏈表節(jié)點(diǎn)數(shù)據(jù)
 */
 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;
 }
 /**刪除節(jié)點(diǎn)
 * @param 刪除節(jié)點(diǎn)的位置
 *
 */
 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;
 }
 /**取鏈表的長(zhǎng)度
 * @return返回鏈表的長(zhǎng)度
 */
 public int length(){
 int length=0;
 Node temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.next;
 }
 return length;
 }
 /**按照值域?qū)︽湵頂?shù)據(jù)排序
 * @return 返回排序后的鏈表頭節(jié)點(diǎn)
 */
 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;
 }
 /**
 * 去除鏈表中值域重復(fù)的元素
 */
 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;
 }
 }
 /**倒序輸出鏈表中所有的數(shù)據(jù)
 * @param hNode 鏈表頭節(jié)點(diǎn)
 */
 public void reversePrint(Node hNode){
 if (hNode!=null) {
  reversePrint(hNode.next);
  System.out.println(hNode.data);
 }
 }
 /**
 * 從頭節(jié)點(diǎn)開(kāi)始到為節(jié)點(diǎn)結(jié)尾打印出值
 */
 public void printList(){
 Node tmpNode=headNode;
 while (tmpNode!=null) {
  System.out.println(tmpNode.data);
  tmpNode=tmpNode.next;
 }
 }
}

二、棧

1、該棧使用數(shù)組實(shí)現(xiàn)，具體的棧操作類

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;
 }
 /**棧滿擴(kuò)容
 * @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];
 }
}

三、隊(duì)列

該隊(duì)列使用鏈?zhǔn)綄?shí)現(xiàn)

1、隊(duì)節(jié)點(diǎn)定義

/**
 * @author colonel
 *隊(duì)節(jié)點(diǎn)定義
 * @param <Elem>
 */
class queueNode<Elem>{
 queueNode<Elem> nextNode=null;
 Elem data;
 public queueNode(Elem data){
 this.data=data;
 }
}

2、隊(duì)列操作類

/**
 * @author colonel
 *隊(duì)列操作類
 * @param <Elem>
 */
class MyQueue<Elem>{
 private queueNode<Elem> headNode=null;
 private queueNode<Elem> tailNode=null;
 private queueNode<Elem> lastNode=null;
 /**判斷該隊(duì)列是否為空
 * @return 返回true or false
 */
 public boolean isEmpty(){
 return headNode==tailNode;
 }
 /**入隊(duì)操作
 * @param data 節(jié)點(diǎn)元素值
 */
 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;
 }
 /**出隊(duì)操作
 * @return 返回出隊(duì)元素
 */
 public Elem pop(){
 if (headNode==lastNode) {
  return null;
 }
 queueNode<Elem> tempNode=headNode;
 Elem statElem=tempNode.data;
 headNode=tempNode.nextNode;
 return statElem;
 }
 /**返回隊(duì)列長(zhǎng)度
 * @return 長(zhǎng)度
 */
 public int size(){
 if (isEmpty()) {
  return 0;
 }
 int length=0;
 queueNode<Elem> temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.nextNode;
 }
 return length;
 }
}

四、二叉樹(shù)

1、節(jié)點(diǎn)定義

/**樹(shù)節(jié)點(diǎn)定義
 * @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、二叉樹(shù)操作類

/**二叉排序樹(shù)操作類
 * @author colonel
 *
 */
class OperateTree{
 public TreeNode rootNode;
 public OperateTree(){
 rootNode=null;
 }
 /**元素插入二叉排序樹(shù)
 * @param data 待插節(jié)點(diǎn)數(shù)據(jù)
 */
 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;
   }
  }
  }
 }
 }
 /**構(gòu)建二叉排序樹(shù)
 * @param item 元素?cái)?shù)組
 */
 public void buildTree(int[] item){
 for (int i = 0; i < item.length; i++) {
  insert(item[i]);
 }
 }
 /**
 * 先序遍歷二叉樹(shù)
 */
 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);
 }
 }
 /**
 * 層序遍歷二叉排序樹(shù)
 */
 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);
  }
 }
 }

五、總結(jié)

更好的理解數(shù)據(jù)結(jié)構(gòu)為何物，還需繼續(xù)探索，謹(jǐn)記。by:colonel

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手