数据的组织结构与算法

第六章数据的组织结构与算法6.1数据结构的基本概念6.2常用的几种数据结构6.3算法6.4程序设计方法16.1数据结构的基本概念6.1.1数值计算与非数值计算数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据对客观事物采用计算机能够识别、存贮和处理形式所进行的描述。简言之，数据就是计算机化的信息。数学模型有定量模型和定性模型两类之分，定量模型指的是可以用数值方程表示的一类计算模型，而定性模型则是指非数值性的数据结构,如表、树和图等及其运算。2

数据结构（DataStructure）问题起源于程序设计的发展。第一个8008芯片只有4K的内存，微软的最初成立就是为这个芯片的机器编写BASIC语言，优化在每一处都非常重要。逐渐地，人们注意了数据表示与操作的结构化，把一些确实能够有效解决问题的数据表示和算法总结出来，如表、栈、队、树、图（稍后会介绍这些术语）等被单独抽出研究，而这些方法便形成一门学问，这就是“数据结构”这门学科的来源。6.1.2数据结构的起源3数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系。物理上的数据结构反映成分数据在计算机内部的存储安排。6.1.3对数据结构的理解41.表示对象/实体及其关系在计算机中的表示。只有对象及其相互关系已存储（表示）在计算机中，才能被进一步处理；2.操作：对对象/实体进行处理、访问。数据结构的一般定义：相互之间存在着一定关系的数据元素的集合及定义在其上的操作（运算）称为数据结构。51.插入：在数据结构中的指定位置增添新的数据元素2.删除：删去数据结构中指定的数据元素。3.查找：在数据结构中寻找某个特定要求的数据元素。4.排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按某个关键字值由小到大或由大到小的次序排列。5.遍历：按某一次序访问数据结构中的每一个数据元素。6.1.4对数据结构中数据元素的操作6

[例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数据结构能解决什么问题7定义变量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结束YESNO8[例6-2]电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)(a2,b2)…(ai，bi)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n。9[例6-3]家族成员的族谱表示一个家族的族谱就构成了一个层次结构，在数据结构中，称为树。图6-2给出了这种族谱关系。10一般般用用示示意意图图表表示示数数据据结结构构。。用小小圆圆圈圈代代表表数数据据元元素素，用小小圆圆圈圈之之间间的的连连线线代代表表小小圆圆圈圈对对应应的的数数据据元元素素具具有有的的关关系系，，如果果强强调调关关系系的的方方向向性性，，可可用用带带箭箭头头的的线线段段表表示示关关系系。。具体体地地讲讲，，若若d1和d2表示示两两个个数数据据元元素素，，它它们们具具有有关关系系＜＜d1,d2＞，，则则表表示示为为如如图图6-3所所示示的的结结构构。。图中中表表示示的的只只是是一一个个抽抽象象关关系系，，不不代代表表具具体体意意义义。。对对于于具具体体的的应应用用，，也也可可以以表表示示家家族族关关系系中中的的父父子子关关系系。。例例如如，，＜＜d1,d2＞可代表d1是d2的父亲。数数据结构的的图示116.2常用用的几种数据据结构根据数据元素素之间的关系系的不同，将将数据结构的的逻辑结构分分为集合结构构、线性结构构、树状结构构和图结构（（图6-4））。12

集合：数据元素间间除了“同属属于一个集合合”外，别无无其它关系。。

线性结构：数据元素间间存在一个对对一个的关系系。

树形结构：数据元素间间存在一个对对多个的关系系。

