数据结构研究的内容.ppt

1、第一讲：数据结构及其研究的内容Data Structure Curriculum int age; bool sex; char position20; char pos_rank20; char department20; RecordType ;,数据在计算机中表示方式： 顺序映像（顺序存储结构）：以相 对的存储位置表示后继 关系。如前述的职工档案管理程序，所有职工的纪录组成一张表，这张表就使一个顺序存储结构。计算机在为这张表分配存储空间时分配一个连续的存储空间。 非顺序映像（链式存储结构）：,链式存储结构里相邻节点间的具体存储位置不是一个顺序关系，查询节点需要借助于指针。 在不同的编程环

2、境中， 存储结构可有不同的描 述方法。当用高级程序 设计语言进行编程时， 通常可用高级编程语言 中提供的数据类型描述 之。,5、数据类型： 在程序设计时，我们必须先对变量进行声明，不同的数据类型他的取值范围不同，施加其上的操作也不同： 如：整型 （int） 取值范围：-32768 32767 可行的操作：+，-，*，/，% 对于浮点型来说，不可以进行% 操作。,数据类型 是一个值的集合和定义在此集合上的一组操作的总称。 尽管同一个数据类型在不同的CPU上处理的方法不同，对程序原来说他们是相同的，程序员可以不考虑具体机器的实现方法。也就是说这些数据类型仅仅取决于它的逻辑特性，与在计算机内的实现无

3、关。在数学抽象的角度上看可以称之为抽象数据类型。,抽象数据类型： （Abstract Data Type ：ADT） 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型可以用一个三元组来表示：（D，S，P） D是数据对象，S是D上的关系集，P是D的基本的操作集 。,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 如：定义复数的抽象数据类型,ADT Complex 数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分, e2 是复 数的虚数部分 基本操作：

4、AssignComplex( for(int i=0;in;i+) s+=i; 问题的规模是n,程序的运算工作量和n成线性的增长关系 ，或者说它可以看作是n的函数f(n)。,随着规模的增大，算法执行所需要的时间的增长率和f(n)的增长率是相同的。用时间复杂度来表示算法的时间效率， T (n) = O(f(n) 称T (n) 为算法的(渐近)时间复杂度,如何估算时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = 原操作的执行次数原操作的执行时间,算法的实行时间和原操作的执行次数是成正比的。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在

5、算法中重复执行的次数作为算法运行时间的衡量准则。,如上例中，时间复杂度为O(n) 例： （a） +x;s+=x; （b）for (i=1;i=n;+i) +x;s+=x; （c）for (j=1;j=n;+j) for (k=1;k=n;k+)+x;s+=x; 基本操作： +x;s+=x; a的执行次数：1 时间复杂度O(1) b的实行次数：n 时间复杂度O(n) c的执行次数：n2 时间复杂度O(n2),例：两矩阵相乘 #define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) n+1 for (j=1;j=n;+j) n*(n+1) Cij=0; n2 for (k=1;k=n,k+) n2(