文档介绍：数据结构与算法
算法+数据结构=程序
1. 数据结构
数据结构
逻辑结构
线性结构(线性表、栈、队、串、数组等)
非线性结构
树型结构
图结构
物理(存储)结构
顺序结构
散列结构
链式结构
索引结构
数据运算
插入运算
索引运算
删除运算
修改运算
集合结构
一些基本概念和术语
数据结构:指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关
系组成。
数据:信息的载体,是可以被计算机识别存储并加工处理的描述客观事物的信息符号的总称。
数据元素:数据的基本单位,在计算机程序中通常作为一个整体考虑。一个数据元素由若干个
数据项组成。
数据项:数据的不可分割的最小单位。
数据对象:性质相同的数据元素的集合,是数据的一个子集。
数据处理:指对数据进行查找、插入、删除、合并、排序、统计以及
简单计算等的操作过程。
结构分类
四种不同结构的关系图
集合
线性结构
树型结构
图形结构
储存结构
顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,通常借助于程序设计语言中的数组来实现。
链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现。
索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。
散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。
2. 算法
定义:指解题方案的准确而完整的描述,是一系列解决问题的清晰 指令,算法代表着用系统的方法描述解决问题的策略机制。
用计算装置能够理解的语言描述的解题过程,具有如下性质:
,或作
用于问题自身的描述上,将产生唯一确定的动作
序列,此序列是有限的;
,或终止于指出问
题对此输入无解。
算法有以下几个重要的特征:
(1)有穷性【Finiteness】:算法的有穷性是指算法必须能在执行有限个步骤之后终止;
(2)确切性【Definiteness】:算法的每一步骤必须有确切的定义;
(3)输入项【Input】:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;
(4)输出项【Output】:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
(5)可行性【Effectiveness】:算法中执行的任何计算步骤都是
可以被分解为基本的可执行的操
作步,即每个计算步都可以在有
限时间内完成(也称之为有效性)。
算法的重要特征
算法的评定
(1)时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。
(2)空间复杂度
算法的空间复杂度是指算法需要消耗的内存空间。包括程序所占的空间,输入的初始数据所占的空
间以及运算时所需的空间。
(3)正确性
算法应满足具体问题的需求。正确性是评价一个算法优劣的最重要的标准。
(4)可读性
算法的可读性是指一个算法可供人们阅读的容易程度。算法应该有利于阅读者对
程序的理解。
(5)健壮性
健壮性是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性。
算法的描述方式
一、自然语言:用人们通使用的语言来表示;
二、流程图:一种表示算法的图形工具,用几何图框表示各种类型的操作,在框内写上简明的文字或
符号表示具体的操作,用箭头的流程表示操作的先后顺序;
三、伪代码:一种非正式的,类似于英语结构的,用于描述模块结构图的语言。简单地说,就是让人
便于理解的代码。不依赖于语言用来表示程序执行过程,而不一定能编译运行的代码;
四、PAD图:用二维树形结构的图表示程序的控制流,以PAD图为基础,遵循
机械的走树规则就能方便地编写出程序,用这种图转换为程序
代码比较容易。