【408数据结构与算法】—广义表(二十六)

简介: 广义表又称列表Lists是n>=0个元素a0,a1,…an-1的哟选序列,其中每一个ai或者是原子,或者是一个广义表

【408数据结构与算法】—广义表(二十六)

一、广义表

  • 广义表又称列表Lists是n>=0个元素a0,a1,…an-1的哟选序列,其中每一个ai或者是原子,或者是一个广义表
  • 广义表通常记作:LS=(a1,a2,…an)

其中:LS为表名,n为表的长度,每一个ai为表的元素。习惯上,一般用大写字母表示广义表,小写字母表示原子。

2345_image_file_copy_425.jpg

2345_image_file_copy_426.jpg

2345_image_file_copy_427.jpg

2345_image_file_copy_428.jpg

二、广义表的相对性质

  1. 广义表中的数据元素有相对次序,一个直接前趋和一个直接后继
  2. 广义表的长度定义为最外层所包含的元素的个数,如:C=(a,(b,c))是长度为2的广义表
  3. 广义表的深度定义为该广义表展开后所包含括号的重数

2345_image_file_copy_429.jpg

  1. 广义表可以为其他广义表共享,如:广义表B就共享表A。在B中不必列出A的值,而是通过名称来引用,B=(A)
  2. 广义表也可以是一个递归的表,注意:递归表的深度是无穷的值,长度是有限的值。如F=(a,F)=(a,(a,(a,……)))
  3. 广义表是多层次的结构,广义表的元素可以是单元素,也可以是子表,而子表的元素还可以是子表

2345_image_file_copy_430.jpg

2345_image_file_copy_431.jpg

广义表与线性表的区别?

  1. 广义表是线性表的推广,是由0个或多个单元素或子表组成的有限序列。
  2. 广义表与线性表的区别在于:线性表的元素都是结构上不可分的单元素,而广义表的元素既可以是单元素,也可以是有结构的表。
  3. 广义表的长度是指广义表中元素的个数。广义表的深度是指广义表展开后所含的括号的最大层数。
  1. 非空广义表的第一个元素称为表头,他可以是一个单元素,也可以是一个子表;除表头元素之外,由其余元素所构成的表称为表尾,非空广义表的表尾必定是一个表。

三、广义表的基本运算

求表头GetHead(L): 非空广义表的第一个元素,可以是一个单一的元素也可以是一个子表

求表尾GetTail(L):非空广义表除去表头元素以外其他元素所构成的表,表尾一定是一个表。

2345_image_file_copy_432.jpg

四、广义表的存储结构

由于广义表中的元素本身又可以具有结构,它是一种带有层次的非线性结构,因此难以用顺序存储结构表示,通常采用链式存储结构。

若广义表不为空,则可分解为表头和表尾两部分。反之,一对确定的表头和表尾可唯一确定一个广义表。

广义表中的元素可以是原子也可以是子表,针对原子和子表可以分别设计不同的节点结构。表节点有标志域、指示表头的指针域和指示表尾的指针域;而原子只有标志域和值域。

2345_image_file_copy_433.jpg

例如广义表LS=(a,(b,c,d)),其链式存储结构如图所示:

2345_image_file_copy_434.jpg



相关文章
|
6月前
|
存储 人工智能 资源调度
第五章 多维数组和广义表【数据结构与算法】【精致版】
第五章 多维数组和广义表【数据结构与算法】【精致版】
109 0
|
6月前
|
存储 算法 数据安全/隐私保护
第二章 线性表【数据结构与算法】【精致版】
第二章 线性表【数据结构与算法】【精致版】
125 0
|
1月前
|
存储
【初阶数据结构】树与二叉树:从零开始的奇幻之旅
【初阶数据结构】树与二叉树:从零开始的奇幻之旅
|
6月前
|
存储 机器学习/深度学习 算法
【专题讲解】数据结构与算法——链表(附代码)
【专题讲解】数据结构与算法——链表(附代码)
57 1
|
6月前
|
存储 人工智能 算法
【408数据结构与算法】—广义表(二十六)
【408数据结构与算法】—广义表(二十六)
|
6月前
|
存储 算法
【408数据结构与算法】—树和二叉树(二十七)
【408数据结构与算法】—树和二叉树(二十七)
|
存储 算法
【AcWing算法基础课】第二章 数据结构(部分待更)(1)
e数组存储每个结点的值,ne数组存储每个结点的指向的下一个结点。
86 0
|
存储 算法 C++
【AcWing算法基础课】第二章 数据结构(部分待更)(3)
路径压缩:查找时,如果还没有找到目标值的父结点时,将路径上每个点的父结点,在向上寻找过程中更新记录。
91 0
|
存储 算法
【AcWing算法基础课】第二章 数据结构(部分待更)(2)
给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
80 0
|
机器学习/深度学习 算法
2022 数据结构与算法《王道》学习笔记 (十二)树和二叉树 详细总结
2022 数据结构与算法《王道》学习笔记 (十二)树和二叉树 详细总结