数据结构—数组和广义表

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

4.2数组

数组:按一定格式排列起来的,具有相同类型的数据元素的集合。

**一维数组:**若线性表中的数据元素为非结果的简单元素,则称为一维数组。

**一维数组的逻辑结构:**线性结构,定长的线性表。

**声明格式:**数据类型 变量名称 [长度] ;

例如:int num[5] = {0,1,2,3,4};

**二维数组:**若一维数组中的数据元素又是一维数组结构,则称为二维数组。

二维数组的逻辑结构:

  1. 非线性结构:每一个数据元素既在一个行表中,又在一个列表中。
  2. 线性结构定长的线性表:该线性表的每个数据元素也是一个定长的线性表。

**声明格式:**数据类型 变量名称 [行数] [列数];

例如:int num [5] [8];

在C语言中,一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型),即:

  typedef int array2[m][n];
等价于:
  typedef int array1[n];
  typedef array1 array2[m];

**三维数组:**若二维数组中的元素又是一个一维数组,则称作三维数组。

**n维数组:**若 n - 1 维数组中的元素又是一个一维数组结构,则称作 n 维数组。

**结论:**线性表结构是数组结构的一个特例,而数组结构又是线性表结构的扩展。

**数组特点:**结构固定——定义后,维数和维界不再改变。

**数组基本操作:**除了结构的初始化和销毁之外,只有取元素和修改元素值的操作。

4.2.1数组的顺序存储结构

数组特点:结构固定——维数和维界不变。

一般都是采用顺序存储结构来表示数组。

**注意:**数组可以是多维的,但存储数据元素的内存单元地址是一维的,因此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题。

一维数组:

例:有数组定义:int a[5]

每个元素占用4字节,假设a[0]存储在2000单元,a[3]地址是多少?

LOC(0) = a = 2000 L=4

LOC(3) = 3*4+2000

LOC(i) = i*L + 首地址

存储单元是一维结构,而数组是个多维结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题。

二维数组可有两种存储方式:

  1. 以行序为主序;

    设数组开始存储位置LOC(0,0),存储每个元素需要L个存储单元

    数组元素a[i] [j]的存储位置是:LOC(i,j)=LOC(0,0) + (n * i + j) * L

  2. 以列序为主序。

**三维数组:**按页/行/列存放,页优先的顺序存储。

4.2.2特殊矩阵的压缩存储

**矩阵:**一个由 m*n 个元素排成的 m 行 n 列的表。

**矩阵的常规存储:**将矩阵描述为一个二维数组。

矩阵的常规存储的特点:

  1. 可以对其元素进行随机存取。
  2. 矩阵运算非常简单;存储的密度为1.

**不适宜常规存储的矩阵:**值相同的元素很多且呈某种规律分布;零元素多。

**矩阵的压缩存储:**为多个相同的非零元素只分配一个存储空间;对零元素不分配空间。

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

1、什么是压缩存储

若多个数据元素的值都相同,则只分配一个元素值的存储空间,且零元素不占存储空间。

2、什么样的矩阵能够压缩?

一些特殊矩阵,如:对称矩阵,对角矩阵,三角矩阵,稀疏矩阵等。

3、什么叫稀疏矩阵?

矩阵中非零元素的个数较少(一般小于5%)

1.对称矩阵

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

**【特点】:**在 n*n 的矩阵 a 中,满足如下性质:aij=aji(1≤i , j≤n)

**【存储方法】:**只存储下(或者上)三角(包括主对角线)的数据元素。共占用 n(n+1)/2个元素空间。

**【存储结构】:**对称矩阵上下三角中的元素数均为:n(n+1)/2

​ 可以以行序为主序将元素存放在一个一维数组 sa[ n(n+1)/2 ]中。

