数据结构基础

概念

• 数据

  数据(data)是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的的原始素材。

  数据可以是连续的值，比如声音、图像，称为模拟数据。也可以是离散的，如符号、文字，称为数字数据。

  在计算机系统中，数据以二进制信息单元 0,1 的形式表示。

  百度百科

• 数据元素

  数据元素(data element)是计算机科学术语。它是数据的基本单位，数据元素也叫做结点或记录。在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成，例如，一本书的书目信息为一个数据元素，而书目信息的每一项（如书名、作者名等）为一个数据项。数据项是数据的不可分割的最小单位。

  百度百科

• 数据项

  数据项是指数据元素可由若干个数据项（data item）组成，数据项是数据的不可分割的最小单位。数据项的名称有编号、别名、简述、数据项的长度、类型、数据项的取值范围。数据项是数据记录中最基本的、不可分的有名数据单位，是具有独立含义的最小标识单位。

  百度百科

• 数据对象

  数据对象是必须由软件理解的复合信息表示。数据对象可能是外部实体、事物、偶发事件或事件、角色、组织单位、地点或结构等。例如，一个人或一部车可以被认为是数据对象，在某种意义上它们可以用一组属性来定义。数据对象描述包括了数据对象及其所有属性。数据对象只封装数据(没有对数据的操作)。

  百度百科

• 数据结构

  名词定义

  数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：

  Data_Structure=(D,R)

  其中 D 是数据元素的集合，R 是该集合中所有元素之间的关系的有限集合。 [2]

  其它定义

  Sartaj Sahni 在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。

  Clifford A.Shaffer 在《数据结构与算法分析》一书中的定义是：“数据结构是 ADT（抽象数据类型 Abstract Data Type） 的物理实现。”

  Robert L.Kruse 在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。

  数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。

分类

物理结构

• 顺序结构

  把数据元素存放在地址连续的存储单元中，其中数据间的逻辑关系和物理关系是一致的;

• 链式储存结构

  链式存储结构是将数据元素放到任意的存储单元里，这组存储元素单元可以是连续的，也可以是不连续的;

逻辑结构

逻辑结构:指的是数据对象元素之间的相互关系

• 集合结构

  集合结构中的元素除了属于同一个集合外，之间没有任何关系

• 线性结构

  线性结构中的数据元素是一对一的关系

  eg: 1 - 2 - 3 - 4 - 5 - 6 - 7 - …

• 树形结构

  树形结构中的数据元素存在一种一对多的的层次关系

• 图形结构

  图形结构中的数据元素是多对多的关系

抽象数据类型

• 数据类型

  是指一组性质相同的值的集合及定义在此集合上的一些操作的总称;

• 数据类型在 C 语言中分为两类

  原子类型:是不可再分解的基本类型，包括整形，字符型等；

  结构类型:由若干个类型组合而成，是可以在分解的，（结构体）

• 抽象是指抽取出事物具有的普遍性的本质

• 线性表

  数组

  一段连续的内存地址

  查询块，增删慢

  链表

  不连续的地址构成 增删块，查询慢

• 栈与队列

  栈 先进后出 FILO

  队列 先进先出 FIFO