vlambda博客
学习文章列表

樊小文的数据结构与算法随笔(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)。