go算法与数据结构

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

稀疏数组

package main

import "fmt"

/*
稀疏数组
案例：五子棋存盘与复盘
节省存储空间
*/
type ValNode struct {
    row int //行
    col int //列
    val int //值
}

//原始数组实现
func normalArray() {
    var chessMap [11][11]int
    chessMap[1][2] = 1 //黑子
    chessMap[2][3] = 2 //白子
    //输出
    for _, v := range chessMap {
        for _, v2 := range v {
            fmt.Printf("%d ", v2)
        }
        fmt.Println()
    }
}

//稀疏数组实现

func sparseArray() {
    //数据源
    var chessMap [11][11]int
    chessMap[1][2] = 1 //黑子
    chessMap[2][3] = 2 //白子
    //切片
    var sparseArr []ValNode
    //创建一个ValNode节点
    valNode := ValNode{
        row: 11,
        col: 11,
        val: 0,
    }
    //输入全局默认节点
    sparseArr = append(sparseArr, valNode)
    for i, v := range chessMap {
        for j, v2 := range v {
            //创建一个节点
            if v2 != 0 {
                valNode := ValNode{
                    row: i,
                    col: j,
                    val: v2,
                }
                sparseArr = append(sparseArr, valNode)
            }

        }
    }
    //输出稀疏数组
    fmt.Println("当前的稀疏数组是。。。")
    //循环切片
    for i, valNode := range sparseArr {
        fmt.Printf("%d:%d %d %d\n", i, valNode.row, valNode.col, valNode.val)
    }
    var chessMap2 [11][11]int
    //稀疏数组恢复原始数组
    for i, valNode := range sparseArr {
        //跳过第一行默认记录值
        if i != 0 {
            chessMap2[valNode.row][valNode.row] = valNode.val
        }
    }
//输出恢复后的数组
for _,v:=range chessMap2{
    for _,v2:=range v{
        fmt.Printf("%d ",v2)
    }
    fmt.Println()
}
}

func main() {
    sparseArray()
}

View Code

队列

使用数据模拟队列

package main

import (
    "errors"
    "fmt"
    "os"
)

//使用结构体管理队列
type Queue struct {
    maxSize int
    array   [5]int //数组=》模拟队列
    front   int    //表示指向队首
    rear    int    //表示指向队尾
}

//添加数据到队列
func (this *Queue) AddQueue(val int) (err error) {
    //先判断队列是否已满
    if this.rear == this.maxSize-1 { //重要提示，rear是队列尾部(含最后元素
        return errors.New("queue full")
    }
    //元素从下标为1开始存入
    this.rear++ //后移
    //存入元素
    this.array[this.rear] = val
    return
}

//从队列中取出元素
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 (this *Queue) ShowQueue() {
    fmt.Println("队列当前的情况是：")
    //this.front//不包含队首
    for i := this.front + 1; i <= this.rear; i++ {
        fmt.Printf("array[%d]=%d\t", i, this.array[i])
    }
}

func main(){
    //创建一个队列
    queue:=&Queue{
        maxSize: 5,
        array:   [5]int{},
        front:   -1,
        rear:    -1,
    }
    var key string
    var val int
    for{
        fmt.Println("\n\n1.输入add表示添加数据到队列")
        fmt.Println("2.输入get表示从队列获取数据")
        fmt.Println("3.输入show表示显示队列")
        fmt.Println("4.输入exit表示退出\n\n")
        fmt.Scanln(&key)
        switch key {
        case "add":
            fmt.Println("请输入入队的数")
            fmt.Scanln(&val)
            err:=queue.AddQueue(val)
            if err!=nil{
                fmt.Println(err.Error())
            }else{
                fmt.Print("加入队列ok")
            }
        case "get":
            val,err:=queue.GetQueue()
            if err!=nil{
                fmt.Println(err.Error())
            }else{
                fmt.Println("從隊列中取出了一个数=",val)
            }
        case "show":
            queue.ShowQueue()
        case "exit":
            os.Exit(0)
        }
    }


}

View Code

通过数组实现环形队列

package main

import (
    "errors"
    "fmt"
    "os"
)

//数组模拟环形队列
/*
1.尾索引下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意
(tail+1)%maxSize==head满
2.tail==head [空]
*/

type CircleQueue struct {
    maxSize int    //4
    array   [5]int //数组
    head    int    //指向队首0
    tail    int    //指向队尾0
}

