数据结构与算法概论

• 数据结构绪论
  • 逻辑结构和物理结构
    • 逻辑结构
    • 物理结构
  • 数据类型
• 算法绪论
  • 算法特性
  • 算法设计的要求
    • 正确性
    • 可读性
    • 健壮性
    • 时间效率高和存储量低
  • 算法效率的度量方法
    • 事后统计方法
    • 事前分析估算方法
  • 函数的渐近增长
  • 算法时间复杂度
    • 算法时间复杂度定义
    • 推导大O阶方法
    • 常数阶O(1)
    • 线性阶O(n)
    • 对数阶O(logn)
    • 平方阶O(n^2)
  • 常见的时间复杂度
  • 最坏情况和平均情况
  • 算法空间复杂度
• 数据结构和算法的联系

数据结构绪论

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构和物理结构

按照视点的不同，我们把数据结构分为逻辑结构和物理结构。

逻辑结构

逻辑结构是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关心的问题。逻辑结构分为以下四种。

（1）集合结构

集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。数据结构中的集合关系就类似于数学中的集合。

（2）线性结构

线性结构中的数据元素之间是一对一的关系。

（3）树形结构

树型结构中的数据元素之间存在一种一对多的层次关系。

（4）图形结构

图形结构的数据元素是多对多的关系。

从之前的例子也可以看出，逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

物理结构

物理结构（存储结构）是指数据的逻辑结构在计算机中的存储形式。

数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

数据元素的存储结构形式有两种：顺序存储和链式存储。

（1）顺序存储结构

顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。 典型的顺序存储结构就是数组。

（2）链式存储结构

链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

显然链式存储就灵活多了，数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它了。

数据类型

数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

在C语言中，按照取值的不同，数据类型可以分为两类：

• 原子类型：不可再分解的类型，包括整型、实型、字符型等。
• 结构类型：由若干个类型组合而成，是可以再分解的。例如整型数组是由若干整型数据组成的。

抽象是指抽取出事物具有的普遍性的本质。它是抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节，只保留实现目标所必需的信息。

抽象数据类型（Abstract Data Type，ADT）：一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

实际上，抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个小规模且容易处理的问题，然后建立一个计算机能处理的数据类型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。

为了便于在之后的讲解中对抽象数据类型进行规范的描述，我们给出了抽象数据类型的标准格式：

ADT 抽象数据类型名
Data
	数据元素之间逻辑关系的定义
Operation
	操作1
		初始条件
		操作结构描述
	操作2
		...
	操作3
		...
endADT

算法绪论

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

算法具有零个或多个输入，有一个或多个输出。

有穷性只算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成。

确定性：算法的每一步骤都要具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。

可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。

算法设计的要求

正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题得需求，能够得到问题的正确答案。

但是算法得”正确“通常在用法上有很大的差别，大体上分为以下四个层次。

（1）算法程序没有语法错误。

（2）算法程序对于合法的输入数据能够产生满足要求的输出结果。

（3）算法程序对于非法的输入数据能够得出满足规格说明的结果。

（4）算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

一般情况下，我们把层次（3）作为一个算法是否正确的标准。

可读性

算法设计的另一目的是为了便于阅读、理解和交流。

健壮性

当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

时间效率高和存储量低

设计算法应该尽量满足时间效率高和存储量低的需求。

算法效率的度量方法

事后统计方法

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编写的程序的运行时间进行比较，从而确定算法效率的高低。

这种方法有多种缺陷，我们考虑不予采纳。

事前分析估算方法

事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行统计。

一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。

最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

函数的渐近增长

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N,f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)。

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

算法时间复杂度

算法时间复杂度定义

在进行算法分析时，语句总的执行次数T(n)是关于问题规模的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的函数。

这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

if ( A > B ) {
    for ( i=0; i<N; i++ )
        for ( j=N*N; j>i; j-- )
            A += B;
}
else {
    for ( i=0; i<N*2; i++ )
        for ( j=N*2; j>i; j-- )
            A += B;
}

这段代码时间复杂度为$O(N^3)$

推导大O阶方法

（1）用常数1取代运行时间中的所有加法常数。

（2）在修改后的运行次数函数中，只保留最高阶项。

（3）如果最高阶项存在且其系数不是1，则去除与这个项相乘的系数。得到的结果就是大O阶。

常数阶O(1)

不管算法运行次数常数是多少，我们都记作O(1)，而不能是O(3)、O(12)等其他任何数字。

线性阶O(n)

要分析算法的复杂度，关键就是要分析循环结构的运行情况。

int i,sum;
sum=0;
for(i=0;i<n;i++)
	sum+=i;

对数阶O(logn)

int count=1;
while(count<n)
	count=count*2;

平方阶O(n^2)

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

下面这个程序的时间复杂度为O(m*n)

int i,j;
for(i=0;i<m;i++)
{
	for(j=0;j<n;j++)
	{
		/*时间复杂度为O(1)的程序步骤序列*/
	}
}

下面这个程序的时间复杂度为O(n^2)

int i,j;
for(i=0;i<n;i++)
{
	for(j=i;j<n;j++)
	{
		/*时间复杂度为O(1)的程序步骤序列*/
	}
}

常见的时间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

最坏情况和平均情况

平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。也就是说，我们运行一段程序代码时，是希望看到平均运行时间的。可现实中，平均运行时间很难通过分析得到，一般都是通过一定数量的实验数据后估算出来的。

