Qeuroal's Blog

静幽正治

基本术语

二叉树性质

  1. 在二叉树得第i(i >= 1)层最多有$2^{i-1}$个节点
  2. 深度为k(k>=1)的二叉树上至多含$2^k-1$个节点
  3. 对任何一颗二叉树,若它含有$n_0$个叶子节点、$n_2$个度为2得节点,则必存在关系式:$n_0=n_2+1$
  4. 具有n个节点的完全二叉树的深度为$\lfloor{\log{_2n}+1} \rfloor$
  5. 若对含n个节点的完全二叉树从上到下且从左到右进行1至n的编号,则对完全二叉树中任意一个编号为i的结点(简称为结点i),有以下关系:
    1. 若i=1,则结点i是二叉树的根,无双亲节点;若i>1,则结点$\lfloor{i/2} \rfloor $为其双亲结点
    2. 若2i>n,则节点i无左孩子;否则结点2i为其左孩子;
    3. 若2i+1>n,则结点i无右孩子;否则,结点2i+1为其右孩子。

定义

  1. 树(Tree)是n(n >= 0 )个结点的有限集。n = 0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(root)的结点;(2)在 n > 1 时,其余结点可分为m(m > 0)个互不相交的有限集 $T_1, T_2, T_3 … T_m$,其中每一个集合本身又是一颗树,并且称为根的子树(SubTree)。

  2. n > 0时根结点是唯一的,不可能存在多个根结点。

  3. m > 0时,子树的个数没有限制,但他们一定是互不相交的。

  4. 结点用用改的子树数称为结点的度。

  5. 度为0的结点称为叶子结点或终端结点;度不为0的结点称为非终端结点或分支结点。

  6. 除根结点之外,分支结点称为内部节点。

  7. 树的度是树内各结点度的最大值。

为什么$n$个结点的树,有$n - 1$条边

  1. 假设有1个结点时,则有0条边
  2. 有2个结点时,若是连通的且不能为环,所以就得有$1$条边将这两个结点连接在一起
  3. 若有3个结点时,将前两个看为一个整体,则必须有$1$条边,将这两个部分连接在一起
  4. 以此类推

【释】:整体化一思想

  1. 内存单元从0开始编号,称为内存地址。每个内存单元可以看作一间房间,内存地址就是门牌号。

数据类型

基本数据类型/原始类型(primitive type)

  1. 用于保存简单的单个数据
  2. 首字母一般小写
  3. 基本数据类型:
    1. int (4B)
      Java的整型数字中间可以加入下划线以便用户识别。
    2. short (2B)
    3. long (8B)
    4. byte (1B)
    5. float (4B)
      1. 对于float类型,需要加上f后缀,如: float f = 3.14e5f;
      2. float类型可最大表示 $3.4 \times 10^{38}$
    6. double (8B)
      float类型可最大表示 $1.79 \times 10^{308}$
    7. boolean (1B)

      Java语言对布尔类型的存储并没有做规定,因为理论上存储布尔类型只需要1 bit,但是通常JVM内部会把boolean表示为4字节整数。

    8. char (2B)
      1. 布尔类型boolean只有true和false两个值
      2. 字符类型char表示一个字符。Java的char类型除了可表示标准的ASCII外,还可以表示一个Unicode字符,如: char a = '中';
      3. 注意char类型使用单引号’,且仅有一个字符,要和双引号”的字符串类型区分开。
  4. 引用类型
    1. 除了上述基本类型的变量,剩下的都是引用类型。例如,引用类型最常用的就是String字符串: String s = "hello";
    2. 引用类型的变量类似于C语言的指针,它内部存储一个“地址”,指向某个对象在内存的位置.

    通俗的解释:引用类型的变量赋值,先申请内存存放内容,然后变量再指向它,若改变变量的值,则会再重新申请内存,放入内容,再将变量指向这块内存,原来的内存还在只不过无法通过变量指向它罢了。

  5. 常量
