储存结构和逻辑结构

储存结构

存储结构分四类顺序存储链接存储索引存储散列存储

顺序结构和链接结构适用在内存结构中。

索引结构和散列结构适用在外存与内存交互结构。

顺序存储:

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

特点:

1、随机存取表中元素。

2、插入和删除操作需要移动元素。

链接存储:

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

特点:

1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。

索引存储:

除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。

特点:

索引存储结构是用结点的索引号来确定结点存储地址,其优点是检索速度快,缺点是增加了附加的索引表,会占用较多的存储空间。

散列存储:

散列存储,又称hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。

特点:

散列是数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的,而不像在数组中的遍历过程,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置,这样的访问速度就省去了遍历数组的实现,因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)。

逻辑结构

逻辑结构大概可以分为两种:线性结构非线性结构(集合、树、网)。

线性结构:有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继。例如:线性表,典型的线性表有:顺序表、链表、栈(顺序栈、链栈)和队列(顺序队列、链队列)。它们共同的特点就是数据之间的线性关系,除了头结点和尾结点之外,每个结点都有唯一的前驱和唯一的后继,也就是所谓的一对一的关系。

非线性结构:对应于线性结构,非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。常见的非线性结构包括:树(二叉树)、图(网)等。

举个例子来区分两者:

与储存结构无关,因为栈只是逻辑结构,而无关储存结构;但是链栈顺序栈就不仅仅是逻辑结构,他们还与储存结构有关。

说点什么

avatar
  Subscribe  
提醒