图或网状结构构：数据元素间间存在多个对对多个的关系系。6.2常用用的几种数据据结构131.栈(stack)栈是只能在某某一端插入和和删除的特殊殊线性表。进行删除和插插入的一端称称栈顶，另一堆称栈底。插入一般称为为进栈（Push），删除则称为出栈（Pop）。栈也称为后进进先出表（LIFO：LastIn,FirstOut）。操作系统中的的中断调用及及返回就是采采用栈结构线线性结构14队列是限定在在一端进行插插入，另一端端进行删除和和特殊线性表表。通常把队列的的删除和插入入分别称为出出队和入队。。允许出队的的一端称为队队头，允许入入队的一端称称为队尾。所所有需要进队队的数据项，，只能从队尾尾进入，队列列中的数据项项只能从队头头离去。由于于总是先入队队的元素先出出队（先排队队的人先买完完东西），这这种表也称为为先进先表（（FIFO：：FirstIn,FirstOut））表。2.队列151.链表是指指用一组任意意的存储单元元来依次存放放线性表的数数据元素。2.在存储每每个结点值的的同时，必须须存储指示其其后继（或前前趋）结点的的地址（或位位置）信息，，这个信息称称为指针(pointer)或链(link)。如果链表表的每一个结结点只有一个个指针域，则则这种链表称称为单链表结结点结构，如如图6-9(a)所示；；如果链表的的每一个结点点有两个指针针域，则这种种链表称为双双链表结点结结构。一个指指针域指向其其前趋结点，，一个指针域域向其后继结结点。如图6-9(b)所示。3.链表16[例6.4]单循环链表的的应用单循环链表的的一个典型例例子是约瑟夫环（JosephCircle），其描述如下下：编号为1,2,...,n的n个人人按顺时针方方向围坐一圈圈，每人持有有一个密码（（正整数）。。现在给定一一个随机数m>0，从编编号为1的人人开始，按顺顺时针方向1开始顺序报报数，报到m时停止。报报m的人出圈圈，同时留下下他的密码作作为新的m值值，从他在顺顺时针方向上上的下一个人人开始，重新新从1开始报报数，如此下下去，直至所所有的人出列列为止。17当n和m较大时，，用人工工求解约约瑟夫环环问题是是相当繁繁琐的。。采用单循循环链表表就容易易解决。。其基本思思路是：：ｎ人围成一一圈，把把一人看看成一个个结点，，ｎ人之间的的关系采采用链接接方式，，即每一一结点有有一个前前趋结点点和一个个后继结结点，每每一个结结点有一一个指针针指向下下一个结结点，最最后一个个结点指指针指向向第一个个结点。。这就是是单循环环链的数数据结构构。当ｍ人出列时时，将ｍ结点的前前趋结点点指针指指向ｍ结点的后后继结点点指针，，即把ｍ结点驱出出循环链链。181．树的的定义树是由一一个或多多个结点点组成的的有限集集合，如如图6-12所所示。树树结构19必有一个个特定的的称为根（ROOT）的的结点，，根的每每个分支支称为子树（sub-tree）），子树树也是一一棵树树中的每每一个结结点都可可以不止止一个直直接后继继，结点点的后继继结点称称为该结结点的““子结点点”（Children）除根结点点外的所所有结点点有且只只有一个个直接前前趋,结结点的前前趋结点点称为该该结点的的“父结结点”（（Parent）同一父结结点的子子结点称称为“兄兄弟”（（Sibling）结点下不不再有分分支的称称为树叶叶（leaf）），或者者叶子结结点树结构的的特点20二叉树的的特点：：树中的的每个结结点最多多只有两两棵子树树，即树树中任何何结点的的度数不不得大于于２。二叉树的的子树有有左右之之分，称称为左子子树和右右子树。。而且子子树的左左右次序序是重要要的，即即使在只只有一棵棵子树的的情况下下，也应应分清楚楚。例如如图6-13是是两棵不不同的二二叉树。。2．二叉叉树21所谓遍历历二叉树树，就是是按一定的的规则和和顺序走走遍二叉叉树的所所有结点点，使每一一个结点点都被访访问一次次，而且且只被访访问一次次。二叉树的的遍历可可分为先序遍历历中序遍历历后序遍历历3．二叉叉树的遍遍历221．先序序遍历递递归算法法定义：：若二叉树树非空，，则依次次执行操操作：(1)访问问根结点点；(2)遍遍历左左子树；；(3)遍遍历右子子树。ABDGECF2.中序遍历历递归算算法定义义：若二叉树树非空，，则依次次执行操操作：(1)遍历左左子树；；(2)访问问根结点点；(3)遍遍历右子子树。GDBEACF3．后序序遍历递递归算法法定义：：若二叉树树非空，，则依次次执行操操作：(1)遍历左左子树；；(2)遍历历右子树树；(3)访访问根结结点。GDEBFCA23一个图由由有限的的顶点（（Vertices））和边（（Edge）组组成，所所以可形形式化地地用G＝（V，E））代表一个个图。图图中的结结点称为为顶点，，顶点之之间的连连线代表表边。图图结构24图(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)表示示一条边边。图图结构25下图（无无向图G1）给给出了一一个图的的示例，，在该图图中：集合V＝＝{v1,v2,v3,v4}；集合E＝＝{(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)}图图结构26如果数据据结构中中，数据据元素之之间不考考虑关系系问题（（无前趋趋/后继继之分）），则称称这种结结构为集合。在集合合中，各各元素是是“平等等”的，，它们的的共同关关系是：：都属于于同一个个集合。。集合276.3算算法算算法的特特性算法是对对问题求求解过程程的一种种描述，，是为解解决一个个或一类类问题给给出的一一个确定定的、有有限长的的操作序序列。1.有穷穷性2.确定定性3.可行行性4.有输输入5.有输输出28算法的五五个特性性（1）有穷性：：对任何合合法的输输入值，，一个算算法必须须总是在在执行有有穷步之之后结束束，且每每一步都都可在有有穷时间间内完成成；（2）确定性：：算法中每每一条指指令必须须有确切切的含义义，不会会产生二二义性，，对于相相同的输输入只能能得出相相同的输输出。（3）可行性：：即算法中中描述的的操作都都可以通通过已经经实现的的基本运运算执行行有限次次来实现现的。（4）输入：一个算法法有0个个或多个个输入，，这些输输入取自自于某个个特定的的数据对对象的集集合，它它可以使使用输入语句句从外部提提供，也也可以在在算法内内通过赋初值给定。（5）输出：一个算法法有一个个或多个个的输出出，这些些输出是是同输入入有着某某些特定定关系的的量。29在设计算算法时，，通常应应考虑以以下原则则：首先设计计的算法法必须是是“正确的”其次应有有很好的的“可读性”，还必必须具有有“健壮性”最后还应应考虑所所设计算算法的复复杂性，，即有““高效率与与低存储储量”。什什么是““好”的的算法30算法的正正确性所谓算法法的正确性，也称可可靠性或或有效性性，是指指：程序不含含语法错错误。程序对于于几组输输入的数数据能够够得出满满足规格格说明要要求的结结果。程序对于于精心选选择的典典型、苛苛刻而带带有刁难难性的几几组输入入数据能能够得出出满足规规格说明明要求的的结果。。程序对于于一切合合法的输输入数据据都能产产生满足足规格说说明要求求的结果果。31在算法是是正确的的前提下下，算法法的可读性是摆在第第一位的的。可读读性好有有助于人人们对算算法的理理解，难难懂的程程序易隐隐藏较多多错误，，难以调调试和修修改。算法的效率指的是算算法执行行时计算算机资源源的消耗耗，它包包括运行行时间代代价和存存储空间间代价。。算法的健壮性指的是，，算法应应对非法法输入的的数据做做出恰当当反映或或进行相相应处理理。它强强调的是是，如果果输入非非法数据据时，算算法应能能加以识识别并做做出处理理，而不不是产生生误动作作或陷入入瘫痪。。32算法的复复杂性是是算法运运行所需需要的计计算机资资源的量量。算法法的复杂杂性是算算法效率率的度量量，是评评价算法法优劣的的重要依依据。算法的复复杂性有有时间复杂杂性和空间复杂杂性之分。需要的时时间资源源的量，，即算法法的运行行速度，，称作时间复杂杂性。需要的空空间（即即存储器器）资源源的量称称作空间复杂杂性。算算法复杂杂性331．自然然语言自然语言言是人们们日常所所用的语语言，如如汉语、、英语、、德语等等。例如，求求3个数中中最大者者的问题题，可以以描述为为：①比较较前两个个数。②将①①中较大大的数与与第三个个数进行行比较。。③步骤骤②中较较大的数数即为所所求。算算法的表表示342．流程程图流程图是是描述算算法的常常用工具具。它采采用美国国国家标标准化协协会ANSI（（AmericanNationalStandardInstitute）规定定的一组组图形符符号来表表示算法法起止框判断框处理框输入/输出框注释框流向线连接点353．伪代代码伪代码是是用介于于自然语语言和计计算机语语言之间间的文字字和符号号来描述述算法的的工具。。它不用用图形符符号，因因此书写写方便格格式紧凑凑，易于于理解，，便于向向计算机机程序设设计语言言过渡。。例：求两两个数的的较大者者，用伪伪代码描描述算法法如下：：FindthebiggerInput:twonumbers:a,b1.if(thefirstnumberaisgreaterthanorequaltothesecondnumberb)then1.1returnaelse1.2returnbendifend364．计算算机程序序设计语语言一般而言言，计算算机程序序设计语语言描述述的算法法是清晰晰的、简简明的，，最终也也能由计计算机处处理的，，然而也也不是完完善无缺缺。它需需要设计计者用特特定程序序设计语语言编写写的算法法，限制制了与他他人的交交流；容容易陷入入描述计计算步骤骤的细节节而忽视视算法的的本质。。376.4程程序设设计方法法计计算机程程序的性性质计算机程序包包含两方面的的内容：对象及对象之之间关系(数数据结构)；；描述对这些对对象进行处理理的加工规则则(算法)。。38目的性—程序有明确确的目的，程程序运行时能能完成赋予它它的功能。分步性—程序为完成成其复杂的功功能，由一系系列计算机可可执行的步骤骤组成。有序性—程序的执行行步骤是有序序的，不可随随意改变程序序步骤的执行行顺序。有限性—程序是有限限的指令序列列，程序所包包含的步骤是是有限的。操作性—有意义的程程序总是对某某些对象进行行操作，使其其改变状态，，完成其功能能。计算机程序具具有以下性质质：39数据结构是数数据构造的逻逻辑表示形式式，算法是处处理问题的方方法和步骤，，最后问题的的解由计算机机程序给出。。这是程序员员在程序设计计时应考虑的的主要问题。。程程序设计计与数据结构构、算法之间间的关系401.程序的控制结结构一个可以用顺序、选择、、循环和跳转转(如goto语句)四种程程序结构解决决的问题，也也一定能用顺顺序、选择、、循环三种程程序结构解决决。但确实存在这这样的问题，，它可以用顺顺序、选择、、循环三种程程序结构解决决，但不能用用其中任何两两种解决。换句话说，顺顺序、选择、、循环三种程程序结构构成成了一个最小小完备集。我我们将这三种种程序结构叫叫基本程序结构构。结结构化程序序设计41三种基本结构构的图示：顺序结构选择结构42循环结构的图图示：当型(While型)循循环结构直到型(Until型)循环43顺序程序设计计44分支结构45循环结构462.结构化程程序设计方法法结构化程序设设计方法主要要包括程序结结构的自顶向向下和模块化化设计方法。。47程序设计的一一般步骤如下下：1.分析问题题对要解决的问问题，首先必必须分析清楚楚，明确题目目的要求，列列出所有已知知量，找出题题目的求解范范围、解的精精度等。2.建立数学学模型对实际问题进进行分析之后后，找出它的的内在规律，，就可以建立立数学模型。。只有建立了了模型的问题题，才能可能能利用计算机机来解决。3.确定算法法建立数学模型型后，还不能能着手编程序序，必须根据据数据结构，，确定解决问问题的算法。。一般确定算算法要注意：：算法的逻辑结结构尽可能简简单；算法所要求的的存贮量应尽尽可能少；在满足题目条条件要求下，，使所需的计计算量最小。程程序设计的的步骤484.编写程序序把整个程序看看作一个整体体，先全局后后局部，自顶顶向下，一层层一层分解处处理，如果某某些子问题的的算法相同而而仅参数不同同，可以用子子程序来表示示。5.调试运行行；6.分析结果果；7.写出程序序的文档主要是对程序序中的变量、、函数或过程程作必要的说说明，解释编编程思路，需需要时给出程程序流程图，，并讨论运行行结果。499、静夜四无无邻，荒居居旧业贫。。。1月-231月-23Sunday,January1,202310、雨中中黄叶叶树，，灯下下白头头人。。。20:48:1820:48:1820:481/1/20238:48:18PM11、以我我独沈沈久，，愧君君相见见频。。。1月-2320:48:1820:48Jan-2301-Jan-2312、故人江海别别，几度隔山山川。。20:48:1920:48:1920:48Sunday,January1,202313、乍见翻翻疑梦，，相悲各各问年。。。1月-231月-2320:48:1920:48:19January1,202314、他乡生白白发，旧国国见青山。。。01一月月20238:48:19下下午20:48:191月-2315、比不了了得就不不比，得得不到的的就不要要。。。。一月238:48下午午1月-2320:48January1,202316、行动动出成成果，，工作作出财财富。。。2023/1/120:48:1920:48:1901January202317、做前，能够够环视四周；；做时，你只只能或者最好好沿着以脚为为起点的射线线向前。。8:48:19下午8:48下下午20:48:191月-239、没有失败败，只有暂暂时停止成成功！。1月-231月-23Sunday,January1,202310、很很多多事事情情努努力力了了未未必必有有结结果果，，但但是是不不努努力力却却什什么么改改变变也也没没有有。。。。20:48:1920:48:1920:481/1/20238:48:19PM11、成功就就是日复复一日那那一点点点小小努努力的积积累。。。1月-2320:48:1920:48Jan-2301-Jan-2312、世间成成事，不不求其绝绝对圆满满，留一一份不足足，可得得无限完完美。。。20:48:1920:48:1920:48Sunday,January1,202313、不知知香积积寺，，数里里入云云峰。。。1月-231月-2320:48:1920:48:19January1,202314、意意志志坚坚强强的的人人能能把把世世