數據結構數據結構(演算法)的介紹數據結構的介紹 1) 數據結構是一門研究演算法的學科，只從有了編程語言也就有了數據結構.學好數據結構可以編寫出更加漂亮,更加有效率的代碼。 2) 要學習好數據結構就要多多考慮如何將生活中遇到的問題,用程式去實現解決. 3) 程式 = 數據結構 + 演算法 20.2 數 ...

數據結構

數據結構(演算法)的介紹

數據結構的介紹

1) 數據結構是一門研究演算法的學科，只從有了編程語言也就有了數據結構.學好數據結構可以編寫
出更加漂亮,更加有效率的代碼。
2) 要學習好數據結構就要多多考慮如何將生活中遇到的問題,用程式去實現解決.
3) 程式 = 數據結構 + 演算法
20.2 數據結構和演算法的關係

演算法是程式的靈魂。

為什麼有些網站能夠在高併發，和海量吞吐情況下依然堅如磐石,大家可能會
說: 網站使用了伺服器群集技術、資料庫讀寫分離和緩存技術(比如 Redis 等),那如果我再深入的問
一句，這些優化技術又是怎樣被那些天才的技術高手設計出來的呢?
大家請思考一個問題，是什麼讓不同的人寫出的代碼從功能看是一樣的，但從效率上卻有天壤之別

曾經我聽有人是這麼說的：" 我是做伺服器的，環境是 UNIX，功能是要支持上千萬人同時線上，
並保證數據傳輸的穩定, 在伺服器上線前，做內測，一切 OK,可上線後，伺服器就支撐不住了, 公
司的 CTO 對我的代碼進行優化，再次上線，堅如磐石。那一瞬間,我認識到程式是有靈魂的，就是
演算法。拿在公司工作的實際經歷來說,如果你不想永遠都是代碼工人,那就花時間來研究下演算法吧!"

稀疏 sparsearray 數組

先看一個實際的需求

編寫的五子棋程式中，有存檔退出和續上盤的功能
分析按照原始的方式來的二維數組的問題因為該二維數組的很多值是預設值 0, 因此記錄了很多沒有意義的數據

基本介紹

當一個數組中大部分元素為０，或者為同一個值的數組時，可以使用稀疏數組來保存該數組。
稀疏數組的處理方法是:
1) 記錄數組一共有幾行幾列，有多少個不同的值
2) 思想：把具有不同值的元素的行列及值記錄在一個小規模的數組中，從而縮小程式的規模

應用實例

1) 使用稀疏數組，來保留類似前面的二維數組(棋盤、地圖等等)
2) 把稀疏數組存檔，並且可以從新恢複原來的二維數組數

package main
import (
    "fmt"
)

type ValNode struct {
    row int
    col int
    val int
} 

func main() {

    //1. 先創建一個原始數組
    var chessMap [11][11]int
    chessMap[1][2] = 1 //黑子
    chessMap[2][3] = 2 //藍子

    //2. 輸出看看原始的數組
    for _, v := range chessMap {
        for _, v2 := range v {
            fmt.Printf("%d\t", v2)
        }
        fmt.Println()
    } 

    //3. 轉成稀疏數組。想-> 演算法
    // 思路
    //(1). 遍歷 chessMap, 如果我們發現有一個元素的值不為0，創建一個node結構體
    //(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 := 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)
    }

    //將這個稀疏數組，存檔 d:/chessmap.data

    //如何恢複原始的數組

    //1. 打開這個d:/chessmap.data => 恢複原始數組.

    //2. 這裡使用稀疏數組恢復


    // 先創建一個原始數組
    var chessMap2 [11][11]int 

    // 遍歷 sparseArr [遍歷文件每一行]
    for i, valNode := range sparseArr {
        if i != 0 { //跳過第一行記錄值
            chessMap2[valNode.row][valNode.col] = valNode.val
        }
    }

    // 看看chessMap2 是不是恢復.
    fmt.Println("恢復後的原始數據......")
    for _, v := range chessMap2 {
        for _, v2 := range v {
            fmt.Printf("%d\t", v2)
        }
        fmt.Println()
    }
}

隊列(queue)

隊列介紹

隊列是一個有序列表，可以用數組或是鏈表來實現。
遵循先入先出的原則。即：先存入隊列的數據，要先取出。後存入的要後取出

數組模擬隊列

package main
import (
    "fmt"
    "os"
    "errors"
)

//使用一個結構體管理隊列
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")
    }

    this.rear++ //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])
    }
    fmt.Println()
}



