关于数据结构:数据结构环形链表

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

package main

import "fmt"

// 定义一个环形链表的节点构造体
type circleSingleLink struct {
    id int
    name string
    next *circleSingleLink
}

// 插入节点到环形链表
func Insert(head, newnode *circleSingleLink) {
    // 判断是否为空链表
    if head.next == nil{
        // 如果为空则把增加的第一个元素给头节点，这里和其余链表有些区别，其余链表头结点是空的
        head.id = newnode.id
        head.name = newnode.name
        // 重点是要让一个节点也造成一个环形，即收尾相接
        head.next = head
        return
    }
    // 增加非头结点到环形链表
    temp := head
    for{
        if temp.next == head {
            // 尾部增加
            temp.next = newnode
            newnode.next = head
            break
        }
        temp = temp.next
    }
}

// 显示环形链表的所有节点信息
func CircleList(head *circleSingleLink){
    // 判断链表是否为空
    if head.next == nil {fmt.Println("链表为空")
        return
    }

    temp := head
    for {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 := head
    if temp.next == nil { // 链表为空的时候
        fmt.Println("链表为空")
        return head
    }
    if temp.next == head { // 只有一个头结点的环形链表
        temp.next = nil
        return head
    }
    helper := head
    for {
        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 main

import "fmt"

type Boy struct {
    id int
    next *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 = boy
            curBoy = boy
            curBoy.next = first
        }else {
            curBoy.next = boy
            curBoy = boy
            curBoy.next = first // 形成环形链表
        }
    }
    return first
}

// 显示环形链表
func ShowBoy (first *Boy) {
    if first.next == nil {fmt.Println("链表为空")
        return
    }
    curBoy := first
    for {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.next
        tail = tail.next
    }
    fmt.Println()
    // 开始循环删除环形链表中第 countNum- 1 个节点
    for {
        for i := 0; i < countNum - 1; i++ {
            first = first.next
            tail = tail.next
        }
        // 打印行将出圈的节点信息
        fmt.Printf("编号为 %d 的节点出圈 \n", first.id)
        // 删除此时 first 指向的以后节点
        first = first.next
        tail.next = first
        // 确定完结条件
        if tail == first {break}
    }
    // 打印最初一个出圈的节点
    fmt.Printf("编号为 %d 的节点出圈 \n", first.id)
}

func main(){first := CreateLink(51)
    ShowBoy(first)
    PlayGame(first, 2, 3)
}