数据结构专升本复习.ppt

《数据结构专升本复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章数据的三个层次：数据、数据元素、数据项数据结构的概念：定义、逻辑结构、物理(存储)结构理解数据类型、抽象数据类型的概念。算法的概念(算法特性，算法设计要求)理解时间复杂度、空间复杂度的概念。数据是对客观事物的符号表示。数据结构相关的基本概念在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。基本概念和术语数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。有两类数据元素：一类是不可分割的"原子"型数据元素，如：整数"5"，字符"N"等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个"数据项"。例如描述一个学生的信息的数据元素可由

2、下列个数据项组成。数据结构简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义为：DataStructures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构顺序存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。链式存储结构常见的存储结构顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。数据类型和抽象数据类型数据类型是一个“值”的集合和定义在此集合

3、上的“一组操作”的总称。例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。例如，矩阵的抽象数据类型定义为，矩阵是一个由mn个数排成m行n列的表，它可以进行初等变换、相加、相乘、求逆、……等运算。抽象数据类型的形式描述为ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是D的基本操作集。一、算法定义算法（Algorithm）：是对特定问题求解步骤的一种描述，是由若干条指令组成的有限

4、序列，其中每一条指令表示一个或多个操作。它应该满足下列五个重要特性：1、有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。2、确定性算法中每一条指令必须有确切的含义，且执行路径唯一。即对于相同的输入只能得出相同的输出。3、可行性算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4、输入一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。5、输出一个算法有一个或多个的输出，这些输出同输入有着某些特定关系的量。1.2算法描述二、算法设计的要求：1、正确性算法应满足具体问题的需求。通常算法的正确性可分为四个层次：a.程序不含语法错误;b.程序对于

5、几组输入数据能够得出满足规格说明要求的结果;c.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。二、算法设计的要求：2、可读性算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，晦涩难懂的程序易于隐藏较多错误难以调试和修改。3、健壮性当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。4、效率与低存储需求举例问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：

6、（1）输入x，y，z三个数值；（2）从三个数值中挑选出最小者并换到x中；（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。三、算法复杂性的概念确切地说，算法的复杂性是运行算法所需要的计算机资源的量。需要的时间资源的量称为时间复杂性需要的空间资源的量称为空间复杂性**在算法分析中，通常所说的找到了时间复杂性的级别，是指找到了同样级别的最简单的函数。如：307n2、n2/2、n2都是同一级别的函数，最简单的函数是n2。所以，307n2、n2/2、n2的级别都是O(n2)。f、g同级别：满足：f=O(g)且g=O(f)例１、for(i=1;i<=n;++i)for(j=1;j<=n

7、;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3频度：是指该语句重复执行的次数例２、{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1);如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(i=1;i<=n;++i