《数据结构域算法设计-第1章 数据结构概述 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第1章 数据结构概述 课件（20页珍藏版）》请在金锄头文库上搜索。
1、第1章 数据结构概述早在上世纪60年代，人类就提出了数字社会的梦想。实 际上，现实世界中的任何事与物都可以进行数字化，它们在 计算机中的表现均为数据。这些数据来源于现实，表征着具 体的意义，而且在计算机中有着统一的表示方法。研究数据 在计算机中的表示方法、存储方法以及在其上的操作，就构 成了数据结构的主要内容。计算机科学各个领域都要用到各 种数据结构。操作系统中用队列、存储管理表及目录树等； 数据库系统运用线性表、索引树等进行数据管理；而在人工 智能领域涉及各种不同的数据结构，如广义表、集合、搜索 树及有向图等。本章主要介绍数据结构和算法的基本概念及 相关内容。1.1 数据结构计算机科学是一门
2、研究数据表示和数据处理的科学。在 利用计算机进行数据处理时，实际需要处理的数据元素一般 有很多。要提高数据处理效率，且节省存储空间，如何组织 数据就成了关键问题。而数据结构用来反映一个数据的内部 构成，即数据由哪些成分构成，以什么方式构成，是什么结 构。为了更好地回答这个问题，下面先对一些基本概念和术 语进行介绍，然后给出数据结构的具体定义。1.1.1 基本概念在系统地学习数据结构知识之前，先对一些基本概念和 术语赋予确切的含义。 1数据（Data） 2数据元素（Data Element）和数据项（Data Item） 3数据对象（Data Object） 4数据类型（Data Type） 5
3、数据结构（Data Structure）1.1.2 什么是数据结构数据结构（Data Structure）是指互相之间存在着一种 或多种关系的数据元素的集合。根据数据元素间关系的不同 特性，通常有下列四类基本的结构： 集合结构 线性结构 树形结构 图形结构1.1.2 什么是数据结构1.1.3 数据结构的逻辑结构和物理结构数据结构包括数据的逻辑结构和数据的物理结构。下面 简要介绍这两种结构的形式。 1逻辑结构 2物理结构数据的存储结构可采用顺序存储或链式存储的方法。 顺序存储方法是把逻辑上相邻的元素存储在物理位置相 邻的存储单元中，由此得到的存储表示称为顺序存储结构。 顺序存储结构是一种最基本的
4、存储表示方法，通常借助于程 序设计语言中的数组来实现。 链式存储方法对逻辑上相邻的元素不要求其物理位置相 邻，元素间的逻辑关系通过附设的指针字段来表示，由此得 到的存储表示称为链式存储结构。链式存储结构通常借助于 程序设计语言中的指针类型来实现。1.1.4 三类数据逻辑结构数据数据的逻辑结构有四种基本类型：集合结构、线性 结构、树形结构和图结构。线性表和树是最常用的两种高效 数据结构，许多高效的算法能够用这两种数据结构来设计实 现。下面通过实例来进一步理解后3类数据结构。 1线性结构 2树形结构 3图形结构1.1.5 数据的操作数据的操作是指作用在某种数据结构上的操作，如插入、 删除、修改等操
5、作。数据结构不同，插入、删除以及修改等的 操作对象也不同，操作所需的条件以及复杂程度也不同。如在 一个线性结构中插入一条记录，只需要知道插入到第几个位置 就可以将数据准确的插入到某个位置。 常见操作总结如下： 1初始化2查找 3插入4修改 5删除6遍历 7销毁1.1.6 数据结构讨论的内容及作用数据结构主要研究数据的各种逻辑结构和在计算机中 的存储结构，还研究对数据进行的查找、插入、删除、排序 、遍历等基本运算或操作以及这些运算在各种存储结构上具 体实现的算法。 当今计算机的操作对象的关系更加复杂，操作形式不 再是单纯的数值计算，而更多的是对这些具有一定关系的数 据进行组织和管理，这就叫做非数
6、值处理，这类问题的数学 模型不再是数学方程所能描述的，而是诸如表、树和图之类 的数据结构。要使计算机能够更有效地进行这些非数值型处 理，就必须弄清楚这些操作对象的特点、在计算机中的表现 方式以及各个操作的具体实现方法。这些都是数据结构这门 课要研究的内容。 1.2 算法上面介绍过了数据结构、数据以及数据操作，而要把这些 编成具有某种功能的程序之前需要思考的就是实现的算法。算 法是独立于具体的实现环境的以及具体的数据结构的，是程序 的“灵魂”。1.2.1 什么是算法算法是对特定问题求解过程的描述，是独立于具体的实 现环境的以及具体的数据结构。一个算法必须满足下面5个 特征。 1有穷性 2确定性
7、3可行性 4有输入 5有输出1.2.2 算法的描述算法的描述是对要解决一个问题或要完成的任务所采取 的方法和步骤的描述，包括需要什么输入数据、输出结果、采 用什么结构及如何安排这些语句等，通常算法的描述方法可以 归纳为以下几种： 自然语言 图形 算法语言 形式语言1.2.3 算法设计的目标设计算法时，一般要达到以下几个目标： （1）正确性 （2）可读性 （3）健壮性 （4）高效性1.2.4 算法效率分析通常情况下，衡量一个算法的好坏需要考虑以下几项原 则：正确性、可读性、健壮性以及时间和空间的复杂度。算 法的效率就是算法的时间复杂度，算法的时间复杂度越低就 说明算法的效率越高。 为了能够比较客
8、观地反映出一个算法的效率，在度量一 个算法的工作量时，不仅应该与所使用的计算机、程序设计 语言以及程序编制者无关，而且还应该与算法实现过程中的 许多细节无关。为此，可以用算法在执行过程中所需基本运 算的执行次数来度量算法的工作量。1.2.5 算法存储空间分析算法的存储空间分析是指分析算法的执行过程中所需的 最大存储空间及分析算法的空间复杂度。算法的空间复杂度 也是衡量一个算法好坏的重要指标。 算法的存储空间包括：算法程序所占的空间、输入的初 始数据所占的存储空间以及算法执行过程中所需要的额外空 间。其中，额外空间包括算法程序执行过程中的工作单元以 及某种数据结构所需要的附加存储空间（例如，在链
9、式结构 中，除了要存储数据本身外，还需要存储链接信息）。如果 额外空间量相对于问题规模来说是常数，则称该算法是原地 （in place）工作的。在许多实际问题中，为了减少算法所 占的存储空间，通常采用压缩存储技术，以便尽量减少不必 要的额外空间。1.2.6 算法设计的基本方法计算机解题的过程实际上是在实施某种算法，这些算法 可称为计算机算法。计算机算法不同于人工处理的方法。在 实际应用时，各种方法之间往往存在着一定的联系。 1列举法 2归纳法 3递推法 4递归法 5减半递推技术 6回溯法1.3 数据结构、算法和程序针对同一问题可以设计多个算法来解决，算法的效率可 通过使用合适的数据结构来改善。
10、例如，可以通过设计合适 的数据结构来降低算法的时空开销等。算法的实现也离不开 具体的数据结构。1.3.1 数据结构与算法简单说来，数据结构是一门研究非数值计算的程序设计 问题中计算机的操作对象以及它们之间的关系和操作等的学 科。例如，图书馆的书目查询系统的自动化问题，可引入线 性的数据结构线性表来解决；计算机和人对奕问题可引 入“树”这种数据结构来建立模型；而多叉路口交通灯的管理 问题可引入“图”这种数据结构来解决。下面以书目查询系统 为例，说明数据结构与算法的关系。1.3.2 数据结构+算法=程序数据结构和算法之间关系密切，这个上面已经提到。著 名的计算机学家N.Width提出了这样一个公式：数据结构+算 法=程序。这一公式揭示了计算机科学的两个重要支柱算法 和数据结构的重要性和统一性。既不能离开数据结构去分析 问题的算法，也不能脱离算法去孤立地研究数据结构。一个 算法结合合适的数据结构并利用机器可执行的指令来书写， 它就是一个程序。1.4 本章小结本章重点介绍了数据结构与算法的相关概念。数据结构 研究的是数据的逻辑结构、存储结构和基本运算，数据结构 是指互相有关联的数据元素的集合，可用 data_Structure=(D,S)表示。算法是程序的“灵魂”，而选择合 适的数据结构是优化算法的重要方法。算法和数据结构构成 了程序。
