昭通昭阳区城乡建设管理局网站深圳手机医疗网站建设

当前位置： 首页 > news >正文

昭通昭阳区城乡建设管理局网站,深圳手机医疗网站建设,wordpress配置字体,房价下跌最惨10大城市1.1 数据结构的研究内容 计算机解决问题的步骤 从具体问题抽象出数学模型设计一个解此数学模型的算法编写程序#xff0c;进行测试、调试#xff0c;直到解决问题 计算机解决问题的过程中寻求数学模型的实质是 分析问题#xff0c;从中提取操作的对象#xff0c;并找出这些…1.1 数据结构的研究内容 计算机解决问题的步骤 从具体问题抽象出数学模型设计一个解此数学模型的算法编写程序进行测试、调试直到解决问题 计算机解决问题的过程中寻求数学模型的实质是 分析问题从中提取操作的对象并找出这些操作对象之间的关系 操作对象与操作对象之间的关系就是数据结构 用数学语言加以描述即建立相应的数学方程 数据结构主要研究非数值计算问题非数值计算问题无法用数学方程建立数学模型数据结构是一门研究非数值计算程序设计中的操作对象(如表、树、图)以及这些对象之间的关系和操作的学科 1.2 基本概念和术语 1.2.1 数据、数据元素、数据项和数据对象 数据(Data) 是客观事物的符号表示是所有能输人到计算机中并被计算机程序处理的符号的总称。数据是信息的载体能够被计算机识别、存储和加工数据包括数值型数据(如整数、实数)和非数值型数据(如文字、图) 数据元素(Data Element) 是数据的基本单位在计算机中通常作为一个整体进行考虑和处理。某些情况下数据元素也称为元素、记录、节点、顶点。数据元素用于完整地描述一个对象如学生表中的一名学生记录一个数据元素由若干个数据项组成 数据项(Data ltem) 是组成数据元素的、有独立含义的、不可分割的最小单位。例如学生基本信息中的学号、姓名、性别等都是数据项。 数据对象(Data Object) 是性质相同的数据元素的集合是数据的一个子集。例如学生基本信息表中的一些学生记录是一个数据对象。 数据、数据元素、数据项之间的关系 数据 数据元素 数据项 数据元素与数据对象 数据元素 组成数据的基本单位与数据的关系集合的个体 数据对象 性质相同的数据元素的集合与数据的关系集合的子集
1.2.2 数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 数据结构是带“结构”的数据元素的集合“结构”是指数据元素之间存在的关系 数据结构包括逻辑结构和存储结构 逻辑结构 数据元素之间的逻辑关系数据的逻辑结构是从逻辑关系上描述数据与数据的存储无关是独立于计算机的是从具体问题抽象出来的数学模型 存储结构 数据元素及其关系在计算机内存中的表示又称映像、存储方式数据对象在计算机中的存储表示称为数据的存储结构也称为物理结构 既要存储各数据元素的数据又要存储数据元素之间的逻辑关系 逻辑结构种类的划分 将逻辑结构划分为线性结构和非线性结构 线性结构有且仅有一个开始和一个终端节点并且所有节点都最多只有一个直接前趋和一个直接后继 如线性表、栈、队列 非线性结构一个节点可能有多个直接前趋或多个直接后继 如树、图 将逻辑结构划分为四种基本的逻辑结构 集合结构数据元素之间除了“属于同一个集合”的关系外别无其他关系线性结构数据元素之间存在一对一的关系树结构数据元素之间存在一对多的关系图结构或网状结构数据元素之间存在多对多的关系其中集合结构、树结构、图结构数据非线性结构 逻辑结构种类的划分 顺序存储结构 顺序存储结构是借助元素在存储器种的相对位置来表示数据元素之间的逻辑关系通常借助程序设计语言的数组类型来描述顺序存储结构要求所有的元素依次存放在一片连续的存储空间中 链式存储结构 用一组任意的存储单元存储数据元素数据元素之间的逻辑关系使用指针来表示链式存储结构通常借助于程序设计语言的指针类型来描述 索引存储结构 在存储节点信息的同时建立附加的索引表可以加快查询速度 散列存储结构 根据节点的关键字直接计算出该节点的存储地址 逻辑结构和存储结构的关系 存储结构是逻辑关系的映像于元素本身的映像逻辑结构是数据结构的抽象存储结构是数据结构的实现逻辑结构与存储结构综合起来建立了数据元素之间的结构关系
1.2.3 数据类型和抽象数据类型 数据类型 是一组性质相同的值的集合和定义在这个值集上的一组操作的总称数据类型隐含地规定了数据的取值范围、存储方式以及允许进行的运算数据类型 值得集合 值集合上得一组操作 抽象数据类型 抽象就是抽取出实际问题得本质抽象数据类型是指一个数学模型以及定义在此数学模型上得一组操作的总称不考虑计算机内的具体存储结构和运算的具体实现算法 数学模型由用户定义的、表示应用问题的数学模型抽象数据类型具体包括数据对象、数据对象上关系的集合、数据对象的基本操作的集合 抽象数据类型的形式化定义 抽象数据类型可用DSP三元组表示 D数据对象S数据对象上的关系集P对数据对象的基本操作集 抽象数据类型的定义格式 ADT 抽象数据类型名 {数据对象数据对象的定义数据关系数据关系的定义基本操作基本操作的定义 } ADT 抽象数据类型名数据对象和数据关系的定义采用数学符号和自然语言描述基本操作的定义格式 基本操作名(参数表)初始条件初始条件描述操作结果操作结果描述操作结果的两种参数 赋值参数为操作提供输入值引用参数以开头除了可以提供输入值外还可返回操作结果 初始条件描述了操作执行之前数据结构和参数应该满足的条件若不满足则操作失败并返回相应出错信息若初始条件为空则省略操作结果说明了操作正常完成之后数据结构的变化状况和应该返回的结果 抽象数据类型的定义举例 Circle的定义 ADT Circle {数据对象D {rxy | rxy 均为实数}数据关系R {rxy | r 是半径xy 是圆心坐标}基本操作Circle(Crxy)操作结果构造一个圆double Area©初始条件圆存在操作结果计算面积double Circumference©初始条件圆存在操作结果计算周长 } ADT Circle1.3 抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型来表示实现即利用处理器中已经存在的数据类型来说明新的结构用已经实现的操作来组合新的操作使用类C语言作为抽象数据类型的表示与实现的描述工具以复数为例 抽象数据类型的定义 ADT Complex {数据对象:D{e1,e2| e1,e2∈R,R是实数集}数据关系:S{e1,e2le1是复数的实部e2是复数的虚部}基本操作:Creat ( C, x, y )操作结果:构造复数C其实部和虚部分别被赋以参数x和y的值。GetReal©初始条件:复数C已存在。操作结果:返回复数C的实部值。GetImag©初始条件:复数C已存在。操作结果:返回复数C的虚部值。Add(c1,c2)初始条件:c1c2是复数。操作结果:返回两个复数c1和C2的和。Sub(c1,c2)初始条件:c1c2是复数。操作结果:返回两个复数c1和 c2的差。 }ADT Complex抽象数据类型的表示部分类C语言 typedef struct // 复数类型 {float Realpart // 实部float Imagepart // 虚部 }Complex;抽象数据类型的实现部分类C语言 void Create( Complex Cfloat xfloat y){ //构造一个复数C.Realpartx;C.Imageparty;}float GetReal (Complex C){ //取复数Cxyi的实部return C.Realpart;}float GetImag (Complex C){ //取复数Cxyi的虚部return C.Imagepart ;}Complex Add (Complex C1Complex C2){ //求两个复数C1和C2的和sumComplex sum;sum.RealpartC1.Realpart C2.Realpart ;sum.ImagepartC1.Imagepart C2.Imagepart;return sum;}Complex Sub (Complex C1, Complex C2){ //求两个复数C1和C2的差differenceComplex difference;difference.RealpartC1.Realpart-C2.Realpart;difference.ImagepartC1.Imagepart-C2.Imagepart;return difference;}1.4 算法和算法分析 1.4.1 算法的定义及特性 算法 对特定问题求解方法和步骤的一种描述它是指令的有限序列其中每个指令表示一个或多个操作算法就是解决问题的方法和步骤 算法的描述方法 自然语言描述流程图伪代码、类语言程序代码 算法与程序 算法 是解决问题的一种方法或一个过程考虑如何将输入转换为输出一个问题可以有多种算法 程序 是用某种程序设计语言对算法的具体实现程序 数据结构 算法 数据结构通过算法实现操作算法根据数据结构设计程序 算法的五个重要特性 有穷性算法在执行有穷步之后结束且每一步都必须在有穷步时间内完成确定性对于每种情况下所执行的操作在算法中都有确切的规定不会产生二义性使算法的执行者和阅读者都能明确其含义及如何执行对于相同的输入只能得到相同的输出可行性算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现输入一个算法有0个或多个输入输出一个算法有一个或多个输出
1.4.2 评价算法优劣的基本标准 正确性 在合理的数据输入下能够在有限的运行时间内得到正确的结果。程序对于精心选择的、典型、苛刻且带有刁难的几组输入数据可以得出满足要求的结果 可读性 一个好的算法首先应便于人们理解和相互交流其次才是机器可执行性。可读性强的算法有助于人们对算法的理解而难懂的算法易于隐藏错误且难于调试和修改。 健壮性 当输人的数据非法时好的算法能适当地做出正确反应或进行相应处理而不会产生一些莫名其妙的输出结果。 高效性 高效性包括时间和空间两个方面。花费尽量少的时间和尽量低的存储需求时间高效是指算法设计合理执行效率高可以用时间复杂度来度量空间高效是指算法占用存储容量合理可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。
1.4.3 算法的时间复杂度 算法效率分析的目的 看算法实际是否可行并在同一问题存在多个算法时可进行时间和空间性能上的比较以便从中挑选出较优算法。 算法的效率从以下两个方面进行考虑 时间效率 指算法所耗费的时间 空间效率 指算法执行过程中所耗费的存储空间 时间效率与空间效率有时是矛盾的 算法的时间效率可以依据该算法编写的程序在计算机上执行所消耗的时间来度量衡量算法效率的方法主要有两类 事后统计法事前分析估算法 事后统计法 需要先将算法实现然后测算其时间和空间开销。必须把算法转换成可执行的程序耗费时间和精力时空开销的测算结果依赖于计算机的软硬件等环境因素这容易掩盖算法本身的优劣。 事前分析估算法 对算法所消耗资源的一种估算方法通过计算算法的渐近复杂度来衡量算法的效率。算法运行时间 一个简单操作所需的时间 X 简单操作的次数也即算法中每条语句的执行时间之和 算法运行时间 Σ(每条语句的执行次数 X 该语句执行一次所需的时间) 一条语句的重复执行次数称为语句频度 算法运行时间 Σ(每条语句的频度 X 该语句执行一次所需的时间) 设每条语句执行一次所需的时间为单位时间则一个算法的执行时间可用该算法中所有语句频度之和来度量为了便于比较不同的算法的时间效率仅比较算法的数量级即只采用算法中基本语句的执行次数来度量算法的工作量 基本语句算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献度最大执行的次数最多 使用O表示数量级算法中基本语句重复执行的次数是问题规模n的某个函数f(n)算法的时间度量为T(n) O(f(n))表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐渐时间复杂度简称时间复杂度 例如f(n)2n33n22n1f(n) 2n^3 3n^2 2n 1f(n)2n33n22n1则T(n) O(f(n)) O(n3)一般情况下不必计算所有操作的执行次数而只需考虑算法中基本操作执行的次数它是问题规模n的某个函数用T(n)表示 定理1.1 若f(n)amnmam−1nm−1…a1na0f(n) amn^m a{m-1}n^{m-1} … a_1n a0f(n)am​nmam−1​nm−1…a1​na0​是一个m次多项式则T(n)O(nm)T(n) O(n^m)T(n)O(nm)在计算算法时间复杂度时可用忽略所有低次幂项和最高次幂的系数这样可以简化算法分析也体现出增长率的含义 分析算法时间复杂度的基本方法 1.找出语句频度最大的那条语句作为基本语句2.计算基本语句的频度得到问题规模n的某个函数f(n)3.取其数量级用符号“O”表示 算法的时间复杂度分析举例 x 1; for (i1; in; i)for (j1; ji; j)for (k1; kj; k)x;∑i1n∑j1i∑k1j1\sum{i1}^{n} \sum{j1}^{i} \sum{k1}^{j} 1∑i1n​∑j1i​∑k1j​1∑i1n∑j1ij\sum{i1}^{n} \sum{j1}^{i} j∑i1n​∑j1i​j∑i1ni(i1)2\sum{i1}^{n} \frac{i(i1)}{2}∑i1n​2i(i1)​12(∑i1ni2(∑i1ni)\frac{1}{2} (\sum{i1}^{n} i^2 (\sum_{i1}^{n} i)21​(∑i1n​i2(∑i1n​i)12(n(n1)(2n1)6n(n1)2)\frac{1}{2}(\frac{n(n1)(2 n1)}{6}\frac{n(n1)}{2})21​(6n(n1)(2n1)​2n(n1)​)该算法的时间复杂度为T(n) O(n3) for (i1; in; ii*2) {x;s0; }若循环执行1次i 1*2 2若循环执行2次i 2*2 22若循环执行3次i 3*2 23…若循环执行x次i x*2 2x设循环中语句的执行次数为x由于循环条件in所以2xn2^xn2xnxlog2nx log_2nxlog2​n所以该算法的时间复杂度为T(n)O(log2n)T(n) O(log_2n)T(n)O(log2​n) 常见的时间复杂度按数量级递增排列依次为 常数阶 O(1)、对数阶 O(log2nlog_2nlog2​n)、线性阶 O(n)、线性对数阶 O(nlog2nnlog_2nnlog2​n)、平方阶 O(n2)、立方阶 O(n3)、…、k次方阶 O(nk)、指数阶 O(2n)、阶乘 O(n!) 一般情况下随着n增大T(n)的增长较慢的算法为较优的算法一般情况下算法的时间复杂度不仅与问题的规模有关还与问题的其他因素相关如随问题的输入数据集不同而不同最好时间复杂度 算法在最好情况下的时间复杂度指算法计算量可能达到的最小值 最坏时间复杂度 算法在最坏情况下的时间复杂度指算法计算量可能达到的最大值 平均时间复杂度 指算法在所有可能情况下按照输入实例以等概率出现时算法计算量的加权平均值 很多情况下算法的平均复杂度难于确定通常在讨论算法在最坏情况下的时间复杂度即分析在最坏情况下算法执行时间的上界保证算法的运行时间不会比它更长大O的加法法则与乘法法则 加法法则T(n)T1(n)T2(n)O(f(n))O(g(n))O(max(f(n),g(n)))T(n) T_1(n) T_2(n) O(f(n)) O(g(n)) O(max(f(n), g(n)))T(n)T1​(n)T2​(n)O(f(n))O(g(n))O(max(f(n),g(n)))乘法发则T(n)T1(n)∗T2(n)O(f(n))∗O(g(n))O(f(n)∗g(n))T(n) T_1(n) * T_2(n) O(f(n)) * O(g(n)) O(f(n) * g(n))T(n)T1​(n)∗T2​(n)O(f(n))∗O(g(n))O(f(n)∗g(n))
1.4.4 算法的空间复杂度 采用渐近空间复杂度作为算法所需存储空间的量度简称空间复杂度它也是问题规模n的函数记作 S(n)O(f(n))S(n) O(f(n))S(n)O(f(n)) 一般情况下一个程序在机器上执行时除了需要寄存本身所用的指令、常数、变量和输入数据外还需要一些对数据进行操作的辅助存储空间。若算法执行时所需要的辅助空间相对于输入数据量而言是个常数则称这个算法为原地工作辅助空间为O(1)求算法的空间复杂度举例。 数组逆序将一维数组逆序存放为原数组算法1 for (i0; in; i) {t a[i];a[i] a[n-i-1];a[n-i-1] t; }算法1仅需要另外借助一个变量t与问题规模n大小无关所以其空间复杂度为O(1)。 算法2 for (i0; in; i)b[i] a[n-i-1]; for (i0; in; i)a[i] b[i];算法2需要另外借助一个大小为n的辅助数组b所以其空间复杂度为O(n)。 对于一个算法其时间复杂度和空间复杂度往往是相互影响的当追求一个较好的时间复杂度时可能导致占用较多的存储空间即可能使空间复杂度的性能变差反之亦然