数据结构--环形链表

环形链表的一种Go语言实现

package mainimport "fmt"//定义一个环形链表的节点结构体 type circleSingleLink struct {id intname stringnext *circleSingleLink }//插入节点到环形链表 func Insert(head, newnode *circleSingleLink) {//判断是否为空链表if head.next == nil{//如果为空则把添加的第一个元素给头节点，这里和其他链表有些区别，其他链表头结点是空的head.id = newnode.idhead.name = newnode.name//重点是要让一个节点也形成一个环形，即收尾相接head.next = headreturn}//添加非头结点到环形链表temp := headfor{if temp.next == head {//尾部添加temp.next = newnodenewnode.next = headbreak}temp = temp.next} }//显示环形链表的所有节点信息 func CircleList(head *circleSingleLink){//判断链表是否为空if head.next == nil {fmt.Println("链表为空")return}temp := headfor {fmt.Printf("[%d %s] -> ", temp.id, temp.name)//注意这里是这样判断终止条件的if temp.next == head{break}temp = temp.next} }//删除环形链表的一个节点(难点) func CircleDelete(head, node *circleSingleLink) *circleSingleLink { //之所以有返回值是因为头结点的值和指向要发生变化//删除思路：//先让temp 指向head//再让helper指向环形链表的最后//让temp和要删除的节点比较，如果相同，则让helper完成删除节点，重点是要考虑是否为头结点，因为环形链表的头结点有值temp := headif temp.next == nil { //链表为空的时候fmt.Println("链表为空")return head}if temp.next == head { //只有一个头结点的环形链表temp.next = nilreturn head}helper := headfor {if helper.next == head {break}helper = helper.next //将指针定位到环形链表的尾节点}//如果有两个及以上的节点for {if temp.next == head {//说明到最后一个并且还没判断是否是要删除的节点if temp.id == node.id {helper.next = temp.next}else {fmt.Println("没有该节点")}break}if temp.id == node.id { //找到了要删除的节点if temp == head { //如果删除的是头结点head = head.next}//删除非头结点helper.next = temp.next //helper始终在temp的后一个break}temp = temp.next //用作比较helper = helper.next //用作操作}return head }func main(){//定义一个链表的头head := &circleSingleLink{}//定义第一个节点node1 := &circleSingleLink{id: 1,name : "number1",}node2 := &circleSingleLink{id: 2,name : "number2",}node3 := &circleSingleLink{id: 3,name : "number3",}Insert(head, node1)Insert(head, node2)Insert(head, node3)head = CircleDelete(head, node1)CircleList(head) }

约瑟夫问题：

package mainimport "fmt"type Boy struct {id intnext *Boy }//创建一个环形链表,并返回头指针 func CreateLink(num int) *Boy {first := &Boy{} //头指针不能动，因此需要一个辅助指针进行循环创建curBoy := &Boy{}if num < 1 {return first}for i := 1; i <= num; i++ {boy := &Boy{id: i,next: nil,}if i == 1 { //因为第一个小孩比较特殊first = boycurBoy = boycurBoy.next = first}else {curBoy.next = boycurBoy = boycurBoy.next = first //构成环形链表}}return first }//显示环形链表 func ShowBoy (first *Boy) {if first.next == nil {fmt.Println("链表为空")return}curBoy := firstfor {fmt.Printf("小孩%d -> ", curBoy.id)if curBoy.next == first {break}curBoy = curBoy.next} }//使用环形链表实现约瑟夫问题 func PlayGame(first *Boy, startNo int, countNum int) {//空链表的情况if first.next == nil {fmt.Println("链表为空，游戏结束")return}//定义两个指针循环，其中first负责比较，tail负责删除tail := first//将tail指正定位到链表的最后for {if tail.next == first {break}tail = tail.next}//开始移动startNo-1步for i := 0; i < startNo -1; i++ {first = first.nexttail = tail.next}fmt.Println()//开始循环删除环形链表中第countNum-1个节点for {for i := 0; i < countNum - 1; i++ {first = first.nexttail = tail.next}//打印即将出圈的节点信息fmt.Printf("编号为%d的节点出圈\n", first.id)//删除此时first指向的当前节点first = first.nexttail.next = first//确定结束条件if tail == first {break}}//打印最后一个出圈的节点fmt.Printf("编号为%d的节点出圈\n", first.id) }func main(){first := CreateLink(51)ShowBoy(first)PlayGame(first, 2, 3) }

总结

以上是生活随笔为你收集整理的数据结构--环形链表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。