1、第六章第六章 数据的组织结构与算法数据的组织结构与算法 6.1 数据结构的基本概念数据结构的基本概念 6.2 常用的几种数据结构常用的几种数据结构 6.3 算法算法 6.4 程序设计方法程序设计方法16.1数据结构的基本概念数据结构的基本概念 6.1.1 数值计算与非数值计算数值计算与非数值计算 数据是描述客观事物的数值、字符以及能输入机器数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，且能被处理的各种符号集合。换句话说，数据对客数据对客观事物采用计算机能够识别、存贮和处理形式所进观事物采用计算机能够识别、存贮和处理形式所进行的描述行的描述。简言之，。简言之，数
2、据就是计算机化的信息数据就是计算机化的信息。数学模型有定量模型和定性模型两类之分，定量模数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而型指的是可以用数值方程表示的一类计算模型，而定性模型则是指非数值性的数据结构定性模型则是指非数值性的数据结构,如表、树和图如表、树和图等及其运算。等及其运算。2 数据结构（数据结构（Data StructureData Structure）问题起源于程序设计的发）问题起源于程序设计的发展。展。第一个第一个80088008芯片只有芯片只有4K4K的内存，微软的最初成立就是的内存，微软的最初成立就是为这个芯片的机器编写为这个
3、芯片的机器编写BASICBASIC语言，优化在每一处都语言，优化在每一处都非常重要。逐渐地，人们注意了数据表示与操作的结非常重要。逐渐地，人们注意了数据表示与操作的结构化，把一些确实能够有效解决问题的数据表示和算构化，把一些确实能够有效解决问题的数据表示和算法总结出来，如表、栈、队、树、图（稍后会介绍这法总结出来，如表、栈、队、树、图（稍后会介绍这些术语）等被单独抽出研究，而这些方法便形成一门些术语）等被单独抽出研究，而这些方法便形成一门学问，这就是学问，这就是“数据结构数据结构”这门学科的来源。这门学科的来源。6.1.2 6.1.2 数据结构的起源数据结构的起源3 数据结构有逻辑上的数据结构
4、和物理上的数据结构之数据结构有逻辑上的数据结构和物理上的数据结构之分分 。逻辑上的数据结构反映成分数据之间的逻辑关系。逻辑上的数据结构反映成分数据之间的逻辑关系。物理上的数据结构反映成分数据在计算机内部的物理上的数据结构反映成分数据在计算机内部的存储安排。存储安排。6.1.3 6.1.3 对数据结构的理解对数据结构的理解41.表示表示 对象对象/实体及其关系在计算机中的表示。只有对象及实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进其相互关系已存储（表示）在计算机中，才能被进一步处理；一步处理；2.操作：对对象操作：对对象/实体进行处理、访问。实体进行处理、
5、访问。数据结构数据结构的一般的一般定义定义：相互之间存在着一定关系的：相互之间存在着一定关系的数据元素的集合及定义在其上的操作（运算）称为数据元素的集合及定义在其上的操作（运算）称为数据结构。数据结构。51.1.插入插入：在数据结构中的指定位置增添新的数据元素：在数据结构中的指定位置增添新的数据元素2.2.删除删除：删去数据结构中指定的数据元素。：删去数据结构中指定的数据元素。3.3.查找查找：在数据结构中寻找某个特定要求的数据元素。：在数据结构中寻找某个特定要求的数据元素。4.4.排序排序：（在线性结构中）重新安排数据元素之间的逻：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按某
6、个关键字值由小到大或由大到辑顺序关系，使之按某个关键字值由小到大或由大到小的次序排列。小的次序排列。5.5.遍历遍历：按某一次序访问数据结构中的每一个数据元素。：按某一次序访问数据结构中的每一个数据元素。6.1.4 6.1.4 对数据结构中数据元素的操作对数据结构中数据元素的操作6 例例6.1 6.1 解一元二次方程解一元二次方程axax2 2+bx+c=0.+bx+c=0.利用计算机解此方程，第一个问题就是利用计算机解此方程，第一个问题就是如何在计算机中如何在计算机中表示该方程表示该方程。分析该方程，可知决定方程的是方程的三个系。分析该方程，可知决定方程的是方程的三个系数值：数值：a a、b
7、 b、c c，而它们的次序表示它们分别属于那一项，而它们的次序表示它们分别属于那一项，其他符号是为增加可读性而引入的，因此，可用这三个系数其他符号是为增加可读性而引入的，因此，可用这三个系数的线性排列在计算机中表示该方程。例如：的线性排列在计算机中表示该方程。例如：3x3x2 2-x+1=0-x+1=0表示为（表示为（3,-1,13,-1,1）x x2 2-3=0-3=0 表示为表示为(1,0,-3)(1,0,-3)在数据结构中，在数据结构中，将若干个数线性排列的数（元素）称为将若干个数线性排列的数（元素）称为线性表，线性表，因此，一元二次方程因此，一元二次方程axax2 2+bx+c=0+b
8、x+c=0就在计算机中表示就在计算机中表示为线性表（为线性表（a,b,ca,b,c）。解方程实质上是）。解方程实质上是对线性表对线性表(a,b,c)(a,b,c)进行操作。进行操作。6.1.5 6.1.5 数据结构能解决什么问题数据结构能解决什么问题7定义变量X和一个线性表，如数组int S3;S2，S1，S0可以分别存放三个系数值输入S2，S1，S0三个系数值输入任意一个值X开始S2*X*X+S1*X+S00，从编号为，从编号为1的人开始，按顺时针方向的人开始，按顺时针方向1开始开始顺序报数，报到顺序报数，报到m时停止。报时停止。报m的人出圈，同时留下他的密码作为新的的人出圈，同时留下他的密
9、码作为新的m值，值，从他在顺时针方向上的下一个人开始，重新从从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至开始报数，如此下去，直至所有的人出列为止。所有的人出列为止。17u 当当n和和m较大时，用人工求解约瑟夫环问题是相当繁琐的。较大时，用人工求解约瑟夫环问题是相当繁琐的。u 采用单循环链表就容易解决。采用单循环链表就容易解决。u 其基本思路是：其基本思路是：人围成一圈，把一人看成一个结点，人围成一圈，把一人看成一个结点，人之间的关系采用链接方人之间的关系采用链接方式，即每一结点有一个前趋结点和一个后继结点，每一个结点有一式，即每一结点有一个前趋结点和一个后继结点，每一个结
10、点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当是单循环链的数据结构。当人出列时，将人出列时，将结点的前趋结点指针结点的前趋结点指针指向指向结点的后继结点指针，即把结点的后继结点指针，即把结点驱出循环链。结点驱出循环链。18 1 1树的定义树的定义 树是由一个或多个结点组成的有限集合，如图树是由一个或多个结点组成的有限集合，如图6-126-12所示。所示。6.2.2 6.2.2 树结构树结构19u 必有一个特定的称为必有一个特定的称为根根（ROOT）的结点，根的每个分支）的结点，根的每个分支称为称
11、为子树子树（sub-tree），子树也是一棵树），子树也是一棵树u 树中的每一个结点都可以不止一个直接后继，结点的后继树中的每一个结点都可以不止一个直接后继，结点的后继结点称为该结点的结点称为该结点的“子结点子结点”（Children）u 除根结点外的所有结点有且只有一个直接前趋除根结点外的所有结点有且只有一个直接前趋,结点的前趋结点的前趋结点称为该结点的结点称为该结点的“父结点父结点”（Parent）u 同一父结点的子结点称为同一父结点的子结点称为“兄弟兄弟”（Sibling）u 结点下不再有分支的称为树叶（结点下不再有分支的称为树叶（leaf），或者叶子结点），或者叶子结点树结构的特点树结
12、构的特点20二叉树的特点：树中的每个结点最多只有两棵子树，即树中二叉树的特点：树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于。任何结点的度数不得大于。二叉树的子树有左右之分，称为左子树和右子树。而且子树二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的，即使在只有一棵子树的情况下，也应的左右次序是重要的，即使在只有一棵子树的情况下，也应分清楚。例如图分清楚。例如图6-136-13是两棵不同的二叉树。是两棵不同的二叉树。2 2二叉树二叉树21所谓遍历二叉树，就是所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所按一定的规则和顺序走遍二叉树的所有结点有结点，使每
13、一个结点都被访问一次，而且只被访问一次。，使每一个结点都被访问一次，而且只被访问一次。二叉树的遍历可分为二叉树的遍历可分为 先序遍历先序遍历 中序遍历中序遍历 后序遍历后序遍历 3 3二叉树的遍历二叉树的遍历22若二叉树非空，则依次执行操作：若二叉树非空，则依次执行操作：(1)(1)访问根结点；访问根结点；(2)(2)遍历左子树；遍历左子树；(3)(3)遍历右子树。遍历右子树。A AB BD DG GE EC CF F2.若二叉树非空，则依次执行操作：若二叉树非空，则依次执行操作：(1)(1)遍历左子树；遍历左子树；(2)(2)访问根结点；访问根结点；(3)(3)遍历右子树。遍历右子树。G G
14、D DB BE EA AC CF F若二叉树非空，则依次执行操作：若二叉树非空，则依次执行操作：(1)(1)遍历左子树；遍历左子树；(2)(2)遍历右子树；遍历右子树；(3)(3)访问根结点。访问根结点。G GD DE EB BF FC CA A23 一个图由有限的顶点（一个图由有限的顶点（VerticesVertices）和边（）和边（EdgeEdge）组成，）组成，所以可形式化地用所以可形式化地用G G（V V，E E）代表一个图。图中的结点代表一个图。图中的结点称为顶点，顶点之间的连线代表边。称为顶点，顶点之间的连线代表边。6.2.3 6.2.3 图结构图结构24图图(Graph)(Gr
15、aph)是由非空的顶点集合和一个描述顶点之间关系是由非空的顶点集合和一个描述顶点之间关系边（或者弧）的集合组成。边（或者弧）的集合组成。其形式化定义为：其形式化定义为：G G（V V，E E）V Vvi|vi|vidataobjectvidataobject E E(vi,vjvi,vj)|vi,)|vi,vjvj V V P(viP(vi,vjvj)其中，其中，G G表示一个图，表示一个图，V V是图是图G G中顶点的集合，中顶点的集合，E E是图是图G G中边的中边的集合，集合集合，集合E E中中P(vi,vjP(vi,vj)表示顶点表示顶点vivi和顶点和顶点vjvj之间有一条直之间有一
16、条直接连线，即偶对接连线，即偶对(vi,vjvi,vj)表示一条边表示一条边。6.2.3 6.2.3 图结构图结构25下图（无向图下图（无向图G1G1）给出了一个图的示例，在该图中：）给出了一个图的示例，在该图中：集合集合V Vv1,v2,v3,v4v1,v2,v3,v4；集合集合E E(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)6.2.3 6.2.3 图结构图结构26u如果数据结构中，数据元素之间不考虑关系问题（无前如果数据结构中，数据元素之间不考虑关系问题（无前趋趋/后继之分），
17、则称这种结构为后继之分），则称这种结构为集合集合。在集合中，各。在集合中，各元素是元素是“平等平等”的，它们的共同关系是：都属于同一个的，它们的共同关系是：都属于同一个集合。集合。6.2.4 6.2.4 集合集合276.3 6.3 算法算法6.3.1 6.3.1 算法的特性算法的特性 算法是对问题求解过程的一种描述，是为解决一个或算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。一类问题给出的一个确定的、有限长的操作序列。1.1.有穷性有穷性2.2.确定性确定性3.3.可行性可行性4.4.有输入有输入5.5.有输出有输出28算法的五个特性算法的五个特性（
18、1 1）对任何合法的输入值，一个算法必须总是在执行对任何合法的输入值，一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成；有穷步之后结束，且每一步都可在有穷时间内完成；（2 2）算法中每一条指令必须有确切的含义，不会产生算法中每一条指令必须有确切的含义，不会产生二义性，对于相同的输入只能得出相同的输出。二义性，对于相同的输入只能得出相同的输出。（3 3）即算法中描述的操作都可以通过已经实现的基本即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的运算执行有限次来实现的。（4 4）一个算法有一个算法有0个或多个输入，这些输入取自于某个特个或多个输入，这些输入取自于某个
19、特定的数据对象的集合，它可以使用定的数据对象的集合，它可以使用输入语句输入语句从外部提供，也从外部提供，也可以在算法内通过可以在算法内通过赋初值赋初值给定。给定。（5 5）一个算法有一个或多个的输出，这些输出是同输入一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量有着某些特定关系的量。29 在设计算法时，通常应考虑以下原则：在设计算法时，通常应考虑以下原则：首先设计的算法必须是首先设计的算法必须是“正确的正确的”其次应有很好的其次应有很好的“可读性可读性”，还必须具有，还必须具有“健壮性健壮性”最后还应考虑所设计算法的复杂性，即有最后还应考虑所设计算法的复杂性，即有“高效率与低
20、高效率与低存储量存储量”。6.3.2 6.3.2 什么是什么是“好好”的算法的算法30算法的正确性算法的正确性所谓算法的所谓算法的，也称可靠性或有效性，是指：，也称可靠性或有效性，是指：程序不含语法错误。程序不含语法错误。程序对于几组输入的数据能够得出满足规格说明要求的程序对于几组输入的数据能够得出满足规格说明要求的结果。结果。程序对于精心选择的典型、苛刻而带有刁难性的几组输程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。入数据能够得出满足规格说明要求的结果。程序对于一切合法的输入数据都能产生满足规格说明要程序对于一切合法的输入数据都能产生满足规格说明要求
21、的结果。求的结果。31在算法是正确的前提下，算法的在算法是正确的前提下，算法的是摆在第一位的。可是摆在第一位的。可读性好有助于人们对算法的理解，难懂的程序易隐藏较多错读性好有助于人们对算法的理解，难懂的程序易隐藏较多错误，难以调试和修改。误，难以调试和修改。算法的算法的指的是算法执行时计算机资源的消耗，它包括运指的是算法执行时计算机资源的消耗，它包括运行时间代价和存储空间代价。行时间代价和存储空间代价。算法的算法的指的是，算法应对非法输入的数据做出恰当反指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。它强调的是，如果输入非法数据时，算映或进行相应处理。它强调的是，如果输入非法数据时，
22、算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。32算法的复杂性是算法运行所需要的计算机资源的量。算法算法的复杂性是算法运行所需要的计算机资源的量。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。的复杂性是算法效率的度量，是评价算法优劣的重要依据。算法的复杂性有算法的复杂性有时间复杂性时间复杂性和和空间复杂性空间复杂性之分。之分。需要的时间资源的量，即算法的运行速度，称作需要的时间资源的量，即算法的运行速度，称作。需要的空间（即存储器）资源的量称作需要的空间（即存储器）资源的量称作。6.3.3 6.3.3 算法复杂性算法复杂
23、性331 1自然语言自然语言 自然语言是人们日常所用的语言，如汉语、英语、德语自然语言是人们日常所用的语言，如汉语、英语、德语等。等。例如，求例如，求3 3个数中最大者的问题，可以描述为：个数中最大者的问题，可以描述为：比较前两个数。比较前两个数。将中较大的数与第三个数进行比较。将中较大的数与第三个数进行比较。步骤中较大的数即为所求。步骤中较大的数即为所求。6.3.4 6.3.4 算法的表示算法的表示342 2流程图流程图 流程图是描述算法的常用工具。它采用美国国家标准化协会流程图是描述算法的常用工具。它采用美国国家标准化协会ANSIANSI（American National Standar
24、d InstituteAmerican National Standard Institute）规定的一组图形符）规定的一组图形符号来表示算法号来表示算法 起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点353 3伪代码伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便格式紧凑，描述算法的工具。它不用图形符号，因此书写方便格式紧凑，易于理解，便于向计算机程序设计语言过渡。易于理解，便于向计算机程序设计语言过渡。例：求两个数的较大者，用伪代码描述
25、算法如下：例：求两个数的较大者，用伪代码描述算法如下：Find the bigger Find the bigger Input:two number s:a,b Input:two number s:a,b 1.if(the first number a is greater than or equal to the 1.if(the first number a is greater than or equal to the second number b)second number b)then then 1.1 return a 1.1 return a else else 1.2 r
26、eturn b 1.2 return b end if end if end end364 4计算机程序设计语言计算机程序设计语言 一般而言，计算机程序设计语言描述的算法是清一般而言，计算机程序设计语言描述的算法是清晰的、简明的，最终也能由计算机处理的，然而也不是晰的、简明的，最终也能由计算机处理的，然而也不是完善无缺。它需要设计者用特定程序设计语言编写的算完善无缺。它需要设计者用特定程序设计语言编写的算法，限制了与他人的交流；容易陷入描述计算步骤的细法，限制了与他人的交流；容易陷入描述计算步骤的细节而忽视算法的本质。节而忽视算法的本质。376.4 6.4 程序设计方法程序设计方法6.4.1
27、6.4.1 计算机程序的性质计算机程序的性质 计算机程序包含两方面的内容：计算机程序包含两方面的内容：对象及对象之间关系对象及对象之间关系(数据结构数据结构)；描述对这些对象进行处理的加工规则描述对这些对象进行处理的加工规则(算法算法)。38 程序有明确的目的，程序运行时能完成赋予它的程序有明确的目的，程序运行时能完成赋予它的功能。功能。程序为完成其复杂的功能，由一系列计算机可执程序为完成其复杂的功能，由一系列计算机可执行的步骤组成。行的步骤组成。程序的执行步骤是有序的，不可随意改变程序步程序的执行步骤是有序的，不可随意改变程序步骤的执行顺序。骤的执行顺序。程序是有限的指令序列，程序所包含的步
28、骤是有程序是有限的指令序列，程序所包含的步骤是有限的。限的。有意义的程序总是对某些对象进行操作，使其改有意义的程序总是对某些对象进行操作，使其改变状态，完成其功能。变状态，完成其功能。计算机程序具有以下性质：计算机程序具有以下性质：39 数据结构是数据构造的逻辑表示形式，算法是处理问题数据结构是数据构造的逻辑表示形式，算法是处理问题的方法和步骤，最后问题的解由计算机程序给出。这是的方法和步骤，最后问题的解由计算机程序给出。这是程序员在程序设计时应考虑的主要问题。程序员在程序设计时应考虑的主要问题。6.4.2 6.4.2 程序设计与数据结构、算法之间的关系程序设计与数据结构、算法之间的关系401
29、.1.程序的控制结构程序的控制结构 一个可以用一个可以用顺序、选择、循环和跳转顺序、选择、循环和跳转(如如gotogoto语句语句)四种程序结构解决的问题，也一定能用顺序、选择、四种程序结构解决的问题，也一定能用顺序、选择、循环三种程序结构解决。循环三种程序结构解决。但确实存在这样的问题，它可以用顺序、选择、循但确实存在这样的问题，它可以用顺序、选择、循环三种程序结构解决，但不能用其中任何两种解决。环三种程序结构解决，但不能用其中任何两种解决。换句话说，顺序、选择、循环三种程序结构构成了换句话说，顺序、选择、循环三种程序结构构成了一个最小完备集。我们将这三种程序结构叫一个最小完备集。我们将这三
30、种程序结构叫基本程基本程序结构。序结构。6.4.3 6.4.3 结构化程序设计结构化程序设计 41三种基本结构的图示：顺序结构顺序结构选择结构选择结构42循环结构的图示：当型当型(While型型)循环结构循环结构 直到型直到型(Until型型)循环循环 43顺序程序设计顺序程序设计44分支结构分支结构45循环结构循环结构462.2.结构化程序设计方法结构化程序设计方法 结构化程序设计方法主要包括程序结构的自顶向下和模结构化程序设计方法主要包括程序结构的自顶向下和模块化设计方法。块化设计方法。47 程序设计的一般步骤如下：程序设计的一般步骤如下：1.1.分析问题分析问题 对要解决的问题，首先必须
31、分析清楚，明确题目的要求，对要解决的问题，首先必须分析清楚，明确题目的要求，列出所有已知量，找出题目的求解范围、解的精度等。列出所有已知量，找出题目的求解范围、解的精度等。2.2.建立数学模型建立数学模型 对实际问题进行分析之后，找出它的内在规律，就可以对实际问题进行分析之后，找出它的内在规律，就可以建立数学模型。只有建立了模型的问题，才能可能利用建立数学模型。只有建立了模型的问题，才能可能利用计算机来解决。计算机来解决。3.3.确定算法确定算法 建立数学模型后，还不能着手编程序，必须根据数据结建立数学模型后，还不能着手编程序，必须根据数据结构，确定解决问题的算法。一般确定算法要注意：构，确定
32、解决问题的算法。一般确定算法要注意：算法的逻辑结构尽可能简单；算法的逻辑结构尽可能简单；算法所要求的存贮量应尽可能少；算法所要求的存贮量应尽可能少；在满足题目条件要求下，使所需的计算量最小在满足题目条件要求下，使所需的计算量最小。6.4.4 6.4.4 程序设计的步骤程序设计的步骤48 4.4.编写程序编写程序 把整个程序看作一个整体，先全局后局部，自顶向把整个程序看作一个整体，先全局后局部，自顶向下，一层一层分解处理，如果某些子问题的算法相下，一层一层分解处理，如果某些子问题的算法相同而仅参数不同，可以用子程序来表示。同而仅参数不同，可以用子程序来表示。5.5.调试运行；调试运行；6.6.分析结果；分析结果；7.7.写出程序的文档写出程序的文档 主要是对程序中的变量、函数或过程作必要的说明，主要是对程序中的变量、函数或过程作必要的说明，解释编程思路，需要时给出程序流程图，并讨论运解释编程思路，需要时给出程序流程图，并讨论运行结果。行结果。49
