逻辑结构与四个主要的存储结构是什么_逻辑结构和存储结构的区别

/*（理解数据结构–个人学习笔记理解）*/

理解逻辑结构和存储结构

逻辑结构：

数据的逻辑结构是从数据元素的逻辑关系上描述数据的，是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的。

数据的逻辑结构与数据的存储无关，是独立于计算机的，因此数据的逻辑结构可以看作从具体问题抽象出来的数据模型。

数据的逻辑结构可以采用多种表达方式，常见的有图表和二元组等等。（在这儿就不再举例）

逻辑结构类型：

• 集合：

集合（set）是指数据元素之间除了“同属于一个集合”的关系以外别无其它关系。

• 线性结构：

线性结构（linear structure）是指该结构中的数据元素之间存在一对一的关系。其特点是开始的元素和终端元素都是唯一的，除了开始元素和终端元素以外，其余元素有且仅有一个前驱元素和一个后继元素。

• 树形结构：

树形结构是指该结构中的元素之间存在一对多的关系。其特点是除了开始元素以外，每个元素有且仅有一个前驱元素，除了终端元素以外，每个元素有一个或多个后记元素。其中二叉树就是一种典型的树形结构。

存储结构：

数据的逻辑结构在计算机存储器中的存储表示称为数据的存储结构（也称为印像），也就是逻辑结构在计算机中的存储实现。

当把数据对象存储到计算机中时，通常要求既要存储逻辑结构中的每一个数据元素，又要存储数据元素之间的逻辑关系。

• 顺序存储结构

顺序存储结构（sequential storage structure）是采用一组连续的存储单元存放所有的数据元素，也就是说，所有数据元素在存储器中占有一整块存储空间，而且逻辑上相邻的元素在存储器中的存储位置也相邻。

因此，数据元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。

主要优点：

• 顺序结构存储效率高，因为分配给数据的存储单元全部用于存放数据元素，元素之间的逻辑关系没有占用额外的存储空间；
• 在采用这种存储方法是可实现对元素的随机存取，即每个元素对应一个逻辑序号，由该序号可直接计算出对应元素的存储地址，从而获取。

主要缺点：

• 不便于修改数据，对元素的插入或删除操作可能需要移动一系列的元素。

举例：一个普通的学生表可以采用C/C++语言中的结构体数组来存储，设计对应的结构体数组Stud并初始化的过程如下：

struct
{ int no;              //存储学号
  char name[8];        //存储姓名
  char sex[2];         //存储性别
  char class[4];       //存储班级
}Stud[7]={
  
  {1,"张三","男",""},...,{5,"李四","女",""}};

其中，数组名称Stud 作为数组的起始地址，用于唯一标识该存储结构，如图所示。在Stud数组中各元素在内存中顺序存放，即 Stud[i存放在Stud[i十1]之前，而Stud[i+1]存放在Stud[i]之后，所以Stud是学生表的一种顺序存储结构。

• 链式存储结构

在链式存储结构（linked storage structure）中，每个逻辑元素用一个内存结点存储，每个结点是单独分配的，所有的结点地址不一定是连续的，所有无须占用一整块存储空间。

为了表示元素之间的逻辑关系，给每个结点附加指针域，用于存放相邻结点的存储地址，也就是通过指针域将所有结点链接起来，这就是链式存储结构名称的由来。

主要优点：

• 链式存储便于数据修改，在对元素进行插入或者删除操作时仅需要修改相应结点的指针域，不必移动结点。

主要缺点：

• 与顺序结构相比，链式存储结构空间利用率较低，因为非陪给元素的存储单元有一部分被用来存储结点之间的逻辑关系。

注意：另外，由于逻辑上相邻的元素在存储空间中不一定相邻，所以不能对元素进行随机存取。

举例：一个普通的学生表可以采用C/C++语言中的结构体数组来存储，设计存放每个元素的结点类型StudType如下：

typedef struct Studnode
{    int no;            //存储学号
     char name[8];      //存储姓名
     char sex[2];       //存储性别
     char class[4];     //存储班级
     struct Studnode *next; //存储指向下一个学生结点的指针
}StudType;            //结点类型

学生表中的每个学生记录采用一个StudType类型的结点单独存储，一个学生结点的next域指向逻辑结构中它的后继学生记录对应的结点，从而构成一个链表，其存储结构如图所示，首结点地址为head，用它来标识整个学生链表，尾结点的指针域为空。

由head所指结点的next域得到下一个结点的地址，然后再由它得到下一个结点的地址，.…,这样就可以找到任何一个结点的地址，所以 head标识的链表是学生表的一种链式存储结构。

• 索引存储结构

索引存储数据结构（indexed storage structure）是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表，其中每个数据元素由一个关键字和对应的存储地址。

索引表中的每一项称为索引项，索引项的一半形式就为“关键字，地址”，其中“关键字”唯一标识一个元素，“地址”对应关键字的元素在主数据中的存储地址。在按关键字查找时，首先在索引表中利用关键字的有序性快速查找到该关键字的地址，然后通过地址在主数据表中找到对应的元素。

主要优点：

• 查找效率高。

主要缺点：

• 需要建立索引表，从而增加了空间开销。

（后续会为大家演示索引存储结构）

• 哈希（或散列）存储结构

哈希(或散列)存储结构(hashed storage structure)的基本思想是根据元素的关键字通过哈希(或散列)函数直接计算出一个值，并将这个值作为该元素的存储地址。

• 主要优点：

优点是查找速度快，只要给出待查元素的关键字就可立即计算出该元素的存储地址。

注意：与前3种存储方法不同的是，哈希存储方法只存储元素的数据，不存储元素之间的逻辑关系。哈希存储结构一般只适合要求对数据能够进行快速查找和插入的场合。

（后续会为大家演示哈希存储结构）

上述4种基本的存储方法既可以单独使用，也可以组合使用。同一种逻辑结构采用不同的存储方法可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构视具体要求而定，主要考虑的是运算方便及算法的时空要求。

今天的文章逻辑结构与四个主要的存储结构是什么_逻辑结构和存储结构的区别分享到此就结束了，感谢您的阅读。