> 文档中心 > 数据结构基本概念

数据结构基本概念


1、什么是数据结构

答:数据结构研究的是数据以及数据之间的关系和运算,即数据结构就是指数据以及数据之间的关系和运算。(计算机的操作对象就是数据)

2、算法是什么?

答:算法是对计算机上执行的计算过程的具体描述。

3、算法和数据结构的关系?

答:算法依赖于具体的数据结构,数据结构直接关系到算法的选择和效率。

4、数据结构产生的原因?

由于应用问题的复杂程度不断增加、信息量剧增与信息范围的拓宽,导致程序规模越来越大,程序结构更加复杂,为了解决这些问题必须研究数据之间的关系,数据结构由此而生。

数据结构的基本术语

数据:数据结构中的数据是指可以输入到计算机中并可以被计算机识别、存储和加工处理的符号,是计算机处理的信息的符号化表现形式,例如声音、图像、文本、视频、整数、实数等都可以用数据来表示。

数据元素:数据元素是数据的基本单位,也是数据结构中讨论的基本单位,简称元素。一个数据元素可以包含一个简单的数据项,如一个实数,也可以包含多个不同类型或者相同类型的数据项,如一名教师、一本图书、一件商品信息等都包含多个数据项,数据元素可以是具体的,也可以是抽象的,如一次旅游、一次会议、一次考试等,一个客观存在的事件都可以是数据元素。

数据项:数据项是数据的不可分割的最小单位,又称数据域,数据项也是数据结构讨论的最小单位,数据元素是数据项的集合。例如一名教师信息包括年龄、身高、体重、教师编号、性别等,教师信息是数据元素,年龄等信息是数据项,教师信息这个数据元素有年龄等数据项组成。

数据对象:数据对象是具有相同性质的数据元素的集合,是数据的一个子集。例如:整数数据对象={0,±1,±2,...},数据对象可以是有穷集,也可以是无穷集。

数据结构:结构是把成员组织在一起的方式,数据结构就是以数据为成员的结构,数据结构就是把数据元素组织在一起的方式,是带结构的数据元素的集合,数据元素之间存在着一种或多种特定的关系。例如:在银行办业务的队列中,每个顾客不仅有个人信息,还有相互之间的先后顺序关系,地图上每个城市除了有城市名称等数据信息外还有相互之间的位置关系。

结点:数据结构中的数据元素称为结点,在研究实际问题时,一个结点可以是用高级语言的基本数据类型表示的信息,例如一个字符、一个整数,还可以是由基本数据类型的某种组成方式构成的复杂信息,如:学生的基本信息等。数据结构将结点看成一个整体,重点讨论结点之间的关系。

数据处理:数据处理是指对数据元素处理的方式,包括对数据的增、删、改、查、排序等基本操作,也包括对数据元素的分析操作。

数据结构研究学习的三个方面:

 数据的逻辑结构:在数据集合中,各种数据元素之间固有的逻辑关系。

 数据的存储结构:在对数据进行存储时,各数据元素在计算机中的存储关系。

 数据结构的操作:各种数据结构要进行的操作,以及基于计算机中的存储方式如何实现这些操作,简单来说就是说各种数据结构都有哪些操作以及如何实现这些操作。

数据元素之间的关系:具有相同特征的数据元素集合中,通常数据元素之间固有的关系用前驱和后继关系描述;一般来说,数据元素之间的任何关系都可以用前驱和后继关系来描述。

数据的逻辑结构

数据的逻辑结构定义了数据结构中数据元素之间的逻辑关系。

逻辑结构包含两方面信息:1、数据元素的信息;2、各数据元素之间的关系。

将数据的逻辑结构定义:一个数据结构是一个二元组:Date_Structures=(D,R); 其中D是数据元素的有限集,R是D上关系的有限集。

一般以二元组的形式表示D中各数据元素之间的关系;例如:a与b是D中两个数据元素;a与b之间的关系用,表示a是b的前驱,b是a的后继,每两个相邻元素之间的关系都可以用这种形式表示。

