通过golang实现一些经典算法问题

1、sparsearray 稀疏数组

1.1、先看一个问题

1.2、基本介绍


1.3、举栗说明

1.4、应用实例


代码：

package main

import "fmt"

/**
 *  @Description：稀疏数组
 *  @Author: guai
 *  @Date：2020/3/1 9:06
**/

type valNode struct {
	row int
	col int
	val int
}

func main() {
	//1、创建一个原始数组
	var chessMap [11][11]int
	chessMap[1][2] = 1
	chessMap[2][3] = 2

	//2、输出原始数组
	for _, v := range chessMap {
		for _, v2 := range v {
			fmt.Printf("%d\t", v2)
		}
		fmt.Println()
	}

	//3、转换成系数数据  。思考->算法
	//1)遍历chessMap，如果我们发现一个元素的值不为0，创建一个node结构体
	//2）将其放入对应的切片
	var sparseArr []valNode
	//标准的一个稀疏数组应该还有一个记录元素的二维数组的模型（行/列/默认值）
	//创建一个valNode值节点
	valArr := valNode{
		row: 11,
		col: 11,
		val: 0,
	}
	sparseArr = append(sparseArr, valArr)
	for i, v := range chessMap {
		for j, v1 := range v {
			if v1 != 0 {
				valArr := valNode{
					row: i,
					col: j,
					val: v1,
				}
				sparseArr = append(sparseArr, valArr)
			}

		}
	}
	//输出稀疏数组
	for i, valArr := range sparseArr {
		fmt.Printf("%d:%d %d %d\n", i, valArr.row, valArr.col, valArr.val)
	}

	//4、将稀疏数组复原
	//创建原始数组
	var chessMap1 [11][11]int
	for i,valArr:=range sparseArr{
		if i!=0{
			chessMap1[valArr.row][valArr.col]=valArr.val
		}
	}

	for _,val:=range chessMap1{
		for _,val1:=range val{
			fmt.Printf("%d \t",val1)
		}
		fmt.Println()
	}
}

结果：

2、golang中队列的实现
2.1、应用场景

2.2、队列介绍

2.3、数组模拟队列 front前rear后

2.4、实现一个非环形的队列（数组来实现）


代码：

package main

import (
	"errors"
	"fmt"
	"os"
)

/**
*  @Description： golang中队列的实现
 *  @Author: guai
 *  @Date：2020/3/1 9:34
**/
//顶定义一个队列结构体
type queueType struct {
	array   [5]int
	maxSize int
	front   int
	rear    int
}

//添加数据
func (this *queueType) addQueue(val int) (err error) {
	//判断队列满否
	if this.rear == this.maxSize-1 {
		return errors.New("queue is full")
	}
	//rear 后移
	this.rear++
	this.array[this.rear] = val
	return
}

//取出数据
func (this *queueType) getQueue() (val int, err error) {
	//判断队列空否
	if this.rear == this.front {
		return 0, errors.New("queue is empty")
	}
	this.front++
	return this.array[this.front], nil
}

//显示队列
func (this *queueType) showQueue() (err error) {
	if this.rear == this.front {
		return errors.New("queue is empty")
	}
	for i := this.front + 1; i <= this.rear; i++ {
		fmt.Printf("array[%d]:%d\n", i, this.array[i])
	}
	return nil
}
func main() {
	queueT := &queueType{
		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("1、输入exit退出程序")

		fmt.Scan(&key)
		switch key {
		case "add":
			fmt.Println("请输入一个整数")
			fmt.Scan(&val)
			err := queueT.addQueue(val)
			if err != nil {
				fmt.Println("add err:", err.Error())
			} else {
				fmt.Println("add success")
			}
		case "get":
			val, err := queueT.getQueue()
			if err != nil {
				fmt.Println("get err:", err.Error())
			} else {
				fmt.Println("get val:", val)
			}
		case "show":
			err := queueT.showQueue()
			if err != nil {
				fmt.Println("show err:", err.Error())
			}
		case "exit":
			fmt.Println("exit")
			os.Exit(0)
		default:
			fmt.Println("input err,input again please!")
		}
	}
}

结果：

2.5、实现一个循环队列 （通过数据完成）

package main

import (
	"errors"
	"fmt"
	"os"
)

/**
 *  @Description： 通过数组实现循环队列  （ ctrl+r：查找替换）
 *  @Author: guai
 *  @Date：2020/3/1 10:26
**/

//定义一个循环队列
type circleQueue struct {
	array [5]int
	//最大值为4
	maxSize int
	//队列头
	head int
	//队列尾
	tail int
}