//入队
func (this *CircleQueue) Push(val int) (err error) {
    if this.IsFull() {
        return errors.New("queue full")
    }
    //分析指出this.tail 在队列尾部，但是包含最后的元素
    this.array[this.tail] = val //把值给队尾
    //如果当前行满。回到行初开始(加1是因为下标从零开始)
    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")
    }
    //取出head指向队首，并且含队首元素
    val = this.array[this.head]
    //%如果满行回到行首
    this.head = (this.head + 1) % this.maxSize
    return
}

//显示队列
func (this *CircleQueue) ListQueue() {
    fmt.Println("环形队列情况如下")
    //取出当前队列有多少个元素
    size := this.Size()
    if size == 0 {
        fmt.Println("队列为空")
    }
    //设计一个辅助便理那个指向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
}
/*
1.队尾在队首之后
this.tail% this.maxSize + this.maxSize% this.maxSize - this.head% this.maxSize
队尾之前的长度+1-队首之前的长度=总长度
*/

func main() {
    cq := CircleQueue{
        maxSize: 5,
        array:   [5]int{},
        head:    0,
        tail:    0,
    }
    var key string
    var val int
    for {
        fmt.Println("\n\n1.输入add表示添加数据到队列")
        fmt.Println("2.输入get表示从队列获取数据")
        fmt.Println("3.输入show表示显示队列")
        fmt.Println("4.输入exit表示退出\n\n")
        fmt.Scanln(&key)
        switch key {
        case "add":
            fmt.Println("请输入入队的数:")
            fmt.Scanln(&val)
            err := cq.Push(val)
            if err != nil {
                fmt.Println(err.Error())
            } else {
                fmt.Println("入队成功")
            }
        case "get":
            val, err := cq.Pop()
            if err != nil {
                fmt.Println(err.Error())
            } else {
                fmt.Printf("出队成功:%d", val)
            }
        case "show":
            cq.ListQueue()
        case "exit":
            os.Exit(0)
        default:
            fmt.Println("输入错误")
        }
    }
}

View Code

链表

单向链表

package main

import "fmt"

/*
单向链表的应用
水浒英雄排行榜
*/

type HeroNode struct {
    no       int
    name     string
    nickname string
    next     *HeroNode //表示指向下一个节点
}

//给链表插入一个节点
//编写第一个插入方法，在单链表最后加入

func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
    temp := head
    for {
        if temp.next == nil { //表示找到最后
            break
        }
        temp = temp.next //让temp不断指向下一个节点
    }
    //3.将newHeroNode加入到链表最后
    temp.next = newHeroNode
}

//第二种插入方法，根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHreoNode *HeroNode) {
    //1.找到适当的节点
    temp := head
    flag := true
    //让插入的节点的no,和temp的下一个结点比较
    for {
        if temp.next == nil { //说明到了链表最后
            break
        } else if temp.next.no >= newHreoNode.no {
            //说明newHeroNode就应该插入到temp后面
            break
        } else if temp.next.no == newHreoNode.no {
            //说明链表中已经有这个no,就不插入
            flag = false
            break
        }
        //不断寻找下一个结点
        temp = temp.next
    }

    if !flag {
        fmt.Println("对不起，已经存在no=", newHreoNode.no)
        return
    } else {
        newHreoNode.next = temp.next
        temp.next = newHreoNode
    }
}

//显示所有链表节点信息
func ListNode(head *HeroNode) {
    //1.创建一个辅助结点
    temp := head
    //先判断该链表是不是一个空链表
    if temp.next == nil {
        fmt.Println("空空如也。。。")
        return
    }
    //2.遍历这个链表
    for {
        fmt.Printf("[%d,%s,%s==>", temp.next.no,
            temp.next.name, temp.next.nickname)
        //判断是否链表后
        temp = temp.next
        if temp.next == nil {
            break
        }
    }
}

