[数据结构]数据结构的基本概念

电玩女神 2022-07-16 04:42 262阅读 0赞

## 什么是数据结构？ ##

感觉学过数据结构后有必要再区分一下基本的概念，这样才能更加容易深层次理解后续的内容。那么要搞清楚什么是数据结构那么首先来看一下数据结构的一些基本概念:

下面逐个分析其意义:

<table> 
 <thead> 
  <tr> 
   <th align="left">数据</th> 
   <th align="left">是描述客观事物的符号，是计算机中可以操作的对象， 是能被计算机识别，并输入给计算机处理的集合。有两个特点:1.能输入到计算机 2.能被计算机程序处理</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">数据对象(人类)</td> 
   <td align="left">是<strong>性质相同</strong>的数据元素的集合(指数据元素有相同数量和类型的数据项)</td> 
  </tr> 
  <tr> 
   <td align="left">数据元素(人)</td> 
   <td align="left">是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称作记录</td> 
  </tr> 
  <tr> 
   <td align="left">数据项(眼，手)</td> 
   <td align="left">一个元素可以由若干个数据项组成，是数据不可分割的最小单位。(数据元素才是数据结构中建立数据模型的着眼点)</td> 
  </tr> 
 </tbody> 
</table>

数据结构:(结构即关系)比如分子结构，就是说组成分子的原子之间的排列方式。由此给出数据结构的定义:  
**数据结构是相互之间存在的一种或多种特定关系的数据元素的集合**

--------------------

## 分清逻辑结构与物理结构 ##

### 逻辑结构 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">逻辑结构</th> 
   <th align="left">是指数据对象中数据元素之间的相互关系。分为四种:集合结构，线性结构，树形结构，图形结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">集合结构</td> 
   <td align="left">集合结构中的元素除了同属一个结合外，他们之间没有其他关系</td> 
  </tr> 
  <tr> 
   <td align="left">线性结构</td> 
   <td align="left">数据元素之间是一对一的关系</td> 
  </tr> 
  <tr> 
   <td align="left">树形结构</td> 
   <td align="left">数据元素之间存在一种一对多的层次关系</td> 
  </tr> 
  <tr> 
   <td align="left">图形结构</td> 
   <td align="left">图形结构中的元素是多对多的关系</td> 
  </tr> 
 </tbody> 
</table>

### 物理结构 ###

<table> 
 <thead> 
  <tr> 
   <th align="left">物理结构</th> 
   <th align="left">是指数据的逻辑结构在计算机中的存储形式。分为顺序存储结构和式存储结构</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">顺序存储结构:</td> 
   <td align="left">指数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的</td> 
  </tr> 
  <tr> 
   <td align="left">链式存储结构</td> 
   <td align="left">是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的</td> 
  </tr> 
 </tbody> 
</table>

--------------------

## 抽象数据类型 ##

### 数据类型 ###

数据类型:是指一组性质相同的值得集合及定义在此集合上的一些操作的总称

比如在c语言中，按照值得不同数据类型可以分为两类

*  原子类型: 是不可以再分解的基本类型，包括整型，实型，字符型等
 *  结构类型:由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干个整型数据组成。

### 抽象数据类型 ###

抽象是指抽取出事物具有的普遍性的本质。对已有数据类型进行抽象，就有了如下定义:

**抽象数据类型(Abstract Data Type,ADT):是指一个数学模型及定义在该模型上的一组操作**

注意:*抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关*

一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作，至于到底有哪些操作，则由设计者根据实际需要决定。其标准格式为:

ADT 抽象数据类型名
    Data
        数据元素之间逻辑关系的定义
    Operation
        操作1
            初始条件
            操作结构描述
        操作2
        ...
        操作n
        ...
    endADT

抽象数据类型体现了程序设计中问题分解，抽象和信息隐藏的特性