算法与数据结构基础.ppt

第四章算法与数据结构基础,本章学习要点：,算法,程序设计基础,数据结构基础,4.1算法,4.1.1解决实际问题的步骤从问题到程序,1.从具体问题抽象出数学模型（数学建模）,数学建模是十分关键的第一步，同时也是十分困难的一步。,数学模型一般是对实际事物的一种数学简化，建立数学模型的过程，是把错综复杂的实际问题简化、抽象为合理的数学结构的过程。,数学建模不但需要具有深厚扎实的数学基础，而且还要具有敏锐的洞察力、想象力和广博的知识面。,2算法设计,算法的描述通常可以采用“自顶向下、逐步求精”的方法，即先建立一个抽象的、粗略的算法，然后将其逐步细化，更精确地描述出来。,算法是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以便能在有限步骤内得到特定问题的解,3程序设计,问题求解的算法确定之后必须通过程序设计（编码）将其转换为程序，才能在计算机上实现,程序设计是一个将算法转换为用程序设计语言表示的过程。根据实际情况可以采用汇编语言或高级程序设计语言来进行程序设计。,4.调试,调试是为了发现程序中的错误而运行程序的过程。,测试前需要预先设计足够的测试数据，使用这组测试数据来测试程序是否能够获得预期的正确结果。,测试的结果如果正确，则结题结束；否则进一步测试程序是否有错。如果程序有错，则转去修改程序；否则需要检查算法是否有错。如果算法有错，则转去修改算法；否则将需要重新进行数学建模，检查问题的数学模型与实际要求是否相符。,4.1.2什么是算法,1.算法的定义,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列,2算法的特性,（1）有穷性（Finiteness）,一个算法必须在有穷步之后结束，即必须在有限时间内完成。实际应用中，算法的有穷性应该包括执行时间的合理性。,（2）确定性（Definiteness）,算法的每一步必须有确切的含义，无二义性，且在任何条件下算法只有唯一一条执行路径，即对于相同的输入只能得出相同的输出。,（3）可行性（Effectiveness）,算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。,（4）输入（Input）,一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。,（5）输出（Output）,一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。,3算法和程序的区别,一个算法必须是有穷的，但一个程序不一定满足有穷性,程序中的指令必须是机器可执行的，而算法中的指令则无此限制,算法代表了对问题的解，而程序则是算法在计算机上特定的实现,4算法的描述,（1）自然语言描述,自然语言就是用人们日常使用的语言描述解决问题的方法和步骤，描述方法通俗易懂,自然语言在语法和语义上往往具有多义性，并且比较烦琐，对程序流向等描述不明了、不直观,（2）伪代码描述,伪代码是介于自然语言和计算机语言之间的文字和符号，它与一些高级编程语言（如C和C+）类似，但是不需要真正编写程序时所要遵循的严格规则。,伪代码用一种从顶到底，易于阅读的方式表示算法。在程序开发期间，伪代码经常用于“规划”一个程序，然后再转换成某种语言程序。,3流程图描述,流程图使用不同的几何图形来表示不同性质的操作，使用流程线来表示算法的执行方向，,流程图具有直观形象、逻辑清楚、易于理解等特点，但它占用篇幅较大，流程随意转向，规模较大的流程图不易读懂。,图4-1流程图基本符号及其含义,4.1.3算法的评价标准,1正确性,算法的执行结果应当满足预先规定的功能和性能的要求。正确性表明算法必须满足实际需求，达到解决实际问题的目的。,2可读性,一个算法应当思路清晰、层次分明、简单明了、易读易懂。可读性要求表明算法主要是人与人之间交流解题思路和进行软件设计的工具，因此可读性必须强。同时一个可读性强的算法，其程序的可维护性、可扩展性都要好许多，,返回本节首页,返回本章首页,3健壮性,健壮性要求表明算法要全面细致地考虑所有可能出现的边界情况，并对这些边界条件做出完备的处理，尽可能使算法没有意外的情况。,4高效性,有效使用存储空间和有较好的时间效率。高效性要求主要是指时间效率，即解决相同规模的问题时间尽可能短。,4.2程序设计基础,4.2.1程序设计语言,程序设计语言是人与计算机交互的工具，人要把需要计算机完成的工作告诉计算机，就需要使用程序设计语言编写程序，让计算机去执行。,随着计算机科学技术的发展，程序设计语言也经历了机器语言、汇编语言和高级程序设计语言3个阶段。,4.2.2结构化程序设计,1.什么是结构化程序设计,结构化程序设计，是指采用自顶向下、逐步求精的设计方法和单入口、单出口的控制成分的一种程序设计技术。,该设计方法符合人们解决复杂问题的普遍规律，因此可以显著提高程序设计的成功率和生产率。,用先全局后局部、先整体后细节、先抽象后具体的逐步求精过程开发出的程序有清晰的层次结构，容易阅读和理解。,2.结构化程序的3种控制结构,顺序结构,分支结构,循环结构,图4-2顺序结构,图4-3分支结构,图4-4循环结构,4.2.3良好的程序设计风格,在程序设计中要使程序结构合理、清晰，形成良好的编程习惯，对程序的要求不仅是可以在机器上执行，得出正确的结果，而且还要便于程序的调试和维护。应该遵循以下一些规则。,源程序文档化原则,数据说明原则,语句构造原则,输入/输出原则,追求效率原则,返回本节首页,返回本章首页,4.3数据结构基础,4.3.1数据与数据结构,1数据（Data）,数据，指凡是能输入到计算机并能被计算机程序所处理的符号总称。,数据不仅包含用于科学计算的数值，其它如字符、图像、声音、动画、视频等信息都可以视为数据。,2数据元素（DataElement）,数据集合中的每一个个体称为数据元素，它是数据的基本单位，又可称为结点或记录。同类数据元素的集合称为数据对象。,3数据结构（DataStucture）,“数据结构”是指带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种逻辑联系（比如一对一的关系、一对多的关系或多对多的关系）。,4数据结构研究的内容,（1）从学科的角度,逻辑结构,指数据元素之间的逻辑关系，它与数据在计算机中的存储方式无关，数据的逻辑结构分为线性结构、树形结构和网状结构，如图4-5，4-6，4-7所示。,主要研究数据的逻辑结构、物理结构以及数据结构上的基本数据运算。,物理结构,指数据在计算机中是如何表示的，即数据的逻辑结构在计算机存储器上的实现。它有多种不同的方式，其中顺序存储结构和链式存储结构是最常用的两种存储方式。,数据运算,数据的每一种逻辑结构都有相应的基本运算或操作，主要包括建立、查找、插入、删除、修改、排序等。,图4-5线性结构,图4-6树形结构,图4-7网状结构,（2）从课程的角度来看,系统介绍线性表、栈、队列、串、数组与广义表、树和二叉树、图等基本类型的数据结构及其相应运算的实现算法，并将讨论在程序设计中经常会遇到的查找和排序问题。,4.3.2典型的数据结构,1线性表,（1）线性表的定义,线性表是一种最简单且最常用的数据结构，它是由n个数据元素组成的有限序列。每一个数据元素根据不同的情况可以是一个数、一个符号或者一个记录等信息。,图4-8典型的线性表学生成绩表,（2）线性表的存储结构,线性表通常可采用顺序存储和链式存储两种存储结构。,顺序存储结构的线性表（顺序表）,图4-9顺序表结构示意图,使用一组地址连续的存储单元来依次存放线性表中的每个数据元素,长度计算和访问第i个位置的元素等操作都非常方便，效率较高,实现插入或删除表元素，则因为需要移动大量相关元素而花费较多的时间,链式存储结构的线性表（链表）,图4-10链表结构示意图,使用不一定连续的存储单元来存放线性表中的每个数据元素。,每个存储单元除了有一个存放数据元素本身的数据信息的数据域之外，还需要存储一个直接后继元素地址的指针域，如图4-11。,图4-11存储单元结构,（3）线性表的运算,对线性表L，通常可以进行以下一些基本运算。（其中i为位置，X为新元素）,求表的长度Length（L）,取表元素Get（L，i）,查找特定元素Locate（L，x）,插入新元素Insert（L，i，x）,删除表元素Delete（L，i）,2堆栈,（1）堆栈的定义,它是一种操作受限制的特殊线性表，它只能够在表的一端（表尾）进行插入和删除操作，该表尾称为栈顶（top）。,堆栈常用的操作是进栈和出栈，遵循“先进后出”（FILO）的原则进行，如图4-9所示。,图4-12堆栈的进栈和出栈,（2）堆栈的存储结构,堆栈也可分为顺序存储结构的栈（顺序栈）和链式存储结构的栈（链栈）两种，但在实际应用中一般都采用顺序存储结构。,顺序栈中，元素进栈和出栈的操作如图4-13所示。,图4-13顺序栈进栈操作示意图,（3）堆栈的运算,对于一个堆栈S，可以进行以下一些基本运算。（其中X为新元素）,初始化空栈InitStack（S）,进栈Push（S，x）,出栈POP（S）,取栈顶元素Gettop（S）,3队列,（1）队列的定义,它也是一种操作受限制的特殊线性表，与栈不同的是，队列中规定只能在表的一端（表尾）进行插入操作，而在表的另一端（表头）进行删除操作,队列常用的操作是入队列和出队列，遵循“先进先出”（FIFO）的原则进行，如图4-14所示。,图4-14队列的入队列和出队列操作示意图,（2）队列的存储结构,队列的存储结构也可分为顺序存储结构的队列（顺序队列）和链式存储结构的队列（链队列）两种，实际应用中更多地是采用链式