数据结构

作者: 雪上霜 | 来源:发表于2020-06-20 15:13 被阅读0次

IOS开发_数据结构
py基础
思维导图之数据结构+算法
数据结构与算法分析：大纲]
数据结构：数组
数据结构—概述
OVS 源码分析整理
01. 数据结构与算法绪论
数据结构与算法 - 查找
C#之数据结构（上）

稀疏数组

image.png

代码实现：

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

type ValNode struct {
    row int
    col int
    val int
}

var chessMap2 [11][11]int

func printArr(arr [11][11]int){
    for _,v := range arr{
        for _,v2 := range v{
            fmt.Printf("%d\t",v2)
        }
        fmt.Println()
    }
}

func changSparse(arr [11][11]int)[]ValNode{
    //1)遍历chessMap，如果有一个元素的值不为0，创建一个node结构体，
    //2)将其放入切片中。

    var sparseArr []ValNode

    //标准的一个稀疏数组应该还有一个记录原始二位数组的规模（行列,默认值）
    valNode := ValNode{
        row: 11,
        col: 11,
        val: 0,
    }
    sparseArr = append(sparseArr,valNode)
    for i,v := range arr{
        for j,v2 := range v{
            if v2 != 0{
                //创建一个valNode值结点
                valNode := ValNode{
                    row: i,
                    col: j,
                    val: v2,
                }
                sparseArr = append(sparseArr,valNode)
            }
        }
    }
    return sparseArr
}

func writeSparse(sparseArr []ValNode){
    file,err := os.OpenFile("chessMap.txt", os.O_APPEND|os.O_CREATE, 0666)
    if err != nil{
        panic(err)
    }
    defer file.Close()

    //var buf []string
    //w := bufio.NewWriter(file)
    for _,v := range sparseArr{
        //buf = []string{strconv.Itoa(v.row),strconv.Itoa(v.col),strconv.Itoa(v.val)}
        file.WriteString(strconv.Itoa(v.row))
        file.WriteString(" ")
        file.WriteString(strconv.Itoa(v.col))
        file.WriteString(" ")
        file.WriteString(strconv.Itoa(v.val))
        file.WriteString("\n")
    }
}

func readFile(){
    //如何恢复原始数组
    //1、打开文件
    f,err := os.Open("chessMap.txt")
    if err != nil{
        panic(err)
    }
    //2、遍历数据，恢复

    r := bufio.NewReader(f)
    for {
        // 分行读取文件  ReadLine返回单个行，不包括行尾字节(\n  或 \r\n)
        //data, _, err := r.ReadLine()

        // 以分隔符形式读取,比如此处设置的分割符是\n,则遇到\n就返回,且包括\n本身 直接返回字符串
        //str, err := r.ReadString('\n')

        // 以分隔符形式读取,比如此处设置的分割符是\n,则遇到\n就返回,且包括\n本身 直接返回字节数数组
        data, err := r.ReadBytes('\n')

        // 读取到末尾退出
        if err == io.EOF {
            break
        }

        if err != nil {
            fmt.Println("read err", err.Error())
            break
        }

        // 打印出内容
        //fmt.Printf("%v", string(data))
        var row int
        var col int
        var val int


        str := strings.Trim(string(data),"\n")
        s := strings.Split(str," ")
        for i,v := range s{
            n,_ := strconv.Atoi(v)
            if n == 11{
                break
            }
            if i == 0{
                row = n
            }else if i == 1{
                col = n
            }else{
                val = n
            }
        }
        chessMap2[row][col] = val
    }
}
func main(){
    //1、先创建一个原始数值
    var chessMap [11][11]int
    chessMap[1][2] = 1  //黑子
    chessMap[2][3] = 2  //蓝子

    //2、输出原始数组
    printArr(chessMap)

    //3、转成稀疏数组
    sparseArr := changSparse(chessMap)

    //输出稀疏数组
    fmt.Println("稀疏数组为：")
    for i,valNode := range sparseArr{
        fmt.Printf("%d:%d %d %d\n",i,valNode.row,valNode.col,valNode.val)
    }

    //将稀疏数组存盘
    writeSparse(sparseArr)
    fmt.Println("写入成功。。。")

    readFile()
    //输出读取后的数组
    printArr(chessMap2)
    //暂时用稀疏数组恢复
    //先创建一个原始数组大小
    //var chessMap2 [11][11]int
    ////遍历sparseArr
    //for i,valNode := range sparseArr{
    //  if i != 0{//跳过第一个值
    //      chessMap2[valNode.row][valNode.col] = valNode.val
    //  }
    //}
    //
    //fmt.Println("恢复后的数据：")
    ////遍历chessMap2
    //for _,v := range chessMap2{
    //  for _,v2 := range v{
    //      fmt.Printf("%d\t",v2)
    //  }
    //  fmt.Println()
    //}
}

