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

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）最坏情况复杂度T_worst(n)；

（2）平均复杂度T_avg(n)。

3 复杂度的渐进表示法

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

T(n)=Ω(f(n))表示存在常数C>0，n₀>0使得当n≥n₀时有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）若两段算法分别有复杂度T₁(n)=O(f₁(n))和T₂(n)=O(f₂(n))，则

①两段代码的和T₁(n)+T₂(n)=max(O(f₁(n)), T₂(n)=O(f₂(n)))

②两段代码嵌套起来T₁(n)×T₂(n)=O(f₁(n)×f₂(n))。

（2）若T(n)是关于n的k阶多项式，那么T(n)= θ(n^k)。

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

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

1.3 应用实例

1.例1

复杂度为O(N³)

算法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(N²)

算法3：分而治之

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

 

图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。