对于算法的分析，一种方法是计算所有情况的平均值，这种时间复杂度的计算方法被称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法被称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数。

数据结构和算法的联系

由放书问题得出了下面的结论：

打印1-N这N个数的循环写法和递归写法运行结果不同，得出了下面的结论：

计算多项式，普通写法和秦久韶算法有着明显的区别。

计时的基本程序如下：

#include <stdio.h>
#include <time.h>

clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被调函数运行时间——以秒为单位
void MyFunction()
{

}
int main()
{
    printf("%d\n",CLK_TCK);//本机每秒所走的时钟打点数为1000
    start = clock();
    MyFunction();
    stop = clock();
    duration = ((double)(stop-start))/CLK_TCK;
    printf("%f\n",duration);
}

#include <stdio.h>
#include <math.h>
#include <time.h>

clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被调函数运行时间——以秒为单位

#define MAXN 10    //多项式最大项数，即多项式阶数+1
double f1(int n,double a[],double x);
double f2(int n,double a[],double x);

int main()
{
    int i;
    double a[MAXN];    //存储多项式的系数
    for(i=0;i<MAXN;i++) a[i] = double(i);
    return 0;
}

这个程序第18行为何会报错error: expected expression before 'double'？

double(i)应该写成(double)i。。。。。

此外在C语言中，CLK_TCK 是一个过时的宏定义，代表每秒的时钟计时单元数。在新的标准中，该宏定义已被废弃。可以直接使用 CLOCKS_PER_SEC 来代替 CLK_TCK。

所以，将计算duration的代码修改为以下形式：

duration = ((double)(stop - start))/CLOCKS_PER_SEC;

单次运行代码如下：

#include <stdio.h>
#include <math.h>
#include <time.h>

clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被调函数运行时间——以秒为单位

#define MAXN 10    //多项式最大项数，即多项式阶数+1
double f1(int n,double a[],double x);
double f2(int n,double a[],double x);

int main()
{
    int i;
    double a[MAXN];    //存储多项式的系数
    for(i=0;i<MAXN;i++)
        a[i] = (double)i;

    start = clock();
    f1(MAXN,a,1.1);
    stop = clock();
    //duration = ((double)(stop-start))/CLK_TCK;
    duration = ((double)(stop - start))/CLOCKS_PER_SEC;
    printf("ticks1 = %f\n",(double)(stop - start));
    printf("duration1 = %6.2e\n", duration);

    start = clock();
    f2(MAXN,a,1.1);
    stop = clock();
    duration = ((double)(stop - start))/CLOCKS_PER_SEC;
    //duration = ((double)(stop-start))/CLK_TCK;
    printf("ticks1 = %f\n",(double)(stop - start));
    printf("duration1 = %6.2e\n", duration);

    return 0;
}

double f1(int n,double a[], double x)
{
    int i;
    double p = a[0];
    for(i=1;i<=n;i++)
        p+=(a[i]*pow(x,i));
    return p;
}

double f2(int n,double a[], double x)
{
    int i;
    double p = a[n];
    for(i=n;i>0;i--)
        p+=(a[i-1]+x*p);
    return p;
}

ticks1 = 0.000000
duration1 = 0.00e+000
ticks1 = 0.000000
duration1 = 0.00e+000

多项式阶数太低，两个程序运行时间都不到一个tick，几乎没有差别。

多次重复运行代码如下：

#include <stdio.h>
#include <math.h>
#include <time.h>

clock_t start,stop;
//clock_t是clock()函数返回的变量类型
double duration;
//记录被调函数运行时间——以秒为单位

#define MAXN 10    //多项式最大项数，即多项式阶数+1
#define MAXK 1e7  //被测函数最大重复调用次数
double f1(int n,double a[],double x);
double f2(int n,double a[],double x);

int main()
{
    int i;
    double a[MAXN];    //存储多项式的系数
    for(i=0;i<MAXN;i++)
        a[i] = (double)i;

    start = clock();
    for(i=1;i<MAXK;i++)       //重复调用函数以获得充分多的时钟打点数
        f1(MAXN,a,1.1);
    stop = clock();
    //duration = ((double)(stop-start))/CLK_TCK;
    duration = ((double)(stop - start))/CLOCKS_PER_SEC/MAXK;    //计算函数单次运行的时间
    printf("ticks1 = %f\n",(double)(stop - start));
    printf("duration1 = %6.2e\n", duration);

    start = clock();
    for(i=1;i<MAXK;i++)       //重复调用函数以获得充分多的时钟打点数
        f2(MAXN,a,1.1);
    stop = clock();
    //duration = ((double)(stop-start))/CLK_TCK;
    duration = ((double)(stop - start))/CLOCKS_PER_SEC/MAXK;    //计算函数单次运行的时间
    printf("ticks1 = %f\n",(double)(stop - start));
    printf("duration1 = %6.2e\n", duration);


    return 0;
}

double f1(int n,double a[], double x)
{
    int i;
    double p = a[0];
    for(i=1;i<=n;i++)
        p+=(a[i]*pow(x,i));
    return p;
}

double f2(int n,double a[], double x)
{
    int i;
    double p = a[n];
    for(i=n;i>0;i--)
        p+=(a[i-1]+x*p);
    return p;
}

ticks1 = 2092.000000
duration1 = 2.09e-007
ticks1 = 443.000000
duration1 = 4.43e-008

两个程序运行时间差了一个数量级！由此可见：