链表
链表是一种由节点(Node)组成的线性数据集合，每个节点通过指针指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。
单链表：每个节点仅指向下一个节点，最后一个节点指向空(null)
双链表：每个节点有两个指针p,n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。
循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。
时间复杂度：
1.索引：O(n)
2.查找：O(n)
3.插入：O(1)
4.删除：O(1)
常规的删除算法思路：由于链表无法随机存储，只能从头到尾去遍历整个链表，遇到目标节点之后删除之，这样的话时间复杂度为O(n)。
但是如果我们直接找到要删除节点的下一个节点，不用遍历整个链表，只需把删除节点 i 的下一个节点 j 的内容复制到 i 上，然后把 i 的指针指向 j 的next，然后删除 j 节点，相当于删除了 i 节点，无需遍历整个链表，时间复杂度O(1)
插入算法思路：
1-140F9162221102.jpg
新节点的指针域指向 b ,老节点的指针域指向 x
栈
栈是一种动态集合，它是一种LIFO（last in first out后进先出）结构
栈的实现：
（1）数组
（2）链表
栈要记录的数据：
（1）栈顶位置top
注意这个top有两种理解方式，一种是表示栈的最后一个数据的位置，另一种是表示栈的最后一个数据的下一个位置，这两种理解对栈的操作代码有一定的影响
（2）栈最大大小size
栈的操作：
（1）STACK_EMPTY（）：判断栈是否为空
（2）PUSH（X）：向栈中添加一个值，注意栈是否为满的
（3）POP（）：从栈中弹出一个值，注意栈是否为空
image.png
队列
与栈不同，它是一种FIFO（first in first out先进先出）结构
队列的实现：
（1）数组
（2）链表
队列要记录的数据：
（1）队首位置head：第一个元素位置
（2）队尾位置tail：下一个元素要插入的位置（最后一个元素的下一个位置）
（3）队列最大大小size
队列的操作：
（1）ENQUEUE（x）：入队
（2）DEQUEUE（）：出队
（3）EMPTY（）：队列为空，head=tail
（4）FULL（）：队列为满，head=（tail+1）%size
image.png
树
树的种类：
（1）二叉树
二叉树要存储4个数据，分别是节点携带的信息和其父节点、左右子节点的指针。
（2）分支无限制的有根树：
上面二叉树每个节点最多有两个子节点，而分支无限制的有根数则没有这个限制，可能有3个、5个甚至更多子节点。所以存储这种数据结构的问题在于我们事先并不知道应该设置多少个child指针，若设置的少了不能满足要求，设置的过多又会浪费空间。所以这里提出一种新的描述这种数据结构的方法——左孩子右兄弟表示法，这种方法每个节点设置3个指针：父指针、从左数第一个孩子的指针、其右侧相邻的兄弟指针，如下图所示
image.png
二叉查找树图示
堆
堆实际上是以数组形式存储的二叉树
堆需要存储的数据:
（1）数组的大小max-size
（2）堆元素个数size，这里size要小于max-size
堆中元素通过坐标来确定父节点、左右子节点，具体来说：
一个节点i的父节点：[i/2]
一个节点i的左子节点：[i2]
一个节点i的右子节点：[i2+1]
堆的分类：
（1）最大堆
满足所有节点都比其父节点值小（小于等于）的堆
A[i/2]>=A[i]
（2）最小堆
满足所有节点都比其父节点值大（大于等于）的堆
A[i/2]<=A[i]
堆的操作：
（1）维护堆的性质（HEAPIFY）
这里指维护最大堆或最小堆的性质。假设一个数组中下标为i的节点的子节点满足最大（小）堆性质，但自身不一定满足这个性质，这时就需要HEAPIFY，具体来说是要比较这个节点和其两个子节点的大小，将其中的大（小）的和该节点位置交换，这样这个节点及其两个子节点就满足最大（小）堆的性质了，但是可能交换后子节点不满足堆的性质，所以这里要递归调用HEAPIFY，直到达到最下层节点，这样就维护了堆的性质。HEAPIFY耗时O（lgn）
（2）建堆（BUILD-HEAPIFY）
从中间那个元素开始到第一个元素，逐一调用HEAPIFY函数，即可完成建堆。
逐一从中间那个元素开始递减而不是从第一个元素递增，这时为了保证每次调用HEAPIFY都能保证该节点的子节点都满足最大（小）堆的性质，否则无法调用HEAPIFY。中间那个元素是第一个可能不满足最大（小）堆性质的节点，所以从这里开始维护（HEAPIFY）。一个建堆的例子如下所示：[5,3,17,10,84,19,6,22,9]
image.png
如何建一个最小堆，即将一个二叉树调整为最小堆？
[Heapify]http://www.lintcode.com/zh-cn/problem/heapify/
solution：堆实际上是以数组形式存储的二叉树(因此它的结构是固定的)，有add插入操作(logn)，poll弹出操作(logn)，查看peek操作(O(1))，如果为minheap，则peek出来最小值，如果为maxheap，则peek出来最大值
@ O(n)
public class Solution {
/*
* @param A: Given an integer array
* @return: nothing
*/
public void heapify(int[] A) {
// write your code here
for (int i = A.length / 2; i >= 0; i--) {
siftdown(A, i);
}
}
public void siftdown(int[] A, int k) {
while(k < A.length) {
int smallest = k;
if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
smallest = k * 2 + 1;
}
if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
smallest = k * 2 + 2;
}
if (smallest == k) {
break;
}
int temp = A[smallest];
A[smallest] = A[k];
A[k] = temp;
k = smallest;
}
}
}
更容易理解的版本，siftup
@ O(nlogn)
public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
private void siftup(int[] A, int k) {
while (k != 0) {
int father = (k - 1) / 2;
if (A[k] > A[father]) {
break;
}
int temp = A[k];
A[k] = A[father];
A[father] = temp;
k = father;
}
}
public void heapify(int[] A) {
for (int i = 0; i < A.length; i++) {
siftup(A, i);
}
}
}
网友评论