数据结构——C语言描述第1章-绪论.pptx

《数据结构——C语言描述第1章-绪论.pptx》由会员分享，可在线阅读，更多相关《数据结构——C语言描述第1章-绪论.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构C语言描述（慕课版）第1章 绪论编著：张同珍&学校：上海交通大学绪论数据结构定义基本操作存储结构逻辑结构算法算法的时空复杂度数据结构：数据是外界信息进入计算机，并被计算机处理的符号，数据元素是数据的基本单位。如有一组学生信息，每个学生信息是一个结构类型数据，包含了学号、姓名、年龄等字段，那么这组学生信息是数据，每一个学生信息是数据元素。数据结构：是指相互之间具有一定关系的相同类型的数据元素的集合。数据结构的研究对象：1.元素之间的关系（逻辑结构）2.元素关系操作3.元素和关系在内存中的存储（物理结构）4.在各种存储方式下关系操作的实现5.每种数据结构的典型应用研究数据的逻辑结构就是研究

2、类型相同的一组元素和元素间的关系。数据的逻辑结构集合关系：元素间呈松散关系，结构中不同元素除了同属于一个集合，相互间并无其他制约关系。如同班级里同学间的关系。线性关系：元素间呈现出你先我后的顺序，是一种一对一的关系。如队列中元素间的关系。除了队首，每个元素有且只有一个唯一的直接前驱元素；除了队尾，每个元素有且只有一个唯一的直接后继元素。树形关系：元素间呈现出一对多的关系。如家谱中人物间关系，一个人可以有多个儿子，却只能有一个父亲。即每个元素可以有多个后继，却只能有一个前驱。图关系：元素间呈现多对多的关系。如城市间通过飞机航线形成的关系，例如上海、北京、西安3个城市中，任何两个城市间都可以有直飞

3、航线。分以下几种：数据的逻辑结构：逻辑结构通常可以用二元组描述:Data_Struct=(D,R)，其中D是元素的集合，R是关系的集合。例如整数110组成的有序集就是一个线性结构。D=|1 10，R=1,2 1,2。其中 1,2表示一个有序偶，即x1和x2有顺序关系，x1是直接前驱，x2是直接后继。关系操作（或称基本操作）是和数据的逻辑结构紧密相关的，它来源于关系自身的特点。构造类：在内存中建立这种数据结构。如一个空的队列。基本操作都可以分为五大类：构造类、属性类、数据操纵类、遍历类、典型应用类。属性类：对元素及元素之间的关系的各类查询。属于东瞧瞧、西看看，不影响元素及元素关系本身。数据操纵类

4、：对元素或元素关系有改变的操作，如插入或删除某个元素。修改可视作删除后插入。遍历类：对结构中的每个元素访问且只访问一遍。典型应用类：所属结构独特的应用，不同结构其典型应用各不相同。数据的逻辑结构+基本操作=抽象数据类型ADT（Abstract Data Type）。ADT和在计算机内的表示、实现无关，只和数据自身的逻辑特征相关。ADT类似高级语言中的数据类型，如整型:一个整数集合以及在这个集合中系统支持的基本操作（四则运算、比较运算等）。ADT区别于具体某种类型，只关心元素关系和关系操作，不实际要求数据的具体类型，只要元素类型一致。ADT的描述可以用自然语言也可以用伪代码，其内容包含元素集合、

5、元素关系集合、基本操作。基本操作表明生活中的一个个基本的问题，有明确的已知条件和结果要求。基本操作的具体实现依赖于数据和数据关系在内存中如何存储，在逻辑结构分析阶段并不知道存储方式，因此无法给出，也不需要考虑。顺序存储是用一块连续的空间来存储数据，同时借助这组空间在地址上的邻接及有序性来存储元素之间的关系，顺序存储的结构称顺序结构。高级语言中的数组可以实现连续空间的获取，帮助实现顺序结构。链式存储是在内存中使用多个独立的内存空间，每个独立的空间除了包括存储元素的空间，还包括附加的空间来存储元素之间的关系。链式存储的数据结构称链式结构。存储结构：也称物理结构，是指数据结构在内存中的表示。常见的存

6、储方式有顺序存储和链式存储两种。算法及其要求这里算法是指用计算机解决一个具体问题的方法和步骤。算法必须满足五个特性：一个算法中的每一步要在有限的时间内完成，而整个算法必须在有限步之后完成。有穷性：算法中的每一步都有确定的含义，没有二义性。确定性：算法中的每一步都是经过有限次基本操作就可以完成的，每一步自身没有复杂的算法问题。可行性：根据问题需要，一个算法可以有零个或者若干个输入作为解决问题的已知条件。有输入：算法执行结束后，有零个或者若干个输出作为算法运行结果。有输出：算法及其要求度量算法优劣的几个要素：准确反映并能满足具体问题的要求，即对于任意一个合法的输入，都能给出正确的结果。正确性：可供