队列

image.png

代码实现：

package main

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

type Queue struct {
    maxSize int
    array [5]int    //数组模拟队列
    front int       //表示指向队列首
    rear int        //表示指向队列的尾部
}

//添加数据到队列
func (q *Queue)AddQueue(val int)(err error){
    //先判断队列是否已满
    if q.rear == q.maxSize - 1{
        return errors.New("queue full")
    }
    q.rear++ //后移
    q.array[q.rear] = val
    return
}

//取队列
func (q *Queue)GetQueue()(val int,err error){
    //先判断队列是否为空
    if q.rear == q.front{
        //队空
        return -1,errors.New("queue empty")
    }
    q.front++
    val = q.array[q.front]
    return val,err
}

//显示队列
//找到对首，然后遍历到队尾，不包含队首元素
func (q *Queue)ShowQueue(){
    for i := q.front + 1;i <= q.rear;i++{
        fmt.Printf("array[%d]=%d\t",i,q.array[i])
    }
}

func main(){
    //先创建一个队列
    queue := &Queue{
        maxSize: 5,
        front: -1,
        rear: -1,
    }

    var key string
    var val int
    for{
        fmt.Println("1. 输入add表示添加数据到队列")
        fmt.Println("2. 输入get表示添加数据到队列")
        fmt.Println("3. 输入show表示添加数据到队列")
        fmt.Println("4. 输入exit表示添加数据到队列")

        fmt.Scan(&key)
        switch key {
        case "add":
            fmt.Println("输入你要入队的数")
            fmt.Scan(&val)
            err := queue.AddQueue(val)
            if err == nil{
                fmt.Println("加入队列OK")
            }else{
                fmt.Println(err.Error())
            }
        case "get":
            val,err := queue.GetQueue()
            if err != nil{
                fmt.Println(err.Error())
            }else{
                fmt.Println("从队列中取出一个数",val)
            }
        case "show":
            queue.ShowQueue()
            fmt.Println()
        case "exit":
            os.Exit(0)
        }
    }
}

环形队列

image.png

什么时候队列满：（rear+1）%maxsize == front
什么时候为空：rear == front
初始化：rear = 0,front = 0;
统计队列数：（rear + maxsize - front）% maxsize
代码实现：

package main

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

//使用一个结构体管理环形队列

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

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

    //tail并不在队列尾部，不包含最后的元素
    c.array[c.tail] = val
    c.tail = (c.tail+1) % c.maxSize
    return nil
}

func (c *CircleQueue)Pop()(val int,err error){
    if c.IsEmpty(){
        return 0,errors.New("queue empty")
    }
    //取出元素,head指向队首，含队首元素。
    val = c.array[c.head]
    c.head = (c.head+1)%c.maxSize
    return val,nil
}

//判断环形队列为满
func (c *CircleQueue)IsFull()bool{
    return (c.tail+1)%c.maxSize == c.head
}

//判断队列是否为空
func (c *CircleQueue)IsEmpty()bool{
    return c.head == c.tail
}

//取出环形队列有多少个元素
func (c *CircleQueue)Size()int{
    return (c.tail+c.maxSize-c.head)%c.maxSize
}

