【算法】数据结构和算法理论基础

数组

1. 数组基本概念

在一片连续的内存地址上同意类型的数据集合。

二维数组在C++中内存地址是连续的，但是Java中不是。

Java 中 int[5] [6] 是5个行首指针放在一个连续组里面大小为5，然后各自指向一条连续的6空间。

所以是5*6的连续空间

Java中是每一行当一个，然后每行的头是连续内存。

链表

链表基础

1. 单链表

2. 双链表

3. 循环链表

4. 存储方式

非连续

5. 链表节点的定义

codes：

在下面

6. 链表的操作

a. 删除

直接：前.next = next.next;

java 会自己清除 D；

b. 添加

code:

7. 链表和数组的对比

---

Hash 表

哈希表

键值对。

通过key可以很快的访问value。

一般 Hash Table 都是用来快速判断一个元素是否出现在集合里。

牺牲空间换时间

哈希函数

一个函数：把你输入的东西转换成 哈希表 中的下标。

哈希碰撞

拉链法

哈希表大小为 tableSize

数据规模为 dataSize

要控制tableSize 的大小

达到一个：

即不让太多数组空着浪费，又不会链表太长查找麻烦。

线性试探法

前提：tableSize > dataSize

第二个放的人，这个冲突了就尝试放下一个。

下一个不行就继续下一个。

常见的三种哈希结构

• 数组
• set（集合）
• map（映射）