HSP技术如何应用于双向链表和稀疏数组处理？

本文共计1869个文字，预计阅读时间需要8分钟。

双链表+双链表的基本用法（添加、删除、修改）与单链表的差异不大。双链表中的节点，多了一个指向前一个节点的pre指针，指向下一个节点的是next指针。双链表可以通过这两个指针方便地进行遍历和修改。具体代码可查看链接：https://pan.baidu.com/s/1%E2%80%9D

双向链表

双向链表的基本用法（添加，删除，修改）和单链表的相差不多。双向链表中的节点，多了一个pre，也就是指向前一个节点。具体可以查看代码。

链接：pan.baidu.com/s/1qD-4CQYYdpyeDHuUPy_qGg
提取码：10yl

稀疏数组

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

稀疏数组的处理方法

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

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

3. 稀疏数组列数只有3列。行数为原始二维数组的有效数据个数+1。

稀疏数组举例说明

转化思路 二维数组 转 稀疏数组的思路

1.遍历二维数组，得到有效数据的个数sum。 2.根据sum可以创建稀疏数组sparseArray in[sum+1][3] 3.将二维数组的有效数据存入到稀疏数组。 稀疏数组 转 原始的二维数组

1.先读取稀疏数组的第一行，根据第一行的数据，能够得到原始二维数组的大小和其中的有效数据的个数。 2.再读取稀疏数组的下面几行数据，并根据位置赋值给原始二维数组。 代码实现

public class SparseArray { public static void main(String[] args) { //创建一个原始的二维数组 11*11 //0：表示没有棋子，1：表示黑子，2：表示白子 int chessArray1[][] = new int[11][11]; chessArray1[1][2] = 1; chessArray1[2][3] = 2; //输出原始的二维数组 System.out.println("原始的二维数组--->"); for (int[] row : chessArray1) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } //将二维数组转化为稀疏数组 //1.先遍历二维数组，得到非0的数据的个数 int sum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArray1[i][j] != 0) { sum++; } } } //2.创建对应的稀疏数组 int sparseArray[][] = new int[sum + 1][3]; //给稀疏数组赋值 sparseArray[0][0] = 11; sparseArray[0][1] = 11; sparseArray[0][2] = sum; //遍历二维数组，将非0的值存放到sparseArray稀疏数组中 int count = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArray1[i][j] != 0) { count++; sparseArray[count][0] = i; sparseArray[count][1] = j; sparseArray[count][2] = chessArray1[i][j]; } } } //输出稀疏数组的形式 System.out.println(); System.out.println("稀疏数组--->"); for (int i = 0; i < sparseArray.length; i++) { System.out.printf("%d\t%d\t%d\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]); } //将稀疏数组恢复成原始二维数组 //1.先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组 int chessArray2[][] = new int[sparseArray[0][0]][sparseArray[0][1]]; //2.在读取稀疏数组后几行的数据（从第二行开始），并赋值给原始的二维数组 for (int i = 1; i < sparseArray.length; i++) { chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2]; } //输出恢复后的数组 System.out.println(); System.out.println("恢复后的数组--->"); for (int[] row : chessArray2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } }

要求：

​ 1) 在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data

​ 2) 恢复原来的数组时，读取 map.data 进行恢复

System.out.println("-------------------------------------------------------------"); System.out.println("-------------------------------------------------------------"); File file = new File( "F:\\Code\\Java_Code\\structures-algorithms\\data\\src\\sparsearray\\map.data"); //将稀疏数组写入到磁盘中的map.data try { FileOutputStream fos = new FileOutputStream(file); OutputStreamWriter osw = new OutputStreamWriter(fos, "UTF-8"); BufferedWriter bw = new BufferedWriter(osw); System.out.println("写入磁盘中···"); for (int i = 0; i < sparseArray.length; i++) { bw.write(sparseArray[i][0] + "," + sparseArray[i][1] + "," + sparseArray[i][2] + ","); } bw.close(); osw.close(); fos.close(); System.out.println("写入成功"); } catch (IOException e) { e.printStackTrace(); } //读取磁盘中的map.data,恢复稀疏数组。 try { System.out.println("读取中···"); FileInputStream fis = new FileInputStream(file);//读取文件的数据到字节流inputStream InputStreamReader isr = new InputStreamReader(fis, "UTF-8");//将字节流inputStream转换成字符流inputStreamReader StringBuffer sb = new StringBuffer(); while (isr.ready()) { //read()返回的是读取到的字节 sb.append((char) isr.read()); } isr.close(); fis.close(); System.out.println("读取成功"); String ss = sb.toString(); System.out.println("从磁盘中读取的字符串为:" + ss); System.out.println(); String[] str = sb.toString().split(","); //恢复稀疏数组 int[][] sparseArray2 = new int[str.length / 3][3]; //给稀疏数组赋值 int i = 0; for (String s : str) { sparseArray2[i / 3][i % 3] = Integer.parseInt(s); i++; } //输出还原后的稀疏数组 System.out.println("还原后的稀疏数组-->"); for (int[] sa2 : sparseArray2) { for (int data : sa2) { System.out.printf("%d\t", data); } System.out.println(); } System.out.println(); //再恢复成二维数组 int array[][] = new int[sparseArray2[0][0]][sparseArray2[0][1]]; //赋值给原始二维数组 for (i = 1; i < sparseArray2.length; i++) { array[sparseArray2[i][0]][sparseArray2[i][1]] = sparseArray2[i][2]; } System.out.println("恢复成二维数组-->"); for (int[] row : array){ for (int data:row){ System.out.printf("%d\t",data); } System.out.println(); } } catch (IOException e) { e.printStackTrace(); } 我实验中的问题 fileOutputStream、outputStreamWriter和bufferedWriter

FileOutputStream fileOutputStream = new FileOutputStream("d:/text.txt"); OutputStreamWriter outputStreamWriter = new OutputStreamWriter(fileOutputStream,"MS936"); BufferedWriter bufferedWriter = new BufferedWriter(outputStreamWriter); 如果只用FileOutputStream fileOutputStream = new FileOutputStream("d:/text.txt"); 不是也能输出到"d:/text.txt"吗？ 为什么要用其它两个呢？能起到什么作用呢？ FileOutputStream 是字节流，它一个字节一个字节的向外边送数据。 OutputStreamWrite 是字符流，它一个字符一个字符的向外边送数据。 它们有什么区别么？ 解析： 因为英文字符占一个字节，而中文是一个字符，占俩字节。 如果用stream，你读出来的英语再倒也罢了，读出来的中文可就是乱码或者一个个“？？？？”。 如果用WRITER，就不会有乱码了。 BufferedWriter Buffer是一个缓冲区，为什么要用BUFFER呢？ 如果你直接用stream或者writer，你的硬盘可能就是一个字符或者一个字节读写硬盘一次，可是你用了Buffer， 你的硬盘就是读了一堆数据之后，读写一下硬盘。这样对你硬盘有好处。 StringBuffer()的基本使用

1. StringBuffer: 线程安全的可变字符串
   • 我们如果对字符串进行拼接操作，每次拼接都会构成一个新的String对象，既耗时，又浪费空间
   • StringBuffer可以解决这个问题。
   • StringBuffer和String的区别？前者长度和内容可变，后者不可变
2. StringBuffer的添加功能
   • public StringBuffer append(String str)
     • 可以把任意类型数据添加到字符串缓冲区里面，并返回字符串缓冲区本身
   • public StringBuffer insert(int offset,String str)
     • 在指定位置把任意类型的数据插入到字符串缓冲区里面，并返回字符串缓冲区本身
3. StringBuffer其他使用