//編寫一個主函數測試，測試
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.Scanln(&key)
        switch key {
            case "add":
                fmt.Println("輸入你要入隊列數")
                fmt.Scanln(&val)
                err := queue.AddQueue(val)
                if err != nil {
                    fmt.Println(err.Error())
                } else {

                    fmt.Println("加入隊列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)
        }
    }
}

數組模擬環形隊列

package main
import (
    "fmt"
    "errors"
    "os"
)

//使用一個結構體管理環形隊列
type CircleQueue struct {
    maxSize int // 4
    array [5]int // 數組
    head  int //指向隊列隊首 0
    tail int  //指向隊尾 0
}


//如隊列 AddQueue(push)  GetQueue(pop)
//入隊列
func (this *CircleQueue) Push(val int)  (err error) {
    if this.IsFull() {
        return errors.New("queue full")
    }
    //分析出this.tail 在隊列尾部，但是包含最後的元素
    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")
    }
    //取出,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
}


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.Scanln(&key)
        switch key {
            case "add":
                fmt.Println("輸入你要入隊列數")
                fmt.Scanln(&val)
                err := queue.Push(val)
                if err != nil {
                    fmt.Println(err.Error())
                } else {

                    fmt.Println("加入隊列ok")
                }
            case "get":
                val, err := queue.Pop()
                if err != nil {
                    fmt.Println(err.Error())
                } else {
                    fmt.Println("從隊列中取出了一個數=", val)
                }
            case "show":
                queue.ListQueue()
            case "exit":
                os.Exit(0)
        }
    }
}

鏈表

鏈表介紹

鏈表是有序的列表

單鏈表的介紹

一般來說，為了比較好的對單鏈表進行增刪改查的操作，我們都會給他設置一個頭結點, 頭
結點的作用主要是用來標識鏈表頭，本身這個結點不存放數據。

單鏈表的應用實例
案例的說明：

使用帶 head 頭的單向鏈表實現 –水滸英雄排行榜管理
完成對英雄人物的增刪改查操作

第一種方法在添加英雄時，直接添加到鏈表的尾部

package main
import (
    "fmt"
)

//定義一個HeroNode
type HeroNode struct {
    no       int
    name     string
    nickname string
    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
}

//給鏈表插入一個結點
//編寫第2種插入方法，根據no 的編號從小到大插入..【實用】
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 {
            //說明我們額鏈表中已經有這個no,就不然插入.
            flag = false
            break
        }
        temp = temp.next
    }

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


}
//刪除一個結點
func DelHerNode(head *HeroNode, id int) {
    temp := head
    flag := false
    //找到要刪除結點的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
    } else {
        fmt.Println("sorry, 要刪除的id不存在")
    }
}

//顯示鏈表的所有結點信息
func ListHeroNode(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 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 : "智多星",
    // }

    //3. 加入
    InsertHeroNode2(head, hero3)
    InsertHeroNode2(head, hero1)
    InsertHeroNode2(head, hero2)
    
    // 4. 顯示
    ListHeroNode(head)

    // 5 刪除
    fmt.Println()
    DelHerNode(head, 1)
    DelHerNode(head, 3)
    ListHeroNode(head)
}

雙向鏈表的應用實例

package main
import (
    "fmt"
)

//定義一個HeroNode
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
}

//給雙向鏈表插入一個結點
//編寫第2種插入方法，根據no 的編號從小到大插入..【實用】
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 {
            //說明我們額鏈表中已經有這個no,就不然插入.
            flag = false
            break
        }
        temp = temp.next
    }

    if !flag {
        fmt.Println("對不起，已經存在no=", newHeroNode.no)
        return
    } else {
        newHeroNode.next = temp.next //ok
        newHeroNode.pre = temp//ok
        if temp.next != nil {
            temp.next.pre = newHeroNode //ok
        }
        temp.next = newHeroNode //ok
    }


}
//刪除一個結點[雙向鏈表刪除一個結點]
func DelHerNode(head *HeroNode, id int) {
    temp := head
    flag := false
    //找到要刪除結點的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 //ok
        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 
    }
    //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 ListHeroNode2(head *HeroNode) {

    //1. 創建一個輔助結點[跑龍套, 幫忙]
    temp := head

    // 先判斷該鏈表是不是一個空的鏈表
    if temp.next == nil {
        fmt.Println("空空如也。。。。")
        return 
    }

    //2. 讓temp定位到雙向鏈表的最後結點
    for {
        if temp.next == nil {
            break
        }
        temp = temp.next
    }


    //2. 遍歷這個鏈表
    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 : "豹子頭",
    }

    
    InsertHeroNode(head, hero1)
    InsertHeroNode(head, hero2)
    InsertHeroNode(head, hero3)
    ListHeroNode(head)
    fmt.Println("逆序列印")
    ListHeroNode2(head)

}