2.三角矩阵

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6FofxLkg-1690537372616)(https://tse1-mm.cn.bing.net/th?id=OIF-C.uHr%2bn0jNJ2j8NRD2iircPA&pid=ImgDet&rs=1)]

**【特点】:**对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。

**【存储方法】:**重复元素c共享一个元素存储空间,共占用n(n+1)/2+1个元素空间:[1…n(n+1)/2+1]

上三角矩阵:

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

下三角矩阵:

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

3.对角矩阵(带状矩阵)

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

**【特点】:**在n*n的方阵中,所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为0,则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

4.稀疏矩阵

**稀疏矩阵:**设在 m*n 的矩阵中有 t 个非零元素。

​ 令 δ = t / (m*n)

​ 当 δ ≤ 0.05 时称为稀疏矩阵。

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

**压缩存储原则:**存各非零元素的值,行列位置和矩阵的行列数。

4.1三元组顺序表

数据结构—数组和广义表,数据结构考研,数据结构,java,算法

注意:为更可靠描述,通常再加一个“总体”信息:即总行数、总列数、非零元素总个数。

三元组顺序表又称有序的双下标法。

三元组顺序表的优点:非零元素在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。

三元组顺序表的缺点:不能随机存取。若按行号存取某一行中的非零元素,则需从头开始进行查找。

4.2十字链表
  • **优点:**它能够灵活地插入因运算而产生的新的非零元素,删除因运算而产生的新的零元素,实现矩阵的各种运算。

  • 在十字链表中,矩阵的每一个非零元素用一个结点表示,该结点除了(row,col,value)以外,还要有两个域:

    • right:用于链接同一行中的下一个非零元素。
    • down:用以链接同一列中的下一个非零元素。
  • 十字链表中结点的结构示意图:

    数据结构—数组和广义表,数据结构考研,数据结构,java,算法

    数据结构—数组和广义表,数据结构考研,数据结构,java,算法

4.3广义表

4.3.1广义表定义

广义表(又称列表Lists)是n≥0个元素 a0,a1,…,an-1的有限序列,其中每一个ai或者是原子,或者是一个广义表。

例如:中国举办的国际足球邀请赛,参赛队伍名单可表示如下:

(阿根廷,巴西,德国,法国,(),西班牙,意大利,英国,(国家队,山东鲁能,广州恒大))

在这个表中,叙利亚队应排在法国队的后面,但未能参加,成为空表。国家队,山东鲁队,广州恒大均作为东道主的参赛队参加,构成一个小的线性表,成为原线性表的一个数据元素。这种拓宽了的线性表就是广义表。

  • 广义表通常记作:LS=( a1,a2,…,an

  • 习惯上,一般用大写字母表示广义表小写字母表示原子

  • **表头:**若LS非空(n≥1),则其第一个元素a1就是表头。记作head(LS)=a1.

    注意:表头可以是原子,也可以是子表。

  • 表尾除表头之外的其他元素组成的表。记作tail(LS)=(a2,…,an)

    注意:表尾不是最后一个元素,而是一个子表。

    例如:(1) A=() 空表,长度为0

    ​ (2)B=(( )) 长度为1,表头、表尾均为()。

    ​ (3)C=(a,(b,c)) 长度为2,由原子a和子表(b,c)构成。表头为a,表尾为((b,c))

    ​ (4)D=(x,y,z) 长度为3,每一项都是原子。表头为x,表尾为(y,z)

    ​ (5)E=(C,D) 长度为2,每一项都是子表。表头为C,表尾为(D)

    ​ (6)F=(a,F) 长度为2,第一项为原子,第二项为它本身。表头为a,表尾为(F)。F=(a,(a,(a,…)))

4.3.2广义表的性质
  1. 广义表的数据元素有相对应次序;一个直接前驱和一个直接后继。

  2. 广义表的长度定义为最外层所包括元素的个数,如C=(a,(b,c))是长度为2的广义表。

  3. 广义表的深度定义为该广义表展开后所含括号的重数

    注意:“原子”的深度为0;“空表”的深度为1。

  4. 广义表可以为其他广义表共享:如:广义表B就共享表A。在B中不必列出A的值,而是通过名称来引用。B=(A)

  5. 广义表可以是一个递归的表。

    注意:递归表的深度是无穷值,长度是有限值。

  6. 广义表是一个多层次结构,广义表的元素可以是单元数,也可以是子表,而子表的元素还可以是子表。

    数据结构—数组和广义表,数据结构考研,数据结构,java,算法

4.3.3广义表和线性表的区别

广义表可以看成是线性表的推广线性表是广义表的特例

广义表的结构相当灵活,在某种前提下,它可以兼容线性表、数组、数和有向图等各种常见的数据结构。

当二维数组的每行(或每列)作为子表处理时,二维数组即为一个广义表。

另外,数和有向图也可以用广义表来表示。

由于广义表不仅集中了线性表,数组,数和有向图等常见数据结构的特点,而且可有效地利用存储空间,因此在计算机的许多应用领域都有成功使用广义表的实例。文章来源地址https://www.toymoban.com/news/detail-615983.html

4.3.4广义表的基本运算
  1. 求表头GetHead(L):非空广义表的第一个元素,可以是一个单一元素,也可以是一个子表。
  2. 求表尾GetTail(L):非空广义表除去表头元素以外其他元素所构成的表,表尾一定是一个表。

到了这里,关于数据结构—数组和广义表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构【数组、串、广义表】

    一、数组 1.概念:线性表是通过数组实现的,数组是线性表的推广,数组只有存取元素和修改元素的操作(除了初始化和销毁); 2.数组的存储结构:一个数组的所有元素在内存中占用一段连续的存储空间(顺序存储); 以行为主顺序优先存储; 以列为主顺序优先存储。

    2024年02月15日
    浏览(41)
  • 数据结构--串、数组、广义表

    也叫字符串 抽象类型定义 存储结构(顺序表较为常用) 顺序存储结构 为了方便一些操作,通常串的数组的第一个位置不放元素,而是从ch【1】开始存放元素 链式存储结构 如果一个结点的数据域只放一个字符,那么会导致存储密度异常的底,解决这个问题:在数据域放更多的

    2024年02月15日
    浏览(39)
  • 12-数据结构-数组、矩阵、广义表

    目录 数组、矩阵、广义表   一、数组         二.矩阵 三、广义表         这一章节理解基本概念即可。数组要看清其实下标是多少,并且二维数组,存取数据,要先看清楚是按照行存还是按列存,按行则是正常一行一行的去读写,按列则是,从左至右,一列一列的弄。

    2024年02月13日
    浏览(37)
  • 数据结构之串|数组|广义表

    总结:

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

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

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

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

    2024年02月04日
    浏览(38)
  • 数据结构--》数组和广义表:从基础到应用的全面剖析

            数据结构为我们提供了组织和处理数据的基本工具。而在这个广袤的数据结构领域中,数组和广义表是两个不可或缺的重要概念。它们作为线性结构的代表,在算法与应用中扮演着重要的角色。         无论你是初学者还是进阶者,本文将为你提供简单易懂、

    2024年02月08日
    浏览(46)
  • 24考研数据结构-数组和特殊矩阵

    数据结构是计算机科学中的基础概念,它涉及组织和存储数据的方式以及对数据的操作。在数据结构中,数组和特殊矩阵是两种常见的数据组织形式。本文将对数组和特殊矩阵进行介绍,并讨论它们在实际应用中的特点和用途。 数组是一种线性数据结构,它由相同类型的元素

    2024年02月14日
    浏览(37)
  • 【数据结构】24王道考研笔记——栈、队列和数组

    基本概念 栈是 只允许在一端进行插入或删除操作 的线性表。 栈顶:线性表允许进行插入删除的那一端 栈底:固定的,不允许进行插入删除的那一端 空栈:不含任何元素的空表 特点: 先进后出 基本操作: 常考题型: [外链图片转存失败,源站可能有防盗链机制,建议将图片

    2024年02月09日
    浏览(70)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(78)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包