数据结构A学习.pptx

《数据结构A学习.pptx》由会员分享，可在线阅读，更多相关《数据结构A学习.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、掌握现代信息技术掌握现代信息技术知识知识 具有概念化和抽象具有概念化和抽象化能力化能力 算法与数据结构算法与数据结构什么是数据结构什么是数据结构 数据抽象和抽象数据类型数据抽象和抽象数据类型 描述数据结构和算法描述数据结构和算法算法分析的基本方法算法分析的基本方法第1页/共40页1.1 1.1 算法与数据结构算法与数据结构1.2 1.2 什么是数据结构什么是数据结构 1.3 1.3 数据抽象和抽象数据类型数据抽象和抽象数据类型 1.4 1.4 描述数据结构和算法描述数据结构和算法1.5 1.5 算法分析的基本方法算法分析的基本方法第1章 基础知识第2页/共40页数据结构和算法是计算机学科的基础

2、之一，更是软件技术的基础。数据的组织和表示方法直接影响使用计算机求解问题的效率。程序程序 =数据结构数据结构+算法算法1.1 算法与数据结构第3页/共40页1.2.1 1.2.1 1.2.1 1.2.1 基本概念基本概念基本概念基本概念基本术语 数据（data）：计算机加工处理的对象。数据元素：组成数据的基本单位 数值数据(numerical data)非数值数据(non-numerical data)1.2什么是数据结构第4页/共40页 什么是数据结构什么是数据结构 一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据

3、的存储结构是数据结构的实现形式，是其在计算机内的表示；一个数据结构必须讨论在该类数据上执行的运算才有意义。数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。第5页/共40页1.2.21.2.21.2.21.2.2 数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构 数据的数据的逻辑结构逻辑结构 对对数数据据元元素素间间逻逻辑辑关关系系的的描描述述被被称称为为数数据据的的逻逻辑辑结结构构(logical logical structure)structure)，它它可可以以用用一一个个二二元元组组表表示示：DS=DS=（D

4、D，R R），其其中中，D D是是数数据元素的有限集合，据元素的有限集合，R R是是D D中元素序偶的集合。中元素序偶的集合。第6页/共40页 四类基本逻辑结构（a）集合结构（b）线性结构（c）树形结构（d）图状结构 （a）集合结构）集合结构（b）线性结构）线性结构（c）树型结构）树型结构（d）图形结构）图形结构四类基本结构的示意图四类基本结构的示意图第7页/共40页例例：用图形表示下列数据结构，并指出它们是属于线用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。性结构还是非线性结构。（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f

