繼上一篇單向鏈表，單線鏈表可以進一步擴展為環，如下圖所示：
特點：
1、第一個節點稱為頭部節點，最后一個節點稱為尾部節點
2、每個節點都單方面的指向下一個節點
3、尾部節點下一個節點指向頭部節點
題目：
17世紀的法國數學家加斯帕講了這樣一個故事： 15個教徒和15 個非教徒，在深海?上遇險，必須將一半的人投入海?中，其余的人才能幸免于難，于是想了一個辦法： 30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海?，如此循環進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海?的都是非教徒。
這就是典型的約瑟夫環問題，可以用單向鏈表環解決，具體代碼如下：
|
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
package mainimport "fmt"type LinkNode struct { Data interface{} Next *LinkNode}type SingleLink struct { head *LinkNode tail *LinkNode size int}// 初始化鏈表func InitSingleLink()(*SingleLink){ return &SingleLink{ head:nil, tail:nil, size:0, }}// 獲取頭部節點func (sl *SingleLink)GetHead()*LinkNode{ return sl.head}// 獲取尾部節點func (sl *SingleLink)GetTail()*LinkNode{ return sl.tail}// 打印鏈表func (sl *SingleLink) Print(){ fmt.Println("SingleLink size:",sl.Length()) if sl.size == 0{ return } ptr := sl.GetHead() headNode := sl.GetHead() for ptr != nil{ fmt.Println("Data:",ptr.Data) ptr = ptr.Next if ptr.Next == headNode{ fmt.Println("Data:",ptr.Data) break } }}//鏈表長度func (sl *SingleLink) Length() int{ return sl.size}//插入數據（頭插）func (sl *SingleLink) InsertByHead(node *LinkNode){ if node == nil{ return } // 判斷是否第一個節點 if sl.Length() == 0{ sl.head = node sl.tail = node node.Next = nil }else{ oldHeadNode := sl.GetHead() sl.head = node sl.tail.Next = node sl.head.Next = oldHeadNode } sl.size++}//插入數據（尾插）func (sl *SingleLink) InsertByTail(node *LinkNode) { if node == nil{ return } // 插入第一個節點 if sl.size == 0{ sl.head = node sl.tail = node node.Next = nil }else{ sl.tail.Next = node node.Next = sl.head sl.tail = node } sl.size ++}//插入數據（下標）位置func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){ if node == nil{ return } // 往頭部插入 if index == 0 { sl.InsertByHead(node) }else{ if index > sl.Length(){ return }else if index == sl.Length(){ //往尾部添加節點 sl.InsertByTail(node) }else{ preNode := sl.Search(index-1) // 下標為 index 的上一個節點 currentNode := sl.Search(index) // 下標為 index 的節點 preNode.Next = node node.Next = currentNode sl.size++ } }}//刪除數據（下標）位置func (sl *SingleLink) DeleteByIndex(index int) { if sl.Length() == 0 || index > sl.Length(){ return } // 刪除第一個節點 if index == 0{ sl.head = sl.head.Next sl.tail.Next = sl.head }else{ preNode := sl.Search(index-1) if index != sl.Length()-1{ nextNode := sl.Search(index).Next preNode.Next = nextNode }else{ sl.tail = preNode preNode.Next = sl.head } } sl.size--}// 查詢數據func (sl *SingleLink) Search(index int)(node *LinkNode) { if sl.Length() == 0 || index > sl.Length(){ return nil } // 是否頭部節點 if index == 0{ return sl.GetHead() } node = sl.head for i:=0;i<=index;i++{ node = node.Next } return}func (sl *SingleLink)pop(){ popIndex := 8 delNode := sl.Search(popIndex) fmt.Println("POP node : ",delNode.Data) sl.DeleteByIndex(popIndex) sl.tail = sl.Search(popIndex - 1) sl.head = sl.Search(popIndex) fmt.Printf("Head:%v , Tail:%v\n",sl.head.Data,sl.tail.Data)}func main() { // 初始化鏈表 sl := InitSingleLink() // 生成30個元素的環 for i:=0;i<30;i++{ snode := &LinkNode{ Data:i, } sl.InsertByIndex(i,snode) } //循環淘汰第9個元素 var round int for sl.size > 15{ fmt.Printf("================ Round %d ================\n",round) sl.pop() round ++ } // 獲勝者 fmt.Println("================ Finish ================") fmt.Println("People who survived.") sl.Print()} |
執行結果
================ Round 0 ================
POP node : 9
Head:10 , Tail:8
================ Round 1 ================
POP node : 19
Head:20 , Tail:18
================ Round 2 ================
POP node : 29
Head:0 , Tail:28
================ Round 3 ================
POP node : 10
Head:11 , Tail:8
================ Round 4 ================
POP node : 21
Head:22 , Tail:20
================ Round 5 ================
POP node : 2
Head:3 , Tail:1
================ Round 6 ================
POP node : 14
Head:15 , Tail:13
================ Round 7 ================
POP node : 26
Head:27 , Tail:25
================ Round 8 ================
POP node : 8
Head:11 , Tail:7
================ Round 9 ================
POP node : 23
Head:24 , Tail:22
================ Round 10 ================
POP node : 6
Head:7 , Tail:5
================ Round 11 ================
POP node : 22
Head:24 , Tail:20
================ Round 12 ================
POP node : 7
Head:11 , Tail:5
================ Round 13 ================
POP node : 25
Head:27 , Tail:24
================ Round 14 ================
POP node : 13
Head:15 , Tail:12
================ Finish ================
People who survived.
SingleLink size: 15
Data: 15
Data: 16
Data: 17
Data: 18
Data: 20
Data: 24
Data: 27
Data: 28
Data: 0
Data: 1
Data: 3
Data: 4
Data: 5
Data: 11
Data: 12
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.51cto.com/pmghong/2462943
