广义表的概念。
广义表(lists,又称列表)是线性表的推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。
1、广义表定义。
广义表是n(n≥0)个元素a1,a2,…,ai,…,an的有限序列。
其中:①ai--或者是原子或者是一个广义表。
②广义表通常记作:
ls=( a1,a2,…,ai,…,an)。
③ls是广义表的名字,n为它的长度。
④若ai是广义表,则称它为ls的子表。
注意:①广义表通常用圆括号括起来,用逗号分隔其中的元素。
②为了区分原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。
③若广义表ls非空(n≥1),则al是ls的表头,其余元素组成的表(a1,a2,…,an)称为ls的表尾。
④广义表是递归定义的。
2、广义表表示。
1)广义表常用表示。
① e=()
e是一个空表,其长度为0。
② l=(a,b)
l是长度为2的广义表,它的两个元素都是原子,因此它是一个线性表。
③ a=(x,l)=(x,(a,b))
a是长度为2的广义表,第一个元素是原子x,第二个元素是子表l。
④ b=(a,y)=(x,(a,b)),y)
b是长度为2的广义表,第一个元素是子表a,第二个元素是原子y。
⑤ c=(a,b)=(x,(a,b)),x,(a,b)),y))
c的长度为2,两个元素都是子表。
⑥ d=(a,d)=(a,(a,(a,(…
d的长度为2,第一个元素是原子,第二个元素是d自身,展开后它是一个无限的广义表。
2)广义表的深度。
一个表的"深度"是指表展开后所含括号的层数。
【例】表l、a、b、c的深度为分别为,表d的深度为∞。
3)带名字的广义表表示。
如果规定任何表都是有名字的,为了既表明每个表的名字,又说明它的组成,则可以在每个表的前面冠以该表的名字,于是上例中的各表又可以写成:
e()l(a,b)
a(x,l(a,b))
b(a(x,l(a,b)),y)
c(a(x,l(a,b)),b(a(x,l(a,b)),y))
d(a,d(a,d(…)
4)广义表的图形表示。
a)广义表的图形表示:
①图中的分支结点对应广义表。
②非分支结点一般是原子。
③但空表对应的也是非分支结点。
【例】下图给出了几个广义表的图形表示。
b)广义表的图形形状划分:
①与树对应的广义表称为纯表,它限制了表中成分的共享和递归。
②允许结点共享的表称再入表。
【例】上图(d),子表a是共享结点,它既是c的一个元素,又是子表b的元素;
③允许递归的表称为递归表。
【例】上图(e),表d是其自身的子表。
5)递归表、再人表、纯表、线性表之间的关系满足:
广义表不仅是线性表的推广,也是树的推广。
3、广义表运算。
由于广义表是对线性表和树的推广,并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应,因此广义表的大部分运算与这些数据结构上的运算类似。
在此,只讨论广义表的两个特殊的基本运算:取表头head(ls)和取表尾tail(ls)。
根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素,它可以是原子,也可以是子表,而其表尾必定是子表。
【例】head(l)=a, tail(l)=(b)
head(b)=a, tail(b)=(y)
由于tail(l)是非空表,可继续分解得到:
head(tail(l))=b, tail(tail(l))=
对非空表a和(y),也可继续分解。
注意:广义表()和(()不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则,规定了解决某一特定类型问题的一系列运算,是对解题方 与完整的描述。算法是解题的步骤,可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生,定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图,请画出此图,写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树,其根指针为root,编写求此二叉树叶结点个数的算法,要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...