7、人们阅读的容易程度，可读性好的算法便于阅读、理解、交 流、调试和纠错。可读性：对各种不同的输入都要有相应的反应。输入数据合法，要有相应的输出；输入数据不合法，要有相应的响应处理。健壮性：算法的执行时间，应能满足问题解决的时间容忍要求。如实时系统对处理时间有一个及时性反应的要求。执行时间越短，算法的时间效率越高。时间效率：算法执行期间所需要的最大内存空间。所需要的内存空间越少，空间效率越高。空间效率：算法的时间复杂度算法的执行时间是指依据算法编制的程序运行时所消耗的时间。度量方法有运行后度量和运行前分析。运行后度量：指根据不同算法事先编制好的程序和同样的测试数据，在程序运行时借助机器的计时功能进

8、行计时，当不同程序运行结束时，分别记录实际的运行时间并进行比较。运行前分析：指在算法设计好但还没有编程实现时，根据几个方面的影响因素对算法的执行时间进行分析。算法时间复杂度的影响因素：02OPTION编译后代码的质量：高级语言编制的程序通常要进行编译，不同编译器往往采用不同的优化策略，这样便造成代码运行效率不同，也称代码质量不同。03OPTION书写程序所用的语言：同样的算法，使用的编程语言越高级，实现的效率就越高，但执行的效率就越低。04OPTION问题的规模：规模即指问题涉及的数据量的大小，通常数据量越大效率越低，一旦数据量大到一定级别，可能就要用到大数据处理方法，如用分布式。05OPTI

9、ON算法采用的策略和方法：同一问题可以有不同的方法和策略进行解决，同一算法采用不同的方法策略消耗的时间可能就不同。机器的运算速度：这里主要考虑计算机的主频和字长。01OPTION设计算法时，考虑到时间消耗，主要是从算法的设计方案入手。算法时间复杂度计算运行时间是算法实现中所有语句执行的时间总和，由于不同机型指令集不同，且不同指令执行时间也不同，所以使用算法中语句执行的次数来度量更合理。语句执行次数称时间频度，语句执行的次数越多，时间花费越多。一组相同数据可能引起一些语句反复执行，因此一般算法的时间频度和要处理的数据规模有关，故可以表示为数据规模n的函数T(n)。s=0;for(i=0;in;i

10、+)s=s+i;语句s=0执行1次，i=0执行1次，i0)for(i=0;in;i+)printf(“%d“,i”);elseprintf(“n0的情况，为n次，而非n0，有T(n)Cf(n)。算法时间复杂度计算T(n)=3 2+2+10T(n)3 2+2 2+10 215 2显然存在0=1,=15，当n0时，有T(n)15 2，即f(n)=2，算法的复杂度为O（2)。又T(n)=3n+3的时间复杂度和T(n)=n的时间复杂度一样都是O(n)。可以看出，时间复杂度是一个时间频度表达式中的最高次项，且不带系数。算法时间复杂度计算如果有内外两重循环，相互不独立：s=0;for(i=0;in;i+)

11、for(j=0;ji;j+)s=s+i+j;printf(“s=%d”,s);可以将外循环打开来算：当i=0时，内循环体执行0次；当i=1时，内循环体执行1次；当i=n-1时，内循环体执行n-1次；所以内循环体一共执行0+1+2+n-1=n(n-1)/2次，时间复杂度为O(2)。时间复杂度的计算方法总结：找到算法中和数据规模n有关的循环语句，计算循环体的执行次数获得时间频度函数，取n的最高次项，去掉其系数，即是时间复杂度。按照这个顺序排列，时间效率由高到低。当到达立方阶之后，一旦数据规模大些，时间就不能忍受了，就是一个顽性算法了。空间复杂度的度量实现算法的程序本身需要占据存储空间；01OPTI

12、ON通常1和2是不可避免的，在设计算法时主要关注额外的辅助空间。渐进空间复杂度称空间复杂度，是当数据规模n趋于无穷时的辅助空间量阶。待处理的数据需要在内存中存储，占据一定的空间；02OPTION在处理数据的过程中需要一些额外的辅助空间。03OPTION算法的空间消耗包括3个方面：空间复杂度的度量实现数据序列逆置的算法程序示例一：int a10=1,6,2,5,8,9,5,4,3,12;int t,i;for(i=0;i5;i+)t=ai;ai=a10-i-1;a10-i-1=t;为了完成n=10个元素的逆置，将a0和a9交换，将a1和a8交换，最后直到a4和a5交换，期间使用的辅助空间为一个变量t。故其空间复杂度和元素个数没有关系，为O(1)。空间复杂度的度量实现数据序列逆置的算法程序示例二：int a10=1,6,2,5,8,9,5,4,3,12,b10;int t,i;for(i=0;i10;i+)bi=a10-i-1;for(i=0;i10;i+)ai=bi;为了完成n个元素的逆置，使用了具有n个元素空间的数组b作为辅助空间，最后也能完成逆置，但空间复杂度为O(n)。一般来说，在内存足够大的情况下，算法更加注重时间效率，仅当算法的时间复杂度一致的情况下才比较空间复杂度的优劣。谢谢观看数据结构C语言描述（慕课版）