[数据结构与算法]数据结构（java）

数据结构的笔记整理，方便后期的复习

一、概述

1.数据结构(data structure)是一门研究组织数据方式的学科

2.程序 = 数据结构 + 算法

3.数据结构是算法的基础

• 数据结构包括线性结构和非线性结构

• 1.线性结构

  （1）线性结构是最常用的数据结构，特点为数据元素之间存在一对一的线性关系

  （2）线性结构有两种不同的存储结构：顺序存储结构（数组）和链式存储结构（链表）

  （3）链表的存储元素不一定连续，元素节点存放的数据元素以及相邻元素的地址信息。

  （4）线性结构常见的有：数组、队列、链表和栈

• 2.非线性结构

  非线性结构包括：二维数组、多维数组、广义表、树结构和图结构

• 二、数组

• 1.一维数组
• java中一维数组的声明方式
• 数据类型[ ]? 数组名 = new 数据类型[元素个数]

2.二维数组

java中二维数组的声明方式

数据类型 [][]? 数组名 = new 数据类型[第一维长度][第二维长度]

在实际的计算机内存中是无法以矩阵方式存储，必须以线性方式，视为一维数组的扩展来处理，分为两种方式

（1）以行为主

第一列

存储方式：

先存第一行，存完第一行再存第二行。

数组A有m行n列。

假设a为数组A在内存中的起始地址，d为单位空间，那么数组元素A(I,j)与内存地址有下列关系:

（2）以列为主

存储方式：

先存第一行，存完第一行再存第二行。

数组A有m行n列。

假设a为数组A在内存中的起始地址，d为单位空间，那么数组元素A(I,j)与内存地址有下列关系:

• 三、稀疏数组

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

  稀疏数组的处理方法：

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

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

• 

  public class SparseArray {
      public static void main(String[] args) {
          //创建原始二维数组
          int chessArray[][] = new int[11][11];//初始化一个11行11列的二维数组
          chessArray[1][2] = 1;
          chessArray[1][3] = 4;
          chessArray[2][4] = 2;
          chessArray[3][4] = 3;
          //输出原始二维数组
          System.out.println("原始的二维数组为：");
          for (int[] row:chessArray) {
              for (int data:row) {
                  System.out.printf("%d\t",data);
              }
              System.out.println();
          }
  
          //将二维数组转化为稀疏数组
          //1.遍历二维数组，得到非0元素的个数
          int sum = 0;
          for (int[] row:chessArray) {
              for (int data:row) {
                  if (data != 0){
                      sum++;
                  }
              }
  
          }
          System.out.println(sum);
  
          //2.创建对应的稀疏数组
          //稀释数组第一行分别对应，二位数组总共多少行，多少列，多少个非0元素
          int sparseArray[][] = new int[sum+1][3];
          sparseArray[0][0] = chessArray.length;//总共多少行
          sparseArray[0][1] = chessArray[0].length;//总共多少列
          //System.out.println(chessArray[0].length);
          sparseArray[0][2] = sum;//多少个非0元素
          int row = 1;
          for (int i = 0; i < chessArray.length; i++) {
              for (int j = 0; j < chessArray[i].length; j++) {
                  if (chessArray[i][j] != 0){
                      sparseArray[row][0] = i;
                      sparseArray[row][1] = j;
                      sparseArray[row][2] = chessArray[i][j];
                      row++;
  
                  }
              }
  
          }
       //输出相应的稀疏数组
          System.out.println("得到的稀疏数组为：");
          for (int i = 0; i < sum+1; i++) {
              System.out.printf("%d\t %d\t %d\t\n",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
          }
  
          //将稀疏数组恢复为元素的二维数组
          //1、先读取稀疏数组的第一行，来确定二维数组的大小，创建原始的二维数组
          int  chessArray1[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
          //2、读取稀疏数组后面几行的数据（第二行开始），并将其赋值给二维数组
          //System.out.println(sparseArray.length);
          for (int i = 1; i < sparseArray.length ; i++) {
              chessArray1[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  
          }
          //输出恢复后的二维矩阵
          System.out.println("恢复后的二维矩阵：");
          for (int[] row1:chessArray1) {
              for (int data:row1) {
                  System.out.printf("%d\t",data);
              }
              System.out.println();
          }
      }
  
  }
  

  ?

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