数据结构第一周笔记——基本概念(慕课浙大版本--XiaoYu)上

数据结构定义

1. 没有官方的定义，我选取慕课给出的3个定义中最通俗易懂的记录下来
   
2. 数据结构(data structure)是计算机中存储，组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法--中文维基百科三个例子

1. 例1：如何在书架上摆放图书
   
2. 二分查找：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

1. 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
   

3. 例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数
   

//循环实现

voidPrintN ( intN )

{

   inti;

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

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

   }

   return;

}

//递归实现  弊端：递归的程序对空间的占用有的时候是很恐怖的

voidPrintN ( intN )

{

   if( N ){

       printN( N-1 );

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

   }

   return;

}

//解决问题方法的效率，也跟空间的利用效率有关

4. 例3：写程序计算给定多项式在给定点x处的值
   
   网络异常，图片无法展示

   |

//直接翻译的结构

doublef( intn, doublea[], doublex)

{

   inti;

   doublep=a[0];

   for ( i=0 ; i<=n ; i++ ){

       p+= (a[i] *pow(x,i));

   }

   returnp;

}

//秦久邵的方法

doublef( intn, doublea[], doublex)

{

   inti;

   doublep=a[n]

       for( i=n ; i>0 ; i-- ){

           p=a[i-1] +x*p;

       }

   returnp;

}

4. 秦久邵的方法公式图
   
   网络异常，图片无法展示

   |

clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick,即"时钟打点"

常数CLK_TCK：机器时钟每秒所走的时钟打点数

//这套流程的模板

#include

#include

clock_tstart,stop;//clock_t是clock()函数返回的变量类型

doubleduration;//记录被测函数的运行时间

intmain()

{//不在测试范围内的准备工作写在clock()调用之前

   start=clock();//开始计时

   MyFunction();//把被测函数加在这里

   stop=clock();//停止计时

   duration= ((double)(stop-start))/CLK_TCK;//计算时间

   //其他不在测试范围的处理写在后面，例如输出duration的值

   return0;

}

尝试计算这个图中的式子跑了多久

#include

#include

#include

clock_tstart,stop;

doubleduration;

#define ,MAXN 10 //多项式最大项数，即多项式阶数+1

doublef1(intn , doublea[] , doublex);

doublef2(intn , doublea[] , doublex);

intmain()

{

   inti;

   doublea[MAXN];//存储多项式的系数

   for (i=0; i<MAXN; i++) a[i] = (double)i;

   

   //不在测试范围内的准备工作写在clock()调用之前

   start=clock();//开始计时

   f1(MAXN-1 , a , 1.1);//把被测函数加在这里

   stop=clock();//停止计时

   duration= ((double)(stop-start))/CLK_TCK;//计算时间

   //其他不在测试范围的处理写在后面，例如输出duration的值

   printf("ticks1 = %f\n",(double)(stop-start));

   printf("duration1 = %6.2e\n",duration);

   

   start=clock();//开始计时

   f2(MAXN-1 , a , 1.1);//把被测函数加在这里

   stop=clock();//停止计时

   duration= ((double)(stop-start))/CLK_TCK;//计算时间

   //其他不在测试范围的处理写在后面，例如输出duration的值

   printf("ticks1 = %f\n",(double)(stop-start));

   printf("duration2 = %6.2e\n",duration);

   

   

   return0;

}

//跑出来结果都是0，因为运行太快了，clock函数捕捉不到它的区别

//解决方案：让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可

以下是解决方案修改后的函数，只截取修改的部分

#define ,MAXK 1e7 //被测函数最大重复调用次数

doublef1(intn , doublea[] , doublex);

doublef2(intn , doublea[] , doublex);

intmain()

{

   inti;

   doublea[MAXN];//存储多项式的系数

   for (i=0; i<MAXN; i++)//重复调用函数以获得充分多的时钟打点数

       f1(MAXN-1,a,1.1);

   stop=clock();

   start=clock();//开始计时

   duration= ((double)(stop-start))/CLK_TCK/MAXK;//计算函数单词运行的时间

   //其他不在测试范围的处理写在后面，例如输出duration的值

   printf("ticks1 = %f\n",(double)(stop-start));

   printf("duration1 = %6.2e\n",duration);

   

   //以下第二个f2保持不变进行对比

   

   start=clock();//开始计时

   f2(MAXN-1 , a , 1.1);//把被测函数加在这里

   stop=clock();//停止计时

   duration= ((double)(stop-start))/CLK_TCK;//计算时间

   //其他不在测试范围的处理写在后面，例如输出duration的值

   printf("ticks1 = %f\n",(double)(stop-start));

   printf("duration2 = %6.2e\n",duration);

   

   

   return0;

}

解决问题方法的效率，跟算法的巧妙程度有关

什么是数据结构

1. 数据对象在计算机中的组织方式

1. 逻辑结构(一对多的逻辑结构有个名字叫做"树")=>树形结构    线性结构(一对一)图的结构(多对多)
   
2. 物理存储结构
   
3. 抽象数据类型(Abstract Data Type)

1. 数据类型

