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