数据结构和算法分析：第一章引论

今天药忘吃喽~ 2022-05-11 15:16 269阅读 0赞

# 1.2 数学知识和复习 #

## 1.2.1 指数 ##

![在这里插入图片描述][70]

## 1.2.2 对数 ##

![在这里插入图片描述][70 1]  
![在这里插入图片描述][70 2]

## 1.2.3 级数 ##

![在这里插入图片描述][70 3]  
![在这里插入图片描述][70 4]

## 1.2.4 模运算 ##

![在这里插入图片描述][70 5]

## 1.2.5 证明的方法 ##

1.  归纳法证明：用归纳法进行的证明有两个标准的部分。第一步是证明**基准情形**，就是确定定理对于某个（某些）小的值得正确性。接着就是**归纳假设**。一般来说，它指的就是假设定理对直到某个有限数k得所有得情况都是成立的。
2.  反证法证明：反证法证明就是通过假设定理不成立，然后证明该假设导致某个已知的性质不成立，从而原假设是不成立的。

# 1.3 递归简论 #

当一个函数用它自己来定义时就称为**递归**的。

当编写递归程序时，关键是要记住递归的四条基本准则：
    1. 基准情形。
    2. 不断推进。
    3. 设计法则。
    4. 合成效益法则。

# 1.4 实现泛型构件 pre-Java5 #

面向对象的一个重要目标就是对代码的重用的支持。支持这一目标的一个重要机制就是**泛型机制**。如果除去对象的基本类型之外，实现方法是相同的，那么我们就可以用**泛型实现**。

## 1.4.1 使用Object表示泛型 ##

![在这里插入图片描述][70 6]

## 1.4.2 基本类型的包装 ##

![在这里插入图片描述][70 7]

## 1.4.3 使用接口类型来表示泛型 ##

![在这里插入图片描述][70 8]

## 1.4.4 数组类型的兼容性 ##

Person[] arr=new Employee[5];
    arr[0] = new Student(...);

Java中的数组类型是类型兼容的。这种叫做**协变数组类型**。  
Employee 和 Student 都是继承于Person类的

# 1.5 使用Java5泛型特性来实现泛型构件 #

## 1.5.1 简单的泛型类和泛型接口 ##

![在这里插入图片描述][70 9]

## 1.5.2 自动拆箱/拆箱 ##

Java5矫正了这个情形。如果一个int类型变量被传递到Integer变量对象的地方，那么，编译器将在幕后插入一个对Integer构造方法的调用。这就叫做**自动装箱**。而如果Integer对象被放到需要int类型的地方，则编译器将在幕后插入一个对intValue方法的调用这就叫做**自动拆箱**

## 1.5.3 菱形运算符 ##

![在这里插入图片描述][70 10]

## 1.5.4 带有限制符号的通配符 ##

Java中数组是协变的。但是泛型集合不是协变的。Java5中可以使用通配符来弥补这种不足。  
![在这里插入图片描述][70 11]

## 1.5.5 泛型static方法 ##

![在这里插入图片描述][70 12]

## 1.5.6 类型限界 ##

![在这里插入图片描述][70 13]

## 1.5.7 类型擦除 ##

泛型在很大程度上是Java语言的成分而不是虚拟机的结构。泛型类可以由编译器 通过所谓的**类型擦除**过程而转变为非泛型类。这样，编译器就生成一种与泛型类同名的原始类，但是类型参数都被删除了。

# 1.6 函数对象 #

一种将函数作为参数传递的独创方法是注意到对象既包含数据也包含方法，于是我们可以定义一个没有数据而只有一个方法的类，并传递该类的一个实列。事实上，一个函数通过将其放在一个对象内部而被传递。这样的对象就叫做一个函数对象。  
![在这里插入图片描述][70 14]

[70]: /images/20220505/3fe11a2cf5854ed1becdc1a2a9eff01e.png
[70 1]: /images/20220505/9372990740384d4ab0fbe94c8fa7bfc0.png
[70 2]: /images/20220505/65bee69a41284c59a54bfd99a6ac7a07.png
[70 3]: /images/20220505/9f9dd2ec504642b9a03cc8f2173ef12e.png
[70 4]: /images/20220505/00cb7e4a7c764699be9a45992a15a9f9.png
[70 5]: /images/20220505/3133dcc36ceb4d4c8845940a74869bce.png
[70 6]: /images/20220505/78902c7499f74108b931c8cbfffeba43.png
[70 7]: /images/20220505/15fe533a5a4848548286f79e9513b5c9.png
[70 8]: /images/20220505/9edc09c77ee64553860b8d83ece390b4.png
[70 9]: /images/20220505/65b16b6c9d1b49b0a4d2d7768a3bc15e.png
[70 10]: /images/20220505/662842290d8b4457b869af5c28ce8a06.png
[70 11]: /images/20220505/f68cd9e706c84aa49617bcece4d6d13e.png
[70 12]: /images/20220505/50bb99cbd6b240b9a76a1f7985bafa03.png
[70 13]: /images/20220505/3a5b62021cc440378ce38134011e6073.png
[70 14]: /images/20220505/d72ff3e3f29147e1bf6cffe98a0e1d5d.png