文档介绍：第一节算法
算法概念
算法:解题方案的准确而完整的描述。
(算法不等于程序)
1、算法基本特征:
可行性:(算法与计算公式有差别)
确定性:算法中的每一个步骤都必须有明确定义的,不允许有模棱两可的解释,也不允许有多义性。
有穷性:算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
算法有穷性还应包括合理的执行时间的含义
4)拥有足够的情报
2、算法的基本要素:
两种基本要素:一是对数据对象的运算和操作,二是算法的控制结构。
1)算法中对数据的运算和操作(在计算机中)
算术运算:
逻辑运算:
关系运算:
数据传输:
算法的主要特征着重于算法的动态执行。
2)算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具:传统流程图、N-S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
算法设计基本方法
列举法:
基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型问题。
归纳法:
基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。
递推:
是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。本质上也属于归纳法。
递归:
在解决一些复杂问题时,为了降低问题的复杂程度,一般总是将问题逐层分解,最后归结为一些最简单的问题。本质上也属于归纳法。
递归分为直接递归与间接递归两种。
减半递推技术(分治法)
所谓“减半”,是指将问题的规模减半,而问题的性质不变;所谓“递推”,是指重复“减半”产过程。
回溯法
二、算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1、时间复杂度
是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即:算法的工作量=f(n)
其中n是问题的规模。
在同一个问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入时,可以用以下两种方法来分析算法的工作量。
平均性态:是指用各种特定输入下的运算次数的加权平均值来试题算法的工作量。
设x是所有可能输入中的某个特定输入,p(x)是x出现的概率,t(x)是算法在输入为x时所执行的基本运算次数,则算法的平均性态定义为:
其中Dn表示当规模为n时,算法执行时所有可能输入的集合。
2)最坏情况复杂性
是指在规模为n时,算法所执行的基本运算的最大次数,定义为:
2、算法的空间复杂度
一般是指执行这个算法所需要的内存空间。
第二节数据结构的基本概念
主要研究和讨论以下三个方面的问题:
数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。
在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。
对各种数据结构进行的运算。
一、什么是数据结构
定义:
数据处理:是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。
数据结构:相互有关联的数据元素的集合。
数据元素(元素):现实世界中客观存在的一切个体都可以是数据元素。
在数据处理领域中,每一个需要处理的对象都可以抽象成数据元素。
在数据处理领域中,通常把数据元素之间这种固有的关系简单地用前后件(直接前驱与直接后继)关系来描述。
1、数据的逻辑结构
一个数据结构应包含以下两方面的信息:
表示数据元素的信息;(D:数据元素的集合)
表示各数据元素之间的前后件关系。(R:前后件关系)
所谓数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。
一个数据结构可以表示成:B=(D,R)
其中B表示数据结构。
例:一年四季的数据结构:
B=(D,R)
D={春,夏,秋,冬}
R={(春,夏)(夏,秋)(秋,冬)}
2、数据的存储结构:(数据的物理结构)
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。
一种数据的逻辑结构根据需要可以表示成多种存储结构。
二、数据结构的图形表示
:数据结点(结点)
:有向线段前件结点à后件结点
在数据结构中,没有前件的结点称为根结点;没有后件的结点称为终端结点(叶子结点);除了根结点与终结点外的其他结点一般称为内部结点。
三、线性结构与非线性结构
1、空的数据结构:在一个数据结构中一个数据元素都没有。
2、非空的数据结构:在一个空的数据结构中插入一个新元素后就变为非空;将该元素删除后就变为空的数据结构。
2、线性结构(线性表)
如果一个非空的数据结构满足下列两个条件,则称其为