單向環形鏈表的應用場景

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 //構成一個環形
        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 temp.next == nil {
        fmt.Println("這是一個空的環形鏈表，不能刪除")
        return head
    }
    
    //如果只有一個結點
    if temp.next == head { //只有一個結點
        if temp.no == id {
            temp.next = nil 
        }
        return head
    }

    //將helper 定位到鏈表最後
    for {
        if helper.next == head {
            break
        } 
        helper = helper.next
    }

    //如果有兩個包含兩個以上結點
    flag := true
    for {
        if temp.next == head { //如果到這來，說明我比較到最後一個【最後一個還沒比較】
            break 
        } 
        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 //移動 【一旦找到要刪除的結點 helper】
    }
    //這裡還有比較一次
    if flag { //如果flag 為真，則我們上面沒有刪除
        if temp.no == id {
            helper.next = temp.next
            fmt.Printf("貓貓=%d\n", id)
        }else {
            fmt.Printf("對不起，沒有no=%d\n", id)
        }
    } 
    return head
}

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, 30)

    fmt.Println()   
    fmt.Println()   
    fmt.Println()   
    ListCircleLink(head)

}

環形單向鏈表的應用實例

Josephu 問題

Josephu 問題為：設編號為 1，2，… n 的 n 個人圍坐一圈，約定編號為 k（1<=k<=n）的人從 1
開始報數，數到 m 的那個人出列，它的下一位又從 1 開始報數，數到 m 的那個人又出列，依次類推，
直到所有人出列為止，由此產生一個出隊編號的序列。

提示

用一個不帶頭結點的迴圈鏈表來處理 Josephu 問題：先構成一個有 n 個結點的單迴圈鏈表，然後
由 k 結點起從 1 開始計數，計到 m 時，對應結點從鏈表中刪除，然後再從被刪除結點的下一個結點又
從 1 開始計數，直到最後一個結點從鏈表中刪除演算法結束。
約瑟夫問題

package main
import (
    "fmt"
)


//小孩的結構體
type Boy struct {
    No int // 編號
    Next *Boy // 指向下一個小孩的指針[預設值是nil]
}

// 編寫一個函數，構成單向的環形鏈表
// num ：表示小孩的個數
// *Boy : 返回該環形的鏈表的第一個小孩的指針
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,
        }
        //分析構成迴圈鏈表，需要一個輔助指針[幫忙的]
        //1. 因為第一個小孩比較特殊
        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)
        //退出的條件?curBoy.Next == first
        if curBoy.Next == first {
            break
        }
        //curBoy移動到下一個
        curBoy = curBoy.Next
    }
}

/*
設編號為1，2，… n的n個人圍坐一圈，約定編號為k（1<=k<=n）
的人從1開始報數，數到m 的那個人出列，它的下一位又從1開始報數，
數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列
*/

//分析思路
//1. 編寫一個函數，PlayGame(first *Boy, startNo int, countNum int) 
//2. 最後我們使用一個演算法，按照要求，在環形鏈表中留下最後一個人
func PlayGame(first *Boy, startNo int, countNum int) {

    //1. 空的鏈表我們單獨的處理
    if first.Next == nil {
        fmt.Println("空的鏈表，沒有小孩")
        return
    }
    //留一個，判斷 startNO <= 小孩的總數
    //2. 需要定義輔助指針，幫助我們刪除小孩
    tail := first 
    //3. 讓tail執行環形鏈表的最後一個小孩,這個非常的重要
    //因為tail 在刪除小孩時需要使用到.
    for {
        if tail.Next == first { //說明tail到了最後的小孩
            break
        }
        tail = tail.Next
    }
    //4. 讓first 移動到 startNo [後面我們刪除小孩，就以first為準]
    for i := 1; i <= startNo - 1; i++ {
        first = first.Next
        tail = tail.Next
    } 
    fmt.Println()
    //5. 開始數 countNum, 然後就刪除first 指向的小孩
    for {
        //開始數countNum-1次
        for i := 1; i <= countNum -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(500)
    //顯示
    ShowBoy(first)
    PlayGame(first, 20, 31)

}

排序

排序的介紹

排序是將一組數據，依指定的順序進行排列的過程, 常見的排序：
1) 冒泡排序
2) 選擇排序
3) 插入排序
4) 快速排序

選擇排序基本介紹