//显示队列
func (c *CircleQueue)Show(){
    fmt.Println("环形队列情况如下：")
    //取出当前队列的元素
    size := c.Size()
    if size == 0{
        fmt.Println("队列为空")
    }

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

func main(){
    //先创建一个环形队列
    queue := &CircleQueue{
        maxSize: 5,
        head: 0,
        tail: 0,
    }

    var key string
    var val int
    for{
        fmt.Println("1. 输入add表示添加数据到队列")
        fmt.Println("2. 输入get表示添加数据到队列")
        fmt.Println("3. 输入show表示添加数据到队列")
        fmt.Println("4. 输入exit表示添加数据到队列")

        fmt.Scan(&key)
        switch key {
        case "add":
            fmt.Println("输入你要入队的数")
            fmt.Scan(&val)
            err := queue.Push(val)
            if err == nil{
                fmt.Println("加入队列OK")
            }else{
                fmt.Println(err.Error())
            }
        case "get":
            val,err := queue.Pop()
            if err != nil{
                fmt.Println(err.Error())
            }else{
                fmt.Println("从队列中取出一个数",val)
            }
        case "show":
            queue.Show()
            fmt.Println()
        case "exit":
            os.Exit(0)
        }
    }
}

链表

image.png

package main

import "fmt"

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


func main(){
    //创建一个头节点
    head := &HeroNode{}

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

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

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

    //加入
    InsertNode2(head,hero1)
    InsertNode2(head,hero3)
    InsertNode2(head,hero2)

    ListHeroNode(head)

    fmt.Println()
    //删除
    DelHeroNode(head,2)

    ListHeroNode(head)
}

//尾插入
func InsertNode(head *HeroNode,newHeroNode *HeroNode){
    //先找到该联邦的最后这个结点
    //创建一个辅助结点
    temp := head
    for{
        if temp.next == nil{
            //表示找到最后
            break
        }
        temp = temp.next
    }
    //将newHeroNode加入到链表的最后
    temp.next = newHeroNode
}

//根据编号从小到大插入
func InsertNode2(head *HeroNode,newHeroNode *HeroNode){
    //先找到该联邦的最后这个结点
    //创建一个辅助结点
    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{
            //说明链表中有了相同no，就不插入
            flag = false
            break
        }
        temp = temp.next
    }
    if !flag{
        fmt.Println("对不起，已经存在no=",newHeroNode.no)
        return
    }else{
        newHeroNode.next = temp.next
        temp.next = newHeroNode
    }
}


//显示链表所有节点信息
func ListHeroNode(head *HeroNode){
    temp := head

    //判断该链表是否为空
    if temp == 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 DelHeroNode(head *HeroNode,id int){
    temp := head
    flag := false

    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不存在")
    }
}

双向链表

image.png

package main

import "fmt"

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

func main() {
    //创建一个头节点
    head := &HeroNode{}

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

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

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

    //加入
    InsertNode(head, hero1)
    InsertNode(head, hero2)
    InsertNode(head, hero3)

    ListHeroNode(head)
    fmt.Println()
    ListHeroNode2(head)


    //删除
    //DelHeroNode(head, 2)
    //
    //ListHeroNode(head)
}

//尾插入
func InsertNode(head *HeroNode, newHeroNode *HeroNode) {
    //先找到该联邦的最后这个结点
    //创建一个辅助结点
    temp := head
    for {
        if temp.next == nil {
            //表示找到最后
            break
        }
        temp = temp.next
    }
    //将newHeroNode加入到链表的最后
    temp.next = newHeroNode
    newHeroNode.pre = temp
}

//根据编号从小到大插入
func InsertNode2(head *HeroNode, newHeroNode *HeroNode) {
    //先找到该联邦的最后这个结点
    //创建一个辅助结点
    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 {
            //说明链表中有了相同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 ListHeroNode(head *HeroNode) {
    temp := head

    //判断该链表是否为空
    if temp == 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) {
    temp := head

    //判断该链表是否为空
    if temp == nil {
        fmt.Println("空空如也")
        return
    }
    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 DelHeroNode(head *HeroNode, id int) {
    temp := head
    flag := false

    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不存在")
    }
}

环形链表

image.png

package main

import "fmt"

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

func main() {
    //环形链表头结点
    head := &CatNode{}

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

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

    cat3 := &CatNode{
        no: 3,
        name: "tom3",
    }

    InsertCatNode(head,cat1)
    InsertCatNode(head,cat2)
    InsertCatNode(head,cat3)

    ListCircleLink(head)
    head = DelCatNode(head,1)
    ListCircleLink(head)
}

func InsertCatNode(head *CatNode,newCatNode *CatNode){
    //判断是否添加第一只猫
    if head.next == nil{
        head.no = newCatNode.no
        head.name = newCatNode.name
        head.next = head    //形成环形
        fmt.Println(newCatNode,"加入到环形链表")
        return
    }

    //定义一个临时变量，帮忙找到环形最后的结点
    temp := head
    for{
        if temp.next == head{
            break
        }
        temp = temp.next
    }

    temp.next = newCatNode
    newCatNode.next = head

}

//输出环形链表
func ListCircleLink(head *CatNode){
    fmt.Println("环形链表情况如下：")
    temp := head

    if temp.next == nil{
        fmt.Println("空空如也的环形链表。。。")
        return
    }
    for{
        fmt.Printf("猫的信息为=[id=%d,name=%s]->\n",temp.no,temp.name)
        if temp.next == head{
            break
        }
        temp = temp.next
    }
}

//删除一只猫
func DelCatNode(head *CatNode,id int)*CatNode{
    temp := head
    helper := head
    if head.next == nil{
        fmt.Println("这是一个空的环形链表，无法删除。。。")
        return head
    }

    //只有一个结点
    if temp.next == head{
        temp.next = nil
        return head
    }

    //将helper定位到最后一个结点
    for{
        if helper.next == head{
            break
        }
        helper = helper.next
    }

    //多个结点
    flag := true
    for{
        if temp.next == head{
            break
        }else if temp.no == id{
            if temp == head{
                //说明删除的是头结点
                head = head.next
            }
            helper.next = temp.next
            fmt.Printf("猫=%d\n",id)
            flag = false
            break
        }
        temp= temp.next //移动比较
        helper = helper.next    //找到结点，删除。
    }
    //比较最后一个
    if flag{    //如果flag为真，for中没有删除
        if temp.no == id{
            helper.next = temp.next
            fmt.Printf("猫=%d\n",id)
        }else{
            fmt.Printf("sorry,没有no=%d\n",id)
        }
    }
    return head
}

作业

image.png

package main

import "fmt"

//小孩的结构体
type  Boy struct {
    No int
    Next *Boy
}
//编写一个函数，构成单向的循环链表
//num 表示小孩的个数
//返回第一个小孩的指针。
func AddBoy(num int)*Boy{
    first := &Boy{} //空节点
    curBoy := &Boy{}    //空节点
    //判断
    if num < 1{
        fmt.Println("num的值不对")
        return first
    }
    //循环的构建环形链表
    for i := 1;i <= num;i++{
        boy := &Boy{
            No: i,
        }
        //分析构成循环链表，需要一个辅助指针。
        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.No)
        if curBoy.Next == first{
            break
        }
        curBoy = curBoy.Next
    }
}

