数据结构绪论--课件.pptVIP

*1.4算法和算法分析2算法描述对于一个实际问题，分析采用适合的数学模型，选择合适的数据结构，将求解过程和步骤完整、准确地描述出来。自然语言描述伪码表示流程图表示N-S图表示程序设计语言表示**ppt课件*3算法分析研究和比较各种算法的性能和优劣。算法的衡量标准正确性（无语法错误，对于合法的数据输入能够得到正确的输出结果）可读性健壮性（对于非法的数据输入能够给出相应的反应）时间效率和存储需求1.4算法和算法分析Q2.算法设计的要求？**ppt课件*3算法分析算法分析方法算法分析的两个主要方面时间复杂度：算法对时间的需求。 T(n)=O(f(n))n:表示问题的规模。f(n):表示基本操作执行的次数是问题规模n的某个函数。O表示T(n)的量级。严格的数学定义为，T(n)和f(n)是定义在正整数集合上的两个函数，则存在正的常数C和n0，使得当n=n0时，都满足：1.4算法和算法分析Q3.时间复杂度如何表示？**ppt课件*temp=i;i=j;j=temp;分析算法时间复杂度（1）上面程序段的执行时间是与问题规模n无关的常数。因此算法的时间复杂度为常数阶，记做T(n)=O(1)。若算法的执行时间不随问题规模n的增加而增加，则即使算法中有成千条语句，其执行时间也是一个常数。其时间复杂度为O(1)。1次1次1次总执行频度为31.4算法和算法分析**ppt课件*s=0;for(i=0;in;i++) s=s+i;分析算法时间复杂度（2）因此T(n)=2n+2=O(n)。上面算法的时间复杂度为O(n)。1次n+1次n次总执行频度为2n+21.4算法描述与分析**ppt课件信息工程学院武汉理工大学信息工程学院数据结构*ppt课件*第一章绪论基本概念和术语1算法的表示与分析2**ppt课件*1.1什么是数据结构Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3《数据结构》课程介绍**ppt课件*1.1什么是数据结构Q1：如何采用计算机解决问题？答：寻求数学模型的实质： 分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。(2)设计解此数学模型的算法；(1)从具体问题抽象出一个适当的数学模型；(3)编程，测试、调整直至得到最终解答。**ppt课件*1.1什么是数据结构Q2：数据结构解决什么样的问题？答：数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。**ppt课件*1.1什么是数据结构Q3：《数据结构》课程介绍介于数学、计算机硬件和计算机软件三者之间的一门核心课程*关系对象关系操作数学软件硬件对象关系操作*ppt课件*1.1什么是数据结构算法+数据结构＝程序处理问题的策略问题的数学模型用计算机解决问题的一般步骤：寻求一个适当的数学模型设计一个解决问题的算法编写代码，调试直至得到解答**ppt课件*【例1】数据管理问题—线性问题1.1什么是数据结构**ppt课件*【例2】棋类对弈问题—树型结构1.1什么是数据结构**ppt课件*【例3】交通、道路等问题—图型1.1什么是数据结构**ppt课件*1.2基本概念与术语Q1什么是数据结构？Q2数据结构涵盖的主要内容？Q3学习数据结构有什么用？**ppt课件*答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。元素有限集关系有限集1.2基本概念与术语1基本概念和术语Q1：什么是数据结构？**ppt课件*1基本概念和术语1.2基本概念与术语术语：数据、数据元素和数据项（见教材P4定义）：数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据数据元素数据项例：班级