题目一 认识哈希函数和哈希表

哈希函数

一、性质

1. 哈希函数的输入域是无限大的；
2. 哈希函数的输出域是有穷尽的；
3. 输入如果一样，输出一定一样；
4. 哈希碰撞：输入不一样，也可能得到输出一样的值；（因为输入域无穷大，输出域有限大，所以必然会产生冲突；)
5. 哈希函数的离散性：也就是输出域每个值被输出的概率都差不多一样大；

二、特征

1. 输出的值和输入没有关系；保证它结果是均匀出现的；

三、找到一千个独立的哈希函数

独立的意思在于一个哈希函数不会随着一个的变化而变化；

题目一 实现二叉树的先序、中序、后序遍历

包括递归方式和非递归方式

递归方式遍历

非递归遍历

先序遍历

1. 自行准备一个栈，判断头节点非空时，将头节点压入栈中
2. 以下部分循环：直到栈为空；
   1. 弹出节点，输出
   2. 判断是否有右孩子，有的话压入栈中
   3. 判断是否有左孩子，有的话压入栈中
3. 打印换行，结束

题目一：用数组结构实现大小固定的队列和栈

栈与队列的数据结构都是很熟悉的了；

栈

具体在这里他们的实现：栈的实现涉及：压栈，出栈，返回栈顶元素，返回栈元素个数等等；在栈满时压栈会报错；在栈空时出栈会报错；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public static class ArrayStack {
    private Integer [] arr;
    private Integer size;
    public ArrayStack(int initSize) {
        if (initSize < 0){
            throw new IllegalArgumentException("The init size is less than 0");
        }
        arr = new Integer[initSize];
        size = 0;
    }

    public Integer peek() {
        if (size == 0){
            return null;
        }
        return arr[size - 1];
    }

    public void push(int obj) {
        if (size == arr.length){
            throw new ArrayIndexOutOfBoundsException("The Stack is full");
        }
        arr[size++] = obj;
    }

    public Integer pop() {
        if (size == 0){
            throw new ArrayIndexOutOfBoundsException("The stack is empty");
        }
        return arr[--size];
    }
}

2.1 关系数据库的结构

• 关系数据库由表（table）的集合构成，每个表有唯一的名字；

• 关系模型的术语中，关系用来指代表，而元组用来指代行。属性指代的是表中的列；

• 用关系实例来表示一个关系的特性实例，也就是所包含的一组特定的行；

• 对于关系的每个属性，都存在一个允许取值的集合，成为这个属性的域；如果域中元素被看作不可再分的单元，则域是原子的；（就是一个属性不能再被多个属性表示）

• 空 （null）指是一个特殊的值，表示值未知或不存在；空值会给数据库访问和更新带来很多困难。

2.2 关系数据库模式

​ 需区分 数据库模式 和 数据库实例；前者是数据库的逻辑设计，后者是给定时刻数据库中数据的一个快照；

​ 关系对应于程序设计语言中变量的概念；

​ 关系模式 的概念对应于程序设计语言中类型定义的概念；关系模式由属性序列及各属性对应域组成；

​ 当关系被更新时，关系实例的内容也随时间发生了变化。相反，关系的模式是不常变化的；

1.2 数据库系统的目标

文件处理系统中存储组织信息的主要弊端包括：

• 数据的冗余和不一致
• 数据访问困难
• 数据孤立
• 完整性问题
• 原子性问题
• 并发访问异常
• 安全性问题

1.3 数据视图

​ 数据库系统的一个主要目的是给用户提供数据的抽象视图，就是说，系统隐藏关于数据存储和维护的某些细节；

1.3.1 数据抽象

系统要能高效地检索数据。而这促使设计者再数据库中使用复杂的数据结构来表示数据；

许多用户不懂计算机，需要系统开发人员通过如下几个层次对用户屏蔽复杂性：

标准SQL是非过程化的查询语言，具有操作统一，面向集合、功能丰富、使用简单等多项优点；

但它的缺点在于——缺少流程控制能力，难以实现应用业务中的逻辑控制；所以引入了SQL编程；

3.1 MySQL编程基础

需要将频繁使用的业务逻辑封装成存储程序；

MySQL提供了用于编写结构化程序的数据类型、常量、变量、运算符和表达式等；

3.1.1 常量与变量

程序本身不能改变的数据成为常量；程序运行中可以改变其值的数据成为变量；

1. 常量

常量的格式取决于其数据类型，常用的常量包括字符串常量、数值常量、日期和时间常量、布尔值常量和NULL值；

1）字符串常量

​ 用单引号与双引号括起来的字符序列。推荐使用单引号；

2）数值常量

2.1 SQL语言介绍

SQL（Structured Query Language）语言是一种在关系数据库中定义和操纵数据的标准语言，是用户与数据库之间进行交流的接口。

2.1.1 SQL数据库的体系结构

SQL语言支持关系数据库的三级模式、二级映像的结构，二级映像保证了数据库的数据独立性；

SQL的关系数据库具有的特点：

1. SQL用户可以是应用程序，也可以是终端用户。（嵌入应用程序中，也可以直接访问）
2. SQL用户可以用SQL语言对基本表和视图进行查询。
3. 一个视图是从若干基本表或其他视图上导出的表。在数据库中只存放该视图的定义，不存放该视图所对应的数据。数据都是来自于基本表。视图是一个虚表；
4. 一个或一些基本表对应一个数据文件
   • 一个基本表也可以放在若干数据文件中。
   • 一个数据文件对应存储设备上的一个存储文件；
5. 一个基本表可以带若干索引。索引也放在数据文件中。
6. 一个表空间可以由若干数据文件组成；
7. 一个数据库可以由多个存储文件组成；

快速排序

1
2
3
4
5
6

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return;
    }
    quickSort(arr, 0, arr.length-1);
}

1.1 数据库系统概述

1.1.2 数据库系统的概念

数据库的总目标就是使用户能有效且方便的管理和使用数据库数据。

1. 数据（Data）

数据是数据库存储的基本对象；描述现实世界中各种具体事务或抽象概念的、可存储并具有明确意义的符号记录。

2. 数据库（Database. DB）

数据库是长期存储在计算机内、有组织的、可共享的（1）大量数据的集合。数据库中的数据按一定的数据模型组织，描述和存储，具有（2）较小的冗余、（3）较高的数据独立性和（4）易扩展性。

3. 数据库管理系统（Database Management System， DBMS）

数据库管理系统是数据库系统的核心；

它位于用户和操作系统之间的一层数据库管理软件；

它为用户或应用程序提供访问数据库的方法，包括数据库的（1）定义、（2）建立、（3）查询、（4）更新及各种数据控制等。

快速排序

问题一：partition

给定一个数组$arr$， 和一个数$num$，请把小于等于$num$的数放在数组的左边，大于$num$的数放在数组的右边。

要求额外空间复杂度 $O(1)$ , 时间复杂度$O(N)$;

解决答案