广义表的基本操作

时间:2022-05-21 21:16:54

        这几天学《数据结构》,被其中的广义表难住了,经过今天的小小钻研,总算看懂了。。。

这是广义表的基本概念:


   
 广义表(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的深度为分别为1、2、3、4,表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的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()。

代码操作:广义表的基本操作

<pre name="code" class="cpp"><span style="color:#cc33cc;">#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char elemType;

/************************************************************************/
/* 以下是关于广义表操作的4个简单算法 */
/************************************************************************/
struct GNode{
int tag; /* 标志域:取0表示单元素结点;取1时表示子表结点 */
union{
elemType data;
struct GNode *subList;
};
struct GNode *next; /* 指向后继结点的指针域 */
};

/* 1.求广义表的长度 */
int lenthGList(struct GNode *gl)
{
if(gl != NULL){
return 1 + lenthGList(gl->next);
}else{
return 0;
}
}

/* 2.求广义表的深度 */
int depthGList(struct GNode *gl)
{
int max = 0;
/* 遍历每个结点,求出所以子表的最大深度 */
while(gl != NULL){
if(gl->tag == 1){
/* 递归求出一个子表的深度 */
int dep = depthGList(gl->subList);
/* 让max始终为同一个所求子表中深度的最大值 */
if(dep > max){
max = dep;
}
}
gl = gl->next; /* 让gl指向下一个结点 */
}
return max + 1; /* 返回表的深度 */
}

/* 3.建立广义表的存储结构 */
int creatGList(struct GNode* *gl)</span><span style="color:#33ff33;">//二级指针,以修改后继结点和子表的值</span><span style="color:#cc33cc;">
{
char ch;/* 读入一个字符,此处可能读入'#','(',')',','或者英文字母 */
scanf("%c", &ch);
/* 若输入为#,则置表头指针为空 */
if(ch == '#'){
*gl = NULL;
}
/* 若输入左括号则建立由*gl所指向的子表结点并递归构造子表 */
else if(ch == '('){
*gl = malloc(sizeof(struct GNode));
(*gl)->tag = 1;
creatGList(&((*gl)->subList));
}
/* 若输入为字符则建立由*gl所指向的单元素结点 */
else{
*gl = malloc(sizeof(struct GNode));
(*gl)->tag = 0;
(*gl)->data = ch;
}
/* 此处读入的字符必为逗号或右括号或分号 */
scanf("%c", &ch);
/* 若*gl为空,则什么都不做 */
if(*gl == NULL){
;
}
else if( ch== '\n')</span><span style="color:#cc33cc;">
{
printf("输出了回车键\n");
(*gl)->next = NULL;
return 0;
}
/* 若输入为逗号则递归构造后继表 */
else if(ch == ','){
creatGList(&((*gl)->next));
}
/* 若输入为右括号或分号则置*gl的后继指针域为空 */
else if((ch == ')') || (ch == ';')){
(*gl)->next = NULL;
}
return 0;
}

/* 4.打印广义表 */
int printGList(struct GNode *gl)
{
/* 对于表结点的处理 */
if(gl->tag == 1){
/* 存在子表,先输出左括号 */
printf("(");
/* 若子表为空,则输出'#'字符 */
if(gl->subList == NULL){
printf("#");
}
/* 若子表非表,则递归输出子表 */
else{
printGList(gl->subList);
}
/* 当一个子表输出结束后,再输出右括号 */
printf(")");
}
/* 对单元素结点,则输出该结点的值 */
else{
printf("%c", gl->data);
}
/* 输出该结点的后继表 */
if(gl->next != NULL){
/* 先输出逗号分隔 */
printf(", ");
/* 再递归输出后继表 */
printGList(gl->next);
}
return 0;
}

int main()
{
struct GNode *gl;
printf("输入一个广义表, 以右括号结束 ");
creatGList(&gl);
printf("输出广义表:");
printGList(gl);
printf("\n");
printf("广义表的长度:");
printf("%d ", lenthGList(gl->subList));
printf("广义表的深度:");
printf("%d ", depthGList(gl->subList));
system("pause");
return 0;
}</span>