第一节：数据结构基本知识
1.1 什么是数据结构
例：写程序实现一个函数PrintN，使得传入一个正整数位N的参数后，能顺序打印从1道N的全部正整数。
代码1（循环实现）：
| 1 2 3 4 5 6 7 8 | void PrintN(int N){ int i; for(i =1; i<=N; i++) { printf("%d\n",i); } return; } |
代码2（递归实现）：
| 1 2 3 4 5 6 7 | void PrintN(int N){ if(N){ PrintN(N-1); printf("%d\n",N); } return; } |
结论：解决问题方法的效率，跟空间的利用率有关。
例3：写程序计算给定多项式在给定点x处的值
代码：
| 1 2 3 4 5 6 7 8 9 10 | 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。例子如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #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
复杂度为O(N3)
算法2：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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：分而治之
先将这个数组分为两半，分别递归的解决两边的问题。在左边我们会得到一个左边的最大值，右边会得到一个右边的最大值，然后再求一个跨越边界的最大子列和。然后对其进行比较，寻找到最大值。
图2
算法4：在线处理
代码：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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。
