m数据结构 day1 数据结构定义，数据的逻辑结构和物理结构

缺乏、安全感 2023-07-12 14:42 20阅读 0赞

我不想费脑去记录那些半懂不懂的晦涩概念，比如说**数据结构是数据元素的关系的集合**，太抽象，暂时理解不了，不强行理解，后面慢慢会逐渐加深理解。

实时的排队模块，不用数据库，直接在内存中进行就好了，数据库很慢，也不要用数组，因为还要考虑溢出和新增和删除后的数据移动，数组很不方便，而要用队列。

### 文章目录 ###

*  数据结构
 *   *  数据结构和算法的关系：1+1>2
     *  数据的三种存储结构：线性表，树，图
     *   *  顺序表和数组的区别
 *  数据的逻辑结构和物理结构
 *   *  数据的四种逻辑结构：数据之间的逻辑关系（面向问题）
     *   *  集合结构
         *  线性结构
         *  树形结构
         *  图形结构
     *  数据的两种物理结构：存储结构（面向内存）
     *   *  顺序存储结构（集中存储，底层实现依赖数组）
         *  链式存储结构（分散存储，指针的大型真香现场）
 *  抽象数据类型 ADT
 *   *  先说说数据类型
     *  对已有数据类型进行抽象，就是抽象数据类型（抽象带来美）
     *   *  ==“抽象”主要是说==数据类型的数学特性，即==操作==
         *  抽象和数学，都很美
         *  ADT很有利于程序的需求增加和迭代开发（问题分解，抽象，信息隐藏）

# 数据结构 #

数据结构，直白地理解，就是**研究数据的存储方式**。**选择一种好的方式来存储数据**，是数据结构的核心内容。  
它教会我们“如何存储具有复杂关系的数据更**有助于后期对数据的再利用**”

数据结构教会我们的绝不仅仅是如何存储 1、2、\{a,b,c\} 这样简单的数据，而是解决具有复杂逻辑关系的大量数据的存储问题。

数据结构研究的是程序设计中非数值计算的那部分，即数据本身。因为现实中，其实需要我们努力解决的并不是计算，虽然计算一个结果是最终目的，主要花时间精力的应该是利用更加科学高效的手段，比如栈，树，图等，把数据对象之间的关系和操作设计清楚。

## 数据结构和算法的关系：1+1>2 ##

![在这里插入图片描述][20200416174800333.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

## 数据的三种存储结构：线性表，树，图 ##

原来虽然数据结构那么多，但是按照存储结构来分类却只有三类。实际上这是因为**数据之间的逻辑关系只有这三种:一对一，一对多，多对多。**

*  具备“一对一”关系的数据可以使用线性表来存储；
 *  树存储结构适合存储具有“一对多”关系的数据；
 *  图存储结构适合存储具有“多对多”关系的数据。

顺序表，链表，栈和队列都是线性表。线性表并不是一种**具体**的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。

### 顺序表和数组的区别 ###

顺序表，简单地理解，就是常用的数组，只是换了个名字而已。

由于**顺序表结构的底层实现借助的就是数组**，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，**线性表是一种存储数据的结构**，而**数组只是各种编程语言中的基本数据类型**，并不属于数据结构的范畴。  
![在这里插入图片描述][20200416171341198.png]

# 数据的逻辑结构和物理结构 #

我们可以从逻辑和物理的两种视角出发，看数据结构。

逻辑关系是我们看了问题后理解出来的关系。而存储结构是我们在内存中真真切切地实现这种逻辑关系。

我们可以通过**分析数据之间的逻辑关系来决定使用哪种存储结构**，但具体使用顺序存储还是链式存储，还要通过数据的物理结构来决定。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]

## 数据的四种逻辑结构：数据之间的逻辑关系（面向问题） ##

逻辑结构是针对具体问题的，是为了解决问题而根据对问题的理解选择一个合适的数据结构表示数据元素之间的逻辑关系。当然如果说毫无关系也是一种关系的话，那就可以引出集合关系（见后文详细说逻辑关系的小节）。

我们存储数据不仅仅只是存数据，还要存他们的关系，如果只存数据那用数组就好了，但只有存了关系才能让我们后面要用数据的时候可以成功达到目的。比如我使用数据的时候，希望知道当前数据的前一个数据是什么，或者希望知道当前数据的父节点的数据是什么。所以数据结构在**研究数据的存储时，既要存数据，又要存数据的关系，二者缺一不可。**

### 集合结构 ###

关系：同属于一个集合。没了，，，，所有数据元素平等。其实相当于没有关系。。。  
![在这里插入图片描述][20200309122645322.png]

### 线性结构 ###

关系：一对一。  
![在这里插入图片描述][20200309122721233.png]

### 树形结构 ###

关系：一对多。  
![在这里插入图片描述][20200309122737706.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]

### 图形结构 ###

数据元素之间的关系：多对多。  
![在这里插入图片描述][20200309122821793.png]  
![在这里插入图片描述][20200416171140811.png]

## 数据的两种物理结构：存储结构（面向内存） ##