> 1. 定义变量的时候,如果加上final修饰符,这个变量就变成了常量

   
1
2
3
4
final double PI = 3.14; // PI是一个常量
double r = 5.0;
double area = PI * r * r;
PI = 300; // compile error!
> 2. 常量在定义时进行初始化后就不可再次赋值,再次赋值会导致编译错误。 > 3. 常量的作用是用有意义的变量名来避免魔术数字(Magic number),例如,不要在代码中到处写3.14,而是定义一个常量。如果将来需要提高计算精度,我们只需要在常量的定义处修改,例如,改成3.1416,而不必在所有地方替换3.14。 > 4. 根据习惯,常量名通常全部大写。
  1. var关键字
> 1. 有些时候,类型的名字太长,写起来比较麻烦。例如:`StringBuilder sb = new StringBuilder();`, 这个时候,如果想省略变量类型,可以使用var关键字: `var sb = new StringBuilder();`,编译器会根据赋值语句自动推断出变量sb的类型是StringBuilder。对编译器来说,语句:`var sb = new StringBuilder();`,实际上会自动变成:`StringBuilder sb = new StringBuilder();`
> 2. 使用var定义变量,仅仅是少写了变量类型而已。
  1. 定义变量时,要遵循作用域最小化原则,尽量将变量定义在尽可能小的作用域,并且,不要重复使用变量名。

  2. 整数运算

    1. 整数的数值表示不但是精确的,而且整数运算永远是精确的,即使是除法也是精确的,因为两个整数相除只能得到结果的整数部分
    2. 特别注意:整数的除法对于除数为0时运行时将报错,但编译不会报错
    3. 要特别注意,整数由于存在范围限制,如果计算结果超出了范围,就会产生溢出,而溢出不会出错,却会得到一个奇怪的结果
    4. 自增/自减、+=-=*=/=:同C++
    5. 移位运算
      1. >>: 根据符号位来补充
      2. 无符号的右移运算>>>: 它的特点是不管符号位,右移后高位总是补0
    6. 位运算
      1. 与运算: &
      2. 或运算: |
      3. 非运算: ~
      4. 异或运算: ^
  3. 运算优先级

    • ()
    • ! ~ ++ --
    • * / %
    • + -
    • << >> >>>
    • &
    • |
    • += -= *= /=
  4. 浮点数运算

    1. 浮点数运算会产生误差

      浮点数运算和整数运算相比,只能进行加减乘除这些数值计算,不能做位运算和移位运算。在计算机中,浮点数虽然表示的范围大,但是,浮点数有个非常重要的特点,就是浮点数常常无法精确表示。

      举个栗子:

      浮点数0.1在计算机中就无法精确表示,因为十进制的0.1换算成二进制是一个无限循环小数,很显然,无论使用float还是double,都只能存储一个0.1的近似值。但是,0.5这个浮点数又可以精确地表示。

      因为浮点数常常无法精确表示,因此,浮点数运算会产生误差:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      public class Main {
      public static void main(String[] args) {
      double x = 1.0 / 10;
      double y = 1 - 9.0 / 10;
      // 观察x和y是否相等:
      System.out.println(x);
      System.out.println(y);
      }
      }

      结果为:

      1
      2
      0.1
      0.09999999999999998
    2. 溢出

      整数运算在除数为0时会报错,而浮点数运算在除数为0时,不会报错,但会返回几个特殊值:

      1. NaN表示Not a Number
      2. Infinity表示无穷大
      3. Infinity表示负无穷大
        如:
      1
      2
      3
      double d1 = 0.0 / 0; // NaN
      double d2 = 1.0 / 0; // Infinity
      double d3 = -1.0 / 0; // -Infinity
  5. 布尔运算

    1. 布尔运算是一种关系运算,包括以下几类:
      • 比较运算符:>,>=,<,<=,==,!=
      • 与运算 &&
      • 或运算 ||
      • 非运算 !
    2. 关系运算符的优先级从高到低依次是
      • !
      • >,>=,<,<=
      • ==,!=
      • &&
      • ||
    3. 短路运算、三元运算符:同C++
  6. 字符与字符串

    1. 字符类型

      Java在内存中总是使用Unicode表示字符,所以,一个英文字符和一个中文字符都用一个char类型表示,它们都占用两个字节。要显示一个字符的Unicode编码,只需将char类型直接赋值给int类型即可

      1
      2
      int n1 = 'A'; // 字母“A”的Unicodde编码是65
      int n2 = '中'; // 汉字“中”的Unicode编码是20013
    2. 字符串类型

      和char类型不同,字符串类型String是引用类型,我们用双引号"..."表示字符串。一个字符串可以存储0个到任意个字符:

      1. 常见的转义字符包括:

        • \" 表示字符"
        • \' 表示字符'
        • \\ 表示字符\
        • \n 表示换行符
        • \r 表示回车符
        • \t 表示Tab
        • \u#### 表示一个Unicode编码的字符
      2. 字符串连接

        Java的编译器对字符串做了特殊照顾,可以使用+连接任意字符串和其他数据类型,这样极大地方便了字符串的处理。例如:

        1
        2
        3
        4
        5
        6
        7
        8
        public class Main {
        public static void main(String[] args) {
        String s1 = "Hello";
        String s2 = "world";
        String s = s1 + " " + s2 + "!";
        System.out.println(s);
        }
        }

        如果用+连接字符串和其他数据类型,会将其他数据类型先自动转型为字符串,再连接:

        1
        2
        3
        4
        5
        6
        7
        public class Main {
        public static void main(String[] args) {
        int age = 25;
        String s = "age is " + age;
        System.out.println(s);
        }
        }
      3. 多行字符串

        如果我们要表示多行字符串,使用+号连接会非常不方便:

        从Java 13开始,字符串可以用”””…”””表示多行字符串(Text Blocks)了。举个例子:

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        public class Main {
        public static void main(String[] args) {
        String s = """
        SELECT * FROM
        users
        WHERE id > 100
        ORDER BY name DESC
        """; // 因为""" 换行了,所以相当于在 DESC 后面加了一个\n
        System.out.println(s);
        }
        }

        如果多行字符串的排版不规则,总是以最短的行首空格为基准。

      4. 不可变特性

        String s = “hello”;时,JVM虚拟机先创建字符串”hello”,然后,把字符串变量s指向它:紧接着,执行s = “world”;时,JVM虚拟机先创建字符串”world”,然后,把字符串变量s指向它:原来的字符串”hello”还在,只是我们无法通过变量s访问它而已。因此,字符串的不可变是指字符串内容不可变。

        理解了引用类型的“指向”后,试解释下面的代码输出:

        1
        2
        3
        4
        5
        6
        7
        8
        public class Main {
        public static void main(String[] args) {
        String s = "hello";
        String t = s;
        s = "world";
        System.out.println(t); // t是"hello"还是"world"?
        }
        }
      5. 空值null

        引用类型的变量可以指向一个空值null,它表示不存在,即该变量不指向任何对象。例如:

        1
        2
        3
        4
        String s1 = null; // s1是null
        String s2; // 没有赋初值值,s2也是null
        String s3 = s1; // s3也是null
        String s4 = ""; // s4指向空字符串,不是null

        注意要区分空值null和空字符串””,空字符串是一个有效的字符串对象,它不等于null。

  7. 数组

    1. 定义一个数组类型的变量,使用数组类型 类型[],例如,int[]。和单个基本类型变量不同,数组变量初始化必须使用new int[5]表示创建一个可容纳5个int元素的数组。

    2. Java的数组有几个特点:

      • 数组所有元素初始化为默认值,整型都是0,浮点型是0.0,布尔型是false;
      • 数组一旦创建后,大小就不可改变。
    3. 数组大小:数组变量.length

    4. 数组是引用类型,在使用索引访问数组元素时,如果索引超出范围,运行时将报错

    5. 在定义数组时直接指定初始化的元素,这样就不必写出数组大小,而是由编译器自动推算数组大小

    6. 对于数组ns来说,执行ns = new int[] { 68, 79, 91, 85, 62 };时,它指向一个5个元素的数组;再执行ns = new int[] { 1, 2, 3 };时,它指向一个新的3个元素的数组:但是,原有的5个元素的数组并没有改变,只是无法通过变量ns引用到它们而已。

    7. 字符串数组

      1
      2
      3
      String[] names = {
      "ABC", "XYZ", "zoo"
      };

      对names[1]进行赋值,例如names[1] = "cat";,原来names[1]指向的字符串”XYZ”并没有改变,仅仅是将names[1]的引用从指向”XYZ”改成了指向”cat”,其结果是字符串”XYZ”再也无法通过names[1]访问到了。

      相当于引用嵌套引用

    8. 遍历数组

      1. 方法1

        1
        2
        3
        4
        for (int i=0; i<ns.length; i++) {
        int n = ns[i];
        System.out.println(n);
        }
      2. 方法2: for each 循环

        1
        2
        3
        4
        int[] ns = { 1, 4, 9, 16, 25 };
        for (int n : ns) {
        System.out.println(n);
        }

        变量n直接拿到ns数组的元素,而不是索引。

        若想直接打印ns,可以这么做:System.out.println(Arrays.toString(ns));

    9. 排序数组

      1. 冒泡排序

      2. Java的标准库已经内置了排序功能: Arrays.sort(),例如:

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        import java.util.Arrays;

        public class Main {
        public static void main(String[] args) {
        int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        // 排序前:
        System.out.println(Arrays.toString(ns));
        // 排序
        Arrays.sort(ns);
        // 排序后:
        System.out.println(Arrays.toString(ns));
        }
        }
        1. 当我们调用Arrays.sort(ns);后,变量ns指向的数组内容已经被改变了
        2. 如果对一个字符串数组(String[] ns = { "banana", "apple", "pear" };)进行排序,原来的3字符串在内存中均没有任何变化,但是ns数组的每个元素指向变化了
    10. 多维数组

      1. 例子

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        public class Main {
        public static void main(String[] args) {
        int[][] ns = {
        { 1, 2, 3, 4 },
        { 5, 6, 7 },
        { 9, 10, 11, 12 }
        };
        int[] arr1 = ns[1];
        System.out.println(arr0.length); // 4
        }
        }

        实际上arr1就获取了ns数组的第1个元素。因为ns数组的每个元素也是一个数组,因此,arr1指向的数组就是{ 5, 6, 7 }

      2. 遍历

        1
        2
        3
        4
        5
        6
        7
        for (int[] arr : ns) {
        for (int n : arr) {
        System.out.print(n);
        System.out.print(', ');
        }
        System.out.println();
        }
      3. 小结

        • 二维数组就是数组的数组,三维数组就是二维数组的数组;
        • 多维数组的每个数组元素长度都不要求相同;
        • 打印多维数组可以使用Arrays.deepToString();
        • 最常见的多维数组是二维数组,访问二维数组的一个元素使用array[row][col]
  8. 命令行参数

    Java程序的入口是main方法,而main方法可以接受一个命令行参数,它是一个String[]数组。

    这个命令行参数由JVM接收用户输入并传给main方法:

    1
    2
    3
    4
    5
    6
    7
    public class Main {
    public static void main(String[] args) {
    for (String arg : args) {
    System.out.println(arg);
    }
    }
    }

    我们可以利用接收到的命令行参数,根据不同的参数执行不同的代码。例如,实现一个-version参数,打印程序版本号:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static void main(String[] args) {
    for (String arg : args) {
    System.out.println(arg);
    if ("-version".equals(arg)) {
    System.out.println("v 1.0");
    } else if ("-test".equals(arg)) {
    System.out.println("test");
    }
    }
    }

    上面这个程序必须在命令行执行,我们先编译它: javac Main.java

    然后,执行的时候,给它传递一个-version参数:java Main -version -version -test

  9. I/O

    1. 输出

      1. 输出语句
        • System.out.println()
        • System.out.printf()
      2. 占位符
        占位符 说明
        %d 格式化输出整数
        %x 格式化输出十六进制整数
        %f 格式化输出浮点数
        %e 格式化输出科学计数法表示的浮点数
        %s 格式化字符串

        注意,由于%表示占位符,因此,连续两个%%表示一个%字符本身。

      占位符本身还可以有更详细的格式化参数。下面的例子把一个整数格式化成十六进制,并用0补足8位:

    2. 输入

      1. import语句导入java.util.Scannerimport是导入某个类的语句,必须放到Java源代码的开头
      2. 创建 Scanner 对象并传入 System.in。System.out 代表标准输出流,而System.in代表标准输入流。直接使用System.in读取用户输入虽然是可以的,但需要更复杂的代码,而通过Scanner就可以简化后续的代码。
      3. Scanner对象后,要读取用户输入的字符串,使用scanner.nextLine(),要读取用户输入的整数,使用scanner.nextInt()Scanner会自动转换数据类型,因此不必手动转换。
        例如:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      import java.util.Scanner;

      public class Main {
      public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in); // 创建Scanner对象
      System.out.print("Input your name: "); // 打印提示
      String name = scanner.nextLine(); // 读取一行输入并获取字符串
      System.out.print("Input your age: "); // 打印提示
      int age = scanner.nextInt(); // 读取一行输入并获取整数
      System.out.printf("Hi, %s, you are %d\n", name, age); // 格式化输出
      }
      }
    3. 使用占位符构建字符串,并打印

      1
      2
      String <name> = String.format("%-10d%d", 20, 25)
      System.out.println(<name>)
