0 绪论 据结构基础.doc

绪论 数据结构基础 本章主要掌握如下内容： 数据结构的概念，数据结构描述语言，抽象数据类型ADT，数据存储结构，算法定义及其复杂度问题。 知识点分析 1．基本概念和术语 1）数据：是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。 2）数据元素：是数据集合中的一个实体，是计算机程序中加工处理的基本单位。 数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。 3）数据对象：是性质相同的数据元素的集合，是数据的一个子集。 4）数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。或者说，数据结构是相互之间存在一种或多种特定逻辑关系的数据元素的集合。数据元素之间的相互关系称为结构（Structure）。 以下为重点掌握内容： 根据数据元素之间的关系，有四类基本的结构： ① 集合（元素之间无密切关系）； ② 线性结构（元素之间有一个对一个的关系（1:1））； ③ 树形结构（元素之间有一个对多个（1:n）的关系； ④ 图状结构或网状结构（元素之间有多个对多个（n:m）的关系） (b) 线性结构 (c) 树形结构 (d) 图状结构图0 (b) 线性结构 (c) 树形结构 (d) 图状结构 图0-1 数据元素之间的关系 (a) 集合 线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。 『经典例题解析』 1．以下数据结构中，哪一个是线性结构（ ）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 【答案】D。 【解析】广义表是线性表的推广，其数据元素可以具有不同的结构，不是线性结构；二叉树属于树形结构；稀疏矩阵是指那些非零元素较少且分布没有规律的矩阵，往往用三元组顺序表法、行逻辑连接的顺序表法，以及十字链表法来存储，也不是线性结构；而串是一种线性结构。同线性表不同，串的数据对象约束为字符集，且在串的基本操作中，通常以“串的整体”作为操作对象。 2. 下列数据中，（ ）是非线性数据结构。 A．栈 B. 队列 C. 完全二叉树 D. 堆 【答案】C。 【解析】完全二叉树是一种特殊的二叉树，是非线性数据结构；栈、队列和堆显然属于线性结构。 3. 数据元素是数据的最小单位。( ) 【答案】错误。 【解析】数据项是数据的最小单位。 4. 对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，_（4）_四种。 【答案】集合，线性结构 ，树形结构，图状结构。 2．数据结构的定义 1）形式定义：数据结构是一个二元组：Data_Structure = (D , S)，其中D是数据元素的有限集合，S是D上关系的有限集合。 2）逻辑结构和存储结构 研究数据结构，不仅要研究其逻辑结构，还要研究其存储结构。逻辑结构主要用于描述数据元素之间的逻辑关系；而存储结构是指数据结构在计算机中的表示，又称为物理结构。 以下为重点掌握内容： 有两种形式的存储结构： 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。顺序存储结构把数据元素存储在一段连续的存储单元里，结点之间的关系由存储单元的关系来直接或间接反映。其主要特点为： 结点中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；（当前结点不必保存下一个结点的位置信息） 存储空间是连续的，可以通过计算直接确定数据结构中任意一个结点的存储地址（这就是所谓的随机访问）。 链式存储结构：借助指针来指示逻辑上相邻的数据元素在存储器中的物理位置，因此可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。其主要特点为： 结构中除自身信息外，还有表示连接信息的指针域，因此比顺序存储结构的存储密度小，存储空间利用率低； 存储空间可以是不连续的，因而更适合动态数据的管理。 3）常用数据结构的逻辑结构和存储结构 线性结构：可以有顺序、链式、索引和散列四种存储方式。 树形结构：一般采用链式存储方式；在特定的情况下，也可以采用顺序结构（如一维数组）来存储树形结构。 图状结构：一般只能采取链式存储方式；有时可以采用矩阵存储（邻接矩阵法）。 『经典例题解析』 1．从逻辑上