本文实例讲述了java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考，具体如下：
最近无意中翻到一本书，闲来无事写几行代码，实现几种常用的数据结构，以备后查。
一、线性表（链表）
1、节点定义
|
1 2 3 4 5 6 7 8 9 10 11 |
/**链表节点定义 * @author colonel * */ class node { public int data; node next= null ; public node( int data){ this .data=data; } } |
2、链表操作类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
/**链表操作类 * @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、该栈使用数组实现，具体的栈操作类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
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、队节点定义
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/** * @author colonel *队节点定义 * @param <elem> */ class queuenode<elem>{ queuenode<elem> nextnode= null ; elem data; public queuenode(elem data){ this .data=data; } } |
2、队列操作类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/** * @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、节点定义
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/**树节点定义 * @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、二叉树操作类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
/**二叉排序树操作类 * @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
希望本文所述对大家java程序设计有所帮助。
原文链接：https://blog.csdn.net/sinat_34322082/article/details/53694315
查看更多关于Java数据结构之链表、栈、队列、树的实现方法示例的详细内容...