数据结构复习重点归纳（适于清华严版教材)[3]

数据结构大学教程

The Complete Data Structure Training Course

第一章 数据结构及其基本概念

Chapter Data Structure and Its Basic Concepts

什么是数据结构(What is Data Structure)

如果你问一个木匠学徒你工作的工具要用什么他可能会回答你我只要一把锤子和一个锯但是如果你去问一个老木工或者是大师级的建筑师他会告诉你我需要一些精确的工具由于计算机所解决的问题都是从生活中抽象出来的问题其复杂性不言而喻所以我们需要这样精确有效的工具去解决现实生活中的复杂问题算法数据结构程序设计语言都是这样的工具数据结构是信息的组织方式对于相同的算法用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率这就有必要研究各种抽象数据类型用不同的数据结构表示的效率差异以及其适用场合

[一]何谓数据结构(What is Data Structure)

数据结构是在整个计算机科学与技术领域上广泛被使用的术语它用来反映一个数据的内部构成即一个数据由哪些成分数据构成以什么方式构成呈什么结构数据结构有逻辑上的数据结构和物理上的数据结构之分逻辑上的数据结构反映成分数据之间的逻辑关系而物理上的数据结构反映成分数据在计算机内部的存储安排数据结构是信息的一种组织方式好的数据结构可以提高算法的效率它通常与一组算法的集合相对应通过这组算法集合可以对数据结构中的数据进行某种操作从学科角度来讲数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科

[二]数据结构学科的研究对象 (The Object of Data Structure Research)

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构以及对数据的各种操作因此主要有三个方面的内容数据的逻辑结构;数据的物理存储结构;对数据的操作(即算法)通常算法的设计取决于数据的逻辑结构算法的实现取决于数据的物理存储结构数据结构的研究不仅涉及到计算机硬件的研究比如存储装置和存取方法而且解决编译原理操作系统数据库系统的数据元素在存储器中的分配问题的重要基础

基本概念与学科术语(Basic Concepts and Terminologies)

数据(Data):是一个集合的概念是对客观事物的符号表示在计算机科学中是指所有能被输入到计算机中并被计算机处理的符号的总称是计算机处理的信息的某种特定的符号表示形式

数据元素(Data Element):是数据的基本单位数据中的一个个体又称为记录或者表目

数据项(Data Item)数据的不可分割的最小单位数据元素是数据项的集合

数据对象(Data Object)是性质相同的数据元素的集合是数据的一个子集

[总结]

数据项组成数据元素数据元素组成数据对象数据对象组成数据

数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合它包括三个方面数据元素的逻辑结构存储结构和相适应的运算(操作)

数据元素之间的逻辑关系被称为数据元素的逻辑结构可以用一个二元组表示

Data_Structure = (D S) // Data_Structure= (Datapart LogicStructurePart)

这里D是数据元素的集合S是定义在D(或其他集合)上的关系的集合

S = { R │ R : D×D×}

数据的逻辑结构可归结为以下四类:

()集合结构

结构中的数据元素之间除了同属于一个集合的关系外别无其他关系

()线性结构

结构中的数据元素之间存在一个对一个的前趋后继关系

在此种结构下

有且仅有一个元素无前趋元素

有且仅有一个元素无后继元素

其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素

()树形结构

结构中的数据元素之间存在一个对多个的关系

任何一个节点最多有一个前趋可以有多个后继是一种典型的非线性结构

()图状结构(网状结构)

结构中的数据元素之间存在多个对多个的关系

这种结构的特征是任何一个元素可以有多个前趋也可以有多个后继是一种多对多的前趋后继关系

表和树是最常用的两种高效数据结构许多高效的算法可以用这两种数据结构来设计实现表是线性结构的(全序关系)树(偏序或层次关系)和图(局部有序(weak/local orders))是非线性结构

数据结构在计算机中的表示(又称为映像)称为数据的存储结构(物理结构)

数据结构的物理结构是指逻辑结构的存储映像(image)数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M(维护着逻辑结构S)的一个映射

PDS) > M

存储器模型一个存储器 M 是一系列固定大小的存储单元每个单元 U 有一个唯一的地址 A(U)该地址被连续地编码每个单元 U 有一个唯一的后继单元 U=succ(U)

P 的四种基本映射模型顺序(sequential)链接(linked)索引(indexed)和散列(hashing)映射因此我们至少可以得到×种可能的物理数据结构

sequential (sets)

linked lists

indexed trees

hashing

graphs

需要指出的是并不是所有的可能组合都合理

数据结构DS上的操作所有的定义在DS上的操作在改变数据元素(节点)或节点的域时必须保持DS的逻辑和物理结构

DS上的基本操作任何其他对DS的高级操作都可以用这些基本操作来实现最好将DS和他的所有基本操作看作一个整体——称之为模块(model)我们可以进一步将该模块抽象为数据类型(其中DS的存储结构被表示为私有成员基本操作被表示为公共方法)称之为ADT(即是抽象数据类型Abstract Data Type指一个数学模型以及定义在该模型上的一组操作)

ADT按照其值的不同特性分为下列三种类型

原子类型(Atomic Data Type)变量是不带结构的不可分解的

固定聚合类型(Fixedaggregate Data Type)其值由确定数目的成分按照某种结构组成

可变聚合类型(VariableAggregate Data Type)值的成分的数目不确定

抽象数据类型的描述方法

抽象数据类型可用(DSP)三元组表示

其中D是数据对象S是D上的关系集P是对D的基本操作集

ADT 抽象数据类型名 {

数据对象〈数据对象的定义〉

数据关系〈数据关系的定义〉

基本操作〈基本操作的定义〉

} ADT 抽象数据类型名

其中数据对象和数据关系的定义用伪码描述基本操作的定义格式为

基本操作名(参数表)

初始条件〈初始条件描述〉

操作结果〈操作结果描述〉

基本操作有两种参数赋值参数只为操作提供输入值;引用参数以&打头 除可提供输入值外还将返回操作结果初始条件描述了操作执行之前数据结构和参数应满足的条件若不满足则操作失败并返回相应出错信息操作结果说明了操作正常完成之后数据结构的变化状况和应返回的结果若初始条件为空则将其省略需要注意的是抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现

顺便提一句多形数据类型(Polymorphic Data Type)是指值的成分不确定的数据类型不过这个不太多见或者是可以用ADT表示所以我们在今后的章节再论述

好的和坏的DS如果一个DS可以通过某种线性规则被转化为线性的DS(例如线性表)则称它为好的DS好的DS通常对应于好的(高效的)算法这是由计算机的计算能力决定的因为计算机本质上只能存取逻辑连续的内存单元因此如何没有线性化的结构逻辑上是不可计算的比如对一个图进行操作要访问图的所有结点则必须按照某种顺序来依次访问所有节点(要形成一个偏序)必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作

树是好的DS——它有非常简单而高效的线性化规则因此可以利用树设计出许多非常高效的算法树的实现和使用都很简单但可以解决大量特殊的复杂问题因此树是实际编程中最重要和最有用的一种数据结构树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代反之亦然实际上每一种递归的结构都可以被转化为(或等价于)树形结构说到递归在北京大学的数据结构课程里面有个老师经常说不懂递归就不算北大计算机系的学生这样看来足以从侧面说明书的结构的重要性

[] [] [] []