6数据的组织结构与算法1ppt课件

1、第六章 数据的组织构造与算法6.1 数据构造的根本概念6.2 常用的几种数据构造6.3 算法6.4 程序设计方法16.1数据构造的根本概念6.1.1 数值计算与非数值计算数据是描画客观事物的数值、字符以及能输入机器且能被处置的各种符号集合。换句话说，数据对客观事物采用计算机可以识别、存贮和处置方式所进展的描画。简言之，数据就是计算机化的信息。数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而定性模型那么是指非数值性的数据构造,如表、树和图等及其运算。2 数据构造Data Structure问题来源于程序设计的开展。 第一个8008芯片只需4K的内存，微软的

2、最初成立就是为这个芯片的机器编写BASIC言语，优化在每一处都非常重要。逐渐地，人们留意了数据表示与操作的构造化，把一些确实可以有效处理问题的数据表示和算法总结出来，如表、栈、队、树、图稍后会引见这些术语等被单独抽出研讨，而这些方法便构成一门学问，这就是“数据构造这门学科的来源。6.1.2 数据构造的来源3数据构造有逻辑上的数据构造和物理上的数据构造之分 。逻辑上的数据构造反映成分数据之间的逻辑关系。物理上的数据构造反映成分数据在计算机内部的存储安排。 6.1.3 对数据构造的了解41.表示 对象/实体及其关系在计算机中的表示。只需对象及其相互关系已存储表示在计算机中，才干被进一步处置；2.操

3、作：对对象/实体进展处置、访问。数据构造的普通定义：相互之间存在着一定关系的数据元素的集合及定义在其上的操作运算称为数据构造。 51.插入：在数据构造中的指定位置增添新的数据元素2.删除：删去数据构造中指定的数据元素。3.查找：在数据构造中寻觅某个特定要求的数据元素。4.排序：在线性构造中重新安排数据元素之间的逻辑顺序关系，使之按某个关键字值由小到大或由大到小的次序陈列。5.遍历：按某一次序访问数据构造中的每一个数据元素。6.1.4 对数据构造中数据元素的操作6 例6.1 解一元二次方程ax2+bx+c=0. 利用计算机解此方程，第一个问题就是如何在计算机中表示该方程。分析该方程，可知决议方程

4、的是方程的三个系数值：a、b、c，而它们的次序表示它们分别属于那一项，其他符号是为添加可读性而引入的，因此，可用这三个系数的线性陈列在计算机中表示该方程。例如： 3x2-x+1=0表示为3, -1, 1 x2-3=0 表示为(1, 0, -3) 在数据构造中，将假设干个数线性陈列的数元素称为线性表，因此，一元二次方程ax2+bx+c=0就在计算机中表示为线性表a, b, c。解方程本质上是对线性表(a, b, c)进展操作。6.1.5 数据构造能处理什么问题7定义变量X和一个线性表，如数组int S3; S2，S1，S0可以分别存放三个系数值输入S2，S1，S0三个系数值输入恣意一个值X开场S

5、2*X*X+S1*X+S00，从编号为1的人开场，按顺时针方向1开场顺序报数，报到m时停顿。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开场，重新从1开场报数，如此下去，直至一切的人出列为止。 17当n和m较大时，用人工求解约瑟夫环问题是相当繁琐的。采用单循环链表就容易处理。其根本思绪是： 人围成一圈，把一人看成一个结点，人之间的关系采用链接方式，即每一结点有一个前趋结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据构造。当人出列时，将结点的前趋结点指针指向结点的后继结点指针，即把结点驱出循环链。18 1树的

6、定义 树是由一个或多个结点组成的有限集合，如图6-12所示。6.2.2 树构造19必有一个特定的称为根ROOT的结点，根的每个分支称为子树sub-tree，子树也是一棵树树中的每一个结点都可以不止一个直接后继，结点的后继结点称为该结点的“子结点Children除根结点外的一切结点有且只需一个直接前趋,结点的前趋结点称为该结点的“父结点Parent同一父结点的子结点称为“兄弟Sibling结点下不再有分支的称为树叶leaf，或者叶子结点树构造的特点20二叉树的特点：树中的每个结点最多只需两棵子树，即树中任何结点的度数不得大于。二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的

7、，即使在只需一棵子树的情况下，也应分清楚。例如图6-13是两棵不同的二叉树。 2二叉树21所谓遍历二叉树，就是按一定的规那么和顺序走遍二叉树的一切结点，使每一个结点都被访问一次，而且只被访问一次。 二叉树的遍历可分为先序遍历中序遍历后序遍历 3二叉树的遍历221先序遍历递归算法定义：假设二叉树非空，那么依次执行操作： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。ABDGECF2.中序遍历递归算法定义：假设二叉树非空，那么依次执行操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。GDBEACF3后序遍历递归算法定义：假设二叉树非空，那么依次执行操作： (1)遍

8、历左子树； (2)遍历右子树； (3)访问根结点。GDEBFCA23一个图由有限的顶点Vertices和边Edge组成，所以可方式化地用GV，E代表一个图。图中的结点称为顶点，顶点之间的连线代表边。6.2.3 图构造24图(Graph)是由非空的顶点集合和一个描画顶点之间关系边或者弧的集合组成。其方式化定义为：GV，EVvi| vidataobjectE( vi,vj)| vi, vj V P(vi, vj)其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。6.2.3 图构造25以下图