//1、编写一个函数，PlayGame(first *Boy,startNo int,CountNo int)
//2、最后使用一个算法，在环形链表中留下最后一个人。
func PlayGame(first *Boy,startNo int,CountNo int){

    //空链表，单独处理
    if first.Next == nil{
        fmt.Println("空的链表，没有小孩")
    }
    //判断startNo <= 小孩的总数

    //需要定义辅助指针，帮助删除小孩
    tail := first
    //让tail指向环形链表的最后一个小孩。
    for{
        if tail.Next == first{
            //说明到了最后一个小孩
            break
        }
        tail = tail.Next
    }

    //让first移动到startNo[后面删除小孩，以first为准]
    for i:= 1;i <= startNo - 1;i++{
        first = first.Next
        tail = tail.Next
    }
    fmt.Println()
    //开始数countNum下，然后删除first指向的小孩
    for{
        //开始数countNum - 1次
        for i:= 1;i<=CountNo-1;i++{
            first = first.Next
            tail = tail.Next
        }
        fmt.Printf("小孩编号为%d出圈\n",first.No)
        //删除first
        first = first.Next
        tail.Next = first
        //判断如果 tail == first,圈子中只有一个小孩
        if tail == first{
            break
        }
    }
    fmt.Printf("最后出圈的小孩编号为%d出圈\n",first.No)
}

func main(){
    first := AddBoy(10)
    ShowBoy(first)
    PlayGame(first,2,3)
}

选择排序

image.png

package main

import "fmt"

func Select(arr *[5]int){
    for i := 0;i < len(arr)-1;i++{
        min := i
        for j := i+1;j < len(arr);j++{
            if arr[min] > arr[j]{
                min = j
            }
        }
        if min != i{
            arr[min],arr[i] = arr[i],arr[min]
        }
    }
}
func main(){
    arr := [5]int{10,34,19,100,80}
    Select(&arr)
    fmt.Println(arr)
}

插入排序

image.png

func insert(arr *[5]int){
    for i := 1;i < len(arr);i++{
        tmp := arr[i]
        j := i-1
        for ;j >= 0 && tmp < arr[j];j--{
            arr[j+1] = arr[j]
        }
        if j+1 != i{
            arr[j+1] = tmp
        }
    }
}

快速排序

image.png

func quick(left int,right int,array *[5]int){
    l := left
    r := right
    pivot := array[(left+right)/2]

    for ;l<r;{
        for;array[l] < pivot;{
            l++
        }
        for;array[r] > pivot;{
            r--
        }
        if l >= r {
            break
        }
        array[l],array[r] = array[r],array[l]

        //优化
        if array[l] == pivot{
            r--
        }
        if array[r] == pivot{
            l++
        }
    }
    if l==r{
        l++
        r--
    }
    if left < r{
        quick(left,r,array)
    }
    if right > l{
        quick(l,right,array)
    }
}

