DS数据结构概述

会计学1DS数据结构概述本章重点难点重点:

①数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系；②抽象数据类型(ADT)的概念和实现方法，算法的时间复杂性和空间复杂性分析。难点:

①抽象数据类型(ADT)的概念和实现方法；②算法的时间复杂性和空间复杂性分析。第1页/共37页1.1为什么要学习数据结构算法+数据结构=程序设计

处理问题的策略给出问题的数学模型编制出用计算机处理问题的指令问题构建数学模型算法实现第2页/共37页计算机的发展数据处理的种类数据数值数据

非数值数据

数(整数,实数)字符字符串文字图形图象声音对客观对象的符号表示程序原始数据结果数据软件硬件应用领域第3页/共37页学习数据结构的原因：①计算机处理的数据量越来越大。②数据类型越来越多。③数据的结构越来越复杂。数据结构是一门研究“非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作"的学科。

1.1为什么要学习数据结构第4页/共37页

已知数据如下：结论1：杂乱无章的数据不能表达和交流。例119850700163172978233000340304195902261011工号：1985070016电话号码：3172978邮编：233000身份证号码5页/共37页

例2电话号码簿（a1,b1）（a2,b2）（……）（an,bn）,其中，ai为某人姓名，bi为该人的电话号码。结论2：数据之间是有联系的。第6页/共37页

例3家族的族谱:假设某家族有10个成员A,B,C,D,E,F,G,H,I,J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE结论3：数据之间是有结构的。第7页/共37页学号姓名性别出生日期入学成绩所在班级00201杨润生男82/06/0156100计算机2

00102石磊男83/12/2151200计算机1

00202李梅女83/02/2353200计算机200301马耀先男82/07/1250900计算机3

已知某级学生情况,要求分班按入学成绩排列顺序。说明：在此类文档管理中,可以有查找、修改、插入、删除等操作。例4结论4：在某种数据结构上可以定义一组运算。第8页/共37页1.2数据结构的有关概念和术语1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。2、数据元素：数据的基本单位，又可称为元素、结点、顶点、记录等。3、数据项:是数据不可分割的最小单位。如学号、姓名等。一个数据元素可以由若干个数据项构成。4、数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。5、数据类型：是指一个类型和定义在这个类型上的操作集合。

分为：原子类型和结构类型6、抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集合。优点：将数据和操作封装在一起实现了信息隐藏。第9页/共37页抽象数据类型的定义可以由元素、元素之间的关系及操作三部分构成。

抽象数据类型的定义格式

ADT抽象数据类型名｛

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

｝ADT

抽象数据类型名

例如：P4例1-41.2数据结构的有关概念和术语第10页/共37页1.2数据结构的有关概念和术语数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

形式定义为：Data_Structure(D,R)例如：P5例1-5第11页/共37页数据结构包括以下内容：（1）数据的逻辑结构。从逻辑关系上描述数据，与数据存储无关，独立于计算机。它包括以下四类基本结构：集合：同属一个集合线性结构：一对一树形结构：一对多图状结构或网状结构：多对多1.2数据结构的有关概念和术语第12页/共37页数据结构类型树图线性表栈队列串数组广义表数据结构线性结构非线性结构第13页/共37页（2）数据的物理结构，数据结构在计算机存储器中的表示，又称存储结构。它包括：顺序存储结构：借助数据元素在存储器中相对位置表示逻辑关系链式存储结构：依靠数据元素中的指针表示元素之间的逻辑关系索引散列1.2数据结构的有关概念和术语第14页/共37页对每种数据结构，主要讨论如下三方面的问题：①数据的逻辑结构

数据元素之间的逻辑关系，是具体关系的抽象。②数据的存储结构(物理结构)：

数据元素及其关系在计算机内存中的表示；③数据的运算（或算法）