9、无向图G1给出了一个图的例如，在该图中：集合Vv1,v2,v3,v4；集合E(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)6.2.3 图构造26假设数据构造中，数据元素之间不思索关系问题无前趋/后继之分，那么称这种构造为集合。在集合中，各元素是“平等的，它们的共同关系是：都属于同一个集合。6.2.4 集合276.3 算法6.3.1 算法的特性算法是对问题求解过程的一种描画，是为处理一个或一类问题给出的一个确定的、有限长的操作序列。 1.有穷性2.确定性3.可行性4.有输入5.有输出28算法的五个特性1有穷性：对任何合法的输入值，一个算法必需总是在执行有穷步之后终

10、了，且每一步都可在有穷时间内完成；2确定性：算法中每一条指令必需有确切的含义，不会产生二义性，对于一样的输入只能得出一样的输出。3可行性：即算法中描画的操作都可以经过曾经实现的根本运算执行有限次来实现的。4输入：一个算法有0个或多个输入，这些输入取自于某个特定的数据对象的集合，它可以运用输入语句从外部提供，也可以在算法内经过赋初值给定。5输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。29在设计算法时，通常应思索以下原那么：首先设计的算法必需是“正确的其次应有很好的“可读性，还必需具有“强壮性最后还应思索所设计算法的复杂性，即有“高效率与低存储量。6.3.2 什么是“好

11、的算法30算法的正确性所谓算法的正确性，也称可靠性或有效性，是指：程序不含语法错误。程序对于几组输入的数据可以得出满足规格阐明要求的结果。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据可以得出满足规格阐明要求的结果。程序对于一切合法的输入数据都能产生满足规格阐明要求的结果。31在算法是正确的前提下，算法的可读性是摆在第一位的。可读性好有助于人们对算法的了解，难懂的程序易隐藏较多错误，难以调试和修正。算法的效率指的是算法执行时计算机资源的耗费，它包括运转时间代价和存储空间代价。算法的强壮性指的是，算法应对非法输入的数据做出恰当反映或进展相应处置。它强调的是，假设输入非法数据时，算法应能加

12、以识别并做出处置，而不是产生误动作或堕入瘫痪。32算法的复杂性是算法运转所需求的计算机资源的量。算法的复杂性是算法效率的度量，是评价算法优劣的重要根据。 算法的复杂性有时间复杂性和空间复杂性之分。需求的时间资源的量，即算法的运转速度，称作时间复杂性。 需求的空间即存储器资源的量称作空间复杂性。 6.3.3 算法复杂性331自然言语 自然言语是人们日常所用的言语，如汉语、英语、德语等。 例如，求3个数中最大者的问题，可以描画为： 比较前两个数。 将中较大的数与第三个数进展比较。 步骤中较大的数即为所求。6.3.4 算法的表示342流程图 流程图是描画算法的常用工具。它采用美国国家规范化协会ANS

13、IAmerican National Standard Institute规定的一组图形符号来表示算法 起止框判别框处置框输入/输出框注释框流向线衔接点353伪代码 伪代码是用介于自然言语和计算机言语之间的文字和符号来描画算法的工具。它不用图形符号，因此书写方便格式紧凑，易于了解，便于向计算机程序设计言语过渡。 例：求两个数的较大者，用伪代码描画算法如下： Find the bigger Input: two number s:a,b 1. if (the first number a is greater than or equal to the second number b) then

14、1.1 return a else 1.2 return b end if end364计算机程序设计言语 普通而言，计算机程序设计言语描画的算法是明晰的、简明的，最终也能由计算机处置的，然而也不是完善无缺。它需求设计者用特定程序设计言语编写的算法，限制了与他人的交流；容易堕入描画计算步骤的细节而忽视算法的本质。 376.4 程序设计方法6.4.1 计算机程序的性质计算机程序包含两方面的内容：对象及对象之间关系(数据构造)；描画对这些对象进展处置的加工规那么(算法) 。38目的性 程序有明确的目的，程序运转时能完成赋予它的功能。 分步性 程序为完成其复杂的功能，由一系列计算机可执行的步骤组成。

15、 有序性 程序的执行步骤是有序的，不可随意改动程序步骤的执行顺序。 有限性 程序是有限的指令序列，程序所包含的步骤是有限的。 操作性 有意义的程序总是对某些对象进展操作，使其改动形状，完成其功能。计算机程序具有以下性质： 39数据构造是数据构造的逻辑表示方式，算法是处置问题的方法和步骤，最后问题的解由计算机程序给出。这是程序员在程序设计时应思索的主要问题。 6.4.2 程序设计与数据构造、算法之间的关系401. 程序的控制构造一个可以用顺序、选择、循环和跳转(如goto语句)四种程序构造处理的问题，也一定能用顺序、选择、循环三种程序构造处理。但确实存在这样的问题，它可以用顺序、选择、循环三种程

16、序构造处理，但不能用其中任何两种处理。换句话说，顺序、选择、循环三种程序构造构成了一个最小完备集。我们将这三种程序构造叫根本程序构造。6.4.3 构造化程序设计 41三种根本构造的图示：顺序构造选择构造42循环构造的图示：当型(While型)循环构造 直到型(Until型)循环 43顺序程序设计44分支构造45循环构造462.构造化程序设计方法构造化程序设计方法主要包括程序构造的自顶向下和模块化设计方法。47程序设计的普通步骤如下： 1.分析问题 对要处理的问题，首先必需分析清楚，明确标题的要求，列出一切知量，找出标题的求解范围、解的精度等。2.建立数学模型 对实践问题进展分析之后，找出它的内在规律，就可以建立数学模型。只需建立了模型的问题，才干能够利用计算机来处理。3.确定算法 建立