//删除结点
func DelHeroNode(head *HeroNode, id int) {
    temp := head
    flag := false
    //找到要删除的结点，和temp的下一个结点的no比较
    for {
        if temp.next == nil { //说明到链表最后
            break
        } else if temp.next.no == id {
            //找到了
            flag = true
            break
        }
        temp = temp.next
    }
    if flag {
        temp.next = temp.next.next
    } else {
        fmt.Println("sorry,要删除的id,不存在")
    }
}
func main() {
    //1.先创建一个头结点
    head := &HeroNode{}
    //2.创建一个新的HeroNode
    hero1 := &HeroNode{
        no:       1,
        name:     "宋江",
        nickname: "及时雨",
    }

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

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

    hero4 := &HeroNode{
        no:       3,
        name:     "吴用",
        nickname: "智多星",
    }
    InsertHeroNode(head, hero4)
    InsertHeroNode(head, hero1)
    InsertHeroNode(head, hero2)
    InsertHeroNode(head, hero3)

    ListNode(head)
    //3.加入
    //InsertHeroNode2(head, hero3)
    //InsertHeroNode2(head, hero1)
    //InsertHeroNode2(head, hero2)
    //InsertHeroNode2(head, hero4)
    ////4.显示
    //ListNode(head)
}

View Code

双向链表

package main

import "fmt"

type HeroNode struct {
    no       int
    name     string
    nickname string
    pre      *HeroNode //这个结点指向前一个结点
    next     *HeroNode //着这结点指向下一个结点
}

//给双向链表插入一个结点
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
    //思路
    //1.先找到该链表的最后这个结点
    //2.创建一个辅助结点
    temp := head
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next //让temp不断指向下一个结点
    }
    //3.将newHeroNode加入到链表的最后
    temp.next = newHeroNode
    newHeroNode.pre = temp
}

//给双向链表插入一个结点
//
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {
    //1.找到适当的结点
    //2.创建一个辅助结点
    temp := head
    flag := true
    //让插入结点的no,和temp的下一个结点的no比较
    for {
        if temp.next == nil {
            break
        } else if temp.next.no >= newHeroNode.no {
            //说明newHeroNode就因该插入到temp后面
            break
        } else if temp.next.no >= newHeroNode.no {
            flag = false
            break
        }
        temp = temp.next
    }

    if !flag {
        fmt.Println("对不起，已经存在no=", newHeroNode.no)
        return
    } else {
        newHeroNode.next = temp.next
        newHeroNode.pre = temp
        if temp.next != nil { //不是最后一个才进行操作
            temp.next.pre = newHeroNode
        }
        temp.next = newHeroNode

    }
}

//删除结点
func DelHeroNode(head *HeroNode, id int) {
    temp := head
    flag := true
    //找到要删除的结点的no,和temp的下一个结点no比较
    for {
        if temp.next == nil {
            break
        } else 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("sorry, 要删除的id不存在")
        }
    }
}

//使用单链表的显示方式显示链表
func ListHeroNode(head *HeroNode) {
    //1.辅助结点
    temp := head
    if temp.next == nil {
        fmt.Println("空空如也。。。")
        return
    }
    //遍历链表
    for {
        fmt.Printf("[%d,%s,%s]=>", temp.next.no,
            temp.next.name, temp.next.nickname)
        //判断是否链表
        temp = temp.next
        if temp.next == nil {
            break
        }
    }
}

//方式二
//使用单链表的显示方式显示链表
func ListHeroNode2(head *HeroNode) {
    //1.辅助结点
    temp := head
    if temp.next == nil {
        fmt.Println("空空如也。。。")
        return
    }
    //2.让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
        }
    }
}

func main() {
    //1.先创建一个头结点
    head := &HeroNode{}
    //2.创建一个新的HeroNode
    hero1 := &HeroNode{
        no:       1,
        name:     "宋江",
        nickname: "及时雨",
    }

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

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

    hero4 := &HeroNode{
        no:       3,
        name:     "吴用",
        nickname: "智多星",
    }
    InsertHeroNode(head, hero1)
    InsertHeroNode(head, hero2)
    InsertHeroNode(head, hero3)
    InsertHeroNode(head, hero4)
    ListHeroNode(head)
    fmt.Println("\n逆序打印")
    ListHeroNode2(head)

}

View Code

环形单向链表

package main

import "fmt"

/*
环形单向链表

*/
//定义猫的结构体结点
type CatNode struct {
    no   int //编号
    name string
    next *CatNode
}

//在末尾加入新的结点
func InsertCatNode(head *CatNode, newCatNode *CatNode) {
    //判断是不是添加第一只猫
    if head.next == nil {
        head.no = newCatNode.no
        head.name = newCatNode.name
        head.next = head //构成