大话数据结构.pptx

数据结构的论述数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。程序设计=数据结构+算法一，数据结构的初步认识 数据： 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。（数据不仅仅包括整型，实型等数据类型，还包括字符以及声音，图像，视频等非数值类型。） 数据就是符号 1，可以输入到计算机中。2，可以被计算机处理。 对于整型，实型等数值类型，可以进行数值计算。 对于字符数据类型，就需要进行非数值的处理。而声音，图像，视频等其实可以通过编码的手段变成字符数据来处理的。 数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。例如，在人类中，人就是数据元素。 数据项：一个数据元素可以由若干个数据项组成。例如，人可以有眼睛，鼻子等数据项。数据项是数据不可分割的最小单位。 数据对象： 是性质相同的数据元素的集合，是数据的子集。 性质相同是指数据元素具有相同的数量和类型的数据项。例如人有姓名，生日，性别等相同的数据项。 数据结构：不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。二，数据的逻辑结构和物理结构 逻辑结构： 1，集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。123452，线性结构：线性结构中的数据元素之间是一对一的关系。12734653，树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。1429865374，图形结构：图形结构的数据元素是多对多的关系。7635241 物理结构1，顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。2，链式存储结构;把数据元素存放在任意的存储单元里，这组存储单元可以使连续的，也可以是不连续的。抽象数据类型1.数据类型。 数据类型：是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称。在C语言中可分为a.原子型。b.结构类型。抽象的概念 是指取出事物具有的普遍性的本质。2.抽象数据类型 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。第2章 算法 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。 高斯的故事求1+2+3+100=?int i , sum=0, n=100;For(i=1; iN， f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)。算法时间复杂度定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作： T(n)=O(f(n)。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。(O()用来体现算法时间复杂度的记法，成为大O记法)一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。例如三个求和算法的时间复杂度分别为O(1),O(n),O(n2)。 O(1)常数阶， O(n)线性阶， O(n2)平方阶。推导大O阶1.用常数1取代运行时间中所有加法常项。2.在修改后的运行次数函数中，只保留最高阶项。3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。1.常数阶Int sum =0,n=100; /*执行一次 */Sum=(1+n)*n/2; /*执行一次 */Printf(“%d”,sum) /*执行一次 */2.线性阶3对数阶4平方阶。