選擇式排序也屬於內部排序法，是從欲排序的數據中，按指定的規則選出某一元素，經過和其他
元素重整，再依原則交換位置後達到排序的目的。

選擇排序思想:

選擇排序（select sorting）也是一種簡單的排序方法。它的基本思想是：第一次從 R[0]~R[n-1]中選
取最小值，與 R[0]交換，第二次從 R[1]~R[n-1]中選取最小值，與 R[1]交換，第三次從 R[2]~R[n-1]中選
取最小值，與 R[2]交換，…，第 i 次從 R[i-1]~R[n-1]中選取最小值，與 R[i-1]交換，…, 第 n-1 次從
R[n-2]~R[n-1]中選取最小值，與 R[n-2]交換，總共通過 n-1 次，得到一個按排序碼從小到大排列的有序
序列。

package main
import (
    "fmt"
    "math/rand"
    "time"
)

//編寫函數selectSort 完成排序

func SelectSort(arr *[80000]int) {

    //標準的訪問方式
    //(*arr)[1] = 600 等價於 arr[1] = 900
    //arr[1] = 900
    //1. 先完成將第一個最大值和 arr[0] => 先易後難

    //1 假設  arr[0] 最大值

    for j := 0; j < len(arr) - 1; j++ {

        max := arr[j]
        maxIndex := j
        //2. 遍歷後面 1---[len(arr) -1] 比較
        for i := j + 1; i < len(arr); i++ {
            if max < arr[i] { //找到真正的最大值
                max = arr[i]
                maxIndex = i
            }
        }
        //交換
        if maxIndex != j {
            arr[j], arr[maxIndex] = arr[maxIndex], arr[j]
        }

        //fmt.Printf("第%d次 %v\n  ", j+1 ,*arr)
    }
    

    /*
    max = arr[1]
    maxIndex = 1
    //2. 遍歷後面 2---[len(arr) -1] 比較
    for i := 1 + 1; i < len(arr); i++ {
        if max < arr[i] { //找到真正的最大值
            max = arr[i]
            maxIndex = i
        }
    }
    //交換
    if maxIndex != 1 {
        arr[1], arr[maxIndex] = arr[maxIndex], arr[1]
    }

    fmt.Println("第2次 ", *arr)

    

    max = arr[2]
    maxIndex = 2
    //2. 遍歷後面 3---[len(arr) -1] 比較
    for i := 2 + 1; i < len(arr); i++ {
        if max < arr[i] { //找到真正的最大值
            max = arr[i]
            maxIndex = i
        }
    }
    //交換
    if maxIndex != 2 {
        arr[2], arr[maxIndex] = arr[maxIndex], arr[2]
    }

    fmt.Println("第3次 ", *arr)

    max = arr[3]
    maxIndex = 3
    //2. 遍歷後面 4---[len(arr) -1] 比較
    for i := 3 + 1; i < len(arr); i++ {
        if max < arr[i] { //找到真正的最大值
            max = arr[i]
            maxIndex = i
        }
    }
    //交換
    if maxIndex != 3 {
        arr[3], arr[maxIndex] = arr[maxIndex], arr[3]
    }

    fmt.Println("第4次 ", *arr)*/
}

func main() {
    //定義一個數組 , 從大到小
    //arr := [6]int{10, 34, 19, 100, 80, 789}

    var arr [80000]int
    for i := 0; i < 80000; i++ {
        arr[i] = rand.Intn(900000)
    }

    //fmt.Println(arr)
    start := time.Now().Unix()
    SelectSort(&arr)
    end := time.Now().Unix()
    fmt.Printf("選擇排序耗時=%d秒", end - start)
    fmt.Println("main函數")
    //fmt.Println(arr)
}

插入排序法介紹:

插入式排序屬於內部排序法，是對於欲排序的元素以插入的方式找尋該元素的適當位置，以達到
排序的目的。

插入排序法思想:

插入排序（Insertion Sorting）的基本思想是：把 n 個待排序的元素看成為一個有序表和一個無序表，
開始時有序表中只包含一個元素，無序表中包含有 n-1 個元素，排序過程中每次從無序表中取出第一個
元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成
為新的有序表。

package main
import (
    "fmt"
    "math/rand"
    "time"
)

