约瑟夫环问题解决

ruyuejun · ruyuejun · commit 55e2ecea1d62 · 2019-06-05T15:44:08.000+08:00
diff --git a/sources/go/list/NHRingList/NHRingList.go b/sources/go/list/NHRingList/NHRingList.go
@@ -0,0 +1,72 @@
+/**
+ * 循环链表：无头节点
+ */
+
+ package list
+
+ import (
+	 "fmt"
+ )
+ 
+ // 节点对象，存储循环链表上某个节点数据
+ type node struct {
+	 Data interface{}			// 数据域
+	 Next *node					// 指针域
+ }
+ 
+ // 循环链表对象：存储头指针与长度
+ type NHRingList struct {
+	 Head *node	
+	 Length int					
+ }
+ 
+ // 创建循环链表
+ func New() *NHRingList {
+	 head := &node{nil, nil}		// 头节点存储链表中元素的个数
+	//  head.Next = head				// 循环指向自己
+	 return &NHRingList{
+		 head,
+		 0,
+	 }
+ }
+ 
+ // 增加：末尾添加
+ func (rl *NHRingList) Append(data interface{}){
+ 
+	 insertNode := &node{data, rl.Head}					// 要插入的节点
+
+	 if rl.Length == 0 {								// 第一次添加
+		rl.Head = insertNode
+		rl.Head.Next = insertNode
+	 } else {									// 不是第一次添加
+		tailNode := rl.Head
+		for tailNode.Next != rl.Head {					
+			tailNode = tailNode.Next			// 找到最后一个节点
+		}
+		tailNode.Next = insertNode
+	 }
+
+	 rl.Length++
+	 return
+ }
+
+ // 打印链表
+ func (rl *NHRingList) Show() {
+
+	if rl.Length == 0 {
+		fmt.Println("list is empty")
+		return
+	}
+
+	 currentNode := rl.Head
+	 for i := 0; i <= rl.Length - 1; i++ {
+		 fmt.Print(currentNode.Data)
+		 if i == rl.Length - 1 {
+			 fmt.Print(" \n")
+		 } else {
+			 fmt.Print(" ")
+		 }
+ 
+		 currentNode = currentNode.Next
+	 }
+ }
diff --git a/sources/go/list/RingList/RingList.go b/sources/go/list/RingList/RingList.go
@@ -192,11 +192,18 @@
  }
 
  // 获取头结点
- func (rl *RingList)GetHead() *node{
+ func (rl *RingList)GetHead() *node {
 	return rl.head
  }
 
- // 获取下一个节点
- func (rl *RingList)GetNext(n *node)  *node {
-	return n.next
+ // 获取尾节点
+ func (rl *RingList)GetTail() *node {
+	if rl.Length() == 0 {
+		return nil
+	}
+	currentNode := rl.GetHead()
+	for currentNode.next != rl.GetHead() {
+		currentNode = currentNode.next
+	} 
+	return currentNode
  }
diff --git a/sources/go/main.go b/sources/go/main.go
@@ -5,6 +5,7 @@ import (
 	SequenList "algorithm/list/SequenList"
 	LinkedList "algorithm/list/LinkedList"
 	RingList "algorithm/list/RingList"
+	NHRingList "algorithm/list/NHRingList"
 	DoublyList "algorithm/list/DoublyList"
  	"fmt"
 )
@@ -98,54 +99,6 @@ func testDoublyList() {
 	dl.Show()
 }
 
-// 约瑟夫环
-func testJosephus(){	
-
-	// 生成循环链表
-	rl := RingList.New()
-	for i := 0; i < 41; i++ {					// 多个人组成的循环链表
-		rl.Append(i + 1)						// 每个人都对应自己的原始编号
-	}
-	fmt.Print("生成的循环链表为：")
-	rl.Show()
-
-	// 每次读取3个元素，读取位置从startNode开始
-	startNode := rl.GetHead()				// 起始开始报数的元素
-	delIndex := 0 								// 要删除元素的索引
-
-	num := 0
-	for {
-
-		for i:= 1; i <= 3; i++ {	
-
-			if rl.GetNext(startNode) == rl.GetHead() || startNode == rl.GetHead() {
-				delIndex = 1								// 每次从头结点开始时，删除索引变为0，重新记录
-				num = 0
-				startNode = rl.GetNext(rl.GetNext(startNode))
-			} else {
-				startNode = rl.GetNext(startNode)
-				delIndex ++	
-			}
-			
-		}
-
-
-		// 删除该元素
-		val, _ := rl.Node(delIndex - num)
-		fmt.Println("删除数据为：", delIndex - num, " ", val)
-		rl.Delete(delIndex)
-		num ++
-
-		// 如果只有一个元素
-		if rl.Length() < 3 {
-			break;
-		}
-	}
-
-	fmt.Print("最终的循环链表为：")
-	rl.Show()
-	return
-}
 
 func main() {
 
@@ -159,8 +112,6 @@ func main() {
 
 	// testRingList()					// 测试循环链表
 
-	testJosephus()						// 测试约瑟夫环
-
 	// testDoublyList()					// 测试双向链表
 
 }
