您的位置 首页 golang

golang实现队列、链表、环形单向链表

智云科技发布于 2022年6月16日评论关闭阅读(366)

队列 

 package main
 import  (
    "errors"
    "fmt"
)
//基本实现队列，但是数组没有得到循环利用
type Queue  struct  {
    maxSize int
    array   [5]int
    front   int //队首
    rear    int //队尾
}

func (this *Queue) AddQueue(val int) (err error) {
    //判断队列是否满 rear是队列尾部（含最后元素）
    if this.rear == this.maxSize-1 {
        return errors.New("queue full")
    }

    this.rear++ //后移
    this.array[this.rear] = val
    return
}

func (this *Queue) ShowQueue() {
    //this.front不包含对手的元素
    fmt.Println("显示队列数据：")
    for i := this.front + 1; i <= this.rear; i++ {
        fmt.Printf("array[%d] = %d\t", i, this.array[i])
    }

    fmt.Println()
}

func (this *Queue) GetQueue() (val int,  err  error) {
    //判空
    if this.rear == this.front {
        return -1, errors.New("queue empty")
    }

    this.front++
    val = this.array[this.front]
    return val, err
}

func main() {
    queue := &Queue{
        maxSize: 5,
        front:   -1,
        rear:    -1,
    }

    for i := 1; i <= 5; i++ {
        err := queue.AddQueue(i)
        if err != nil {
            fmt.Printf("error: ", err)
        }
    }
    queue.ShowQueue()

    for i := 1; i <= 2; i++ {
        val, err := queue.GetQueue()
        if err != nil {
            fmt.Println("error: ", err)
        } else {
            fmt.Println("get value is : ", val)
        }
    }

    queue.ShowQueue()
}

分析思路：

1 队列满：(tail + 1) % maxSize == head

tail 和 head之间要空一个元素

2 tail == head 表示队列空

3 初始化： tail = head = 0

4 元素个数统计：(tail – head + maxSize) % maxSize

tail – head > 0: tail – head

tail – head < 0: maxSize + tail – head

合并后即为上式 

 
package main
import (
    "errors"
    "fmt"
)
//环形队列
type CircleQueue struct {
    maxSize int
    array   [5]int //只能装4个元素，空一个
    head    int    //0
    tail    int    //0
}

func (this *CircleQueue) Push(val int) (err error) {
    if this.IsFull() {
        return errors.New("queue full\n")
    }

    this.array[this.tail] = val
    this.tail = (this.tail + 1) % this.maxSize
    return
}

func (this *CircleQueue) Pop() (val int, err error) {
    if this.IsEmpty() {
        return 0, errors.New("queue empty\n")
    }

    val = this.array[this.head]
    this.head = (this.head + 1) % this.maxSize
    return val, err
}

func (this *CircleQueue) ListQueue() {
    fmt.Println("list data: ")
    size := this.Size()
    if size == 0 {
        fmt.Println("queue empty\n")
        return
    }

    //设计辅助变量，指向head
    tempHead := this.head
    for i := 0; i < size; i++ {
        fmt.Printf("arr[%d] = %d\t", tempHead, this.array[tempHead])
        tempHead = (tempHead + 1) % this.maxSize
    }

    fmt.Println()
}

func (this *CircleQueue) IsFull()  bool  {
    return (this.tail+1)%this.maxSize == this.head
}

func (this *CircleQueue) IsEmpty() bool {
    return this.tail == this.head
}

func (this *CircleQueue) Size() int {
    return (this.tail + this.maxSize - this.head) % this.maxSize
}

func main() {
    queue := &CircleQueue{
        maxSize: 5,
        head:    0,
        tail:    0,
    }

    for i := 1; i <= 5; i++ {
        err := queue.Push(i)
        if err != nil {
            fmt.Printf("error: ", err)
        }
    }
    queue.ListQueue()

    for i := 1; i <= 2; i++ {
        val, err := queue.Pop()
        if err != nil {
            fmt.Println("error: ", err)
        } else {
            fmt.Println("get value is : ", val)
        }
    }

    queue.ListQueue()
}

链表

要点：

1 头结点：不放数据，只为标识链表而已 

 package main

import "fmt"

//单向链表