func InsertSort(arr *[80000]int) {

    //完成第一次，給第二個元素找到合適的位置並插入

    for i := 1; i < len(arr); i++ {

        insertVal := arr[i]
        insertIndex := i - 1 // 下標

        //從大到小
        for insertIndex >= 0 && arr[insertIndex] < insertVal {
            arr[insertIndex + 1] = arr[insertIndex] // 數據後移
            insertIndex-- 
        }
        //插入
        if insertIndex + 1 != i {
            arr[insertIndex + 1] = insertVal
        }
        //fmt.Printf("第%d次插入後 %v\n",i, *arr)
    }
    

    /*

    //完成第2次，給第3個元素找到合適的位置並插入
    insertVal = arr[2]
    insertIndex = 2 - 1 // 下標

    //從大到小
    for insertIndex >= 0 && arr[insertIndex] < insertVal {
        arr[insertIndex + 1] = arr[insertIndex] // 數據後移
        insertIndex-- 
    }
    //插入
    if insertIndex + 1 != 2 {
        arr[insertIndex + 1] = insertVal
    }
    fmt.Println("第2次插入後", *arr)

    //完成第3次，給第4個元素找到合適的位置並插入
    insertVal = arr[3]
    insertIndex = 3 - 1 // 下標

    //從大到小
    for insertIndex >= 0 && arr[insertIndex] < insertVal {
        arr[insertIndex + 1] = arr[insertIndex] // 數據後移
        insertIndex-- 
    }
    //插入
    if insertIndex + 1 != 3 {
        arr[insertIndex + 1] = insertVal
    }
    fmt.Println("第3次插入後", *arr)

    //完成第4次，給第5個元素找到合適的位置並插入
    insertVal = arr[4]
    insertIndex = 4 - 1 // 下標

    //從大到小
    for insertIndex >= 0 && arr[insertIndex] < insertVal {
        arr[insertIndex + 1] = arr[insertIndex] // 數據後移
        insertIndex-- 
    }
    //插入
    if insertIndex + 1 != 4 {
        arr[insertIndex + 1] = insertVal
    }
    fmt.Println("第4次插入後", *arr)*/
}
    

func main() {

    

    //arr := [7]int{23, 0, 12, 56,  34, -1, 55}

    var arr [80000]int
    for i := 0; i < 80000; i++ {
        arr[i] = rand.Intn(900000)
    }

    //fmt.Println(arr)
    start := time.Now().Unix()
    //fmt.Println("原始數組=", arr)
    InsertSort(&arr)
    end := time.Now().Unix()

    fmt.Println("main 函數")
    fmt.Printf("插入排序耗時%d秒", end-start)
    //fmt.Println(arr)
}

快速排序法介紹

快速排序（Quicksort）是對冒泡排序的一種改進。基本思想是：通過一趟排序將要排序的數據分
割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這
兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列

package main
import (
    "fmt"
    "math/rand"
    "time"
)

//快速排序
//說明
//1. left 表示 數組左邊的下標
//2. right 表示數組右邊的下標
//3  array 表示要排序的數組
func QuickSort(left int, right int, array *[8000000]int) {
    l := left
    r := right
    // pivot 是中軸， 支點
    pivot := array[(left + right) / 2]
    temp := 0

    //for 迴圈的目標是將比 pivot 小的數放到 左邊
    //  比 pivot 大的數放到 右邊
    for ; l < r; {
        //從  pivot 的左邊找到大於等於pivot的值
        for ; array[l] < pivot; {
            l++
        }
        //從  pivot 的右邊邊找到小於等於pivot的值
        for ; array[r] > pivot; {
            r--
        }
        // 1 >= r 表明本次分解任務完成, break
        if l >= r { 
            break
        }
        //交換
        temp = array[l]
        array[l] = array[r]
        array[r] = temp
        //優化
        if array[l]== pivot  {
            r--
        }
        if array[r]== pivot {
            l++         
        }
    }
    // 如果  1== r, 再移動下
    if l == r {
         l++
         r--
    }
    // 向左遞歸
    if left < r {
        QuickSort(left, r, array)
    }
    // 向右遞歸
    if right > l {
        QuickSort(l, right, array)
    }
}


func main() {

    // arr := [9]int {-9,78,0,23,-567,70, 123, 90, -23}
    // fmt.Println("初始", arr)

    var arr [8000000]int
    for i := 0; i < 8000000; i++ {
        arr[i] = rand.Intn(900000)
    }

    //fmt.Println(arr)
    start := time.Now().Unix()
    //調用快速排序
    QuickSort(0, len(arr) - 1, &arr)
    end := time.Now().Unix()
    fmt.Println("main..")
    fmt.Printf("快速排序法耗時%d秒", end - start)
    //fmt.Println(arr)

}

三種排序方法的速度的分析(上面代碼中已寫入)

棧

package main
import (
    "fmt"
)

