欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

循环链表实现原理及运用约瑟夫环实例

程序员文章站 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() } }