type HeroNode struct {
    no       int
    name     string
    nickname string
    next     *HeroNode
}

//尾插法添加结点
func Insert(head *HeroNode, new *HeroNode) {
    //找到最后结点 temp指向最后结点
    temp := head
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }

    //添加
    temp.next = new
}

//按编号从小到大顺序插入
func Insert2(head *Hero no de, new *HeroNode) {
    temp := head
    flag := true
    for {
        //到链表的最后
        if temp.next == nil {
            break
        } else if temp.next.no > new.no {
            //插入到temp后面
            break
        } else if temp.next.no == new.no {
            //说明链表中有no元素
            flag = false
            break
        }

        temp = temp.next
    }

    if !flag {
        fmt.Println("existed node no = ", new.no)
        return
    } else {
        new.next = temp.next
        temp.next = new
    }
}

func List(head *HeroNode) {
    temp := head
    //判断是否为空
    if temp.next == nil {
        fmt.Println("empty link list.")
        return
    }

    for {
        fmt.Printf("[%d, %s, %s]==>", temp.next.no, temp.next.name, temp.next.nickname)
        temp = temp.next
        if temp.next == nil {
            break
        }
    }

    fmt.Println()
}

func Delete(head *HeroNode, id int) {
    temp := head
    flag := false
    for {
        if temp.next == nil {
            break
        }

        if temp.next.no == id {
            flag = true
            break

        }

        temp = temp.next
    }
    //找到，删除
    if flag {
        temp.next = temp.next.next
    } else {
        fmt.Println("can not find node, delete failed.")
    }
}

func main() {
    //1 创建头结点
    head := &HeroNode{}

    //2 创建一个新的结点
    hero1 := &HeroNode{
        no:       1,
        name:     "宋江",
        nickname: "及时雨",
    }

    hero2 := &HeroNode{
        no:       2,
        name:     "卢俊义",
        nickname: "玉麒麟",
    }

    hero3 := &HeroNode{
        no:       3,
        name:     "林冲",
        nickname: "豹子头",
    }

    hero4 := &HeroNode{
        no:       4,
        name:     "吴用",
        nickname: "智多星",
    }

    Insert2(head, hero3)
    Insert2(head, hero2)
    Insert2(head, hero1)
    Insert2(head, hero4)
    List(head)
    Delete(head, 3)
    List(head)
}  

 
package main

import "fmt"

//双向向链表

type HeroNode struct {
    no       int
    name     string
    nickname string
    next     *HeroNode
    pre      *HeroNode
}

//尾插法添加结点
func Insert(head *HeroNode, new *HeroNode) {
    //找到最后结点 temp指向最后结点
    temp := head
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }

    //添加
    temp.next = new
    new.pre = temp
}

//按编号从小到大顺序插入
func Insert2(head *HeroNode, new *HeroNode) {
    temp := head
    flag := true
    for {
        //到链表的最后
        if temp.next == nil {
            break
        } else if temp.next.no > new.no {
            //插入到temp后面
            break
        } else if temp.next.no == new.no {
            //说明链表中有no元素
            flag = false
            break
        }

        temp = temp.next
    }

    if !flag {
        fmt.Println("existed node no = ", new.no)
        return
    } else {
        //注意这里
        new.next = temp.next
        new.pre = temp
        temp.next = new
        //如果是最后一个节点
        if temp.next != nil {
            new.next.pre = new
        }
    }
}

func List(head *HeroNode) {
    temp := head

    //判断是否为空
    if temp.next == nil {
        fmt.Println("empty link list.")
        return
    }

    //temp指向最后一个元素
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }
    //从后往前打印输出
    for {
        fmt.Printf("[%d, %s, %s]==>", temp.no, temp.name, temp.nickname)
        temp = temp.pre
        if temp.pre == nil {
            break
        }
    }

    fmt.Println()
}

func Delete(head *HeroNode, id int) {
    temp := head
    flag := false
    for {
        if temp.next == nil {
            break
        }

        if temp.next.no == id {
            flag = true
            break

        }

        temp = temp.next
    }
    //找到，删除
    if flag {
        temp.next = temp.next.next
        //最后一个节点，注意这里，容易出错
        if temp.next != nil {
            temp.next.pre = temp
        }
    } else {
        fmt.Println("can not find node, delete failed.")
    }
}