func test(n int) {
    if n > 2 {
        n-- // æ»é¾Ÿ
        test(n)
    } else {
        fmt.Println("n=", n)
    }
    
}

func main() {

    n := 4
    test(n)
}

棧的介紹

有些程式員也把棧稱為堆棧, 即棧和堆棧是同一個概念

1) 棧的英文為(stack)
2) 棧是一個先入後出(FILO-First In Last Out)的有序列表。
3) 棧(stack)是限制線性表中元素的插入和刪除只能線上性表的同一端進行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。
4) 根據堆棧的定義可知，最先放入棧中元素在棧底，最後放入的元素在棧頂，而刪除元素剛好相
反，最後放入的元素最先刪除，最先放入的元素最後刪除

棧的應用場景

1) 子程式的調用：在跳往子程式前，會先將下個指令的地址存到堆棧中，直到子程式執行完後再
將地址取出，以回到原來的程式中。
2) 處理遞歸調用：和子程式的調用類似，只是除了儲存下一個指令的地址外，也將參數、區域變
量等數據存入堆棧中。
3) 表達式的轉換與求值。
4) 二叉樹的遍歷。
5) 圖形的深度優先(depth 一 first)搜索法

package main
import (
    "fmt"
    "errors"
)

//使用數組來模擬一個棧的使用
type Stack struct {
    MaxTop int  // 表示我們棧最大可以存放數個數
    Top int // 表示棧頂, 因為棧頂固定，因此我們直接使用Top
    arr [5]int // 數組模擬棧
}
//入棧
func (this *Stack) Push(val int) (err error) {

    //先判斷棧是否滿了
    if this.Top == this.MaxTop - 1 {
        fmt.Println("stack full")
        return errors.New("stack full")
    }
    this.Top++ 
    //放入數據
    this.arr[this.Top] = val
    return 
}

//出棧
func (this *Stack) Pop() (val int, err error) {
    //判斷棧是否空
    if this.Top == -1 {
        fmt.Println("stack empty!")
        return 0, errors.New("stack empty")
    } 

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

}
//遍歷棧，註意需要從棧頂開始遍歷
func (this *Stack) List() {
    //先判斷棧是否為空
    if this.Top == -1 {
        fmt.Println("stack empty")
        return 
    }
    fmt.Println("棧的情況如下：")
    for i := this.Top; i >= 0; i-- {
        fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
    }

}

