（一）数据结构和算法概论
数据结构在学什么？
1.如何用程序代码把现实世界的问题信息化
2.如何用计算机高效的处理这些信息从而创造价值
数据结构主要研究组织大量数据的方法；
算法分析主要是对算法运行时间和存储空间的评估。
数据：
数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原材料。
数据元素：
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
数据项：
一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
结构：各个元素之间的关系。
数据结构、数据对象：
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据的逻辑结构：
集合、线性结构、树形结构、图状结构（网状结构）
数据的存储结构：
顺序存储、链式存储、索引存储、散列存储
数据的运算：
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体步骤。
定义：
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中[数据结构]，以及在此基础上为实现某个功能（如查找或删除某个元素）而执行的相应操作[算法]。
数据结构=个体+个体的关系
l数据对象在计算机中的组织方式
u逻辑结构
u物理存储结构
l数据对象必定与一系列加在其上的操作相关联
l完成这些操作所用的方法就是算法
算法（解题的方法和步骤）=对存储数据的操作：
l一个有限指令集
l接受一些输入（有些情况下不需要输入）
l产生输出
l一定在有限步骤后终止
l每一条指令必须
n有充分明确的目标，不可以有歧义
n计算机能处理的范围之内
n描述应不依赖于任何一种计算机语言以及具体的实现手段
关于数据组织：解决问题方法的效率，跟数据的组织方式有关；
关于空间使用：解决问题方法的效率，跟空间的利用效率有关；
关于算法效率：解决问题方法的效率，跟算法的巧妙程度有关。
例：写程序计算给定多项式在给定点x处的值
f(x)=a0+a1x+…+an-1xn-1+anxn
doublef(intn,doublea[],doublex)
{
inti;
doublep=a[0];
for(i=1;i=n;i++)
p+=(a*pow(x,i));
returnp;
}
f(x)=a0+x(a1+x(…(an-1+x(an))…))
doublef(intn,doublea[],doublex)
{
intI;
doublep=a[n];
for(i=n;i0;i--)
p=a[i-1]+x*p;
returnp;
}
clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clocktick,即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟打点数。
#includestdio.h#includetime.hclock_tstart,stop;//clock_t是clock()函数返回的变量类型doubleduration;//记录被测函数运行时间，以秒为单位intmain(void){//不在测试范围内的准备工作写在clock()调用之前start=clock();//开始计时MyFunction();//把被测函数加在这里stop=clock();//停止计时duration=((double)(stop–start))/CLK_TCK;//计算运行时间//其他不在测试范围的处理写在后面，例如输出duration的值return0;}
让被测函数重复运行充分多次，使得测出的总的时钟打点间隔充分长，最后计算被测函数平均每次运行的时间即可！
#includestdio.h#includetime.h#includemath.h……#defineMAXK1e7//被测函数最大重复调用次数……intmain(void){……start=clock();for(i=0;iMAXK;i++)//重复调用函数以获得充分多的时钟打点数f1(MAXN-1,a,1.1);stop=clock();duration=((double)(stop–start))/CLK_TCK/MAXK;//计算函数单次运行的时间printf(“ticks1=%f\n”,(double)(stop–start));printf(“duration1=%6.2e\n”,duration);……return0;}
抽象数据类型
l数据类型
u数据对象集
u数据集合相关联的操作集
l抽象：描述数据类型的方法不依赖于具体实现
u与存放数据的机器无关
u与数据存储的物理结构无关
u与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
衡量算法的标准：
1.时间复杂度（大概程序要执行的次数而非时间，因为机器不同，它的执行时间也会不同，导致结果并不统一）
O(1)o(logspan=""2n)o(n)o(nlogspan=""2n)span=""O(n2)o(nspan=""3)o(2span=""n)o(n!)span=""O(nn)/o(n!)/o(2/o(n/o(n)o(nlog/o(log
2.空间复杂度（算法执行过程中，大概所占用的最大内存）[1、2条最为重要]
3.难易程度
4.健壮性
数据结构的地位
数据结构是软件中最核心的课程
程序=数据的存储（数据结构）+数据的操作（算法）+可以被计算机执行的语言
（二）数学知识复习
2.对数
在计算机科学中，除非有特别声明，所有对数都是以2为底的。
3.级数
4.模运算
5.证明方法
归纳法
反证法
（三）递归简论
当一个函数用它自己来定义时就称为是递归的。
基本法则：1.基准情形2.不断推进3.设计法则4.合成效益法则
/*写一个程序，printn()函数，使得传入一个正整数n，顺序打印1到n全部正整数*///循环实现#includestdio.hvoidprintn(intt);voidprintn(intt){inti;for(i=1;i=t;++i)span=""{printf("%d\n",i);}return;}intmain(void){intn;scanf("%d",n);printn(n);return0;}
//递归实现#includestdio.hvoidprintn(intt);voidprintn(intt){if(t){printn(t-1);printf("%d\n",t);}return;}intmain(void){intn;scanf("%d",n);printn(n);return0;}//递归到十万就罢工了卧槽望湖楼下水如天下