数据结构还可以用图形表示:每一个数据元素用中间标有元素值的方框和圆表示,数据元素之间的前驱后继关系用一条从前驱指向后继的又向线段表示。

根据数据结构中各数据元素之间的前驱和后继关系的复杂程度,将逻辑结构分为线性结构和非线性结构。

线性结构

线性结构的特征是数据元素之间存在“一对一”的线性关系。

满足这三个条件的数据结构就是线性结构:

 1、有且仅有一个没有前驱的结点,通常将该节点称为根节点。

 2、除了根节点没有前驱、最后一个结点没有后继之外,其他结点都是一个前驱一个后继。

 3、线性结构在删除或插入任何一个结点后还是线性结构。

线性结构的图形表示方式:

非线性结构

非线性结构的特征是一个结点可能有多个前驱和后继。

树状结构

树状结构指数据元素之间存在“一对多”关系的数据结构。在树状结构中,除了根节点没有前驱,其余每个结点有且只有一个前驱,除了叶子结点没有后继,其余每个结点的后继结点数可以是一个也可以是多个。

树状结构图形表示方式:

网状结构

网状结构中,数据元素间的关系可以是任意的,任意两个数据元素之间都可以关联,一个结点可以有一个或多个前驱结点,也可以有一个或多个后继结点。

图形表示方式:

集合结构

集合结构中,数据元素之间除了同属一个集合外,相互之间没有任何关系,结点之间没有任何前驱和后继的关系。

图形表示方式:

数据的存储结构

数据的存储结构也叫数据的物理结构,是指数据的逻辑结构在计算机存储空间中的存放形式,包含结点的数据和结点间关系的存储表示。数据的存储结构依赖于具体的计算机程序,只在高级语言的层面讨论数据的存储结构。

顺序存储结构

把逻辑上相邻的数据元素,存储在物理位置也相邻的存储单元里,通过存储单元的邻近关系来体现数据元素之间的逻辑关系,这样的结构称为顺序存储结构,主要应用于线性的数据结构。

顺序存储结构只存储结点的数据,不存储结点之间相互关系信息。一般称为紧凑存储结构。

链式存储结构

各个数据元素存储位置随意,不要求逻辑上相邻的数据元素在物理位置上相邻,结点间的逻辑关系用附加的指针域来表示,这种存储方式称为链式存储结构。

适用于线性结构和非线性结构。

适合表示因经常进行插入、删除等操作而频繁发生动态变化的数据结构。

索引存储结构

索引存储结构是顺序存储结构的一种推广,用于大小不等的结点的顺序存储。所有数据元素按照顺序存储方式存储,此外增设一个索引表,表中的索引项一般形式是:(关键字,地址),关键字唯一标识一个结点的数据项,地址是该结点的存储位置。这样的存储结构称为索引存储结构。

散列存储结构

存储方式借助一个hash函数,

散列存储结构的基本思想是根据结点的关键字通过散列函数直接计算出该结点的存储地址。各数据元素均匀分布在存储区里,用散列函数指示各数据元素的存储位置。

数据的操作

数据结构与施加于数据结构上的操作密切相关。每种逻辑结构都有一个操作的集合。数据的操作是定义在数据的逻辑结构上的,操作的具体实现则要在存储结构上进行。

常用的操作有:

创建:建立一个数据结构;

清除:清除一个数据结构;

插入:在数据结构中增加新的结点;

删除:把指定的结点从数据结构中删除;

访问:对数据结构中结点进行访问;

更新:改变指定结点的值或改变指定的某些结点之间的关系;

查找:在数据结构中查找满足一定条件的结点;

排序:对数据结构中各个结点按指定数据项的值,以升序或降序重新排列。

逻辑结构、存储结构和操作的关系

数据的逻辑结构和存储结构是密不可分的,操作算法的设计取决于逻辑结构,算法的实现依赖于采用的存储结构。不同的存储结构,数据处理效率不同;进行数据处理时,针对不同问题,选择合理的逻辑结构和存储结构非常重要。