func main() {

    stack := &Stack{
        MaxTop : 5, // 表示最多存放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) // 5
    //顯示
    stack.List() // 

    fmt.Println()
    val, _ = stack.Pop()
    val, _ = stack.Pop()
    val, _ = stack.Pop()
    val, _ = stack.Pop()
    val, _ = stack.Pop()// 出錯
    fmt.Println("出棧val=", val) // 5
    //顯示
    stack.List() // 
}

棧實現計算表達式

package main
import (
    "fmt"
    "errors"
    "strconv"
)

//使用數組來模擬一個棧的使用
type Stack struct {
    MaxTop int  // 表示我們棧最大可以存放數個數
    Top int // 表示棧頂, 因為棧頂固定，因此我們直接使用Top
    arr [20]int // 數組模擬棧
}
//入棧
func (this *Stack) Push(val int) (err error) {

    //先判斷棧是否滿了
    if this.Top == this.MaxTop - 1 {
        fmt.Println("stack full")
        return errors.New("stack full")
    }
    this.Top++ 
    //放入數據
    this.arr[this.Top] = val
    return 
}

//出棧
func (this *Stack) Pop() (val int, err error) {
    //判斷棧是否空
    if this.Top == -1 {
        fmt.Println("stack empty!")
        return 0, errors.New("stack empty")
    } 

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

}
//遍歷棧，註意需要從棧頂開始遍歷
func (this *Stack) List() {
    //先判斷棧是否為空
    if this.Top == -1 {
        fmt.Println("stack empty")
        return 
    }
    fmt.Println("棧的情況如下：")
    for i := this.Top; i >= 0; i-- {
        fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
    }

}
//判斷一個字元是不是一個運算符[+, - , * , /]
func (this *Stack) IsOper(val int) bool {

    if val == 42 || val == 43 || val == 45 || val == 47 {
        return true
    } else {
        return false
    }
}

//運算的方法
func (this *Stack) Cal(num1 int, num2 int, oper int) int{
    res := 0
    switch oper {
        case 42 :
            res = num2 * num1
        case 43 :
            res = num2 + num1
        case 45 :
            res = num2 - num1
        case 47 :
            res = num2 / num1
        default :
            fmt.Println("運算符錯誤.")
    }
    return res
}

//編寫一個方法，返回某個運算符的優先順序[程式員定義]
//[* / => 1 + - => 0]
func (this *Stack) Priority(oper int) int {
    res := 0
    if oper == 42 || oper == 47 {
        res = 1
    } else if oper == 43 || oper == 45 {
        res = 0
    } 
    return res
} 

func main() {

    //數棧
    numStack := &Stack{
        MaxTop : 20,
        Top : -1,
    }
    //符號棧
    operStack := &Stack{
        MaxTop : 20,
        Top : -1,
    }

    exp := "30+30*6-4-6"
    //定義一個index ，幫助掃描exp
    index := 0
    //為了配合運算，我們定義需要的變數
    num1 := 0
    num2 := 0
    oper := 0
    result := 0
    keepNum := "" 

    for {
        //這裡我們需要增加一個邏輯，
        //處理多位數的問題
        ch := exp[index:index+1] // 字元串.
        //ch ==>"+" ===> 43
        temp := int([]byte(ch)[0]) // 就是字元對應的ASCiI碼
        if operStack.IsOper(temp) { // 說明是符號

            //如果operStack  是一個空棧， 直接入棧
            if operStack.Top == -1 { //空棧
                operStack.Push(temp)
            }else {
                //如果發現opertStack棧頂的運算符的優先順序大於等於當前準備入棧的運算符的優先順序
                //，就從符號棧pop出，並從數棧也pop 兩個數，進行運算，運算後的結果再重新入棧
                //到數棧， 當前符號再入符號棧
                if operStack.Priority(operStack.arr[operStack.Top]) >= 
                    operStack.Priority(temp) {
                        num1, _ = numStack.Pop()
                        num2, _ = numStack.Pop()
                        oper, _ = operStack.Pop()
                        result = operStack.Cal(num1,num2, oper)
                        //將計算結果重新入數棧
                        numStack.Push(result)
                        //當前的符號壓入符號棧
                        operStack.Push(temp)

                }else {
                    operStack.Push(temp)
                }

            }


        } else { //說明是數
            
            //處理多位數的思路
            //1.定義一個變數 keepNum string, 做拼接
            keepNum += ch 
            //2.每次要向index的後面字元測試一下，看看是不是運算符，然後處理
            //如果已經到表達最後，直接將 keepNum
            if index == len(exp) - 1 { 
                val, _ := strconv.ParseInt(keepNum, 10, 64)
                numStack.Push(int(val))
            } else {
                //向index 後面測試看看是不是運算符 [index]
                if operStack.IsOper(int([]byte(exp[index+1:index+2])[0])) {
                    val, _ := strconv.ParseInt(keepNum, 10, 64)
                    numStack.Push(int(val))
                    keepNum = ""
                }
            }
        }

        //繼續掃描
        //先判斷index是否已經掃描到計算表達式的最後
        if index + 1 == len(exp) {
            break
        }
        index++

    }

    //如果掃描表達式 完畢，依次從符號棧取出符號，然後從數棧取出兩個數，
    //運算後的結果，入數棧，直到符號棧為空
    for {
        if operStack.Top == -1 {
            break //退出條件
        }
        num1, _ = numStack.Pop()
        num2, _ = numStack.Pop()
        oper, _ = operStack.Pop()
        result = operStack.Cal(num1,num2, oper)
        //將計算結果重新入數棧
        numStack.Push(result)
        
    }

    //如果我們的演算法沒有問題，表達式也是正確的，則結果就是numStack最後數
    res, _ := numStack.Pop()
    fmt.Printf("表達式%s = %v", exp, res)
}

遞歸

遞歸的一個應用場景[迷宮問題]

遞歸的概念

簡單的說: 第歸就是函數/方法自己調用自己,每次調用時傳入不同的變數.第歸有助於編程者解決
複雜的問題,同時可以讓代碼變得簡潔。

遞歸用於解決什麼樣的問題

1）各種數學問題如: 8 皇後問題 , 漢諾塔, 階乘問題, 迷宮問題, 球和籃子的問題(google 編程大
賽)
2）將用棧解決的問題-->第歸代碼比較簡潔

遞歸需要遵守的重要原則

1) 執行一個函數時，就創建一個新的受保護的獨立空間(新函數棧)
2) 函數的局部變數是獨立的，不會相互影響, 如果希望各個函數棧使用同一個數據，使用引用傳遞
3) 遞歸必須向退出遞歸的條件逼近【程式員自己必須分析】，否則就是無限遞歸，死龜了:)
4) 當一個函數執行完畢，或者遇到 return，就會返回，遵守誰調用，就將結果返回給誰，同時當函數執行完畢或者返回時，該函數本身也會被系統銷毀

