关于数据结构:数据结构哈希表

哈希表的一种 Go 语言实现

package main

import (
    "fmt"
    "os"
)

// 链表中的数据的信息
type Emp struct {
    Id int
    Name string
    Next *Emp
}

func (e *Emp) ShowSelf() {fmt.Printf("链表 %d 找到了该节点 %d\n", e.Id % 7, e.Id)
}

// 定义链表，该链表不带头结点
type EmpLink struct {Head *Emp}

//EmpLink 的增加办法
func (l *EmpLink) Insert (emp *Emp) {
    // 定义两个辅助指针
    cur := l.Head
    var pre *Emp = nil

    // 判断是否为空链表
    if cur == nil { // 链表头部插入
        l.Head = emp
        //cur = emp // 这样会导致节点增加不上，不晓得什么起因
        return
    }

    // 如果不是空链表，给 emp 找到对应的地位并插入
    for {
        if cur != nil { // 链表中部插入
            if cur.Id >= emp.Id {
                pre.Next = emp
                emp.Next = cur
                break
            }
            pre = cur
            cur = cur.Next
        } else { // 链表尾部插入
            pre.Next = emp
            emp.Next = cur
            break
        }
    }
}

func (l *EmpLink)FindId(id int) *Emp{
    cur := l.Head
    for {
        if cur != nil && cur.Id == id {return cur}else if cur == nil {break}
        cur = cur.Next
    }
    return nil
}

// 定义一个显示链表元素的办法
func (l *EmpLink) ShowLink(no int) {
    if l.Head == nil {fmt.Printf("链表 %d 为空 \n", no)
        return
    }

    // 遍历以后链表并显示数据
    cur := l.Head
    for {
        if cur != nil {fmt.Printf("链表 %d 节点 Id= %d 名字 =%s ->", no, cur.Id, cur.Name)
            cur = cur.Next
        } else {break}
    }
    fmt.Println()}

// 定义一个 hash table，外部含有 7 条链表
type HashTable struct {LinkArr [7]EmpLink
}

//hashtable 的增加办法
func (h *HashTable) Insert (emp *Emp) {
    // 应用散列函数，确定将该节点增加到哪个链表
    LinkNo := h.HashFun(emp.Id)
    // 应用对应的链表增加
    h.LinkArr[LinkNo].Insert(emp)
}

func (h *HashTable) Find(no int) *Emp {lindNo := h.HashFun(no)
    return  h.LinkArr[lindNo].FindId(no)
}
// 显示 hashtable 所有节点
func (h *HashTable) ShowAll() {for i := 0; i < len(h.LinkArr); i++ {h.LinkArr[i].ShowLink(i)
    }
}

func (h *HashTable) HashFun (id int) int {return id % 7 // 返回链表下标}

func main(){
    var hashtable HashTable
    key := ""
    id := 0
    name := ""
    for {fmt.Println("==================== 零碎菜单 =====================")
        fmt.Println("input 增加节点")
        fmt.Println("show 显示节点")
        fmt.Println("find 查找节点")
        fmt.Println("exit 退出零碎")
        fmt.Println("请输出你的抉择")
        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.Find(id)
            if emp == nil {fmt.Println("id=%d 的节点不存在 \n", id)
            }else {emp.ShowSelf()
            }
        case "exit":
            os.Exit(0)
        default:
            fmt.Println("输出谬误")
        }
    }
}