package main
import "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您可能感兴趣的文章:python超简单解决约瑟夫环问题C++循环链表之约瑟夫环的实现方法java 实现约瑟夫环的实例代码一个报数游戏js版(约瑟夫环问题)Python实现约瑟夫环问题的方法php解决约瑟夫环示例Java简单实现约瑟夫环算法示例javascript循环链表之约瑟夫环的实现方法深入理解约瑟夫环的数学优化方法约瑟夫环问题的PHP实现 使用PHP数组内部指针操作函数C数据结构循环链表实现约瑟夫环C++ 中循环链表和约瑟夫环