463-数据结构与算法.pptVIP

数据结构与算法 数据结构与算法 数据结构是一门研究非数值计算的程序设计问题中,计算机的操作对象以及它们之间关系和操作等的学科. 一个熟练的高级软件开发应用技术人员一般要有三个阶段的训练: 1.结构语言的训练(例:C++语言基础) 2.数据结构知识的训练 3.大型应用程序的训练 用计算机解决具体问题的步骤: 1.建模: 从具体问题抽象出一个适当的数学模型 2.设计算法: 设计一个解此数学模型的算法 3.编写程序 4.调试,运行,得到最后结果 数据结构与算法 第1章 绪论 第1章 绪论 1.1 数据类型与数据结构 数据（Data）是信息的载体，是对自然界客观事物的符号表示。 数据的基本单位是数据元素（Data Element），有时也称作元素、结点、顶点、记录等。 一个数据元素也可以由若干个数据项（Data Item）组成。 数据项是具有独立含义的数据的不可再分割的最小标识单位。 数据组织的三个层次 数据组织的三个层次分别是数据、数据元素、数据项。 数据可以由若干个数据元素组成，数据元素又可以由若干个数据项组成。 数据项是对数据元素属性的描述，数据元素是对客观世界中某个独立个体的数据描述。 数据元素与数据对象 计算机中的数据可以按类型来划分，划分的结果就是数据对象。 所谓数据对象（Data Object），是指具有相同性质的数据元素的集合，是数据的一个子集。如整数数据对象、字母字符数据对象。 在一个具体问题中，数据元素具有相同性质，属于同一数据对象，数据元素是数据对象的一个实例。 数据类型 数据类型（Data Type）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有原子数据类型和结构数据类型之分。 原子数据类型是由程序设计语言提供的一些基本类型。如整型、实型、布尔型和字符型等，其值不可再分解。 结构数据类型是由程序设计语言中提供的构造机制来定义的数据类型。如数组、文件、结构体、共用体等，其值可以再分解；它的构成成分可以是简单数据类型，也可以是结构数据类型。 数据结构的基本概念 数据结构（Data Structure）是指计算机程序中所操作的对象——数据以及数据元素之间的相互关系和运算。 在任何问题中，数据元素之间都不会是独立的，总是存在着这样或那样的关系，这种数据元素之间的关系也称作结构。 数据结构包含以下三个方面的内容： 数据的逻辑结构 数据的存储结构 数据的运算及实现 数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系。 它只抽象地反映数据元素集合的结构，而不管其存储方式，可用一个二元组给出如下的形式定义： Data-Structure ＝（D,R） 其中： D是数据元素的集合； R是D上关系的集合。 从结构的观点出发，一般可将数据结构分为两大类： 线性结构 如线性表、栈、队列、串、数组和文件等； 非线性结构 如树、图和集合等。 线性结构 在线性结构中，D中数据元素之间存在着一对一的次序关系。 其逻辑特征为： 存在一个惟一被称作“第一个”的数据元素，它没有前趋只有一个直接后继；有时也称作开始结点； 存在一个惟一被称之为“最后一个”的数据元素，它没有后继只有一个直接前趋；有时也称作终端结点； 其它数据元素都有且仅有一个直接前趋（immediate predecessor），也有且仅有一个直接后继（immediate successor）。 非线性结构——树型结构 在非线性结构中，D中数据元素之间不存在一对一的次序关系。 树型结构中的数据元素之间，存在着一对多的层次关系，在树型结构中： 没有直接前趋的结点称之为根结点； 除根结点外每个结点有且仅有一个直接前趋（称之为双亲结点）； 没有直接后继的结点称之为叶结点，除叶结点外每个结点都有一个或多个直接后继（称之为孩子结点）。 树的例子很多，如族谱中的家族树、政府机构中的行政树、计算机文件管理中的目录树、编译程序中用到的语法树等。 树型结构示意图 非线性结构——图型结构 非线性结构中的图结构，其数据元素之间既不存在线性结构中的一对一次序关系，也不存在树型结构中的一对多层次关系。 在图型结构中，D中数据元素之间的关系是多对多的网状关系。 换句话说，图是一种网状结构，任意两个数据元素之间都可能相关；其中的每一个数据元素，既可以有多个直接前趋，也可以有多个直接后继。 如交通网络图，课程之间的先后修关系图，软件开发过程中所用到的程序图、控制流图、数据流图等都是图型结构的例子。 图型结构示意图 非线性结构——集合结构 非线性结构中的集合结构，其D中数据元素之间的关系是“属于同一个集合”。 集合是数据元素关系极为松散的一种结构。通常是用其它结构来表示集合。 数据的