golang的数据结构与算法

1. 稀疏数组 sparesearray

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

       处理方法：

 1）记录该数组一共有几行几列，有多少个不同的值

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

 稀疏数组是一种典型的压缩算法。

• 编写一个五子棋的程序，有存盘退出和续上盘的功能

package main

import "fmt"

func main()  {

	//1.先创建一个原始的数组
	var chessMap [11][11]int
	chessMap[1][2]=1//黑棋
	chessMap[2][3]=2 //蓝棋

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

	type ValNode struct {
         arr int
         col int
         val int
	}

	valnode:=ValNode{
		arr: 11,
		col: 11,
		val: 0,
	}
	var sparseArray []ValNode
	sparseArray=append(sparseArray,valnode)
	//3.转成稀疏数组

	for i,v:=range chessMap{
		for j,v1:=range v{
			if v1!=0{
				valnode=ValNode{
					arr: i,
					col: j,
					val: v1,
				}
				sparseArray=append(sparseArray,valnode)
			}
		}
	}

	  fmt.Println("当前的稀疏数组是：：：：")
	for i,v:=range sparseArray{
		fmt.Printf("%d %d %d %d\n",i,v.arr,v.col,v.val)
	}
		fmt.Println()

	//存盘
	//文件的读写  省略

	//恢复原始数组
	var chessMap2 [11][11]int

	for i,valnode:=range sparseArray{

		if i!=0{  //跳过第一行
			chessMap2[valnode.arr][valnode.col]=valnode.val
		}

	}
    fmt.Println("恢复后的原始数据：：：")


	for _,v:=range chessMap2{
		for _,v1:=range v{
			fmt.Printf("%d\t",v1)
		}
		fmt.Println()
	}

	}