数据结构与算法导论之入门简介

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构与算法导论之入门简介

方瑞东 2014-11-29 11:15:00 浏览797
展开阅读全文

目前,计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据,这就给程序设计带来了一些新的问题。为了编写一个好的程序,必须分析待处理的对象的特征以及各处理对象之间存在的关系,这就是“数据结构”这门学科形成和发展的背景。

“数据结构”作为一门独立的课程,在国外是从1968年才开始设立的。


1、什么是数据结构?

答:大量数据的组织方法。


2、什么是算法分析?

答:算法运行时间的估计。


3、在学习数据结构和算法分析的过程中,最重要的就是解决以下2个问题:

一是对于大规模的输入,如何估计程序的运行时间,更重要的是,弄清如何在尚未具体编码的情况下比较两个程序的运行时间;

二是如何提高程序的运行速度以及确定程序瓶颈的技巧。


4、递归的介绍

当一个函数用自身定义时就称为是递归(recursive)的。

C++允许函数是递归的,但必须要记住,C++所做的仅仅是试图遵循递归思想,不是所有的数学递归函数都能被有效或者正确地用C++的递归模型来实现。要点在于,递归函数f应该像非递归函数一样只用几行就能表示出来。下面给出一个实例。

#include <iostream>
using namespace std;

int f( int x )
{
    if( x == 0 )
        return 0;
    else
        return 2 * f( x - 1 ) +  x * x;
}

int main( )
{
    cout << "f(5) = " << f( 5 ) << endl;
    return 0;
}

实验结果如下:


注意:为了使结果在窗口保留以便观察,可以在return 0前面加上“cin.get();”吐舌头小技巧~~~

从代码可以看出,f(0)=0是基准情况,C++的递归若无基准情况也是毫无意义的,因为递归调用将一直进行到基准情形出现为止。


关于递归有几个可能混淆的概念:

(1)、它是循环逻辑吗?

答案:不是。因为递归虽然用一个函数本身来定义这个函数,但是并没有用一个函数实例本身来定义该特定实例。举例说明,f(5)是通过f(5)得到的值才是循环的,使用f(4)得到的f(5)就不是循环的。

(2)、递归与循环的区别与联系?

答案:后面详解。


下面给出一个“无终止递归函数”实例:

#include <iostream>
using namespace std;

int bad( int n )
{
    if( n == 0 )
        return 0;
    else
        return bad( n / 3 + 1 ) + n - 1;
}

int main( )
{
    cout << "bad is infinite recursion" << endl;
    return 0;
}

bad(1)被定义为bad(1),因此永远得不到正解,除0之外,此程序对任何非负n都无效。

上面的讨论引出递归的前两个基本法则:基准情形(base cases)、不断推进(making progress)。其余两个是:设计法则(design rule)、合成效益法则(compound interest rule)。


下面给出一个“打印整数的递归”例程作为练习。

#include <iostream>
using namespace std;

void printDigit( int n )
{
    cout << n;
}

void printOut( int n )  // Print nonnegative n
{
    if( n >= 10 )
        printOut( n / 10 );
    printDigit( n % 10 );
}

int main(  )
{
    printOut( 1369 );
    cout << endl;
    return 0;
}



网友评论

登录后评论
0/500
评论
方瑞东
+ 关注