【精品数据结构】概论.pptVIP

* 第1章概论 目录 1. 数据结构概述 2. 什么是数据结构 3. 算法 二十世纪四十年代，电子数字计算机问世就是解决复杂的计算问题。早期，电子计算机的应用范围，也只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。 随着计算机科学技术的迅猛发展，计算机的应用已从传统的数值计算领域发展到各种非数值计算领域。当前，计算机已广泛地应用于情报检索、企业管理、系统工程等各个领域；与此相应，计算机的处理对象也从简单的纯数值性数据发展到一般的符号和具有一定结构的数据。 1.1 数据结构概述 问题：对于每一种应用领域的处理对象，如何选择合适的数据表示，如何有效地组织计算机存储，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。 方法：数据结构就是研究和解决这些问题的重要基础理论。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。“数据结构”课程已成为计算机类专业的一门重要专业基础课。 相关术语 1.2什么是数据结构 ?数据(Data)是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的“原料”，而电子计算机则是加工处理数据（信息）的工具。 ??数据元素(Data Element)是数据的基本单位。有些情况下，数据元素也称为结点、顶点、元素、记录。 ??数据项(Data Item)数据的不可分割的具有独立含义的最小单位，数据元素是数据项的集合。 ??数据对象(Data Object)是具有相同性质的数据元素的集合。 ??数据结构(Data Structure)是研究数据元素之间的相互关系，即数据的组织形式。虽然至今还没有一个关于数据结构的标准定义，但它一般包括以下三方面的内容： ① 数据元素之间的逻辑关系，也称为数据的逻辑结构(Logical Structure)。 ② 数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构(Storage Structure)。 ③ 数据的运算，即对数据施加的操作(operation)。 ?数据的逻辑结构是指数据元素和数据元素之间的逻辑关系，它与数据的存储无关，是从具体问题抽象出来的数学模型。 ??数据的存储结构是指逻辑结构在计算机存储器里的实现（亦称为映象），它是依赖于计算机的，我们只在高级语言的层次上讨论存储结构。 ??数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。例如，最常用的运算有：检索、插入、删除、更新、排序等。这些运算实际上是在抽象的数据上所施加的一系列抽象的操作。。 ?所谓抽象的操作，是指我们只知道这些操作是“做什么”，而无须考虑“如何做”。只有确定了存储结构之后，我们才考虑如何具体实现这些运算。换句话说，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。 根据数据元素之间关系的不同，可将数据的逻辑结构分为集合、线性结构、树、图四类 数据类型(Data Type)是指程序设计语言中各变量可取的数据种类。是在程序设计语言中已经实现了的数据结构。 抽象数据类型(Abstract Data Type)是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务（操作）; 抽象数据类型简写做 ADT。 算法与数据结构密切相关，因为数据的运算是通过算法描述的，算法就是解决问题的策略、规则与方法。所以讨论算法是数据结构课程的重要内容之一。 1.3 算法 简单地说算法就是解决特定问题的方法。确切地说，就是对于某一类特定的问题，算法规定了一个运算过程（一系列操作），它必须满足下述准则： ① 输入：具有零个或多个输入的外界量，它们是算法开始 前对算法最初给出的量。 ② 输出：至少产生一个输出，它们是同输入有某种关系的 量。 ③ 有穷性：一个算法必须在执行有穷步之后结束，且每一 步都可在有限时间内完成。 ④ 确定性：算法的每一操作的含义都必须明确，无二义性。⑤ 可行性：算法中每一操作，都是能够由计算机执行的。 1.3.1 什么是算法 求解同一类问题，可以有许多不同的算法，那么如何来评价这些算法的优劣呢？通常可从以下几个方面来衡量： ⑴ 正确性（算法应该是“正确的”，即对任何合法的输入， 算法都能够得到正确的输出。 ⑵ 可读性）算法应易于理解，即在正确性满足的前提下， 越简单越好。 ⑶ 健壮性（算法应能识别非法的输入并能做出处理，而不 是产生误