绪论数据结构基础

《绪论数据结构基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、绪论数据结构基础本章主要掌握如下内容：数据结构的概念，数据结构描述语言，抽象数据类型ADT,数据存储结构，算法定义及其复杂度问题。1.基本概念和术语1）数据：是对客观事物的符号表示。在计算机科学屮其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。2）数据元素：是数据集合屮的一个实体，是计算机程序屮加工处理的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项纟fl成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元索由多个数据项组成，它通常携带着一个概念的多方面信息。3）

2、数据对象：是性质相同的数据元素的集合，是数据的一个子集。4）数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对彖以及它们Z间关系和操作等的学科。或者说，数据结构是相互之间存在一种或多种特定逻辑关系的数据元素的集合。数据元素之间的相互关系称为结构（Structure）<>••以下为重点掌握内容:根据数据元素Z间的关系，冇四类基木的结构：••••••①集合（元素Z间无密切关系）；②线性结构（元素之间有一个对一个的关系（1:1））;③树形结构（元索之间有一个对多个（l:n）的关系；④图状结构或网状结构（元素之间有多个对多个

3、（n:m）的关系）其中数据元素Z间的关系见下图0-1所示。（b）线性结构（a）集合（c）树形结构图0-1（d）图状结构数据元素之间的关系线性表、堆栈、队列都町认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。『经典例题解析11.以下数据结构中，哪一个是线性结构（）？A.广义表B.二叉树C.稀疏矩阵D.串【答案】Do【解析】广义表是线性表的推广，其数据元素可以具有不同的结构，不是线性结构；二叉树属于树形结构；稀疏矩阵是指那些非零元索较少且分布没有规律的矩阵，往往用三元纽顺序表法、行逻辑连接的顺序表法，以及十字链表法来存

4、储，也不是线性结构；而串是一种线性结构。同线性表不同，串的数据对象约束为字符集，且在串的基本操作中，通常以"串的整体”作为操作对-象。1.下列数据小，（）是非线性数据结构。A.栈B.队列C.完全二叉树D.堆【答案】Co【解析】完全二叉树是一种特殊的二叉树，是非线性数据结构；栈、队列和堆显然属于线性结构。2.数据元素是数据的最小单位。（）【答案】错误。【解析】数据项是数据的最小单位。3.对于给定的n个元素，可以构造出的逻辑结构有（1）,（2）,（3）,（4）四种。【答案】集合，线性结构，树形结构，图状结构。1.数据结构的定义1）

5、形式定义：数据结构是一个二元组：Data_Structure=（D,S）,其小D是数据元索的有限集合，S是D上关系的有限集合。2）逻辑结构和存储结构研究数据结构，不仅要研究其逻辑结构，还要研究其存储结构。逻辑结构主要用于描述数据元素之间的逻辑关系；而存储结构是指数据结构在计算机中的表示，又称为物理结构。以下为重点掌握内容：有两种形式的存储结构：①顺序存储结构：借助元素在存储器中的相对位置來表示数据元素之间的逻辑关系。顺序存储结构••••••••把数据元素存储在一段连续的存储单元里，结点之间的关系由存储单元的关系來直接或间接反映

6、。其主要特点为：•结点中只有口身信息域，没右庠援信尽赅，因此存储翎嬰木，存储空间利用率高；（当前结点不必保存下一个结点的位置信息）•存储空间是连续的，可以通过计算直接确定数据结构屮任意一个结点的存储地址（这就是所••••••谓的随机访问）。②链式存储结构：借助指针来指示逻辑上相邻的数据元素在存储器中的物理位置，因此可以把逻辑••上相邻的两个元素存放在物理上不相邻的存储单元中。其主要特点为：•结构屮除自身信息外，还有表示连接信息的指针域，因此比顺序存储结构的存储密度小，存••••••••储空间利用率低；•存储空间可纠星不堆裟的，

7、因而更适合动态数据的管理。3）常用数据结构的逻辑结构和存储结构•线性结构「町以有顺序、链式、索引和散列四种存储方式。•树形结构：一般采用链式存储方式；在特定的情况下，也可以采用顺序结构（如一维数组）來存储树形结构。•图状结构：一般只能采取链式存储方式；有时町以采用矩阵存储（邻接矩阵法）。『经典例题解析］1.从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构【答案】Co【解析】从逻辑上可以把数据结构分为线性结构和非线性结构；从存储上可以分为顺序结构和

8、链式结构。2.以下与数据的存储结构无关的术语是（）oA.循环队列B.链表C.哈希表D.栈【答案】Do【解析】循环队列指的是队列首尾相连，链表的含义是该线性表是链式存储的，哈希表的含义是某组元素的存储以哈希（杂凑）的方式进行，它们都同存储结构相关；而栈是线性表的一种特殊类型,具