数据结构--》数组和广义表:从基础到应用的全面剖析

这篇具有很好参考价值的文章主要介绍了数据结构--》数组和广义表:从基础到应用的全面剖析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。

        无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握数组和广义表在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据结构与算法的奇妙之旅吧。

目录

数组的定义

数组的顺序表示和实现

矩阵的压缩存储

广义表的定义

广义表的存储结构


数组的定义

数组是一组偶对(下标值,数据元素值)的集合。在数组中对于一组有意义的下标,都存在一个与其对应的值。一维数组对应着一个下标值,二维数组对应着两个下标值,如此类推。

数组是由n(n>1)个具有相同数据类型的数据元素 组成的有序序列,且该序列必须存储在一块地址连续的存储单元中。数组具有以下特点:

1)数组中的数据元素具有相同数据类型

2)数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素。

3)数组中的数据元素个数是固定的。

数组的抽象数据类型定义:

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

由上述定义知,n维数组中有个数据元素,每个数据元素都受到n维关系的约束

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数组的顺序表示和实现

数组一般不做插入和删除操作,也就是说数组一旦建立,结构中的元素的个数和元素间的关系就不再发生变化。因此一般都是采用顺序存储的方法来表示数组。

计算机的内存结构是一堆(线性)地址结构,对于多维数组,将其存放(映射)到内存一维结构时,有个次序约定问题。即必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放到内存中。

二维数组是最简单的多维数组,以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。

二维数组的两种存储方式(以行序为主、以列序为主):

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

举个例子:

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

矩阵的压缩存储

        在科学与工程计算问题中,矩阵是一种常用的数学对象,在高级语言编程时,通常将一个矩阵描述为一个二维矩阵。这样可以对其元素进行随机存取,各种矩阵运算也非常简单。

        对于高阶矩阵,若其中非零元素呈某种规律分布或者矩阵中有大量的零元素,若仍然用常规方法存储,可能存储重复的非零元素或零元素,将造成存储空间的大量浪费。所以要对这类矩阵进行压缩存储。

注意:多个相同的非零元素只分配一个存储空间;零元素不分配空间。

接下来我们要掌握 特殊矩阵稀疏矩阵 的压缩存储方式。

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

广义表的定义

        广义表是线性表的推广和扩充,在人工智能领域中应用十分广泛。我们把线性表定义为n(n0)个元素的有穷序列,该序列中的所有元素具有相同的数据类型且只能是原子项(所谓原子项可以是一个数或一个结构,是指结构上不可再分的。)若放松对元素的这种限制,容许它们具有其自身结构,就产生了广义表的概念。

广义表(Lists,又称为列表):是由n(n0)个元素组成的有穷序列:LS=()

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

广义表的存储结构

由于广义表中的数据元素具有不同的结构,通常用链式存储结构表示,每个数据元素用一个结点表示。因此,广义表中就有两类结点:

一类是表结点:用来表示广义表项,由标志域,表头指针域,表尾指针域组成

一类是原子结点:用来表示原子项,由标志域,原子的值域组成。

只要广义表非空,都是由表头和表尾组成。即一个确定的表头和表尾就唯一确定一个广义表。

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

数据结构--》数组和广义表:从基础到应用的全面剖析,算法设计与分析,数据结构,数组和广义表,算法,经验分享

什么是广义表?请简述广义表与线性表的区别?

        广义表(Generalized List)是一种扩展了线性表的数据结构,它允许元素既可以是单值,也可以是子表。广义表通过递归方式定义,可以包含任意嵌套层级的子表,从而形成一个更加复杂和有层次结构的数据集合。

        与广义表相对应的是线性表(Linear List),线性表仅包含单值元素,每个元素都有一个后继元素,形成一个线性结构。线性表是最简单和最常见的数据结构之一,例如数组就是线性表的一种实现。

广义表与线性表的区别主要有以下几点:

1. 元素类型:线性表的元素只能是单值,而广义表的元素可以既是单值,也可以是子表。这使得广义表能够表示更加复杂和有层次结构的数据关系。

2. 结构特点:线性表是一种线性结构,每个元素都有唯一的后继元素,形成了一个简单的序列。而广义表则具有更加复杂的层次结构,可以包含任意嵌套层级的子表,形成了一个树状结构。

3. 操作灵活性:由于广义表具有更复杂的结构,因此在操作和处理数据时,广义表比线性表更加灵活。广义表可以使用递归的方式进行遍历和操作,可以处理各种复杂的数据关系,而线性表则相对简单。

综上所述,广义表是一种扩展了线性表的数据结构,允许元素既可以是单值,也可以是子表。广义表具有更加复杂的层次结构和操作灵活性,可以更好地表示和处理各种复杂的数据关系。

一个广义表是(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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之串|数组|广义表

    总结:

    2024年01月16日
    浏览(45)
  • 数据结构之数组、矩阵和广义表

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月22日
    浏览(44)
  • 数据结构与算法·第5章【数组和广义表】

    两种顺序映象的方式: 以行序为主序(低下标优先); 以列序为主序(高下标优先)。 而 n n n 维数组: LOC(x1, x2, ..., xn) = LOC(0, 0, ..., 0) + [(x1 × b1 + x2) × b2 + x3] × b3 + ... + xn 数据类型定义 其中: A.bounds是每一维可以放多少元素: a[A.bounds[0]][A.bounds[1]][A.bounds[2]]…… A.constants是指向每

    2024年02月08日
    浏览(50)
  • 【数据结构】——多维数组、矩阵以及广义表的相关习题

    1、数组通常具有的两种基本操作是()。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 解析: (A) 基本操作是查找和修改,其中每个元素都可以通过其索引来访问,这是从数组的第一个元素开始计算的。除了访问和修改数组元素之外,还可以执行其他一些操

    2024年02月04日
    浏览(38)
  • 数据结构与算法教程,数据结构C语言版教程!(第五部分、数组和广义表详解)五

    数组和广义表,都用于存储逻辑关系为“一对一”的数据。 数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。 本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和

    2024年01月23日
    浏览(50)
  • 数据结构与算法教程,数据结构C语言版教程!(第五部分、数组和广义表详解)三

    数组和广义表,都用于存储逻辑关系为“一对一”的数据。 数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。 本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和

    2024年01月21日
    浏览(48)
  • 数据结构与算法分析 第七章 串、数组和广义表 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月04日
    浏览(48)
  • 数据结构-广义表的存储结构(两种)

    头尾链表的存储结构由两种节点结构组成: 表结点 表节点由三部分组成,tag为标志,tag=1表示表节点,tag=0表示原子节点,hp和tp表示两个指针,hp指向该节点的下一层的节点,tp指向同一层的后一个节点。 原子节点 原子节点由两部分部分组成,tag为标志,tag=1表示表节点,

    2024年01月19日
    浏览(43)
  • 基础数据结构:数组介绍

    程序设计 = 数据结构+算法 说到数据结构是什么,我们得先来谈谈什么叫数据。 正所谓\\\"巧妇难为无米之炊’,再强大的计算机,也是要有\\\"米’下锅才可以的,否则就是一堆破铜烂铁 这个\\\"米\\\"就是数据。 数据: 是描述客观事物的符号,是计算机中可以操作的对象,是能被计算

    2024年02月11日
    浏览(44)
  • 数据结构基础-数组

    概述 定义 在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key 因为数组内的元素是 连续存储 的,

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包