本文實例講述了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
