数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。
无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握数组和广义表在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。
目录
数组的定义
数组的顺序表示和实现
矩阵的压缩存储
广义表的定义
广义表的存储结构
数组的定义
数组是一组偶对(下标值,数据元素值)的集合。在数组中对于一组有意义的下标,都存在一个与其对应的值。一维数组对应着一个下标值,二维数组对应着两个下标值,如此类推。
数组是由n(n>1)个具有相同数据类型的数据元素 组成的有序序列,且该序列必须存储在一块地址连续的存储单元中。数组具有以下特点:
1)数组中的数据元素具有相同数据类型
2)数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素。
3)数组中的数据元素个数是固定的。
数组的抽象数据类型定义:
由上述定义知,n维数组中有个数据元素,每个数据元素都受到n维关系的约束。
数组的顺序表示和实现
数组一般不做插入和删除操作,也就是说数组一旦建立,结构中的元素的个数和元素间的关系就不再发生变化。因此一般都是采用顺序存储的方法来表示数组。
计算机的内存结构是一堆(线性)地址结构,对于多维数组,将其存放(映射)到内存一维结构时,有个次序约定问题。即必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放到内存中。
二维数组是最简单的多维数组,以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。
二维数组的两种存储方式(以行序为主、以列序为主):
举个例子:
矩阵的压缩存储
在科学与工程计算问题中,矩阵是一种常用的数学对象,在高级语言编程时,通常将一个矩阵描述为一个二维矩阵。这样可以对其元素进行随机存取,各种矩阵运算也非常简单。
对于高阶矩阵,若其中非零元素呈某种规律分布或者矩阵中有大量的零元素,若仍然用常规方法存储,可能存储重复的非零元素或零元素,将造成存储空间的大量浪费。所以要对这类矩阵进行压缩存储。
注意:多个相同的非零元素只分配一个存储空间;零元素不分配空间。
接下来我们要掌握 特殊矩阵 与 稀疏矩阵 的压缩存储方式。
广义表的定义
广义表是线性表的推广和扩充,在人工智能领域中应用十分广泛。我们把线性表定义为n(n0)个元素的有穷序列,该序列中的所有元素具有相同的数据类型且只能是原子项(所谓原子项可以是一个数或一个结构,是指结构上不可再分的。)若放松对元素的这种限制,容许它们具有其自身结构,就产生了广义表的概念。
广义表(Lists,又称为列表):是由n(n0)个元素组成的有穷序列:LS=()
广义表的存储结构
由于广义表中的数据元素具有不同的结构,通常用链式存储结构表示,每个数据元素用一个结点表示。因此,广义表中就有两类结点:
一类是表结点:用来表示广义表项,由标志域,表头指针域,表尾指针域组成
一类是原子结点:用来表示原子项,由标志域,原子的值域组成。
只要广义表非空,都是由表头和表尾组成。即一个确定的表头和表尾就唯一确定一个广义表。
什么是广义表?请简述广义表与线性表的区别?
广义表(Generalized List)是一种扩展了线性表的数据结构,它允许元素既可以是单值,也可以是子表。广义表通过递归方式定义,可以包含任意嵌套层级的子表,从而形成一个更加复杂和有层次结构的数据集合。
与广义表相对应的是线性表(Linear List),线性表仅包含单值元素,每个元素都有一个后继元素,形成一个线性结构。线性表是最简单和最常见的数据结构之一,例如数组就是线性表的一种实现。
广义表与线性表的区别主要有以下几点:
1. 元素类型:线性表的元素只能是单值,而广义表的元素可以既是单值,也可以是子表。这使得广义表能够表示更加复杂和有层次结构的数据关系。
2. 结构特点:线性表是一种线性结构,每个元素都有唯一的后继元素,形成了一个简单的序列。而广义表则具有更加复杂的层次结构,可以包含任意嵌套层级的子表,形成了一个树状结构。
3. 操作灵活性:由于广义表具有更复杂的结构,因此在操作和处理数据时,广义表比线性表更加灵活。广义表可以使用递归的方式进行遍历和操作,可以处理各种复杂的数据关系,而线性表则相对简单。
综上所述,广义表是一种扩展了线性表的数据结构,允许元素既可以是单值,也可以是子表。广义表具有更加复杂的层次结构和操作灵活性,可以更好地表示和处理各种复杂的数据关系。文章来源:https://www.toymoban.com/news/detail-716744.html
一个广义表是(a,(a,b),d,e,(a,(i,j),k)),请画出该广义表的链式存储结构:文章来源地址https://www.toymoban.com/news/detail-716744.html
+---+ +---+ +---+ +---+
| a |---+ | |---+ | d |---+ | e |
+---+ | +---+ | +---+ | +---+
| | |
| +---+ | +---+ |
+---->| a | +---->| b | |
| +---+ | +---+ |
| | |
| +---+ | |
+---->| i | +-------------+
+---+
|
|
|
| +---+
+---->| j |
+---+
|
|
|
|
| +---+
+---->| k |
+---+
到了这里,关于数据结构--》数组和广义表:从基础到应用的全面剖析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!