GoLang 数据结构-哈希表(散列表)

哈希表

 

                                           图片来自百度百科

案例操作(案例操作的存储方式为:输入的ID编号%7)

package main

import (
    "fmt"
    "os"
)

//Cat 流浪猫结构体
type Cat struct {
    ID   int
    Name string
    Age  int

    Next *Cat
}

//ShowMe 显示猫咪自己的信息
func (c *Cat) ShowMe() {
    fmt.Printf("流浪猫链表:%v 找到了猫咪ID: %v  名称:%v
", c.ID%7, c.ID, c.Name)
}

/*
CatLink 猫咪链表结构体

head *Cat 头部指向猫咪
不带表头,第一个节点就开始存放猫咪
*/
type CatLink struct {
    head *Cat
}

//FindEmpByID CatLink的根据id查找猫咪
func (ctl *CatLink) FindEmpByID(id int) *Cat {
    current := ctl.head
    for {
        if current != nil && current.ID == id {
            //找到
            return current
        } else if current == nil {
            break
        }
        //继续往下找
        current = current.Next
    }
    return nil
}

//ShowLinks 显示所有流浪猫的详情信息
func (ctl *CatLink) ShowLinks(id int) {
    if ctl.head == nil {
        fmt.Printf("流浪猫链表 %v 为空...", id)
    }
    //不为空
    current := ctl.head
    for {
        if current != nil {
            fmt.Printf("流浪猫链表[%v] 猫咪ID:%v	名字:%v
", id, current.ID, current.Name)
            current = current.Next
        } else {
            break
        }
    }
    fmt.Println()
}

//Insert CatLink插入方法
func (ctl *CatLink) Insert(cat *Cat) {
    current := ctl.head //辅助指针
    var pre *Cat = nil  //辅助指针,指向current前面
    //如果当前CatLink是一个空链表
    if current == nil {
        ctl.head = cat
        return
    }
    /*
        如果不是空链表,就给cat找到对应的位置并插入数据
        思路:
        让current 与 cat 比较,然后让pre 保持在current前面
    */
    for {
        if current != nil {
            if current.ID > cat.ID {
                break
            }
            //保证同步
            pre = current
            current = current.Next
        } else {
            break
        }
    }
    //退出时,将emp添加到链表最后
    pre.Next = cat
    cat.Next = current
}

/*
HashTable 哈希表

LinkList [10]CatLink 代表含有10个链表数据
*/
type HashTable struct {
    LinkList [10]CatLink
}

//Insert 添加猫咪
func (ht *HashTable) Insert(cat *Cat) {
    linkNo := ht.HashFunc(cat.ID)
    ht.LinkList[linkNo].Insert(cat)

}

/*HashFunc 哈希散列方法 */
func (ht *HashTable) HashFunc(id int) int {
    /*
        这个值就代表链表的下标,
        根据输入的ID值 %7 =几 就分配到第几个ID的链表
    */
    return id % 7
}

//PrintAll 输出所有流浪猫
func (ht *HashTable) PrintAll() {
    for i := 0; i < len(ht.LinkList); i++ {
        ht.LinkList[i].ShowLinks(i)
    }
}

//FindCatByID 根据id查找猫咪
func (ht *HashTable) FindCatByID(id int) *Cat {
    linkNo := ht.HashFunc(id)
    return ht.LinkList[linkNo].FindEmpByID(id)
}
func main() {
    var key int
    var id int
    var name string
    var age int
    // var sex string
    // var color string
    // var Cattype string
    var ht HashTable
    for {
        fmt.Println("			(>^ω^<) 社区流浪猫信息管理系统 (>^ω^<)喵")
        fmt.Println(
            `
            1        添加流浪猫
            2.        显示流浪猫
            3.        查找流浪猫
            4.        退出系统
            请输入(1-4)
        `)
        fmt.Scanln(&key)
        switch key {
        case 1:
            fmt.Println("请输入猫咪的  ID  ")
            fmt.Scanln(&id)
            fmt.Println("请输入猫咪的  名称  ")
            fmt.Scanln(&name)
            fmt.Println("请输入猫咪的  年龄  ")
            fmt.Scanln(&age)
            cat := &Cat{
                ID:   id,
                Name: name,
                Age:  age,
            }
            ht.Insert(cat)

        case 2:
            ht.PrintAll()
        case 3:
            fmt.Println("请输入要查找的猫咪ID")
            fmt.Scanln(&id)
            cat := ht.FindCatByID(id)
            if cat == nil {
                fmt.Println("链表中 未找到该猫咪...")
            } else {
                cat.ShowMe()
            }
        case 4:
            fmt.Println("退出了流浪猫信息管理系统...")
            os.Exit(0)

        default:
            fmt.Println("操作有误(请输入1-4)")
        }
    }
}