//判断队列满否
func (this *circleQueue) isFull() bool {
	return (this.tail+1)%this.maxSize == this.head
}

//判断队列空否
func (this *circleQueue) isEmpty() bool {
	return this.tail == this.head
}

//添加数据
func (this *circleQueue) push(val int) (err error) {
	//判断队列满否
	if this.isFull() {
		return errors.New("queue is full")
	}

	//分析this。tail在队尾但是包含最后的元素
	this.array[this.tail] = val
	// 当tail==4时 队尾重新回到 0的位置形成circle
	this.tail = (this.tail + 1) % this.maxSize
	return
}

//取出数据
func (this *circleQueue) pop() (val int, err error) {
	//判断队列空否
	if this.isEmpty() {
		return 0, errors.New("queue is empty")
	}
	//取出队列的值
	val = this.array[this.head]
	this.head = (this.head + 1) % this.maxSize
	return

}

//显示队列
func (this *circleQueue) show() (err error) {
	if this.isEmpty() {
		return errors.New("queue is empty")
	}
	tempHead := this.head
	for {
		if tempHead == this.tail {
			return
		}
		fmt.Printf("array[%d]:%d\n", tempHead, this.array[tempHead])
		tempHead = (tempHead + 1) % this.maxSize

	}
	return
}

//返回队列中元素个数
func (this *circleQueue) size() int {
	//这里可能 难理解 注意一点
	return (this.tail + this.maxSize - this.head) % this.maxSize
}
func main() {
	circleQ := &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、输入size显示队列中的元素个数")
		fmt.Println("5、输入exit退出程序")

		fmt.Scan(&key)
		switch key {
		case "add":
			fmt.Println("请输入一个整数")
			fmt.Scan(&val)
			err := circleQ.push(val)
			if err != nil {
				fmt.Println("add err:", err.Error())
			} else {
				fmt.Println("add success")
			}
		case "get":
			val, err := circleQ.pop()
			if err != nil {
				fmt.Println("get err:", err.Error())
			} else {
				fmt.Println("get val:", val)
			}
		case "show":
			err := circleQ.show()
			if err != nil {
				fmt.Println("show err:", err.Error())
			}
		case "size":
			fmt.Println("size:", circleQ.size())
		case "exit":
			fmt.Println("exit")
			os.Exit(0)
		default:
			fmt.Println("input err,input again please!")
		}
	}
}

3、链表

3.1、链表是有序的列表，但它在内存中的存储不连续且无序，如下：

3.2、单链表示意图
链表：
通过节点中的next将多个节点连接起来 形成链表

3.3、单链表的应用案例

 package main

import (
	"fmt"
)

/**
 *  @Description：链表
 *  @Author: guai
 *  @Date：2020/3/1 12:20
**/
//定义节点类型
type vegetablesNode struct {
	name  string
	age   int
	skill string
	next  *vegetablesNode
}
//在末尾添加节点
func (list *vegetablesNode) add(newNode *vegetablesNode) {
	defer func() {
		err := recover()
		if err != nil {
			fmt.Println("err:", err)
		}
	}()
	//中间节点
	tempNode := list
	for {
		if tempNode.next == nil {
			break
		}
		tempNode = tempNode.next
	}
	tempNode.next = newNode

}
//显示所有节点
func (list *vegetablesNode) show() {
	tempNode := list
	for {
		if tempNode == nil {
			break
		}
		fmt.Println("node:", tempNode)
		tempNode = tempNode.next

	}
}
//在指定节点后添加节点
func (list *vegetablesNode) insertNode(name string,newNode *vegetablesNode){
	tempNode:=list
	for{
	    tempNode1:=tempNode.next

	    if tempNode==nil{
			fmt.Println("no found :",name)
			break
		}
		if tempNode.name==name{
			newNode.next=tempNode1
			tempNode.next=newNode
			fmt.Println("insert success")
			break
		}
	}
}

func main() {
	list:=vegetablesNode{
		name:"cabbage",
		age:12,
		skill:"eat",
	}

	list.add(&vegetablesNode{
		name:"radish",
		age:12,
		skill:"eat",
	})
	list.show()
	list.insertNode("cabbage",&vegetablesNode{
		name:"chives",
		age:12,
		skill:"eat",
	})
	list.show()
}

结果：

3.4、双向链表
每个节点中有指向前一个节点的 pre和指向后一个结点的next 形成双向的链表

package main

import "fmt"

/**
 *  @Description：双向链表
 *  @Author: guai
 *  @Date：2020/3/1 13:17
**/

//定义节点类型
type doublyLinkedNode struct {
	name  string
	age   int
	skill string
	pre   *doublyLinkedNode
	next  *doublyLinkedNode
}

