本文實例講述了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); } } }五、總結
更好的理解數據結構為何物，還需繼續探索，謹記。by:colonel
新聞熱點
疑難解答
圖片精選
