[理学]第01讲绪论.ppt

数据结构;课程重要性：;Essential of Lecture One ：;例1：书目自动检索系统;例2：人机对弈问题;/ (root);C; 求解非数值计算的问题; 数据结构课程的形成和发展; 数据结构课程所处的地位;二、数据结构基本概念;二、数据结构基本概念;二、数据结构基本概念;;数据的逻辑结构;例：集合结构;一种数据结构 linearity =（D，R） D = {01,02,03,04,05,06,07,08,09,10,} R = {05,01,01,03,03,08,08,02,02,07,07,04,04,06,06,09,09,10} 数据元素之间的联系： 1:1;例：树结构;例：图结构;01;数据的存储结构;顺序存储——借助元素在存储器中的相对位置来 表示数据元素间的逻辑关系 链式存储——借助指示元素存储地址的指针表示 数据元素间的逻辑关系;实战: ;四、抽象数据类型;四、抽象数据类型;ADT的两个重要特征;五、算法分析 (Algorithm);算法的描述方法 用自然语言描述算法 用流程图描述算法 用数学语言或约定的符合语言描述算法 用C++的函数形式来描述算法; 算法着重体现思路和方法，程序着重体现计算机的实现 程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，算法中的指令无此限制 一个算法若用计算机语言来书写，它就可以是一个程序;算法评价标准; 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：;①、x++;s=0; 基本操作是加法及赋值 T(n)=O(2)=O(1) ②、for (i=1;i=n;i++) {x++;s+=x;} 问题规模为n，基本操作是加法及赋值 操作次数为f(n)=n+n T(n)=O(f(n))=O(n+n)=O(2n)=O(n);③、for( i=1;i=n;i++) for (j=1;j=n; j++) { x++; s+=x; } 2n2 问题规模为n，基本操作是加法及赋值 操作次数为f(n)=n*n+n*n T(n)=O(f(n))=O(2n2)=O(n2) ;for(i=1;i=n;i++) for(j=1;j=n;j++) { c[i][j]=0; for(k=1;k=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } ;for (i=1;in;i++) { y=y+1; for (j=0; j=(2*n); j++) x++; };/* 1 * /;实战:;4、填空 给出以下算法的时间复杂度 。 x=n; y=0; while(x=(y+1)*(y+1)) y++;;本讲小结;Astronomy POJ 3101 题目大意： 有n个行星，它们的轨道是同一平面上的同向同心圆，且它们始终做匀速圆周运动，周期ti已知。 所有卫星都处于过圆心的某条直线上的现象，称为卫星平行。 求相邻两次卫星平行现象的间隔时间，用分数表示。;see you later!