数据结构与算法（二）

数据结构与算法（二）

逻辑结构与存储结构

1. 逻辑结构：

        概念：是指数据对象中数据元素之间的相互关系

    （1）集合：这种逻辑结构中的数据元素同属于一个数据集合。

    （2）线性结构：结构中的数据元素之间是一对一的关系。第一个无前驱，最后一个无后继。

    （3）树形结构：结构中的数据元素是一对多的层次关系。

    （4）图结构：结构中的数据元素是多对多的关系。

 2.存储结构

        概念：也称物理结构，指的是数据的逻辑结构在计算机中存储的形式，能反映数据元素之间的逻辑关系。

      （1）顺序存储结构

                把数据元素存放在一组地址连续的存储单位中，其数据元素的逻辑关系和物理结构是一样的。

                优点：节省空间，可以实现随机存取；数据元素可以按元素号随机访问。

                缺点：插入、删除时需要移动元素，效率低。创建时需要先分配存储空间。

      （2）链式存储结构

                把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系。借助指针来表示数据元素之间的逻辑关系。每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继结点的位置。

                优点：插入、删除灵活；

                缺点：不能随机存取，查找速度慢，只能按指针从前到后寻找。存储密度低

                存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。