//在末尾添加节点
func (list *doublyLinkedNode) add(newNode *doublyLinkedNode) {
	defer func() {
		err := recover()
		if err != nil {
			fmt.Println("err:", err)
		}
	}()
	//中间节点
	tempNode := list
	for {
		if tempNode.next == nil {
			break
		}
		tempNode = tempNode.next
	}
	newNode.pre=tempNode
	tempNode.next = newNode
}

//显示所有节点
func (list *doublyLinkedNode) show() {
	tempNode := list
	for {
		if tempNode == nil {
			break
		}
		fmt.Println("node:", tempNode)
		tempNode = tempNode.next

	}
}

//在指定节点后添加节点
func (list *doublyLinkedNode) insertNode(name string, newNode *doublyLinkedNode) {
	tempNode := list
	for {
		tempNode1 := tempNode.next

		if tempNode == nil {
			fmt.Println("no found :", name)
			break
		}
		if tempNode.name == name {

			newNode.next = tempNode1
			tempNode1.pre=newNode

			tempNode.next = newNode
			newNode.pre=tempNode
			fmt.Println("insert success")
			break
		}
	}
}

func main() {
	list := doublyLinkedNode{
		name:  "cabbage",
		age:   12,
		skill: "eat",
	}

	list.add(&doublyLinkedNode{
		name:  "radish",
		age:   12,
		skill: "eat",
	})
	list.show()
	list.insertNode("cabbage", &doublyLinkedNode{
		name:  "chives",
		age:   12,
		skill: "eat",
	})
	list.show()
}

结果：

3.5、循环链表

循环链表介绍

循环列表练习：

package main

import (
	"fmt"
)

/**
 *  @Description：循环列表
 *  @Author: guai
 *  @Date：2020/3/1 12:20
**/

//定义节点类型
type circleNode struct {
	name  string
	age   int
	skill string
	next  *circleNode
}

//在末尾添加节点
func (list *circleNode) add(newNode *circleNode) {
	defer func() {
		err := recover()
		if err != nil {
			fmt.Println("err:", err)
		}
	}()

	//中间节点
	tempNode := list
	for {
		if tempNode.next == list {
			break
		}
		tempNode = tempNode.next
	}
	newNode.next = list
	tempNode.next = newNode

}

//显示所有节点
func (list *circleNode) show() {
	tempNode := list
	for {
		fmt.Println("node:", tempNode, list)

		if tempNode.next == list {
			break
		}
		tempNode = tempNode.next
	}
}

//删除节点
func (list *circleNode) del(name string) {

	if list == nil {
		fmt.Println("list is empty")
		return
	}
	tempNode := list
	//当只有一个节点时
	if tempNode.next == list {
		if tempNode.name == name {
			tempNode = nil
			fmt.Println("del success")
			return
		}
	}
	//将endNode定位到链表最后
	endNode := list
	for {
		if endNode.next == list {
			break
		}
		endNode = endNode.next
	}
	fmt.Println("flagq")

	for {
		if tempNode.next == list {
			break
		}

		if tempNode.name == name {
			//删除的是头节点
			if tempNode == list {
				 *list = *list.next
			//	list.show()
				endNode.next=list
				fmt.Println("del success")
				return
			} else {
				  *endNode.next= *tempNode.next
				fmt.Println("del success1")
				return
			}
		}
		endNode = endNode.next
		tempNode = tempNode.next
	}

	fmt.Println("del fail case by name not found")
}

//在指定节点后添加节点
func (list *circleNode) insertNode(name string, newNode *circleNode) {
	tempNode := list
	if tempNode == nil {
		fmt.Println("no found :", name)
		return
	}
	for {
		tempNode1 := tempNode.next
		if tempNode.name == name {
			newNode.next = tempNode1
			tempNode.next = newNode
			fmt.Println("insert success")
			return
		}
		if tempNode.next == list {
			fmt.Println("no found ",name)
			return
		}
		tempNode=tempNode.next
	}
}

func main() {
	list := circleNode{
		name:  "cabbage",
		age:   12,
		skill: "eat",
	}
	list.next = &list

	list.add(&circleNode{
		name:  "radish",
		age:   12,
		skill: "eat",
	})
	//list.show()
	list.add(&circleNode{
		name:  "radish1",
		age:   12,
		skill: "eat",
	})

	list.show()
	list.insertNode("cabbage", &circleNode{
		name:  "chives",
		age:   12,
		skill: "eat",
	})
	list.show()

	//list.del("cabbage")
	//fmt.Println(list)
	//list.show()

	list.del("radish")
	fmt.Println(list)
	list.show()
}

结果：