5、),(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：bcaefd此结构为线性的。第8页/共40页（2）S=(D,R)D=di|1i5 R=(di,dj),ij d1 d5 d2 d4 d3该结构是非线性的。解：上述表达式可用图形表示为：第9页/共40页1.2.3 1.2.3 1.2.3 1.2.3 数据的存储表示数据的存储表示数据的存储表示数据的存储表示 顺序存储 需要一块连续的存储空间，并把逻辑上相关的数据元素依次存储在该连续的存储区中。Loc（ak）1022*k第10页/共40页 链接存储 几种存储结构几种存储结构 顺序结构顺序结构 链接结构链接结构 索引结构索引结构

6、 散列结构散列结构Data LinkData Link 地址信息称为链。表示空链。第11页/共40页1.2.4 1.2.4 1.2.4 1.2.4 数据结构的运算数据结构的运算数据结构的运算数据结构的运算数据结构最常见的运算 创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；第12页/共40页 静态数据结构和动态数据结构静态数据结构和动态数据结构如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。第13页/共40页1.3.1 1.3.1 抽象、数据抽象和过程抽象

7、抽象、数据抽象和过程抽象抽象、数据抽象和过程抽象抽象、数据抽象和过程抽象 抽象：抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。数据抽象数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。过程抽象：过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。1.3 数据抽象和抽象数据类型第14页/共40页 1.3.2 1.3.2 封装与信息隐蔽封装与信息隐蔽封装与信息隐蔽封装与信息隐蔽 封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。信息隐蔽：对使用者隐藏了数据

8、结构或程序的实现细节。通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。第15页/共40页 1.3.3 数据类型和抽象数据类型数据类型和抽象数据类型数据类型和抽象数据类型数据类型和抽象数据类型 数数据据类类型型 是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。第16页/共40页 整型整型intint的规范的规范 变量 a a 的取值范围是：-3276832767 对变量 a a 执行的

9、操作有：算术运算 +、-、*、/、%关系运算 、=、=、!=赋值运算 =整型整型intint的实现的实现 变量 a 在计算机内存储表示方法。操作的具体实现方法。第17页/共40页 抽抽象象数数据据类类型型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。第18页/共40页 1.3.4 1.3.4 数据结构与抽象数据类型数据结构与抽象数据类型数据结构与抽象数据类型数据结构与抽象数据类型 逻辑结构和运算的定义组成了数据结构的数据结构的规范规范（specification）数

10、据的存储表示和运算算法的描述构成数据结构的数据结构的实现实现(implementation)。从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。第19页/共40页 数据结构的抽象层次数据结构的抽象层次 抽象层：讨论数据的逻辑结构及其运算定义，实现层：讨论数据的存储表示以及运算的算法实现。第20页/共40页1.4.1 1.4.1 数据结构的规范数据结构的规范数据结构的规范数据结构的规范 数据结构被看成是一个类属抽象数据类型(ADT)，用格式化的自然语言来描述。数据结构可以形式地用一个C+的抽象模板类描述。1.4 描述数据结构和算法第21页/共40页A

11、DT1.1栈ADTADTStack数据：数据：0个或多个元素的线性序列（a0,a1,.,an-1）,其最大允许长度为MaxStackSize。运算：运算：Create()：建立一个空栈Destroy()：撤消一个栈Push(x)：值为x的新元素进栈，成为栈顶元素Pop()：从栈中删除栈顶元素Top(x)：在x中返回栈顶元素第22页/共40页templateclassStack/栈类Stack是一个模板抽象类，其成员函数为纯虚函数，未定义数据成员。public:virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;

12、第23页/共40页1.4.2 1.4.2 实现数据结构实现数据结构实现数据结构实现数据结构templateclassSeqStack:publicStackpublic:private:inttop;/top记录最后入栈的元素在s的下标intmaxTop;/最大栈顶指针T*s;/s指向动态生成的一维数组，存放元素;第24页/共40页templateSeqStack:SeqStack(intmSize)maxTop=mSize-1;/设置栈的容量值s=newTmSize;/生成存储栈的数组top=-1;/top=1表示空栈第25页/共40页1.5.1 1.5.1 算法及其性能标准算法及其性能标准

13、算法及其性能标准算法及其性能标准 什么是算法什么是算法 笼笼统统的的说说，算算法法是是求求解解一一类类问问题题的的任任意意一一种种特特殊殊的的方方法法。较较严严格格的的说说法法是是一一个个算算法法是是对对特特定定问问题题的的求求解解步步骤骤的的一一种种描描述述，它它是是指指令令的的有有限限序序列列；此此外外，算算法法具具有有下列五个特征：下列五个特征：1.5 算法分析的基本方法 第26页/共40页 输入输入：算法有零个或多个输入：算法有零个或多个输入 输出输出：算法至少产生一个输出：算法至少产生一个输出 确定性确定性：算法的每一条指令都有确切的定义，没有二义性。：算法的每一条指令都有确切的定义

14、，没有二义性。能能行行性性：算算法法的的每每一一条条指指令令都都足足够够基基本本，它它们们可可以以通通过过已已经经实实现现的的基基本本运运算算执执行行有有限次来实现。限次来实现。有穷性有穷性：算法必须总能在执行有限步之后终止。：算法必须总能在执行有限步之后终止。第27页/共40页1.5.2 1.5.2 1.5.2 1.5.2 算法的时间复杂度算法的时间复杂度算法的时间复杂度算法的时间复杂度 算法的时间复杂度算法的时间复杂度 是程序运行从开始到结束所需的时间。程序步程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。第28页/共40页floatSum(fl

15、oatlist,constintn)/此程序的程序步数为此程序的程序步数为2n3floattempsum=0.0;count+;/针对赋值语句针对赋值语句for(inti=0;in;i+)count+；/针对针对for循环语句循环语句tempsum+=listi;count+;/针对赋值语句针对赋值语句count+;/针对针对for的最后一次执行的最后一次执行count+;/针对针对return语句语句returntempsum;第29页/共40页1.5.3 1.5.3 渐近时间复杂度渐近时间复杂度渐近时间复杂度渐近时间复杂度 定义定义:（大（大O O记号）记号）设f(n)和g(n)是定义在正

16、整数上的正函数，如果存在两个正常数c和n0，使得当nn0时，有f(n)f(n)cg(n)cg(n)则记作f(n)=O(g(n)f(n)=O(g(n)。第30页/共40页 定理定理如果f(n)amnm+am-1nm-1+a1n+a0是m次多项式，则f(n)O(nm)例：T(n)3.6n3+2.5n2+2.8O(n3)第31页/共40页 渐近时间复杂度 使用大O记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。渐近时间复杂度也常简称为时间复杂度。通常用O(1)表示常数计算时间，即算法只需执行有限个程序步。第32页/共40页 关键操作关键操作很多情况下，可以通过考察一个程序中的关键操作（关键操作

17、被认为是一个程序步）的执行次数来计算算法的渐近时间复杂度。有时也需要同时考虑几个关键操作，以反映算法的执行时间。第33页/共40页例voidMult(intann,bnn,cnn,intn)/nn矩阵a与b相乘得到c。for(inti=0;in;i+)/n+1for(intj=0;jn;j+)/n(n+1)cij=0;/n2for(intk=0;kn;k+)/n2（n+1)cij+=aik*bkj;/n3程序步为：2n3+3n2+2n+1cij+aik*bkj可看成关键操作渐近时间复杂度为：T(n)=O(n3)第34页/共40页算法按时间复杂度分类多项式时间算法O(1)O(log2n)O(n)

18、O(nlog2n)O(n2)O(n3)指数时间算法O(2n)O(n!)O(nn)第35页/共40页1.5.4 1.5.4 最好、最坏和平均时间复杂度最好、最坏和平均时间复杂度最好、最坏和平均时间复杂度最好、最坏和平均时间复杂度例子：在一个有n个元素的数组中查找一个指定元素，某个搜索算法从第一个元素开始，一次检查一个数组元素。第36页/共40页上节课练习上节课练习（1）在数据结构中，从逻辑上可以把数据结构分成 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构(2)两种常用的数据结构的物理存储方式有顺序存储和_ A.线性表存储B.散列结构存储 C.集合结构存储D.链式存储(3)对于给定的n个元素,可以构造出的四种逻辑结构是 、_ _。第37页/共40页上节课练习上节课练习有下列二元组表示的数据结构，请指出属于何种逻辑结构。S=D，R；D=a，b，c，d，e，f，g，h；R=,第38页/共40页本章总结本章总结数据结构基本概念数据结构基本概念数据结构的分类数据结构的分类算法及时间复杂度计算算法及时间复杂度计算第39页/共40页感谢您的观看。第40页/共40页