1. 数据对象集：就是我们说的"是什么东西"
   
2. 数据集合相关联的操作集
   

2. 抽象：描述数据类型的方法不依赖于具体实现

1. 与存放数据的机器无关
   
2. 与数据存储的物理结构无关
   
3. 与实现操作的算法和编程语言都无关只描述
   
4. 只描述数据对象集和相关操作集"是什么"，并不涉及"如何做到"的问题
   

2. 数据对象必定与一系列加在其上的操作相关联
   
3. 完成这些操作所用的方法就是算法
   

例4："矩阵"的抽象数据类型定义

1. 类型名称：矩阵(Matrix)
   

Multiply：乘的意思

a是矩阵元素的值：那要用二维数组去存他还是一维数组又或者是十字链表呢？答案是不用关心，我们需要的只是一个矩阵

Matrix Add(...)：先按行加？先按列加？使用什么语言？  答案是统统不管，这就是"抽象"

什么是算法

定义

1. 算法(Algorithm)

1. 一个有限指令集
   
2. 接受一些输入(有些情况不需要输入)
   
3. 一定至少会产生一个输出(否则就没有意义了)
   
4. 一定在有限步骤之后终止的，他不像是操作系统只要不关机就可以一直跑在上面
   
5. 描述算法的时候不能有无限循环的概念的
   
6. 每一条指令必须

1. 有充分明确的目标，不可以有歧义
   
2. 计算机能处理的范围之内(目标不可以太远大)
   
3. 描述手段应该"抽象"，不依赖于任何一种计算机语言以及具体的实现手段
   

2. 例1：选择排序算法的伪码描述
   

voidSelectionSort ( intList[], intN)

{

   //将N个整数List[0]...List[N-1]进行非递减排序

   for(i=0; i<N; i++){

       MinPosition=ScanForMin(List, i, N-1);

       //ist[i]到List[N-1]中找最小元，并将其位置赋给MinPosition;

       Swap(List[i],List[MinPosition]);

       //排序部分的最小元换到有序部分的最后位置;

   }

}

//这不是C语言，虽然他带有C语言的一些特征，但他for循环里面的内容是用自然语言来描述的.上面伪码描述特点：抽象

抽象----

   List到底是数组还是链表(虽然看上去很像数组)?其实不管是数组还是链表都不会报错

   Swap用函数还是用宏去实现(虽然他看上去很像一个函数)?但其实用宏写也可以，在我们使用算法的时候是不关心的

什么是好的算法？

1. 空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
   
2. 时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也跟输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
   

这个n是我们要处理的内容，这个程序所用的时间与空间都跟这个n是有直接关系的

//递归实现  弊端：递归的程序对空间的占用有的时候是很恐怖的

voidPrintN ( intN )

{

   if( N ){

       //假设N=10w，第一步就是10w-1，调用这个函数之前，你的系统需要把当前的这个函数所有的现有的状态都存到系统内存的某一个地方

       //原本是存一下使用后就可以删掉了，使用递归之后在你执行10w-99999之前要把前面所有的运算先执行一遍而不是直接10w-99999，一次性存这么多内容，内存会爆掉的

       //S(N)=C(常数)*N  =>线性增长

       printN( N-1 );

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

   }

   return;

}

借用上面例3的案例

//计算机算加减比算乘除快很多

//直接翻译的结构

doublef( intn, doublea[], doublex)

{

   inti;

   doublep=a[0];

   for ( i=0 ; i<=n ; i++ ){

       p+= (a[i] *pow(x,i));

   }

   returnp;

}//这里一共运行了(1+2+...+n)=(n²+n)/2次乘法        时间复杂度：T(n) = C1n² +C2n

//秦久邵的方法

doublef( intn, doublea[], doublex)

{

   inti;

   doublep=a[n]

       for( i=n ; i>0 ; i-- ){

           p=a[i-1] +x*p;

       }

   returnp;

}//这里一共就运行了n次乘法        时间复杂度：T(n) = C *n

复杂度的渐进表示法

“上界（upper bound）是一个与偏序集有关的特殊元素，指的是偏序集中大于或等于它的子集中一切元素的元素。若数集S为实数集R的子集有上界，则显然它有无穷多个上界，而其中最小的一个上界常常具有重要的作用，称它为数集S的上确界。”

太大的上界跟太小的下界对我们分析算法的时候是没有太大的帮助的，尽可能跟它的真实情况贴得越近越好

当我们在取大O的时候，我们一般取的是最小的那个上界。当我们在取Ω的时候通常是写的我们能力范围内找到的最大的那个下界

复杂度分析窍门

比如说，如果我们有两段算法，我们知道它们复杂度的上界是什么。如果把两段算法拼在一起的时候，总时间就是两段的和。

那么它们的上界，就是两个上界中间，比较大的那个

当我们把两段算法嵌套起来的时候，两个复杂度要相乘的时候，它的上界就是它们上界的乘积

通过这个我们可以知道如果T(n)是关于n的一个k阶多项式的话，真正起作用的只有最大的那一项 ，其他项都是可以忽略不计的

一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度，这是一个相乘的关系

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