数据结构的基础---线性群集存储模式(数组、链表和hash)

时间:2022-04-01 16:46:11

           既然我们开始进入了数据结构的学习,很多东西无可避免,数据的存储方式更是无法回避。作为数据在内存中的组织形式,存储方式直接的决定了我们处理数据的方式。所以我们有必要来讨论两种最基础的数据存储方式。

一:数据存储的概念(群集)

群集是一种结构化的数据类型。它存储数据,并且提供数据的添加、删除、更新操作,以及对群集的不同属性值的设置与返回操作。

群集是一种结构化的数据类型。它存储数据,并且提供数据的添加、删除、更新操作,以及对群集的不同属性值的设置与返回操作。

群集可以分为两类:线性的和非线性的。

线性群集是一张元素列表,表中的元素顺次相连。线性群集中的元素通常由位置来决定次序(例如,第一个元素、第二个元素、第三个元素,依次类推)。在现实世界中,购物清单就是很好的线性群集实例。而在计算机世界中(当然这也是真实世界)则把数组,链表设计成线性群集。

非线性群集所包含的元素在群集内没有位置次序之分。组织结构图就像用架子垒好的台球一样是一个非线性群集的实例。而在计算机世界中树、堆、图和集都是非线性群集。

二:线性群集的数据存储

线性的群集可能是直接存取群集,也可能是顺序存取
群集。

直接存取集:也就是说对于群集中的每一个数据元素我们都可以直接存取,通常表现为数组,我们可以直接根据数组下标定位到具体的数据。

我们可以用数组来存储一个线性的群集。向数组添加新元素是很容易的,只要简单地把新元素放置在数组尾部第一个空位上就可以了。但是,在数组中插入一个元素就不是这么容易的(或高效)了。因为要给插入的元素空出位置,所以需要按顺序向后移动数组元素。从数组的尾部删除一个元素也是很有效率的操作,只要简单地移除掉最后一个元素的值就可以了。但是,删除数组中任何其他位置上的元素就没有这么有效率了,就像处理插入操作一样,为了保持数组中元素的连续性,可能需要先前调整许多数组元素的位置。

字符串是直接存取群集的另外一种类型。字符串是字符的群集。和存取数组元素的方式一样,也可以基于字符的索引对其进行存取。

结构(在其他编程语言中也被称为记录)是最后一种直接存取的群集类型。结构是一种复合数据类型。它所包含的数据可能拥有许多不同的数据类型。

顺序存取集:我们必须一个个的访问元素,每个元素之间都有关联,通过当前元素可以获取与之有关联的元素,通过遍历的方式才能访问我们要的具体的某个元素。最基本得一个表现方式就是链表。

顺序存取群集是把群集元素按顺序存储的表。这里也把此类群集称为线性表。线性表在创建时没有大小限制,这就意味着它们可以动态地扩展和收缩。不能对线性表中数据项进行直接存取访问,而要通过数据项的位置对其进行存取。线性表的第一个元素在表头的位置,而最后一个元素在表尾的位置。

由于不能直接存取线性表的元素,为了访问某个元素就需要遍历线性表直到到达要找元素的位置为止。线性表的实现通常允许两种遍历表的方法:一种是单向从前往后遍历,而另一种则是双向遍历,即从前向后和从后先前遍历。

线性表的某些类型限制访问数据元素。这类线性表有堆栈和队列。堆栈是一种只允许在表头(或顶端)存取数据的表。在表的顶端放置数据项,而且也只能从表的顶端移出数据项。正是基于这种原因,堆栈也被称为后进先出结构。这里把向堆栈添加数据项的操作称为入栈,而把从堆栈移出数据项的操作称为出栈。

最后要讨论的一类线性群集被称为通用的索引群集。这类群集的第一种就是散列表。它存储了一组与关键字相关联的数据值。在散列表中有一个被称为散列函数的特殊函数。此函数会取走一个数据值,并且把此数据值(称为关键字)转换成用来取回数据的整数索引。通常我们使用的索引群集是散列表和字典。

索引群集对于元素的存取使用关键字定位的方式,索引它在元素的访问效率上接近直接存取集,而添加和删除元素不需要移动原有元素,所以在插入和删除的操作上效率也很高,是一种兼具直接存取集合顺序存取集优点的线性群集。

三:3中线性存取集的处理数据方式以及效率简要说明

数据结构的基础---线性群集存储模式(数组、链表和hash)

下面的章节我们将一一的介绍和实现这几种线性群集。