func main() {
    //1 创建头结点
    head := &HeroNode{}

    //2 创建一个新的结点
    hero1 := &HeroNode{
        no:       1,
        name:     "宋江",
        nickname: "及时雨",
    }

    hero2 := &HeroNode{
        no:       2,
        name:     "卢俊义",
        nickname: "玉麒麟",
    }

    hero3 := &HeroNode{
        no:       3,
        name:     "林冲",
        nickname: "豹子头",
    }

    hero4 := &HeroNode{
        no:       4,
        name:     "吴用",
        nickname: "智多星",
    }

    Insert(head, hero1)
    Insert(head, hero2)
    Insert(head, hero3)
    Insert(head, hero4)
    List(head)
}

环形单向链表 

 
package main
import "fmt"

type CatNode struct {
    no   int
    name string
    next *CatNode
}

func Insert(head *CatNode, new *CatNode) {
    //是否是添加第一只猫
    if head.next == nil {
        head.no = new.no
        head.name = new.name
        head.next = head //构成一个环形
        return
    }

    //临时变量:找到最后一个节点
    temp := head
    for {
        if temp.next == head {
            break
        }
        temp = temp.next
    }

    //加入链表中
    temp.next = new
    new.next = head
}

func List(head *CatNode) {
    fmt.Println("list data: ")
    temp := head
    if temp.next == nil {
        fmt.Println("empty circle link list.")
        return
    }

    for {
        fmt.Printf("cat=[id=%d name=%s] -> \n", temp.no, temp.name)
        if temp.next == head {
            break
        }
        temp = temp.next
    }
}

//使用两个临时变量：temp指向head，helper指向尾部，helper的next指向temp
//让temp和要删除的id比较，如果id同，让helper完成删除
//注意：考虑头结点的删除
//由于有可能删除头结点，因此需要在返回值中返回新的头结点
func Delete(head *CatNode, id int) *CatNode {
    //1 判断链表是否为空
    if head.next == nil {
        fmt.Println("empty link list.")
        return head
    }

    //2 只有一个节点
    if head.next == head {
        if head.no == id {
            head.next = nil //将next设为Nil，表示整个链表为空
            return head
        } else {
            return head
        }
    }

    //2个或者多个节点
    temp := head   //指向头结点
    helper := head //指向最后结点
    for {
        if helper.next == head {
            break
        }
        helper = helper.next
    }

    //遍历比较
    find := true //是否找到需要删除的结点，排除最后一个节点，需要对最后一个节点做单独处理
    for {
        //遍历到最后一个结点前一个结点，仍旧没有找到需要删除的结点
        if temp.next == head { //此时temp指向倒数第1个节点
            find = false //表示没有找到
            break
        }

        if temp.no == id {
            helper.next = temp.next
            break
        }

        temp = temp.next
        helper = helper.next
    }

    //如果没有找到
    if !find {
        if temp.no == id {
            helper.next = temp.next
        } else {
            fmt.Printf("do not exist no = %d", id)
        }
    }

    return helper.next //返回头结点
}

func main() {
    //初始化头结点
    head := &CatNode{}

    //创建一只猫
    cat1 := &CatNode{
        no:   1,
        name: "tom",
    }

    //创建一只猫

    cat2 := &CatNode{
        no:   2,
        name: "jack",
    }

    //创建一只猫
    cat3 := &CatNode{
        no:   3,
        name: "cat3",
    }

    Insert(head, cat1)
    Insert(head, cat2)
    Insert(head, cat3)
    List(head)
    head = Delete(head, 4)
    List(head)
}
标签:
打赏 点赞(2)

文章来源：智云一二三科技

文章标题：golang实现队列、链表、环形单向链表

文章地址：https://www.zhihuclub.com/89627.shtml

关于作者: 智云科技

相关文章

热门文章

1分享新浪图床上传接口源码

点赞(1.02K)阅读(63,396)

2PHP简单实现路由Route功能

点赞(1.23K)阅读(36,027)

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

点赞(444)阅读(4,342)

4centos系统如何查看是否安装了mysql

点赞(617)阅读(3,830)

5curl 工具简述

点赞(609)阅读(3,024)
网站地图