栈

image.png

package main

import (
    "errors"
    "fmt"
)

//使用数组模拟一个栈的使用
type Stack struct {
    MaxTop int  //表示栈的最大可以存放数的个数
    Top int     //表示栈顶，
    arr [5]int  //数组模拟栈
}

func (s *Stack)Push(val int)(err error){
    //先判断栈是否满
    if s.Top == s.MaxTop -1 {
        fmt.Println("stack full")
        return errors.New("stack full")
    }

    s.Top++
    //放入数据
    s.arr[s.Top] = val
    return
}

//出栈
func (s *Stack)Pop()(val int,err error){
    //判断栈空
    if s.Top == -1{
        fmt.Println("stack empty")
        return 0,errors.New("stack empty")
    }

    //先取值，再减减
    val = s.arr[s.Top]
    s.Top--
    return val,nil
}

//遍历栈 需要从栈顶开始遍历
func (s *Stack)List(){
    //判断是否为空
    if s.Top == -1{
        fmt.Println("stack empty")
        return
    }

    fmt.Println("栈的情况如下")
    for i:=s.Top;i >= 0;i--{
        fmt.Printf("arr[%d]=%d\n",i,s.arr[i])
    }
}

func main(){
    stack := &Stack{
        MaxTop: 5,
        Top: -1,    //栈顶-1，表示栈空
    }

    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    stack.Push(4)
    stack.Push(5)

    stack.List()
    val,_ := stack.Pop()
    fmt.Println("出栈val= ",val)
    stack.List()
}

递归

image.png

package main

import "fmt"

func main(){
    //先创建一个二维数组，模拟迷宫
    //规则：
    //1.如果元素的值为1，就是墙
    //2.如果元素的值为0，没有走过的路径
    //3.如果元素的值为2，是一个通路。
    //4.如果元素的值为3，是走过的点，但是不通。
    var myMap [8][7]int

    //先把地图的最上和最小设置为1
    for i:=0;i < 7;i++{
        myMap[0][i] = 1
        myMap[7][i] = 1
    }

    for i:=0;i < 8;i++{
        myMap[i][0] = 1
        myMap[i][6] = 1
    }

    myMap[3][1] = 1
    myMap[3][2] = 1


    //输出地图
    for i:=0;i < 8;i++{
        for j := 0;j < 7;j++{
            fmt.Print(myMap[i][j]," ")
        }
        fmt.Println()
    }

    SetWay(&myMap,1,1)

    fmt.Println("探测完毕。。。")
    //完毕
    for i:=0;i < 8;i++{
        for j := 0;j < 7;j++{
            fmt.Print(myMap[i][j]," ")
        }
        fmt.Println()
    }
}

//编写一个函数，完成老鼠找路
//地图是同一个地图，因此使用指针
//i,j表示对地图的哪个点进行测试
func SetWay(myMap *[8][7]int,i int,j int)bool{
    //分析出什么情况下，找到出路
    //myMap[6][5] == 2
    if myMap[6][5] == 2{
        return true
    }else{
        //将继续找
        if myMap[i][j] == 0{
            //如果这个点可以探测

            //假设这个点是可以通的，但是需要探测 上下左右
            //换一个策略：下右上左。
            myMap[i][j] = 2
            if SetWay(myMap,i+1,j){
                return true
            }else if SetWay(myMap,i,j+1){
                return true
            }else if SetWay(myMap,i-1,j){
                return true
            }else if SetWay(myMap,i,j-1){
                return true
            }else{
                myMap[i][j] = 3
                return false
            }
        }else{
            //不能探测 为1，是墙
            return false
        }
    }
}

哈希表

image.png

package main

import (
    "fmt"
    "os"
)

//定义emp
type Emp struct {
    Id int
    Name string
    Next *Emp
}

func (e *Emp)ShowMe(){
    fmt.Printf("链表%d找到该雇员%d\n",e.Id%7,e.Id)
}

