循环链表实现原理及运用约瑟夫环实例
程序员文章站
2022-06-05 15:45:02
package main import "fmt" type LinkNode struct { Data interface{} Next *LinkNode } //创建循环链表 func (node *LinkNode) Create(Data ...interface{}) { if nod... ......
package main
import "fmt"
type linknode struct {
data interface{}
next *linknode
}
//创建循环链表
func (node *linknode) create(data ...interface{}) {
if node == nil {
return
}
if len(data) == 0 {
return
}
//记录头节点
head := node
for _, v := range data {
//创建一个新节点
newnode := new(linknode)
newnode.data = v
//当前节点的下一个节点为新节点
node.next = newnode
node = node.next
}
//形成闭环
//最后一个节点的下一个节点 为第一个节点
node.next = head.next
node = head
}
//打印循环链表
func (node *linknode) print() {
if node == nil {
return
}
//记录循环链表的起始点
start := node.next
//打印链表
for {
node = node.next
if node.data != nil {
fmt.print(node.data, " ")
}
if start == node.next {
break
}
}
// 单向链表打印方式
//for node.next != nil {
// if node.data != nil {
// fmt.println(node.data)
// }
// node = node.next
//}
}
//循环链表长度 返回值 个数
func (node *linknode) length() int {
if node == nil {
return -1
}
//记录循环链表的起始点
start := node.next
//定义计数器
i := 0
for {
node = node.next
i++
if start == node.next {
break
}
}
return i
}
//插入数据(下标 数据)
func (node *linknode) insert(index int, data interface{}) {
if node == nil {
return
}
//判断位置是否越界
if index < 0 || node.length()+1 < index {
return
}
if data == nil {
return
}
fmt.println(node)
//记录链表第一个节点
start := node.next
//记录上一个节点
prenode := node
for i := 0; i < index; i++ {
prenode = node
node = node.next
}
//创建新节点
newnode := new(linknode)
newnode.data = data
//新节点的下一个节点为node
newnode.next = node
//上一个节点的下一个节点为新节点
prenode.next = newnode
//判断如果是第一个节点需要将最后一个节点指向新节点
if index == 1 {
for {
//判断最后一个节点
if start == node.next {
break
}
node = node.next
}
//新节点为最后一个节点的下一个节点
node.next = newnode
}
}
//删除数据 (下标)
func (node *linknode) delete(index int) {
if node == nil {
return
}
if index < 0{
return
}
//起始节点
start := node.next
//记录上一个节点
prenode := node
//循环找到删除数据的位置
for i := 0; i < index; i++ {
prenode = node
node = node.next
}
//判断如果删除的是第一个节点
if index == 1 {
//temp记录最后一个位置
temp := start
for {
if start == temp.next {
break
}
temp = temp.next
}
//将最后一个节点指向新节点
temp.next = node.next
}
//删除数据
prenode.next = node.next
//数据销毁
//node.data = nil
//node.next = nil
node = nil
}
//约瑟夫环
//运用 -- 海盗分金
func main() {
list := new(linknode)
list.create(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)
fmt.println("原始数据:")
list.print()
fmt.println()
fmt.println("删除数据:")
i := 1
for list.length() > 2 {
i += 3
if i > list.length() {
i = list.length()%3 + 1
}
list.delete(i)
list.print()
fmt.println()
}
}
上一篇: 谈谈:借势营销是怎么借势的
下一篇: 今天闺女犯错被老公惩罚打一板子