就是数据元素之间的逻辑结构在内存中实实在在的存储形式。指的是数据在物理存储空间上选择**集中存放还是分散存放**。

存储结构的目标就是把逻辑关系存储到内存中，重点也是必须要正确反映逻辑关系。

注意这里真的说的是内存哈，不是硬盘软盘光盘啥的，因为那些外部存储器的数据组织一般都是用文件结构来描述，而不是数据结构。

物理结构就两种。

### 顺序存储结构（集中存储，底层实现依赖数组） ###

![在这里插入图片描述][2020030912381781.png]

太简单了，好像数组，因为顺序存储的物理结构的底层实现就是依赖于数组。但是数组是一种数据类型，顺序存储结构是存储结构，性质不一样。

但是我们也早就知道了，数组这种结构，随机访问很方便，有利于后期对数据进行遍历；  
但是想在任意位置插入或者删除元素，就很麻烦，很不灵活，虽然很适合存储字符串，但是对于大多数其他问题都是不适合的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]

### 链式存储结构（分散存储，指针的大型真香现场） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

# 抽象数据类型 ADT #

![在这里插入图片描述][20200309125622978.png]

以后说ADT按照这个框架说，比较清晰。  
![在这里插入图片描述][20200309133946190.png]  
感觉很艺术。提炼本质，只要精华

## 先说说数据类型 ##

1.  数据类型是啥，或者用来干啥？
    
    用来说明变量的取值范围和能进行的操作。  
    ![在这里插入图片描述][20200309125526873.png]
2.  为啥需要数据类型？
    
    和我们人类买房一样，大家都想住大房子，但是没钱呀。所有市面上有各种商品房，别墅，单间，公寓，胶囊公寓···大家各取所需。
    
    同样的，内存也不是无限多的。所以也要对数据进行分类，按照取值不同，可大体分为两类数据类型。  
    ![在这里插入图片描述][20200309125246586.png]  
    第一次听到这么新鲜的术语，哈哈，原子类型

## 对已有数据类型进行抽象，就是抽象数据类型（抽象带来美） ##

官话：ADT是一个数学模型，以及定义在这个模型上的一组操作。

既然都抽象了，高级了，本质了，不细节了，自然ADT**只关心本质的逻辑特性，而不关心内存的具体表示和实现**等等细节。

### “抽象”主要是说数据类型的数学特性，即操作 ###

比如其实“整型”就是一种ADT，因为不管什么计算机，比如玩具里的嵌入式单片机，个人电脑，手机，工作站等，都有整型，但是底层的实现肯定略有不同，但是给他们定义的数学特性是一样的，所以在我们编程者看来，他们就是一样的。

### 抽象和数学，都很美 ###

再举一个ADT的例子，这次的例子是自己设计的数据类型。这个例子很美，因为他让我发现ADT和数学很像。数学是抽象的，由于一直沉浸在数学的内部世界，其实我一直不是特别能领会数学的抽象之美，但是这次感受到了。  
比如和平精英游戏中人物，枪，飞机的位置，需要用坐标表示，如果是二维，就是一对点，x和y。如果是三维则是三个点，x,y,z.那么我们就可以定义一个抽象数据类型叫做point，或者position, 他有三个整形变量或者浮点型变量，于是我们操作对象的位置时，就只需要操作一个point数据类型而不是三个浮点数类型了。

### ADT很有利于程序的需求增加和迭代开发（问题分解，抽象，信息隐藏） ###

比如游戏中的人物，还是和平精英吧，人物可以往前走，往后走，左右，跳起来，趴下，还可以收起枪，蹲下等等很多动作，这些操作都是根据实际需要来定义的。可能最开始只给游戏人物定义了跑和趴着两种操作，慢慢的逐渐增加跳，收枪等等。

所以ADT也体现出了**程序设计中的问题分解，抽象，信息隐藏**的特性。每个功能模块的实现细节是一个独立单元，从而把具体的实现过程隐藏起来。

[20200416174800333.png]: https://img-blog.csdnimg.cn/20200416174800333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200416175027549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200416171341198.png]: https://img-blog.csdnimg.cn/20200416171341198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309134106282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200309122645322.png]: https://img-blog.csdnimg.cn/20200309122645322.png
[20200309122721233.png]: https://img-blog.csdnimg.cn/20200309122721233.png
[20200309122737706.png]: https://img-blog.csdnimg.cn/20200309122737706.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200416171113506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200309122821793.png]: https://img-blog.csdnimg.cn/20200309122821793.png
[20200416171140811.png]: https://img-blog.csdnimg.cn/20200416171140811.png
[2020030912381781.png]: https://img-blog.csdnimg.cn/2020030912381781.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200416175117565.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200309124156705.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200309125622978.png]: https://img-blog.csdnimg.cn/20200309125622978.png
[20200309133946190.png]: https://img-blog.csdnimg.cn/20200309133946190.png
[20200309125526873.png]: https://img-blog.csdnimg.cn/20200309125526873.png
[20200309125246586.png]: https://img-blog.csdnimg.cn/20200309125246586.png