哈希表數據結構

package main

import (
	"fmt"
	"os"
)

type Emp struct {
	Id   int
	Name string
	Next *Emp
}

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

//不帶表頭，即第一個節點就放雇員資料
type EmpLink struct {
	Head *Emp
}

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

//給EmpLink寫增加雇員方法，編號從小到大
func (e *EmpLink) AddEmpLink(emp *Emp) {
	cur := e.Head      //輔助指針
	var pre *Emp = nil //輔助指針pre在cur前面
	//如果當前EmpLink是空的
	if cur == nil {
		e.Head = emp
		return
	}
	//給emp找位置並插入
	for {
		if cur != nil {
			if cur.Id > emp.Id { //找到
				break
			}
			pre = cur
			cur = cur.Next
		} else {
			break
		}
	}
	pre.Next = emp
	emp.Next = cur
}

func (e *EmpLink) ShowLink() {
	//如果當前EmpLink是空的
	if e.Head == nil {
		fmt.Println("當前鏈表為空")
		return
	}
	cur := e.Head
	for {
		if cur != nil {
			fmt.Printf("雇員ID=%d 名字=%s ~>", cur.Id, cur.Name)
			cur = cur.Next
		} else {
			break
		}
	}
	fmt.Println()
}

//鏈表數組
type HashTable struct {
	LinkArr [7]EmpLink
}

//給HashTable寫增加雇員方法
func (h *HashTable) Add(emp *Emp) {
	//使用散列函數，確定雇員添到哪個鏈表
	linkNo := h.HashFun(emp.Id)
	//添加
	h.LinkArr[linkNo].AddEmpLink(emp)
}

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

//查找
func (h *HashTable) FindById(id int) *Emp {
	linkNo := h.HashFun(id)
	return h.LinkArr[linkNo].FindByIdEmpLink(id)
}

//散列函數
func (h *HashTable) HashFun(id int) int {
	return id % 7 //得到一個值，就是鏈表的下標
}

func main() {
	key := 0
	id := 0
	name := ""
	var hashTable HashTable
	for {
		fmt.Println("===雇員系統===")
		fmt.Println("\t1.添加")
		fmt.Println("\t2.顯示")
		fmt.Println("\t3.查找")
		fmt.Println("\t4.退出")
		fmt.Scanln(&key)
		switch key {
		case 1:
			fmt.Println("輸入雇員ID")
			fmt.Scanln(&id)
			fmt.Println("輸入雇員 name")
			fmt.Scanln(&name)
			emp := &Emp{
				Id:   id,
				Name: name,
			}
			hashTable.Add(emp)
		case 2:
			hashTable.ShowAll()
		case 3:
			fmt.Println("輸入欲查雇員ID")
			fmt.Scanln(&id)
			emp := hashTable.FindById(id)
			if emp == nil {
				fmt.Println("不存在")
			} else {
				emp.ShowMe()
			}
		case 4:
			os.Exit(0)
		default:
			fmt.Println("輸入錯誤")
		}
	}

}

上次修改於 2021-09-01