Go 稀疏数组学习与实现

仍然还是一个数组

基本介绍

一般就是指二维以上的数组
当一个数组中大部分元素是0 ,或者为同一个值的数组时,可以使用系数数组来保存该数组.

稀疏数组的处理方法:

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SlBq9xxF-1677594413402)(…/…/images/Pasted%20image%2020230228201055.png)]
这就是一个六行七列的二维数组.
所以用一个n行三类的二维数组来记录这个数组
第一列是行数, 第二列是列数, 第三列是值
6 7 0
0 3 22
0 6 15
…
5 2 28

这里的6 7 0 记录的是这个二维数组有6 行7 列 的0 值
其余行记录不一样的值的位置

这是一种压缩
但是我们可以发现,一个数值会多出两个值(行列)来表示,所以如果有值的数,大于了原来数组的1/3 就得不偿失了

代码实现

一个二维数组转换成稀疏数组

package main  //稀疏数组  type ValueNode struct {  row int  col int  Val int  
}  func main() {  // 创建一个原始的数组  var chessMap [11][11]int  chessMap[1][2] = 1  chessMap[2][3] = 2  // 1 代表黑子  //2 代表白子  //输出原始数组  for _, item1 := range chessMap {  for _, item2 := range item1 {  print(item2)  }  println()  }  // 转换成稀疏数组  /*  思路  1.遍历数组,如果发现有一个元素的值不是0 ,就创建一个node结构体  2.将其放入到对应的切片中就可以了  */  var SparseArr []ValueNode  //标准的稀疏数组要记录二维数组的行和列  valueNode := ValueNode{  row: 11,  col: 11,  Val: 0,  }  SparseArr = append(SparseArr, valueNode)  // 结构体切片  //还是要全部扫描一遍的  for i, item1 := range chessMap {  for j, item2 := range item1 {  if item2 != 0 {  // 创节点了  valueNode = ValueNode{  row: i,  col: j,  Val: item2,  }  SparseArr = append(SparseArr, valueNode)  }  }  }  // 输出稀疏数组  for i, valueNode := range SparseArr {  println(i, valueNode.row, valueNode.col, valueNode.Val)  }  }

将稀疏数组输入到一个文件中

package main  import (  "bufio"  "fmt"   "os")  //稀疏数组  type ValueNode struct {  row int  col int  Val int  
}  func main() {  path := "./resources/class.data"  // 创建一个原始的数组  var chessMap [11][11]int  chessMap[1][2] = 1  chessMap[2][3] = 2  // 1 代表黑子  //2 代表白子  //输出原始数组  for _, item1 := range chessMap {  for _, item2 := range item1 {  print(item2)  }  println()  }  //Arr2Sparse(chessMap)  // 转换成稀疏数组  /*  思路  1.遍历数组,如果发现有一个元素的值不是0 ,就创建一个node结构体  2.将其放入到对应的切片中就可以了  */  var SparseArr []ValueNode  //标准的稀疏数组要记录二维数组的行和列  valueNode := ValueNode{  row: 11,  col: 11,  Val: 0,  }  SparseArr = append(SparseArr, valueNode)  // 结构体切片  //还是要全部扫描一遍的  for i, item1 := range chessMap {  for j, item2 := range item1 {  if item2 != 0 {  // 创节点了  valueNode = ValueNode{  row: i,  col: j,  Val: item2,  }  SparseArr = append(SparseArr, valueNode)  }  }  }  //输出稀疏数组  file, err := os.OpenFile(path, os.O_WRONLY, 0666)  if err != nil {  fmt.Println("文件打开失败", err)  }  defer file.Close()  for _, valueNode := range SparseArr {  s := fmt.Sprintf("%d %d %d\n", valueNode.row, valueNode.col, valueNode.Val)  write := bufio.NewWriter(file)  write.WriteString(s)  write.Flush()  if err != nil {  println("写入失败")  }  }  }

稀疏数组变成二维数组

package main  import (  "bufio"  "fmt"   "os")  //稀疏数组  type ValueNode struct {  row int  col int  Val int  
}  func main() {  path := "./resources/class.data"  // 恢复原始的数组  // 打开稀疏数组的文件  //     文件转换成稀疏数组(切片)  var sparse []ValueNode  file, _ := os.Open(path)  defer file.Close()  r := bufio.NewReader(file)  for true {  line, _, err := r.ReadLine()  if err != nil {  break  }  str := string(line)  var (  num1 int  num2 int  num3 int  )  fmt.Sscanf(str, "%d %d %d", &num1, &num2, &num3)  //println(num1, num2, num3)  valnode := ValueNode{  row: num1,  col: num2,  Val: num3,  }  sparse = append(sparse, valnode)  }  //fmt.Println(sparse)  // 得到数据  //创建一个二维数组  chessMap := make([][]int, sparse[0].row)  for i := 0; i < sparse[0].row; i++ {  chessMap[i] = make([]int, sparse[0].col)  }  //fmt.Println(chessMap)  // 遍历稀疏数组  for _, valNode := range sparse {  //跳过第一个,不然会数组越界  if valNode.Val == 0 {  continue  }  /*  或者 if index !=0 {         chessMap[valNode.row][valNode.col] = valNode.Val         }      */      chessMap[valNode.row][valNode.col] = valNode.Val  }  // 输出恢复后的数据  for _, v := range chessMap {  for _, v2 := range v {  print(v2)  }  println()  }  
}