package main
import (
    "fmt"
)

//編寫一個函數，完成老鼠找路
//myMap *[8][7]int:地圖，保證是同一個地圖，使用引用
//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
        }

    }
}

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
    }

    //先把地圖的最左和最右設置為1
    for i := 0 ; i < 8 ; i++ {
        myMap[i][0] = 1
        myMap[i][6] = 1
    }

    myMap[3][1] = 1
    myMap[3][2] = 1
    // ?myMap[1][2] = 1
    // ?myMap[2][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()
    }

}

哈希表(散列)

實際的需求

google 公司的一個上機題:

有一個公司,當有新的員工來報道時,要求將該員工的信息加入(id,性別,年齡,住址..),當輸入該員工
的 id 時,要求查找到該員工的所有信息.
要求: 不使用資料庫,儘量節省記憶體,速度越快越好=>哈希表(散列)

哈希表的基本介紹

散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也
就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做
散列函數，存放記錄的數組叫做散列表。

使用 hashtable 來實現一個雇員的管理系統[增刪改查]

應用實例 google 公司的一個上機題:

有一個公司,當有新的員工來報道時,要求將該員工的信息加入(id,性別,年齡,住址..),當輸入該員工
的 id 時,要求查找到該員工的所有信息.

要求:

1) 不使用資料庫,儘量節省記憶體, 速度越快越好=>哈希表(散列)
2) 添加時，保證按照雇員的 id 從低到高插入
3)
思路分析

1) 使用鏈表來實現哈希表, 該鏈表不帶表頭
[即: 鏈表的第一個結點就存放雇員信息

package main
import (
    "fmt"
    "os"
)

//定義emp
type Emp struct {
    Id int
    Name string
    Next *Emp
}
//方法待定..
func (this *Emp) ShowMe() {
    fmt.Printf("鏈表%d 找到該雇員 %d\n", this.Id % 7, this.Id)
}

//定義EmpLink
//我們這裡的EmpLink 不帶表頭,即第一個結點就存放雇員
type EmpLink struct {
    Head *Emp 
}
//方法待定..
//1. 添加員工的方法, 保證添加時，編號從小到大
func (this *EmpLink) Insert(emp *Emp) {

    cur := this.Head // 這是輔助指針
    var pre *Emp = nil // 這是一個輔助指針 pre 在cur前面
    //如果當前的EmpLink就是一個空鏈表
    if cur == nil {
        this.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 (this *EmpLink) ShowLink(no int) {
    if this.Head == nil {
        fmt.Printf("鏈表%d 為空\n", no)
        return 
    }

    //變數當前的鏈表，並顯示數據
    cur := this.Head // 輔助的指針
    for {
        if cur != nil {
            fmt.Printf("鏈表%d 雇員id=%d 名字=%s ->", no, cur.Id, cur.Name)
            cur = cur.Next
        } else {
            break
        }
    }
    fmt.Println() //換行處理
}

//根據id查找對應的雇員，如果沒有就返回nil
func (this *EmpLink) FindById(id int)  *Emp {
    cur := this.Head
    for {
        if cur != nil && cur.Id == id {
            return cur
        } else if cur == nil {
            break
        }
        cur = cur.Next
    }
    return nil
}

//定義hashtable ,含有一個鏈表數組
type HashTable struct {
    LinkArr [7]EmpLink
}

//給HashTable 編寫Insert 雇員的方法.
func (this *HashTable) Insert(emp *Emp) {
    //使用散列函數，確定將該雇員添加到哪個鏈表
    linkNo := this.HashFun(emp.Id)
    //使用對應的鏈表添加
    this.LinkArr[linkNo].Insert(emp) //
}

//編寫方法，顯示hashtable的所有雇員
func (this *HashTable) ShowAll() {
    for i := 0; i < len(this.LinkArr); i++ {
        this.LinkArr[i].ShowLink(i)
    }
}

//編寫一個散列方法
func (this *HashTable) HashFun(id int) int {
    return id % 7 //得到一個值，就是對於的鏈表的下標
}
//編寫一個方法，完成查找
func (this *HashTable) FindById(id int) *Emp {
    //使用散列函數，確定將該雇員應該在哪個鏈表
    linkNo := this.HashFun(id)
    return this.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 "show":
                hashtable.ShowAll()
            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 "exit":
                os.Exit(0)
            default :
                fmt.Println("輸入錯誤")
        }
    }

}

go-數據結構