数据结构基础知识

大家好，我是讯享网，很高兴认识大家。

数据结构绪论：

早期的计算机主要用于数值计算，现在，计算机主要用于非数值计算，包括处理字符，表格和图像等具有一定结构的数据。这些数据内容存在着某种着联系，只有分清楚数据的内在联系，合理的组织数据，才能对他们进行有效地处理，设计出高效的算法。如何合理的组织数据，高效的处理数据，这就是“数据结构”主要研究的问题。

程序设计 = 数据结构 + 算法

数据结构概念和术语：

数据，数据元素，数据项和数据对象：
数据（Data）：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。（数值和非数值）
数据元素（Data Element）：是数据的基本单位，在计算机中常作为一个整体进行考虑和处理。（也被称为“元素”“记录”等）
数据项（Data Item）：是组成数据元素的，有独立含义的，不可分割的最小单位。
数据对象（Data Object）：是性质相同数据元素的集合，是数据的一个子集。（只要集合内元素的性质均相等，都可称之为一个数据对象）

数据结构：

数据结构（Data Structure）：是相互之间存在的一种或多种特定关系的数据元素的集合。“结构”就是指数据元素之间存在的关系。
数据结构包括逻辑结构和存储结构（物理结构）两个层次。

1.逻辑结构：

数据的逻辑结构：是从逻辑关系上描述数据结构，它与数据的存储无关，是独立于计算机的。（是从具体问题抽象出来的数学模型）。
数据的逻辑结构的两个要素:一是数据元素；二是关系。（关系是指两个元素间的逻辑关系）

逻辑结构的四种结构：

集合结构，线性结构，树结构，图结构（网状结构）
其中集合结构，树结构和图结构都属于非线性结构。
线性结构包括线性表（典型的线性结构），队和队列（具有特殊限制的线性表，数据操作只能在表的一端或两端进行），字符串，数组和广义表。
非线性结构包括树，二叉树，有向图和无向图。

1）集合结构：

数据元素之间除了“属于同一集合”的关系外，别无其它关系。
讯享网

2）线性结构：

数据元素之间存在一对一的关系。（有且仅有一个开始和一个终端结点，前一个结点称为前驱，后一个结点称为后继）
除开始和终端节点外所有的节点都有一个前驱和后继。（开始只有一个后继，终端只有一个前驱）

3）树结构：

数据元素之间存在一对多的关系。

4）图结构或网状结构：

数据之间存在多对多的关系。

存储结构（物理结构）：

数据对象在计算机中的存储表示称为数据的存储结构，也称物理结构

存储结构的两种结构：

顺序存储结构，链式存储结构

1）顺序存储结构：

顺序结构是指借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。（通常借助程序设计语言的数组类型来描述）

2）链式存储结构：

顺序存储结构要求所有元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。
但为了表示结点之间的关系，需要给每个节点附加指针字段，用于存放后继元素的存储地址。
所以链式存储结构通常借助于程序设计语言的指针类型来描述。

数据类型和抽象数据类型

数据类型(Data Type)：

数据类型的分类为：原子类型和结构类型；

原子类型 = 一种值的集合 + 定义在值集合上的一组操作。（比如：int，float，字符串）
- int型：包括值集（1,2,3,4,5。。。），并且可以在这些值上进行±*/
结构类型 = 一种数据结构 + 定义在这种数据结构上的一组操作。

原子类型 + 结构类型 = 数据类型

抽象数据类型（Abstract Data Type , ADT）：

是指一个数学模型以及定义在这个模型上的一组操作。

包括三个部分：

由用户定义，从问题抽象出数据模型（逻辑结构）
定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内具体存储结构与运算的具体实现算法

抽象数据类型的定义格式如下：

ADT 抽象数据类型名{ 
    数据对象 : <数据对象的定义> 数据关系 : <数据关系的定义> 基本操作 : <基本操作的定义> }ADT 抽象数据类型名 其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式为： 基本操作名 (参数表) 初始条件 : <初始条件描述> 操作结果 : <操作结果描述>

讯享网

本文格式及部分内容借鉴于：

▶博客： https://blog.csdn.net/lesileqin/article/details/
▶书籍： 《数据结构》 作者：严蔚敏