樊小文的数据结构与算法随笔(1)
穷竭搜索
递归函数
递归函数=>在一个函数中再次调用该函数本身的行为叫做递归,这样的函数称为递归函数.
例子一
n!=n*(n-1)!
转化↓
intfact(int n) {
if(n==0)return 1;
return n*fact(n-1);
}
例子二
an=an-1+an-2(n>1)
转化↓
intfib(int n){
if(n<=1)return n;
return fib(n-1)+fib(n-2);
}
记忆化↓
int memo[MAX_N+1];
int fib(int n){
if(n<=1)returnn;
if(nemo[n]!=0)returnmemo[n];
returnmemo[n]=fib(n-1)+fib(n-2);
}
穷竭搜索不是普通的算法,是一种思维。
栈和队列
栈
栈(Stack)是支持push和pop两种操作的数据结构。
push是在栈的顶端放入一组数据的操作。
pop是从其顶端取出一组数据的操作。
这意味着,最后放入的元素能够最先取出(LIFO: Last In First Out)。
队列
队列(Queue)亦是支持push和pop两种操作的数据结构。
不同的是,队列的pop完成的是取出底端一组数据的操作。
这意味着,最先放入的元素能够最先取出(FIFO: First In FirstOut)。