数据结构基本概述

雨点打透心脏的1/2处 2022-06-06 08:35 180阅读 0赞

## 课程简介 ##

1.  首先我要谈一谈数据结构到达是干什么，又是研究什么？  
    我直接开门见山把，数据结构根据字面意思就是针对数据的，那么我们研究的是数据的特性，数据之间的逻辑结构，数据之间的物理结构或者称数据的存储结构，以及针对一个具体应用围绕数据设计的算法。  
    下面来具体解析下什么是计算机中的数据（Data）:只要你可以输入到电脑并且可以被编程语言处理的符号就算是计算中的数据。那么在现实中代表什么呢，比如图像，声音，符号都是。  
    那么数据元素是什么呢，是计算机处理的基本单位，比如树中的一个节点。  
    数据元素又又很多数据项(Data Item)组成，数据对象（Data Object）又是什么就是相同数据元素的集合。  
    为什么要引入数据结构呢，以前我们研究少量和简单的数据，随着软件越来越复杂和数据越来越多，比如我需要在一个大量联系册子子找一个人的联系方法，如果我们没有对数据进行使用好的数据结构去管理和维护，那么我们只能在杂乱无章的数据里去找，只能逐一的去对比，随着数据的增加时间消耗是越来越大，因此数据结构的研究是越来越严峻。
    
    下面进入正题：什么是什么数据结构，根据字面上意思肯定是围绕计算机可以处理的数据，数据之间的结构。

![这里写图片描述][SouthEast]

数据结构其实就是数据之间的关系，打个比方你和你爸爸，你和一个不认识的人，你和你爸爸之间就有关系。1对1可以说是线性关系，你和那个不认识的人就没有关系。  
跟上上面描述场景，我们知道这个数据结构其实是建立在逻辑上的关系，也就是看不见摸不着，是在脑袋去想得，在内存上你直接是看不出啥关系的。

因为引入数据结构课程中讨论的几种常用数据结构：  
1. 集合 比如人群之间的陌生人组成的集合，他们之间没有任何联系和关系  
2. 线性结构 一个班里被赋予学号的全部学生，他们如果从学号的角度上看他们之间就是线性的结构  
3. 树形结构 我们的盘里的目录文件夹目录的组成结构  
4. 图形结构/网状结构 人之间的关系网络，错综复杂

数据结构的形式定义是什么呢，二元组Data Structure(D,S) 那么D是什么呢当然是数据Data Structure是数据之间的关系。二元组字面意思就是2个集合。

现在我们来具体讨论数据的逻辑结构和物理（存储）结构。

数据逻辑结构计算 数据之间的关系，这个关系是抽象的看不见，在脑袋里想得，或者你把关系描述在纸上。  
数据存储结构：这个是针对内存上，数据在内存上之间的关系。

那么数据之间的逻辑结构分哪几种呢，比如线性，集合，树，图等逻辑结构。

数据之间的物理结构分如下两种：首先我们先谈内存是什么样的。在内存中我们看成是可以放数据的盒子，而这个盒子是一排的，我们根据内存1个字节就编号比如1M = 104byte 那么编号就是从0到1023，这样我们就可以把这1M内存看成一排1024个可以放和取数据的盒子。  
下面牛B的存储结构或者是物理结构马上出场，就是我们非常常用的顺序存储结构比如我们的数组数据类型用的存储结构就是顺序存储结构，那么为什么叫顺序2字呢，就是数据是按照内存编号的顺序来存储的，不能出现空了盒子不放顺序，这样就有好处，盒子的编号其实就指示了你当初数据存放的先后顺序，如果说你把数据进行排序后按照顺序存储结构进行存放后，那么数据之间的前后关系可以直接用盒子的编号也就是内存的地址进行指示。所以顺序存储结构的特性就是顺序存储内存里面的数据之间的关系就是用内存编号来表示的  
那么链式存储结构又是什么呢，数据是存在不相邻也就是内存是分开的比较随意的是操作系统给分配的，那么数据之间的关系是怎么样的啊，比如我想输出一组数据已经排序好的数据，并且由小到大，那么我输出了第一个数据后，怎么样输出第二个小的数据呢，内存又不是连续的。那么链表是直接把当前数据类里加入一个变量用于保存下个数据节点的内存地址，这样一个指示下一个，这样整体数据就都联系起来。

下面数据类型的引入：我们已经知道一些定义好的数据类型比如int char float … int可以取 0 1,2，3,4 很多。int这个类型又可以进行 1 + 1 1 - 1 等，从这里我们看到我们这个int类型 有对属于这个类型里面的数据进行减等操作，因为我们可以总结出数据类型就是针对这个类型定义一组数据集合以及在这个数据集合上的操作。

现在就引入ADT抽象数据类型，定义和上面的数据类型其实一样的，区别就是抽象数据类型是可以由我们程序员去自定义，方便扩展和根据具体场景去设计。用三元组表示就是(D,S,P)分别是数据，数据之间的关系，针对数据进行的处理，每个字母都是英文的第一个字母。具体你查下。

[SouthEast]: /images/20220606/65676767af4b423586c4c6843e758256.png