用 Go 来实现链表、栈、队列、散列表、树、二叉树、堆、图

概念

散列表 又名哈希表 或 Hash表 散列表是根据关键码值(Key value)而直接进行访问的数据结构

散列表是数组的一种扩展，有数组演化而来。

常见应用场景

Go 中的 map

实现散列表

package main

import (
   "fmt" 
   "os"
)

// 定义员工结构体
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
      }
   }
   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 run xxx.go

===============雇员系统菜单============
input 表示添加雇员
show  表示显示雇员
find  表示查找雇员
exit  表示退出系统
请输入你的选择
输入错误
===============雇员系统菜单============
input 表示添加雇员
show  表示显示雇员
find  表示查找雇员
exit  表示退出系统
请输入你的选择
input
输入雇员id
1
输入雇员name
peter
===============雇员系统菜单============
input 表示添加雇员
show  表示显示雇员
find  表示查找雇员
exit  表示退出系统
请输入你的选择
input
输入雇员id
2
输入雇员name
kris
===============雇员系统菜单============
input 表示添加雇员
show  表示显示雇员
find  表示查找雇员
exit  表示退出系统
请输入你的选择
show
链表0 为空
链表1 雇员id=1 名字=peter ->
链表2 雇员id=2 名字=kris ->
链表3 为空
链表4 为空
链表5 为空
链表6 为空