稀疏数组
image.png
image.png
image.png
image.png
image.png
代码实现：
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)
type ValNode struct {
row int
col int
val int
}
var chessMap2 [11][11]int
func printArr(arr [11][11]int){
for _,v := range arr{
for _,v2 := range v{
fmt.Printf("%d\t",v2)
}
fmt.Println()
}
}
func changSparse(arr [11][11]int)[]ValNode{
//1)遍历chessMap，如果有一个元素的值不为0，创建一个node结构体，
//2)将其放入切片中。
var sparseArr []ValNode
//标准的一个稀疏数组应该还有一个记录原始二位数组的规模（行列,默认值）
valNode := ValNode{
row: 11,
col: 11,
val: 0,
}
sparseArr = append(sparseArr,valNode)
for i,v := range arr{
for j,v2 := range v{
if v2 != 0{
//创建一个valNode值结点
valNode := ValNode{
row: i,
col: j,
val: v2,
}
sparseArr = append(sparseArr,valNode)
}
}
}
return sparseArr
}
func writeSparse(sparseArr []ValNode){
file,err := os.OpenFile("chessMap.txt", os.O_APPEND|os.O_CREATE, 0666)
if err != nil{
panic(err)
}
defer file.Close()
//var buf []string
//w := bufio.NewWriter(file)
for _,v := range sparseArr{
//buf = []string{strconv.Itoa(v.row),strconv.Itoa(v.col),strconv.Itoa(v.val)}
file.WriteString(strconv.Itoa(v.row))
file.WriteString(" ")
file.WriteString(strconv.Itoa(v.col))
file.WriteString(" ")
file.WriteString(strconv.Itoa(v.val))
file.WriteString("\n")
}
}
func readFile(){
//如何恢复原始数组
//1、打开文件
f,err := os.Open("chessMap.txt")
if err != nil{
panic(err)
}
//2、遍历数据，恢复
r := bufio.NewReader(f)
for {
// 分行读取文件 ReadLine返回单个行，不包括行尾字节(\n 或 \r\n)
//data, _, err := r.ReadLine()
// 以分隔符形式读取,比如此处设置的分割符是\n,则遇到\n就返回,且包括\n本身 直接返回字符串
//str, err := r.ReadString('\n')
// 以分隔符形式读取,比如此处设置的分割符是\n,则遇到\n就返回,且包括\n本身 直接返回字节数数组
data, err := r.ReadBytes('\n')
// 读取到末尾退出
if err == io.EOF {
break
}
if err != nil {
fmt.Println("read err", err.Error())
break
}
// 打印出内容
//fmt.Printf("%v", string(data))
var row int
var col int
var val int
str := strings.Trim(string(data),"\n")
s := strings.Split(str," ")
for i,v := range s{
n,_ := strconv.Atoi(v)
if n == 11{
break
}
if i == 0{
row = n
}else if i == 1{
col = n
}else{
val = n
}
}
chessMap2[row][col] = val
}
}
func main(){
//1、先创建一个原始数值
var chessMap [11][11]int
chessMap[1][2] = 1 //黑子
chessMap[2][3] = 2 //蓝子
//2、输出原始数组
printArr(chessMap)
//3、转成稀疏数组
sparseArr := changSparse(chessMap)
//输出稀疏数组
fmt.Println("稀疏数组为：")
for i,valNode := range sparseArr{
fmt.Printf("%d:%d %d %d\n",i,valNode.row,valNode.col,valNode.val)
}
//将稀疏数组存盘
writeSparse(sparseArr)
fmt.Println("写入成功。。。")
readFile()
//输出读取后的数组
printArr(chessMap2)
//暂时用稀疏数组恢复
//先创建一个原始数组大小
//var chessMap2 [11][11]int
////遍历sparseArr
//for i,valNode := range sparseArr{
// if i != 0{//跳过第一个值
// chessMap2[valNode.row][valNode.col] = valNode.val
// }
//}
//
//fmt.Println("恢复后的数据：")
////遍历chessMap2
//for _,v := range chessMap2{
// for _,v2 := range v{
// fmt.Printf("%d\t",v2)
// }
// fmt.Println()
//}
}
队列
image.png
image.png
image.png
代码实现：
package main
import (
"errors"
"fmt"
"os"
)
type Queue struct {
maxSize int
array [5]int //数组模拟队列
front int //表示指向队列首
rear int //表示指向队列的尾部
}
//添加数据到队列
func (q *Queue)AddQueue(val int)(err error){
//先判断队列是否已满
if q.rear == q.maxSize - 1{
return errors.New("queue full")
}
q.rear++ //后移
q.array[q.rear] = val
return
}
//取队列
func (q *Queue)GetQueue()(val int,err error){
//先判断队列是否为空
if q.rear == q.front{
//队空
return -1,errors.New("queue empty")
}
q.front++
val = q.array[q.front]
return val,err
}
//显示队列
//找到对首，然后遍历到队尾，不包含队首元素
func (q *Queue)ShowQueue(){
for i := q.front + 1;i <= q.rear;i++{
fmt.Printf("array[%d]=%d\t",i,q.array[i])
}
}
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.Scan(&key)
switch key {
case "add":
fmt.Println("输入你要入队的数")
fmt.Scan(&val)
err := queue.AddQueue(val)
if err == nil{
fmt.Println("加入队列OK")
}else{
fmt.Println(err.Error())
}
case "get":
val,err := queue.GetQueue()
if err != nil{
fmt.Println(err.Error())
}else{
fmt.Println("从队列中取出一个数",val)
}
case "show":
queue.ShowQueue()
fmt.Println()
case "exit":
os.Exit(0)
}
}
}
环形队列
image.png
什么时候队列满：（rear+1）%maxsize == front
什么时候为空：rear == front
初始化：rear = 0,front = 0;
统计队列数：（rear + maxsize - front）% maxsize
代码实现：
package main
import (
"errors"
"fmt"
"os"
)
//使用一个结构体管理环形队列
type CircleQueue struct {
maxSize int //4
array [4]int //数组
head int //队首
tail int //队尾
}
func (c *CircleQueue)Push(val int)(err error){
if c.IsFull(){
return errors.New("queue full")
}
//tail并不在队列尾部，不包含最后的元素
c.array[c.tail] = val
c.tail = (c.tail+1) % c.maxSize
return nil
}
func (c *CircleQueue)Pop()(val int,err error){
if c.IsEmpty(){
return 0,errors.New("queue empty")
}
//取出元素,head指向队首，含队首元素。
val = c.array[c.head]
c.head = (c.head+1)%c.maxSize
return val,nil
}
//判断环形队列为满
func (c *CircleQueue)IsFull()bool{
return (c.tail+1)%c.maxSize == c.head
}
//判断队列是否为空
func (c *CircleQueue)IsEmpty()bool{
return c.head == c.tail
}
//取出环形队列有多少个元素
func (c *CircleQueue)Size()int{
return (c.tail+c.maxSize-c.head)%c.maxSize
}
//显示队列
func (c *CircleQueue)Show(){
fmt.Println("环形队列情况如下：")
//取出当前队列的元素
size := c.Size()
if size == 0{
fmt.Println("队列为空")
}
//设计一个辅助的变量，指向head
tempHead := c.head
for i:=0;i < size;i++{
fmt.Printf("arr[%d]=%d\t",tempHead,c.array[tempHead])
tempHead = (tempHead+1) % c.maxSize
}
fmt.Println()
}
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.Scan(&key)
switch key {
case "add":
fmt.Println("输入你要入队的数")
fmt.Scan(&val)
err := queue.Push(val)
if err == nil{
fmt.Println("加入队列OK")
}else{
fmt.Println(err.Error())
}
case "get":
val,err := queue.Pop()
if err != nil{
fmt.Println(err.Error())
}else{
fmt.Println("从队列中取出一个数",val)
}
case "show":
queue.Show()
fmt.Println()
case "exit":
os.Exit(0)
}
}
}
链表
image.png
image.png
image.png
image.png
package main
import "fmt"
//定义一个HeroNode
type HeroNode struct {
no int
name string
nickname string
next *HeroNode //表示指向下一个节点
}
func main(){
//创建一个头节点
head := &HeroNode{}
//创建一个新的HeroNode
hero1 := &HeroNode{
no:1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroNode{
no:2,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroNode{
no:3,
name: "林冲",
nickname: "豹子头",
}
//加入
InsertNode2(head,hero1)
InsertNode2(head,hero3)
InsertNode2(head,hero2)
ListHeroNode(head)
fmt.Println()
//删除
DelHeroNode(head,2)
ListHeroNode(head)
}
//尾插入
func InsertNode(head *HeroNode,newHeroNode *HeroNode){
//先找到该联邦的最后这个结点
//创建一个辅助结点
temp := head
for{
if temp.next == nil{
//表示找到最后
break
}
temp = temp.next
}
//将newHeroNode加入到链表的最后
temp.next = newHeroNode
}
//根据编号从小到大插入
func InsertNode2(head *HeroNode,newHeroNode *HeroNode){
//先找到该联邦的最后这个结点
//创建一个辅助结点
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 ListHeroNode(head *HeroNode){
temp := head
//判断该链表是否为空
if temp == nil{
fmt.Println("空空如也")
return
}
//遍历链表
for{
fmt.Printf("[%d,%s,%s]==>",temp.next.no,temp.next.name,temp.next.nickname)
temp = temp.next
if temp.next == nil{
break
}
}
}
func DelHeroNode(head *HeroNode,id int){
temp := head
flag := false
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不存在")
}
}
双向链表
image.png
image.png
package main
import "fmt"
//定义一个HeroNode
type HeroNode struct {
no int
name string
nickname string
next *HeroNode //表示指向下一个节点
pre *HeroNode //指向前一个结点
}
func main() {
//创建一个头节点
head := &HeroNode{}
//创建一个新的HeroNode
hero1 := &HeroNode{
no: 1,
name: "宋江",
nickname: "及时雨",
}
hero2 := &HeroNode{
no: 2,
name: "卢俊义",
nickname: "玉麒麟",
}
hero3 := &HeroNode{
no: 3,
name: "林冲",
nickname: "豹子头",
}
//加入
InsertNode(head, hero1)
InsertNode(head, hero2)
InsertNode(head, hero3)
ListHeroNode(head)
fmt.Println()
ListHeroNode2(head)
//删除
//DelHeroNode(head, 2)
//
//ListHeroNode(head)
}
//尾插入
func InsertNode(head *HeroNode, newHeroNode *HeroNode) {
//先找到该联邦的最后这个结点
//创建一个辅助结点
temp := head
for {
if temp.next == nil {
//表示找到最后
break
}
temp = temp.next
}
//将newHeroNode加入到链表的最后
temp.next = newHeroNode
newHeroNode.pre = temp
}
//根据编号从小到大插入
func InsertNode2(head *HeroNode, newHeroNode *HeroNode) {
//先找到该联邦的最后这个结点
//创建一个辅助结点
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
newHeroNode.pre = temp
if temp.next != nil{
temp.next.pre = newHeroNode
}
temp.next = newHeroNode
}
}
//显示链表所有节点信息
func ListHeroNode(head *HeroNode) {
temp := head
//判断该链表是否为空
if temp == nil {
fmt.Println("空空如也")
return
}
//遍历链表
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) {
temp := head
//判断该链表是否为空
if temp == nil {
fmt.Println("空空如也")
return
}
for {
if temp.next == nil{
break
}
temp = temp.next
}
//遍历链表
for {
fmt.Printf("[%d,%s,%s]==>", temp.no, temp.name, temp.nickname)
temp = temp.pre
if temp.pre == nil {
break
}
}
}
func DelHeroNode(head *HeroNode, id int) {
temp := head
flag := false
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
if temp.next != nil{
temp.next.pre = temp
}
} else {
fmt.Println("sorry,要删除的id不存在")
}
}
环形链表
image.png
image.png
package main
import "fmt"
//定义猫的结构体
type CatNode struct {
no int
name string
next *CatNode
}
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,1)
ListCircleLink(head)
}
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 head.next == nil{
fmt.Println("这是一个空的环形链表，无法删除。。。")
return head
}
//只有一个结点
if temp.next == head{
temp.next = nil
return head
}
//将helper定位到最后一个结点
for{
if helper.next == head{
break
}
helper = helper.next
}
//多个结点
flag := true
for{
if temp.next == head{
break
}else 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 //找到结点，删除。
}
//比较最后一个
if flag{ //如果flag为真，for中没有删除
if temp.no == id{
helper.next = temp.next
fmt.Printf("猫=%d\n",id)
}else{
fmt.Printf("sorry,没有no=%d\n",id)
}
}
return head
}
作业
image.png
image.png
package main
import "fmt"
//小孩的结构体
type Boy struct {
No int
Next *Boy
}
//编写一个函数，构成单向的循环链表
//num 表示小孩的个数
//返回第一个小孩的指针。
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,
}
//分析构成循环链表，需要一个辅助指针。
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)
if curBoy.Next == first{
break
}
curBoy = curBoy.Next
}
}
//1、编写一个函数，PlayGame(first *Boy,startNo int,CountNo int)
//2、最后使用一个算法，在环形链表中留下最后一个人。
func PlayGame(first *Boy,startNo int,CountNo int){
//空链表，单独处理
if first.Next == nil{
fmt.Println("空的链表，没有小孩")
}
//判断startNo <= 小孩的总数
//需要定义辅助指针，帮助删除小孩
tail := first
//让tail指向环形链表的最后一个小孩。
for{
if tail.Next == first{
//说明到了最后一个小孩
break
}
tail = tail.Next
}
//让first移动到startNo[后面删除小孩，以first为准]
for i:= 1;i <= startNo - 1;i++{
first = first.Next
tail = tail.Next
}
fmt.Println()
//开始数countNum下，然后删除first指向的小孩
for{
//开始数countNum - 1次
for i:= 1;i<=CountNo-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(10)
ShowBoy(first)
PlayGame(first,2,3)
}
选择排序
image.png
image.png
package main
import "fmt"
func Select(arr *[5]int){
for i := 0;i < len(arr)-1;i++{
min := i
for j := i+1;j < len(arr);j++{
if arr[min] > arr[j]{
min = j
}
}
if min != i{
arr[min],arr[i] = arr[i],arr[min]
}
}
}
func main(){
arr := [5]int{10,34,19,100,80}
Select(&arr)
fmt.Println(arr)
}
插入排序
image.png
func insert(arr *[5]int){
for i := 1;i < len(arr);i++{
tmp := arr[i]
j := i-1
for ;j >= 0 && tmp < arr[j];j--{
arr[j+1] = arr[j]
}
if j+1 != i{
arr[j+1] = tmp
}
}
}
快速排序
image.png
func quick(left int,right int,array *[5]int){
l := left
r := right
pivot := array[(left+right)/2]
for ;l<r;{
for;array[l] < pivot;{
l++
}
for;array[r] > pivot;{
r--
}
if l >= r {
break
}
array[l],array[r] = array[r],array[l]
//优化
if array[l] == pivot{
r--
}
if array[r] == pivot{
l++
}
}
if l==r{
l++
r--
}
if left < r{
quick(left,r,array)
}
if right > l{
quick(l,right,array)
}
}
栈
image.png
image.png
package main
import (
"errors"
"fmt"
)
//使用数组模拟一个栈的使用
type Stack struct {
MaxTop int //表示栈的最大可以存放数的个数
Top int //表示栈顶，
arr [5]int //数组模拟栈
}
func (s *Stack)Push(val int)(err error){
//先判断栈是否满
if s.Top == s.MaxTop -1 {
fmt.Println("stack full")
return errors.New("stack full")
}
s.Top++
//放入数据
s.arr[s.Top] = val
return
}
//出栈
func (s *Stack)Pop()(val int,err error){
//判断栈空
if s.Top == -1{
fmt.Println("stack empty")
return 0,errors.New("stack empty")
}
//先取值，再减减
val = s.arr[s.Top]
s.Top--
return val,nil
}
//遍历栈 需要从栈顶开始遍历
func (s *Stack)List(){
//判断是否为空
if s.Top == -1{
fmt.Println("stack empty")
return
}
fmt.Println("栈的情况如下")
for i:=s.Top;i >= 0;i--{
fmt.Printf("arr[%d]=%d\n",i,s.arr[i])
}
}
func main(){
stack := &Stack{
MaxTop: 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)
stack.List()
}
递归
image.png
image.png
image.png
image.png
package main
import "fmt"
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
}
for i:=0;i < 8;i++{
myMap[i][0] = 1
myMap[i][6] = 1
}
myMap[3][1] = 1
myMap[3][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()
}
}
//编写一个函数，完成老鼠找路
//地图是同一个地图，因此使用指针
//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
}
}
}
哈希表
image.png
image.png
image.png
package main
import (
"fmt"
"os"
)
//定义emp
type Emp struct {
Id int
Name string
Next *Emp
}
func (e *Emp)ShowMe(){
fmt.Printf("链表%d找到该雇员%d\n",e.Id%7,e.Id)
}
//定义EmpLink
//不带表头，第一个结点就存放雇员
type EmpLink struct {
Head *Emp
}
//方法待定
//添加员工方法,保证添加时，编号从小到大
func (e *EmpLink)Insert(emp *Emp){
cur := e.Head //辅助指针
var pre *Emp = nil //辅助指针
//如果当前的EmpLink是空链表
if cur == nil{
e.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 (e *EmpLink)ShowLink(no int){
if e.Head == nil{
fmt.Printf("链表%d为空\n",no)
return
}
//变量当前链表，并显示数据
cur := e.Head //辅助指针
for{
if cur != nil{
fmt.Printf("链表%d雇员id = %d 名字= %s->",no,cur.Id,cur.Name)
cur = cur.Next
}else{
break
}
}
fmt.Println()
}
//根据ID查找对应雇员，如果没有返回空
func (e *EmpLink)FindById(id int)*Emp{
cur := e.Head
for{
if cur != nil && cur.Id == id{
return cur
}
if cur == nil{
break
}
cur = cur.Next
}
return nil
}
//定义hashtable含有一个链表数组
type HashTable struct {
LinkArr [7]EmpLink
}
//给HashTable编写Insert 雇员的方法
func (h *HashTable)Insert(emp *Emp){
//使用散列函数，确定该雇员添加到哪个链表
linkNo := h.HashFun(emp.Id)
//使用对应的链表添加
h.LinkArr[linkNo].Insert(emp)
}
//编写一个散列方法
func (h *HashTable)HashFun(id int)int{
return id % 7 //得到一个值，链表的下标
}
//编写方法，显示hashtable的所有雇员
func (h *HashTable)ShowAll(){
for i:=0;i < len(h.LinkArr);i++{
h.LinkArr[i].ShowLink(i)
}
}
//编写方法，完成查找
func (h *HashTable)FindById(id int)*Emp{
linkNo := h.HashFun(id)
return h.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 "find":
fmt.Println("请输入ID号：")
fmt.Scanln(&id)
emp := hashtable.FindById(id)
if emp == nil{
fmt.Printf("id = %d的雇员不存在\n",id)
}else{
emp.ShowMe()
}
case "show":
hashtable.ShowAll()
case "exit":
os.Exit(2)
default:
fmt.Println("输入错误")
}
}
}
二叉树
image.png
image.png
package main
import "fmt"
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//前序遍历
func PreOrder(node *Hero){
if node != nil{
fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历
func InfixOrder(node *Hero){
if node != nil{
PreOrder(node.Left)
fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
PreOrder(node.Right)
}
}
//后序遍历
func PostOrder(node *Hero){
if node != nil{
PreOrder(node.Left)
PreOrder(node.Right)
fmt.Printf("no=%d,name=%s\n",node.No,node.Name)
}
}
func main(){
//构建一个二叉树
root := &Hero{
No: 1,
Name: "宋江",
}
left1 := &Hero{
No: 2,
Name: "吴用",
}
right1 := &Hero{
No: 3,
Name: "卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No: 4,
Name: "林冲",
}
right1.Right = right2
PreOrder(root)
InfixOrder(root)
PostOrder(root)
}
网友评论