阅读全文 »

  • AT 计划在计算机上运行的命令和程序。
  • ATTRIB 显示或更改文件属性。
  • BREAK 设置或清除扩展式 CTRL+C 检查。
  • CACLS 显示或修改文件的访问控制列表(ACLs)。
  • CALL 从另一个批处理程序调用这一个。
  • CD 显示当前目录的名称或将其更改。
  • CHCP 显示或设置活动代码页数。
  • CHDIR 显示当前目录的名称或将其更改。
  • CHKDSK 检查磁盘并显示状态报告。
  • CHKNTFS 显示或修改启动时间磁盘检查。
  • CLS 清除屏幕。
  • CMD 打开另一个 Windows 命令解释程序窗口。
  • COLOR 设置默认控制台前景和背景颜色。
  • COMP 比较两个或两套文件的内容。
  • COMPACT 显示或更改 NTFS 分区上文件的压缩。
  • CONVERT 将 FAT 卷转换成 NTFS。您不能转换当前驱动器。
  • COPY 将至少一个文件复制到另一个位置。
  • DATE 显示或设置日期。
  • DEL 删除至少一个文件。
  • DIR 显示一个目录中的文件和子目录。
  • DISKCOMP 比较两个软盘的内容。
  • DISKCOPY 将一个软盘的内容复制到另一个软盘。
  • DOSKEY 编辑命令行、调用 Windows 命令并创建宏。
  • ECHO 显示消息,或将命令回显打开或关上。
  • ENDLOCAL 结束批文件中环境更改的本地化。
  • ERASE 删除至少一个文件。
  • EXIT 退出 CMD.EXE 程序(命令解释程序)。
  • FC 比较两个或两套文件,并显示不同处。
  • FIND 在文件中搜索文字字符串。
  • FINDSTR 在文件中搜索字符串。
  • FOR 为一套文件中的每个文件运行一个指定的命令。
  • FORMAT 格式化磁盘,以便跟 Windows 使用。
  • FTYPE 显示或修改用于文件扩展名关联的文件类型。
  • GOTO 将 Windows 命令解释程序指向批处理程序中某个标明的行1. 。
  • GRAFTABL 启用 Windows 来以图像模式显示扩展字符集。
  • HELP 提供 Windows 命令的帮助信息。
  • IF 执行批处理程序中的条件性处理。
  • LABEL 创建、更改或删除磁盘的卷标。
  • MD 创建目录。
  • MKDIR 创建目录。
  • MODE 配置系统设备。
  • MORE 一次显示一个结果屏幕。
  • MOVE 将文件从一个目录移到另一个目录。
  • PATH 显示或设置可执行文件的搜索路径。
  • PAUSE 暂停批文件的处理并显示消息。
  • POPD 还原PUSHD保存的当前目录的上一个值。
  • PRINT 打印文本文件。
  • PROMPT 更改Windows命令提示符。
  • PUSHD 保存当前目录,然后对其进行更改。
  • RD 删除目录。
  • RECOVER 从有问题的磁盘恢复可读信息。
  • REM 记录批文件或CONFIG.SYS中的注释。
  • REN 重命名文件。
  • RENAME 重命名文件。
  • REPLACE 替换文件。
  • RMDIR 删除目录
  • SET 显示、设置或删除Windows环境变量。
  • SETLOCAL 开始批文件中环境更改的本地化。
  • SHIFT 更换批文件中可替换参数的位置。
  • SORT 对输入进行分类。
  • START 启动另一个窗口来运行指定的程序或命令。
  • SUBST 将路径跟一个驱动器号关联。
  • TIME 显示或设置系统时间。
  • TITLE 设置CMD.EXE会话的窗口标题。
  • TREE 以图形模式显示驱动器或路径的目录结构。
  • TYPE 显示文本文件的内容。
  • VER 显示Windows版本。
  • VERIFY 告诉Windows 是否验证文件是否已正确写入磁盘。
  • VOL 显示磁盘卷标和序列号。
  • XCOPY 复制文件和目录树。
  • appwiz.cpl 添加删除程序
  • control userpasswords2 用户帐户设置
  • cleanmgr 垃圾整理
  • CMD 命令提示符可以当作是Windows的一个附件
  • Ping,Convert这些不能在图形环境下使用的功能要借助它来完成。
  • cmd jview察看Java虚拟机版本。
  • command.com 调用的则是系统内置的NTVDM,一个DOS虚拟机。它完全是一个类似VirtualPC的虚拟环境,和系统本身联系不大。当我们在命令提示符下运行 DOS程序时,实际上也是自动转移到NTVDM虚拟机下,和CMD本身没什么关系。
  • calc 启动计算器
  • chkdsk.exe Chkdsk磁盘检查
  • compmgmt.msc 计算机管理
  • conf 启动netmeeting
  • control userpasswords2 User Account 权限设置
  • devmgmt.msc 设备管理器
  • diskmgmt.msc 磁盘管理实用程序
  • dfrg.msc 磁盘碎片整理程序
  • drwtsn32 系统医生
  • dvdplay 启动Media Player
  • dxdiag DirectX Diagnostic Tool
  • gpedit.msc 组策略编辑器
  • gpupdate /target:computer /force 强制刷新组策略
  • eventvwr.exe 事件查看器
  • explorer 打开资源管理器
  • logoff 注销命令
  • lusrmgr.msc 本机用户和组
  • msinfo32 系统信息
  • msconfig 系统配置实用程序
  • net start (servicename) 启动该服务
  • net stop (servicename) 停止该服务
  • notepad 打开记事本
  • nusrmgr.cpl 同control userpasswords,打开用户帐户控制面板
  • Nslookup IP地址侦测器
  • oobe/msoobe /a 检查系统是否激活
  • perfmon.msc 计算机性能监测程序
  • progman 程序管理器
  • regedit 注册表编辑器
  • regedt32 注册表编辑器
  • regsvr32 /u *.dll 停止dll文件运行
  • route print 查看路由表
  • rononce -p 15秒关机
  • rsop.msc 组策略结果集
  • rundll32.exe rundll32.exe %Systemroot%System32shimgvw.dll,ImageView_Fullscreen 启动一个空白的Windows图片和传真查看器
  • secpol.msc 本地安全策略
  • services.msc 本地服务设置
  • sfc /scannow 启动系统文件检查器
  • sndrec32 录音机
  • taskmgr 任务管理器(适用于2000/xp/2003)
  • tsshutdn 60秒倒计时关机命令
  • winchat XP自带局域网聊天
  • winmsd 系统信息
  • winver 显示About Windows窗口
  • wupdmgr Windows Update
  • mspaint:打开画图
  • calc:打开计算器
  • winver:检查window版本
  • mstsc:远程桌面连接
  • write:写字板
  • mem.exe:显示内存的使用情况
  • notepad:打开记事本
0%