文档介绍：公共基础知识部分之第一章数据结构与算法 算法 数据结构的基本概念 线性表及其顺序存储结构 栈和队列 线性链表 树与二叉树 查找技术 排序技术 算法的基本概念所谓算法是指解题方案的准确而完整的描述。§ 算法 1、算法的基本特征>可行性:算法原则上能够精确地执行,甚至人们只用笔和纸做有限次运算即可完成。>确定性:算法的每一步都必须有确切的定义>有穷性:一个算法必须在执行有穷步后结束,即算法必须能够终止>拥有足够的情报:我们要使算法有效就必须拥有足够的情报 2、算法的基本要素> 数据对象的运算和操作 (+、-、*、/) (&、||、!) (>、<、=、#) (赋值、输入、输出) >算法的控制结构一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 3、算法设计基本方法列举法: 指针对待解决的问题,列举所有可能的情况,并用问题中给定的条件来检验。归纳法:特殊——一般的抽象过程递推: 从已知初始条件出发,逐次推出所要求的各中间结构和最后结果递归: 将复杂的问题逐层分解,最后归结为一个简单的问题, 再沿原分解的逆过程逐步进行综合。分为直接递归和间接递归减半递推技术: 把规模较大较复杂的问题,分成几个规模较小较简单的问题回溯法: 通过对问题的分析,找出一个解决问题的线索,多次试探,若成功,则得出解,若失败,则回退,换别的路线再进行试探 算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联系。 1、算法的时间复杂度指执行算法所需要的计算工作量。工作量可以用算法在执行过程中所需基本运算的执行次数来度量。其中基本运算次数是问题规模的函数,即算法的工作量=f(n) 。>平均性态>最坏情况复杂性注意:算法程序执行的具体时间受使用计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关 2、算法的空间复杂度指执行这个算法所需要的内存空间,包含: >算法程序所占的空间>输入的初始数据所占的空间>算法执行过程中所需要的额外空间§ 数据结构的基本概念数据结构作为计算机的一门学科,主要研究以下三个方面的问题: (1)数据的逻辑结构(2)数据的存储结构(物理结构) (3)对各种数据结构进行的运算数据结构学科的研究目的:提高数据处理的效率。主要包括 1、数据的处理速度 2、尽量节省在数据处理过程中所占用的计算机存储空间 数据结构的定义数据处理:是指对数据集合中的各元素以各种形式进行运算。包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素。数据结构:是指反映数据元素之间关系的数据元素集合的表示。数据元素之间的任何关系都可以用前后件关系来描述。 1、数据的逻辑结构所谓逻辑结构实际上就是指数据元素之间的前后件关系。其中前后件关系是指它们的逻辑关系,而与他们在计算机中的存储位置无关。它包含两个要素: ?数据元素的集合,通常记为 D; ?数据元素之间的关系(前后件关系),通常记为 R。形式表示如下: B=(D,R)其中 B表示数据结构 2、数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(即数据的物理结构)。常用的存储结构有顺序、链接、索引等存储结构。