稀疏数组

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是：

• 记录数组一共有几行几列，有多少个不同的值
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

简单来说 , 就是将无用的数据扔掉 , 进而无损压缩数据

type ValNode struct {
	row int
	col int
	val int
}

func main() {
	var chessMap [11][11]int
	chessMap[1][2] = 1
	chessMap[2][3] = 2
	for _, v1 := range chessMap {
		for _, v2 := range v1 {
			fmt.Printf("%d\t",v2)
		}
		fmt.Println()
	}

	var sparseArr []ValNode
	// 标准的稀疏数组需要一个 `记录二维数组的规模(行和列)`
	head := ValNode{
		row:11,
		col:11,
		val:0,
	}
	sparseArr = append(sparseArr,head)
	// 储存稀疏数组
	for i, v1 := range chessMap {
		for j, v2 := range v1 {
			if v2 != 0 {
				valNode := ValNode{
					row:i,
					col:j,
					val:v2,
				}
				sparseArr = append(sparseArr,valNode)
			}
		}
	}
	// 输出稀疏数组
	for i,valNode := range sparseArr {
		fmt.Printf("%d:%d %d %d\n",i,valNode.row,valNode.col,valNode.val)
	}
}

环形队列

数组模拟环形队列

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下其中 maxsize是该队列的最大容量。

  

• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输岀而改变，而rear则是随着数据输入而改变，

• 一般约定 , 当rear距离front只有一个空位的时候为对满 (也就是说,队尾差一位就能追上对首)

  • 所以就是判断 : (rear + 1) % maxSize == head

总结 :

• 初始化 : rear == head == 0
• 对空 : rear == head
• 对满 : (rear + 1) % maxSize == head
• 队列的元素个数 : (rear + maxSize - head) % maxSize (为了保证不出现负数 , 要加一个maxSize)

type CircleQueue struct {
	maxSize int
	array [4]int
	front int // 队首指针
	rear int // 队尾部指针
}

func (this *CircleQueue) IsFull() bool {
	return (this.rear + 1) % this.maxSize == this.front
}

func (this *CircleQueue) IsEmpty() bool {
	return this.front == this.rear
}

func (this *CircleQueue) Size() int {
	return (this.rear + this.maxSize - this.front) % this.maxSize
}

func (this *CircleQueue) Push(val int) (err error) {
	// 先判断队列是否已满
	if this.IsFull() {
		return errors.New("queue full")
	}
	this.rear++ // 后移
	this.array[this.rear] =val
	return
}

func (this *CircleQueue) Pop() (val int, err error) {
	if this.IsEmpty() {
		return 0 , errors.New("queue empty")
	}
	this.front = (this.front + 1) % this.maxSize
	val = this.array[this.front]
	return val ,err
}

func (this *CircleQueue) List() {
	size := this.Size()
	if size == 0 {
		fmt.Println("Queue Empty")
	}
	dummy := this.front
	for i:= 0; i < size; i++ {
		fmt.Printf("arr[%d]=%d\t", dummy, this.array[dummy])
		dummy = (dummy +1) % this.maxSize
	}
}


func main() {
	queue := &CircleQueue{
		maxSize :4,
		front :0,
		rear :0,
	}

	err := queue.Push(100)
	if err != nil {
		fmt.Println("error")
	}
	queue.Push(200)
	queue.Push(300)

	queue.List() // array[0]=100    array[1]=200    array[2]=300

	res,err := queue.Pop()
	if err != nil {
		fmt.Println("error")
	}
	fmt.Println(res) // 100
}

环形单向链表

环形单向链表一般也拥有dummyHead

type CricleNode struct {
	val int
	next *CricleNode
}

func (n *CricleNode) append(val int) {
	pre := n
	realHead := pre.next

	// realHead是空
	if pre.next == nil {
		newNode := &CricleNode{val:val}
		pre.next = newNode
		newNode.next = newNode
	} else {
		pre = realHead
		for pre.next != realHead{
			pre = pre.next
		}
		newNode := &CricleNode{
			val:val,
			next:realHead,
		}
		pre.next = newNode
	}
}

func (n *CricleNode) List() {
	if n.next == nil {
		return
	}
	pre := n.next
	realHead := pre
	for {
		fmt.Println(pre.val)
		pre = pre.next
		if pre == realHead {
			break
		}
	}
}

func main() {
	DummyHead := &CricleNode{}
	DummyHead.append(100)
	DummyHead.append(200)
	DummyHead.append(300)
	DummyHead.List()
}

双向链表

对比单向链表的优势 :

• 支持向前查找
• 单向链表不支持自我删除 , 必须依赖其他辅助节点 , 而双向链表支持自我删除

排序

选择排序

func SelectSort(arr []int) []int {
	Len := len(arr)
	for i:=0; i<=Len -1; i++ {
		maxIdx := i
		for j:=i; j<=Len -1; j++ {
			if arr[j] < arr[maxIdx] {
				maxIdx = j
			}
		}
		arr[i],arr[maxIdx] = arr[maxIdx],arr[i]
	}
	return arr
}

func main() {
	arr := []int{9,6,3,8,5,2,7,4,1}
	res := SelectSort(arr)
	fmt.Println(res)
}

插入排序

func InsertSort(arr []int) []int {
	Len := len(arr)
	for i:=1; i<= Len-1; i++ {
		for idx := i; idx > 0;idx--{
			if arr[idx] < arr[idx-1] {
				arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
			}
		}
	}
	return arr
}

func main() {
	arr := []int{9,6,3,8,5,2,7,4,1}
	res := InsertSort(arr)
	fmt.Println(res)
}