数据结构(1)绪论

野性酷女 2022-02-03 06:41 448阅读 0赞

# 基本概念&术语： #

## 数据结构是相互之间存在一种或多种特定关系的数据元素集合。 ##

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等问题的学科。

![img][]

<table> 
 <thead> 
  <tr> 
   <th>数据</th> 
   <th>是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的<strong>符号集合</strong>。</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>数据元素</td> 
   <td>是<strong>组成数据</strong>的、有一定意义的<strong>基本单位</strong>，在计算机中通常作为整体处理。也被<strong>称为记录</strong>。</td> 
  </tr> 
  <tr> 
   <td>数据项</td> 
   <td>一个数据元素可以由若干个数据组成。是<strong>数据不可分割的最小单位</strong>。</td> 
  </tr> 
  <tr> 
   <td>数据对象</td> 
   <td>是<strong>性质相同的数据元素的集合</strong>，是<strong>数据的子集</strong>。</td> 
  </tr> 
 </tbody> 
</table>

#  #

# 逻辑结构&物理结构 #

## 一、逻辑结构 ##

数据对象中数据元素之间的相互关系，逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个适合的数据结构表示数据元素之间的逻辑关系。

数据的逻辑结构主要有以下几类：

1.  **集合**：集合中的元素相互独立，除了同属于一个集合之外，别无其他关系。
2.  **线性结构**：线性结构中的节点具有一对一的关系，其特点是开始节点和终端节点都是唯一的，除开始节点和终端节点之外，其余节点有且仅有一个前驱，有且仅有一个后继。
3.  **树形结构**：树形结构中的节点具有一对多的关系，其特点是每个节点最多只有一个前驱，但可以有多个后继，可以有多个终端节点。
4.  **图形结构**：图形结构中的节点具有多对多的关系，其特点是每个节点的前驱和后继的数量都可以是任意的。

![å¾ç¤º][1]

# 二、物理结构（存储结构） #

数据的逻辑结构在计算机中的存储形式。

1.  顺序存储方法：把逻辑上相邻的节点存储在物理上相邻的存储单元里，节点之间的逻辑关系由存储单元的邻接关系来体现。
    
    优点：节省存储空间，可以实现节点的随机存取（每个节点对应一个序号，由该序号可直接确定节点的存储地址）
    
    缺点：不便于修改（在对节点进行插入、删除的操作时，可能要移动一系列的节点）。
2.  链式存储方法：该方法不需要逻辑上相邻的节点在物理位置上也相邻，节点之间的逻辑关系由附加的指针字段表示。
    
    优点：便于修改（在进行插入、删除操作时，只需要修改对应节点的指针域，不必移动节点）。
    
    缺点：存储空间利用率较低（有一部分空间用来存储节点之间的逻辑关系了），不能进行随机存取（因为逻辑上相邻的节点在物理位置上不一定相邻）。
3.  索引存储方法：该方法通常在存储节点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中关键字唯一标识一个节点，地址则是指向该节点的指针。
    
    优点：支持随机访问（因为索引表是顺序存储的，类似于 C语言中的指针数组），具有较高的数据修改运算效率。
    
    缺点：索引存储的方法增加了索引表，降低了存储空间的利用率。
4.  哈希（或散列）存储方法：该方法根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该节点的存储地址。
    
    优点：哈希存储方法的优点就是查找数据快，只要给出要查找节点的关键字，就可以立即计算出对应节点的存储地址。
    
    缺点：哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。所以哈希存储方法一般只适合要求能够快速查找和插入的场合。

上面 4种基本的存储方法，既可以单独使用，也可以组合起来使用。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构，主要根据运算方便和算法的时空要求来决定。

# 抽象数据类型 #

**数据类型**：一组性质相同的值的集合及定义在此集合上的一些操作的总称。

数据类型分两类：  
1.原子类型：不可以再分解的基本类型，包括整型、字符型。

2.结构类型：由若干个类型组合而成，是可以再分解的。例如整型数组是由若干整型数据组成的。

**抽象**：抽取事物具有的普遍的本质

**抽象数据类型 （Abstract Data Type，ADT）**：一个数学模型及定义在该模型上的一组操作。仅取决于他的一组逻辑特性，与其在计算机内部如何表示和实现无关。 意义在于数据类型的数学抽象特性。

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

![img][img 1]

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

![img][img 2]

[img]: /images/20220203/f85d1c51cefe4c9f8935d2b8cc21753a.png
[1]: https://user-gold-cdn.xitu.io/2018/9/5/165aa394f9ec67b0?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[img 1]: /images/20220203/ff15cbeea0864a678f61a4cdc09968e4.png
[img 2]: /images/20220203/d5498465aeb14f219b8dfb44243dcdfc.png