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

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

 /**链表操作类 * @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 (indexlength()) { 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; } } } 

 class MyStack{ 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]; } } 

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

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

 /**树节点定义 * @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;<span style="color:transparent">来源gaodai#ma#com搞*!代#%^码网</span> } } 

 /**二叉排序树操作类 * @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 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); } } }