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

1第六章数据的组织结构与算法6.1数据结构的基本概念6.2常用的几种数据结构6.3算法6.4程序设计方法26.1数据结构的基本概念6.1.1数值计算与非数值计算数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据对客观事物采用计算机能够识别、存贮和处理形式所进行的描述。简言之，数据就是计算机化的信息。数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而定性模型则是指非数值性的数据结构,如表、树和图等及其运算。3数据结构（DataStructure）问题起源于程序设计的发展。第一个8008芯片只有4K的内存，微软的最初成立就是为这个芯片的机器编写BASIC语言，优化在每一处都非常重要。逐渐地，人们注意了数据表示与操作的结构化，把一些确实能够有效解决问题的数据表示和算法总结出来，如表、栈、队、树、图（稍后会介绍这些术语）等被单独抽出研究，而这些方法便形成一门学问，这就是“数据结构”这门学科的来源。6.1.2数据结构的起源4数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系。物理上的数据结构反映成分数据在计算机内部的存储安排。6.1.3对数据结构的理解51.表示对象/实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进一步处理；2.操作：对对象/实体进行处理、访问。数据结构的一般定义：相互之间存在着一定关系的数据元素的集合及定义在其上的操作（运算）称为数据结构。61.插入：在数据结构中的指定位置增添新的数据元素2.删除：删去数据结构中指定的数据元素。3.查找：在数据结构中寻找某个特定要求的数据元素。4.排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按某个关键字值由小到大或由大到小的次序排列。5.遍历：按某一次序访问数据结构中的每一个数据元素。6.1.4对数据结构中数据元素的操作7[例6.1]解一元二次方程ax2+bx+c=0.利用计算机解此方程，第一个问题就是如何在计算机中表示该方程。分析该方程，可知决定方程的是方程的三个系数值：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数据结构能解决什么问题8定义变量X和一个线性表，如数组intS[3];S[2]，S[1]，S[0]可以分别存放三个系数值输入S[2]，S[1]，S[0]三个系数值输入任意一个值X开始S[2]*X*X+S[1]*X+S[0]1E-5？输出X结束YESNO9[例6-2]电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)(a2,b2)…(ai，bi)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n。10[例6-3]家族成员的族谱表示一个家族的族谱就构成了一个层次结构，在数据结构中，称为树。图6-2给出了这种族谱关系。11一般用示意图表示数据结构。用小圆圈代表数据元素，用小圆圈之间的连线代表小圆圈对应的数据元素具有的关系，如果强调关系的方向性，可用带箭头的线段表示关系。具体地讲，若d1和d2表示两个数据元素，它们具有关系＜d1,d2＞，则表示为如图6-3所示的结构。图中表示的只是一个抽象关系，不代表具体意义。对于具体的应用，也可以表示家族关系中的父子关系。例如，＜d1,d2＞可代表d1是d2的父亲。6.1.6数据结构的图示126.2常用的几种数据结构根据数据元素之间的关系的不同，将数据结构的逻辑结构分为集合结构、线性结构、树状结构和图结构（图6-4）。13◇集合：数据元素间除了“同属于一个集合”外，别无其它关系。◇线性结构：数据元素间存在一个对一个的关系。◇树形结构：数据元素间存在一个对多个的关系。◇图或网状结构：数据元素间存在多个对多个的关系。6.2常用的几种数据结构141.栈(stack)栈是只能在某一端插入和删除的特殊线性表。进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（Push），删除则称为出栈（Pop）。栈也称为后进先出表（LIFO：LastIn,FirstOut）。操作系统中的中断调用及返回就是采用栈结构6.2.1线性结构15队列是限定在一端进行插入，另一端进行删除和特殊线性表。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先表（FIFO：FirstIn,FirstOut）表。2.队列161.链表是指用一组任意的存储单元来依次存放线性表的数据元素。2.在存储每个结点值的同时，必须存储指示其后继（或前趋）结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。如果链表的每一个结点只有一个指针域，则这种链表称为单链表结点结构，如图6-9(a)所示；如果链表的每一个结点有两个指针域，则这种链表称为双链表结点结构。一个指针域指向其前趋结点，一个指针域向其后继结点。如图6-9(b)所示。3.链表17[例6.4]单循环链表的应用单循环链表的一个典型例子是约瑟夫环（JosephCircle），其描述如下：编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人出列为止。18当n和m较大时，用人工求解约瑟夫环问题是相当繁琐的。采用单循环链表就容易解决。其基本思路是：ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前趋结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前趋结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。191．树的定义树是由一个或多个结点组成的有限集合，如图6-12所示。6.2.2树结构20必有一个特定的称为根（ROOT）的结点，根的每个分支称为子树（sub-tree），子树也是一棵树树中的每一个结点都可以不止一个直接后继，结点的后继结点称为该结点的“子结点”（Children）除根结点外的所有结点有且只有一个直接前趋,结点的前趋结点称为该结点的“父结点”（Parent）同一父结点的子结点称为“兄弟”（Sibling）结点下不再有分支的称为树叶（leaf），或者叶子结点树结构的特点21二叉树的特点：树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，称为左子树和右子树。而且子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清楚。例如图6-13是两棵不同的二叉树。2．二叉树22所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。二叉树的遍历可分为先序遍历中序遍历后序遍历3．二叉树的遍历231．先序遍历递归算法定义：若二叉树非空，则依次执行操作：(1)访问根结点；(2)遍历左子树；(3)遍历右子树。ABDGECF2.中序遍历递归算法定义：若二叉树非空，则依次执行操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。GDBEACF3．后序遍历递归算法定义：若二叉树非空，则依次执行操作：(1)遍历左子树；(2)遍历右子树；(3)访问根结点。GDEBFCA24一个图由有限的顶点（Vertices）和边（Edge）组成，所以可形式化地用G＝（V，E）代表一个图。图中的结点称为顶点，顶点之间的连线代表边。6.2.3图结构25图(Graph)是由非空的顶点集合和一个描述顶点之间关系――边（或者弧）的集合组成。其形式化定义为：G＝（V，E）V＝{vi|vi∈dataobject}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。6.2.3图结构26下图（无向图G1）给出了一个图的示例，在该图中：集合V＝{v1,v2,v3,v4}；集合E＝{(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)}6.2.3图结构27如果数据结构中，数据元素之间不考虑关系问题（无前趋/后继之分），则称这种结构为集合。在集合中，各元素是“平等”的，它们的共同关系是：都属于同一个集合。6.2.4集合286.3算法6.3.1算法的特性算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。1.有穷性2.确定性3.可行性4.有输入5.有输出29算法的五个特性（1）有穷性：对任何合法的输入值，一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成；（2）确定性：算法中每一条指令必须有确切的含义，不会产生二义性，对于相同的输入只能得出相同的输出。（3）可行性：即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现的。（4）输入：一个算法有0个或多个输入，这些输入取自于某个特定的数据对象的集合，它可以使用输入语句从外部提供，也可以在算法内通过赋初值给定。（5）输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。30在设计算法时，通常应考虑以下原则：首先设计的算法必须是“正确的”其次应有很好的“可读性”，还必须具有“健壮性”最后还应考虑所设计算法的复杂性，即有“高效率与低存储量”。6.3.2什么是“好”的算法31算法的正确性所谓算法的正确性，也称可靠性或有效性，是指：程序不含语法错误。程序对于几组输入的数据能够得出满足规格说明要求的结果。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。程序对于一切合法的输入数据都能产生满足规格说明要求的结果。32在算法是正确的前提下，算法的可读性是摆在第一位的。可读性好有助于人们对算法的理解，难懂的程序易隐藏较多错误，难以调试和修改。算法的效率指的是算法执行时计算机资源的消耗，它包括运行时间代价和存储空间代价。算法的健壮性指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。它强调的是，如果输入非法数据时，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。33算法的复杂性是算法运行所需要的计算机资源的量。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。算法的复杂性有时间复杂性和空间复杂性之分。需要的时间资源的量，即算法的运行速度，称作时间复杂性。需要的空间（即存储器）资源的量称作空间复杂性。6.3.3算法复杂性341．自然语言自然语言是人们日常所用的语言，如汉语、英语、德语等。例如，求3个数中最大者的问题，可以描述为：①比较前两个数。②将①中较大的数与第三个数进行比较。③步骤②中较大的数即为所求。6.3