第一节:数据结构基本知识

1.1 什么是数据结构

例:写程序实现一个函数PrintN,使得传入一个正整数位N的参数后,能顺序打印从1道N的全部正整数。

代码1(循环实现):

void PrintN(int N){       int i;       for(i =1; i<=N; i++)       {              printf("%d\n",i);       }       return;}

代码2(递归实现):

void PrintN(int N){       if(N){              PrintN(N-1);              printf("%d\n",N);       }       return;}

结论:解决问题方法的效率,跟空间的利用率有关。

例3:写程序计算给定多项式在给定点x处的值

代码:

double f(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;}

C语言中提供了一个函数为clock(),它捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时钟单位是clock tick。常熟CLK_TCK为机器时钟每秒所周的clock tick。例子如下:

#include <stdio.h>#include <time.h>clock_t start,stop;/*clock_t是clock()函数返回的变量类型*/double duration; int main(){       start = clock();       MyFunction();//所需要测量运行时间的函数       stop = clock();       duration = ((double)(stop-start)/CLK_TCK;       return 0;}

结论:解决问题方法的效率,跟算法的巧妙程度有关。

什么是数据结构?

数据对象在计算机中的组织方式。数据对象必定与一系列加在其上面的操作相关联,完成这项操作所用的方法就是算法。

抽象数据类型

抽象是指:描述数据类型的方法不依赖与具体事项,它:

与存放数据的机器无关;与数据存储的物理结构无关;与实现操作的算法和编程语言均无关。

它只描述数据对象集和相关操作集“是什么”,并不涉及“如何做”的问题。

1.2 算法

1.什么是算法?

算法是:

(1)一个有限指令集;

(2)接受一些输入(有时候也没有输入);

(3)产生输出;

(4)一定在有限步骤后终止;

(5)每一条指令必须:有充分明确的目标,不可以有歧义;计算机能够处理的范围之内;描述应不依赖于任何一种计算机语言以及具体的实现

2.什么是好的算法?

在分析一般算法的效率时,我们经常关注一下两种复杂度:

(1)最坏情况复杂度Tworst(n);

(2)平均复杂度Tavg(n)。

3 复杂度的渐进表示法

T(n)=O(f(n))表示存在常数C>0,n0>0使得当n≥n0时有T(n)≤Cf(n);

T(n)=Ω(f(n))表示存在常数C>0,n0>0使得当n≥n0时有T(n)≥Cf(n);

T(n)=θ(h(n))表示同时又T(n)= O(f(n))和T(n)=Ω(f(n))。

不同复杂度函数的感性理解,如表1.1所示。

1.1 不同复杂度函数的规模

函数

1

2

4

8

16

32

1

1

1

1

1

1

1

logn

0

1

2

3

4

5

n

1

2

4

8

16

32

nlogn

0

2

8

24

64

160

n2

1

4

16

64

256

1024

n3

1

8

64

512

4096

32768

2n

1

4

16

256

65536

4294967296

n!

1

2

24

40326

2092278988000

26313*1033

如果复杂度为灰色斜体的部份,要想办法尽可能降到黑色部分。

复杂度分析小窍门:

(1)若两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n)),则

两段代码的和T1(n)+T2(n)=max(O(f1(n)), T2(n)=O(f2(n)))

两段代码嵌套起来T1(n)×T2(n)=O(f1(n)×f2(n))。

(2)若T(n)是关于n的k阶多项式,那么T(n)= θ(nk)。

(3)一个for循环的时间复杂度等于循环次数乘循环体内代码的复杂度。

(4)if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度,总体复杂度取三者中最大。

1.3 应用实例

1.例1

1522767675424103.jpg

复杂度为O(N3)

算法2:

int MaxSubseqSum2(int A[], int N){       int ThisSum, MaxSum=0;       int i ,j;       for(i=0;i<N;i++)/*i是子列左端的位置*/       {              ThisSum =0;/*ThisSum是从A[i]dao A[j]的子列和*/              for(j=i; j<N;j++)              {                     ThisSum+=A[j];                     /*对于相同的i,不同的j,只要把j-1此循环的基础上累加1项即可*/                     if(ThisSum>MaxSum)                     MaxSum=ThisSum;              }       }       return MaxSum;}

复杂度为O(N2)

算法3:分而治之

先将这个数组分为两半,分别递归的解决两边的问题。在左边我们会得到一个左边的最大值,右边会得到一个右边的最大值,然后再求一个跨越边界的最大子列和。然后对其进行比较,寻找到最大值。

1522767648119445.jpg 

图2

算法4:在线处理

代码:

int MaxSubseqSum4(int A[], int N){       int ThisSum, MaxSum;       int i;       ThisSum=MaxSum=0;       for(i=0;i<N;i++){              ThisSum +=A[i];/*向右累加*/              if(ThisSum>MaxSum)                     MaxSum=ThisSum;/*发现更大和则更新当前结果*/              else if(ThisSum<0)/*如果当前子列和为负*/                  ThisSum=0;/*则不可能使后面的部分和增大,抛弃之*/       }       return MaxSum;}

复杂度为O(N)

为了理解这个算法,举个例子来走一遍过程。假设一组数字为:

序号

0

1

2

3

4

5

6

7

取值

-1

3

-2

4

-6

1

6

-1

刚开始,我们就令ThisSum和MaxSum为0。进入for循环。

i取值

步骤

ThisSum

MaxSum

0

ThisSum为-1,-1<0,故抛弃这个值

0

0

1

然后ThisSum加上A[1],由于之前ThisSum令为0了,所以现在值为3。然后ThisSum>MaxSum,所以把ThisSum赋值给MaxSum,后者等于3。

3

3

2

然后ThisSum加上A[2],当前和为+1,然后MaxSum>ThisSum,所以不赋值,由于ThisSum为+1,故不抛弃。

+1

3

3

ThisSum加上A[3],结果为5,然后ThisSum>MaxSum,所以把ThisSum赋值给MaxSum,后者等于5

+5

5

4

ThisSum加上A[4],结果为-1。此时ThisSum小于MaxSum,所以不改变Max的值。又由于This<0,故赋值为0。

0

5

5

ThisSum加上A[5],值为1,此时ThisSum小于MaxSum,所以不改变Max的值。

1

5

6

ThisSum加上A[6],值为7,此时ThisSum大于MaxSum,所以把ThisSum赋值给MaxSum,后者等于7

7

7

7

ThisSum加上A[7],值为6,此时ThisSum小于MaxSum,所以不改变Max的值。

6

7

 

故最大值为7。