本文实例讲述了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