//定义EmpLink
//不带表头，第一个结点就存放雇员
type EmpLink struct {
    Head *Emp
}
//方法待定
//添加员工方法,保证添加时，编号从小到大
func (e *EmpLink)Insert(emp *Emp){

    cur := e.Head   //辅助指针
    var pre *Emp = nil  //辅助指针
    //如果当前的EmpLink是空链表
    if cur == nil{
        e.Head = emp
        return
    }
    //如果不是空链表,给emp找到对应的位置并插入
    //让cur和emp比较，让pre保持在cur之前。
    for{
        if cur != nil{
            //比较
            if cur.Id > emp.Id{
                break
            }
            pre = cur
            cur = cur.Next
        }else{
            break
        }
    }
    //退出时，是否将emp添加到最后还是插入
    pre.Next = emp
    emp.Next = cur
}

//显示当前链表信息
func (e *EmpLink)ShowLink(no int){
    if e.Head == nil{
        fmt.Printf("链表%d为空\n",no)
        return
    }

    //变量当前链表，并显示数据
    cur := e.Head   //辅助指针
    for{
        if cur != nil{
            fmt.Printf("链表%d雇员id = %d 名字= %s->",no,cur.Id,cur.Name)
            cur = cur.Next
        }else{
            break
        }
    }
    fmt.Println()
}

//根据ID查找对应雇员，如果没有返回空
func (e *EmpLink)FindById(id int)*Emp{
    cur := e.Head
    for{
        if cur != nil && cur.Id == id{
            return cur
        }
        if cur == nil{
            break
        }
        cur = cur.Next
    }
    return nil
}



//定义hashtable含有一个链表数组
type HashTable struct {
    LinkArr [7]EmpLink
}

//给HashTable编写Insert 雇员的方法
func (h *HashTable)Insert(emp *Emp){
    //使用散列函数，确定该雇员添加到哪个链表
    linkNo := h.HashFun(emp.Id)
    //使用对应的链表添加
    h.LinkArr[linkNo].Insert(emp)
}

//编写一个散列方法
func (h *HashTable)HashFun(id int)int{
    return id % 7   //得到一个值，链表的下标
}

//编写方法，显示hashtable的所有雇员
func (h *HashTable)ShowAll(){
    for i:=0;i < len(h.LinkArr);i++{
        h.LinkArr[i].ShowLink(i)
    }
}

//编写方法，完成查找
func (h *HashTable)FindById(id int)*Emp{
    linkNo := h.HashFun(id)
    return h.LinkArr[linkNo].FindById(id)
}

func main(){
    key := ""
    id := 0
    name := ""
    var hashtable HashTable
    for{
        fmt.Println("==========雇员系统菜单=========")
        fmt.Println("input 表示添加雇员")
        fmt.Println("show  表示显示雇员")
        fmt.Println("find  表示查找雇员")
        fmt.Println("exit  表示退出系统")
        fmt.Println("请输入你的选择")
        fmt.Scanln(&key)
        switch key {
        case "input":
            fmt.Println("输入雇员ID")
            fmt.Scanln(&id)
            fmt.Println("输入雇员name")
            fmt.Scanln(&name)
            emp := &Emp{
                Id: id,
                Name: name,
            }
            hashtable.Insert(emp)
        case "find":
            fmt.Println("请输入ID号：")
            fmt.Scanln(&id)
            emp := hashtable.FindById(id)
            if emp == nil{
                fmt.Printf("id = %d的雇员不存在\n",id)
            }else{
                emp.ShowMe()
            }
        case "show":
            hashtable.ShowAll()
        case "exit":
            os.Exit(2)
        default:
            fmt.Println("输入错误")
        }
    }
}

二叉树

image.png

package main

import "fmt"

type Hero struct {
    No int
    Name string
    Left *Hero
    Right *Hero
}

//前序遍历
func PreOrder(node *Hero){
    if node != nil{
        fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
        PreOrder(node.Left)
        PreOrder(node.Right)
    }
}

//中序遍历
func InfixOrder(node *Hero){
    if node != nil{
        PreOrder(node.Left)
        fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
        PreOrder(node.Right)
    }
}

//后序遍历
func PostOrder(node *Hero){
    if node != nil{
        PreOrder(node.Left)
        PreOrder(node.Right)
        fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
    }
}

func main(){
    //构建一个二叉树
    root := &Hero{
        No: 1,
        Name: "宋江",
    }

    left1 := &Hero{
        No: 2,
        Name: "吴用",
    }

    right1 := &Hero{
        No: 3,
        Name: "卢俊义",
    }
    root.Left = left1
    root.Right = right1

    right2 := &Hero{
        No: 4,
        Name: "林冲",
    }
    right1.Right = right2

    PreOrder(root)
    InfixOrder(root)
    PostOrder(root)
}