即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。第15页/共37页1.3算法和算法描述1、算法算法是对特定问题求解步骤的一种描述，是指令的集合。算法的特性：有穷性、确定性、可行性、输入、输出第16页/共37页算法的基本特征有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定性：组成算法的操作必须清晰无二义性。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。输入：作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。第17页/共37页2、算法设计的要求正确性可读性健壮性高效性1.3算法和算法描述第18页/共37页算法必须是“正确的”所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。应有很好的“可读性”一个算法应当思路清晰、层次分明、简单明了、易读易懂。算法的设计要求第19页/共37页必须具有“健壮性”算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。算法的效率应考虑所设计的算法具有“高效率与低存储量”。高效率与低存储量是矛盾的，要视具体问题而定。算法的设计要求第20页/共37页算法描述：1.文字形式:用中文或英文这样的文字来描述算法。2.伪码形式:用一种仿程序设计语言的语言来描述算法。比如类C语言。3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。1.3算法和算法描述第21页/共37页算法描述：类C语言比程序设计语言更容易描述和被理解，比文字描述的自然语言更接近程序设计语言，容易转换成高级语言。例如：P7例1-61.3算法和算法描述第22页/共37页1.算法是对特定问题求解步骤的一种描述，是指令的集合。一个问题可以有多种算法。2.程序是用某种程序设计语言对算法的具体实现。软件开发生命周期：需求分析→概要设计→算法设计→程序编码→运行维护算法和程序的区别第23页/共37页1.程序可以是无穷的，例如：OS；算法必须是有穷的。2.程序可以是错误的，算法必须是正确的。3.程序是用程序设计语言描述，在机器上可以运行；算法也可以用框图，自然语言等方式描述。算法和程序的区别第24页/共37页1.4算法时空效率分析方法算法分析就是对算法质量优劣的评价，通常分为事后统计和事前分析两种方法。算法分析应从两个角度：依据算法编写的程序在计算机中运行时间的多少的度量，即时间复杂度。依据算法编写的程序在计算机中占存储空间的多少的度量，即空间复杂度。注：时间复杂度和空间复杂度合称算法的复杂度。第25页/共37页1.4算法时空效率分析方法1.算法的时间复杂度程序运行所需要的时间取决于以下因素：

(1)机器执行指令的速度(2)书写算法的程序设计语言(3)编译产生的机器语言代码质量(4)算法所选用的策略(5)问题的规模，即算法的时间效率与算法所处理的数据个数n的函数关系。第26页/共37页算法的时间复杂度 是算法执行的时间耗费，是求解问题规模n的函数。记为：T(n)=O(f(n))。

(1)时间复杂度的计算方法——频度统计法例1：语句x=x+1;执行频度为1，时间复杂度记为：T(n)=O(1)1.4算法时空效率分析方法第27页/共37页

(1)时间复杂度的计算方法——频度统计法例2：

for(i=1;i<=n;i++) x=x+1;

算法的频度=n+1

则算法的时间复杂度为O(n)1.4算法时空效率分析方法第28页/共37页(1)时间复杂度的计算方法——频度统计法例3：

for(i=1;i<=n;++i)for(j=1;j<=n;++j) x=x+1;

算法的频度=n(n+1)

则算法的时间复杂度为O(n2)1.4算法时空效率分析方法第29页/共37页(1)时间复杂度的计算方法——频度统计法例4：

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]+=a[i][k]*b[k][j];}

算法的频度=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

则算法的时间复杂度为O(n3)1.4算法时空效率分析方法第30页/共37页(2)有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。此时，一种办法是讨论平均时间复杂度，一种办法是讨论最坏的情况下的时间复杂度。(3)常见的时间复杂度按数量级递增排列依次为：常数阶O(1)<对数阶O(log2n)<线性阶O(n)<线性对数阶O(nlog2n)<平方阶O(n2)<立方阶O(n3)<k次方阶O(nk)<指数阶O(2n)。

1.4算法时空效率分析方法第31页/共37页讨论：

“不必最求高效算法，低效算法可以在高速计算机上得到补偿。”这一说法正确吗？1.4算法时空效率分析方法第32页/共37页设A1,A2,A3是求解同一问题的不同算法，其时间复杂度分别是：O(n),O(nlgn),O(N!)。C1和C2为计算机，且C2的计算速度是C1的10倍。复杂度C1可解规模C2可解规模可解规模的关系

O(n)N11N21N21=10N11O(nlgn)N12N22N22=10N12O(N!)N13N23N23=N13+小常数1.4算法时空效率分析方法结论：“不必最求高效算法，低效算法可以在高速计算机上得到补偿。”这一说法是错误的!第33页/共37页2