数据结构

定义：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集
合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

性质：

程序=数据结构+算法

作用：

描述现实世界的数学模型(逻辑结构)如何在计算机上表示和实现。

简介：

数据结构指的是数据的逻辑结构和存储结构，而算法则是对数据运算的描述。 名词介绍数据：描述客观事物的符号
数据元素：组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录
数据项：一个数据元素可以由若干个数据项组成。
数据对象：是性质相同的数据元素的集合，是数据的子集。
数据结构：是互相之间存在一种或多种特定关系的数据元素的集合
抽象数据类型：是指一个数学模型以及定义在此数据明星上的一组操作：数列、列表。树、图
数据的抽象运算：数据的检索（查找）、插入、删除、更新、排序等。

分类：

逻辑结构：集合结构、线性结构、树形结构、图形结构

介绍：一组数据在自然界中所体现的逻辑结构，是对数据元素之间存在的逻辑关系的描述

集合机构：

多个元素同属于同一空间，彼此无关联

线性结构：

元素之间有一对一关系（Next、Prev），只有唯一的前驱，和唯一的后继

树形结构：

元素之间有一对多关系（Chirldren、Parent），右根节点和叶子节点组成，每个节点都有唯
一的前驱，和多个后继。

图形结构：元素之间有多对多的关系，每一个节点都有多个前驱，和多个后继

物理结构：顺序存储结构、链式存储结构

介绍：数据逻辑结构在计算机中表示和实现，又称为存储结构

顺序存储结构：

借助元素在存储器中的相对位置表示数据元素之间的逻辑关系，必须是连续的空间。逻辑上紧密相连的数据在存储上也紧密相连。存储单元地址连续，他以”物理位置相邻”来表示限行表中数据元素间的逻辑关系

特点：

(1)每个节点都有对应的序号，根据序号得出存储地址，可以随机取值
(2)插入删除操作时，会移很多节点

上列表格(代表物理内存地址)中我们想要存储数据：（1,2,3,4,5,6,7）
当我们把数据”1”存储到102位置，”2”存储到103位置，”3”存储到104位置以此类推”7”存储到
108位置，那么当我们知道数据”1”的存储位置时，我们即可推算出数据”5”的存储位置为106
位置。

| 301 |

查，删，插原理：

当我们拿出去数据”1”，为了保证逻辑上的关系在存储也是紧密相连的，当数据”1”被删除
了以后，后面的元素需要陆续向前移动，即数据”2”存储地址变更为：102，数据”3”存储
地址变更为：103，依次类推。插入同理，移动数据时，是最后一个数据移动，否则会被
覆盖！

链式存储结构：

借助只是元素存储地址的指针标识数据元素间的逻辑关系。还需要存储一个节点(节点=数据的本身信息+直接后继的信息(存储位置))。
特点：
(1)结点除了存储子什么信息域外，还有标识关联信息的指针域，链式存储结构的存储密度小，存储空间利用率低。
(2)在物理内存地址上可以不相邻，不可以随机取值，只能顺序取值
(3)插入删除灵活，比用移动节点，只要修改节点的指针就可以。

| 301 |

上列表格(代表物理内存地址)中我们想要存储数据：（1,2,3,4,5）
我们将数据”1”的存储地址存储到102中，数据”1”和数据”2”的内存地址存储到103位置，数据”2”和数据”3”的存储地址存储到105位置，数据”3”和数据”4”的存储地址存储到106位置，数据”4”和数据”5”的存储地址存储到201位置…….数据”5”储到203位置。这种存储结构行程了链系的存储结构，即使内存空间不连续，也可以找到对应的元素。

| 301 |

查，删，插原理：
当我们拿出去数据”1”，为了保证逻辑上的关系在存储也是紧密相连的，当数据”1”被删除
了以后，后面的元素需要陆续向前移动，即数据”2”存储地址变更为：102，数据”3”存储
地址变更为：103，依次类推。插入同理，移动数据时，是最后一个数据移动，否则会被
覆盖！

对比：顺序结构查找快 o(1)，插入删除慢 o(n)。链式结构插入删除快 o(1)、查找慢 o(n)