2018-04-03 1,021 views 2

数据结构【浙江大学】（第1节）整理

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

1.1 什么是数据结构

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

代码1（循环实现）：

void&nbsp;PrintN(int&nbsp;N){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=1;&nbsp;i&lt;=N;&nbsp;i++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;%d\n&quot;,i);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;
}

void PrintN(int N){

       int i;

       for(i =1; i<=N; i++)

       {

              printf("%d\n",i);

       }

       return;

}

代码2（递归实现）：

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

void PrintN(int N){

       if(N){

              PrintN(N-1);

              printf("%d\n",N);

       }

       return;

}

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

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

代码：

double&nbsp;f(int&nbsp;n,&nbsp;double&nbsp;a[],&nbsp;double&nbsp;x)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;double&nbsp;p&nbsp;=&nbsp;a[n];
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=n;i&gt;0;i--)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;a[i-1]+x*p;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;p;
}

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

#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
n²	1	4	16	64	256	1024
n³	1	8	64	512	4096	32768
2ⁿ	1	4	16	256	65536	4294967296
n!	1	2	24	40326	2092278988000	2631310³³*

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

复杂度分析小窍门：

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

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

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