avatar

数据结构之广义表的相关知识点

一,广义表的基本概念

  广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构(即可以有子表)。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中,广义表是一种最基本的数据结构,就连LISP 语言的程序也表示为一系列的广义表。

二,广义表的基本表示

 1,概念角度分析:

广义表是n个元素a1,a2,a3…. an组成的有限序列,通常记为:LS = (a1,a2,a3…. an);
其中,LS代表表名,ai 代表表中元素即为表元素,其既可以为单个原子元素又可以是一个广义表,当ai为为广义表是成为LS的一个子表(此处体现出来了递归思想)。
★特别提醒:
a,n为表的长度,当n = 0时,LS为空表;n >0时,表的第一个表元素称为广义表的表头(head),除此之外,其它表元素组成的表称为广义表的表尾(tail)。即当a1为表 头元素时,(a2,a3 ……an)为表尾元素。
b,因为元素可以为子表,所以就体现出来层次结构(关于分层,请看下图)。

 2,举例说明:

A=( ); //A是一个空表
B=(e); //表B有一个原子
C=(a, (b,c,d) ); //两个元素为原子a和子表(b,c,d)
D=(A,B,C); //有三个元素均为列表
E=(a,E); //递归的列表,包含两个元素,一个是单元素a,另一个是子表,但该子表是其自身.所以,E相当于一个无限的广义表( a,(a,(a,…))).

 3,几个常见术语:

a,表的深度:表展开后所含括号的层数;
b,表的长度:长度为第一层的元素个数(原子和子表都只算一个);
c,表头、表尾。

 4,图形化理解表:
表的定义
  5,表头表尾的求法:
  以C表为例:GetHead(C) = a; GetTail(c) = ( (b,c,d) );
  算法实现(存储结构采用头尾链表存储表示,详见下图):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
PGNode GetHead(PGNode p)
{
if( !p || p->tag==0 )
{
printf("表头子表元素不存在\n");
return NULL;
}
return p->ptr.sublist ;
}
PGNode GetTail(PGNode p)
{
if( !p || p->tag==0 )
{
printf("空表或者为单个原子元素\n");
return NULL;
}
return p->ptr.next ;
}

三、广义表的存储结构

  由于表元素的特殊性,通常采用链式存储,而不采用顺序存储,由于可能会有两种表元素,所以需要采用两种结构的节点,分别为原子节点和表结点。
  按照其节点结构的不同,可以设计两种不同的存储结构:
  a,广义表的头尾链表存储表示:
头尾链表存储表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef int NodeType; //节点类型,1为表结点,0为原子节点;
typedef char ElemType;//元素类型是字符型
struct GNode{

NodeType  NodeTag;      //标志域

union{           //值域或子表的表头指针域

        ElemType data;

struct { GNode *sublist,*next }ptr;

};  //ptr表节点的指针域,sublist , next表头表尾指针;

}*PGNode;

  b, 广义表的扩展线性链表表示:
扩展线性链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  typedef int NodeType; //节点类型,1为表结点,0为原子节点;            

typedefchar ElemType;//元素类型是字符型
struct GNode

{

 NodeType NodeTag;      //标志域

    union{           //值域或子表的表头指针域

          ElemType data;

           struct GNode *sublist;

    };

    struct GNode *next;  //指向后继结点的指针域

}*PGNode;

扩展线性链表2

四、广义表基本操作(创建,遍历,求深度,查找某一元素)的代码实现

  由于广义表的形成缘由有递归的思想(子表),所以, 广义表的操作可采用递归与非递归算法实现;在其存储结构上,可采用上述两种的任何一种。
  下面将采用递归算法、存储结构采用扩展线性链表来实现广义表的基本操作:
  4.1 节点定义:

1
2
3
4
5
6
7
8
9
10
11
typedef int NodeType;
typedef char ElemType;//元素类型是字符型
typedef struct GNode
{
NodeType NodeTag; //标志域
union{ //值域或子表的表头指针域
ElemType data;
struct GNode *sublist;
};
struct GNode *next; //指向后继结点的指针域
}*PGNode;

  4.2 建立广义表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
CreateGList(PGNode *GL)
{
char ch;
scanf("%c", &ch);//读入一个字符,此处只可能读入空格#、左括号或英文字母
if(ch=='#')//若输入为空格,则置表头指针为空
{
*GL = NULL;
}
else if(ch=='(')//若输入为左括号则建立由*GL所指向的子表结点并递归构造子表
{
*GL = (PGNode GL)malloc(sizeof(struct GNode));
(*GL)->NodeTag = 1;
CreateGList(&((*GL)->sublist));
}
else{ //若输入为字符则建立由*GL所指向的单元素结点
*GL = (PGNode GL) malloc(sizeof(struct GNode));
(*GL)->NodeTag = 0;
(*GL)->data = ch;
}
scanf("%c", &ch);//此处读入的字符必为逗号、右括号或分号
if(*GL==NULL); //若*GL为空,则什么都不做
{
return ;
}
else if(ch==',')//若输入逗号则递归构造后继表
{
CreateGList(&((*GL)->next));
}
else if((ch==')') || (ch==';'))//若输入为右括号或分号则置*GL的后继指针域为空
{
(*GL)->next = NULL;
}
}

  4.3 求广义表的深度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int DepthGList(PGNode GL)
{
int max=0;//给max赋初值
//遍历表中每一个结点,求出所有子表的最大深度
while(GL!=NULL)
{
if(GL->NodeTag==1){
int dep = DepthGList(GL->sublist);//递归调用求出一个子表的深度
if(dep > max)
max = dep;//让max始终为同一层所求过的子表中深度的最大值
}
GL = GL->next;//使GL指向同一层的下一个结点
}
return(max + 1);//返回表的深度
}

  4.4 求广义表的长度

1
2
3
4
5
6
7
int LengthGList(PGNode GL)
{
if(GL!=NULL)
return(1 + LengthGList(GL->next));
else
return(0);
}

  4.5 打印输出广义表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 void PrintGList(PGNode GL)
{
//对于表结点的处理情况
if(GL->NodeTag==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);//再递归输出后继表
}
}

  4.6 构建总体代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 #include<stdio.h>
#include<stdlib.h>
typedef int NodeType;
typedef char ElemType;
typedef struct GNode
{
NodeType NodeTag;
union{
ElemType data;
struct GNode *sublist;
};
struct GNode *next;
}*PGNode;
void CreateGList(PGNode *GL)
{
char ch ;
scanf("%c",&ch);
if( ch== '#')
{
*GL = NULL;
}
else if( ch=='(' )
{
*GL = (PGNode) malloc ( sizeof(struct GNode) );
(*GL)->NodeTag = 1;
CreateGList( &(*GL)->sublist );
}
else
{
*GL = (PGNode) malloc ( sizeof(struct GNode) );
(*GL)->NodeTag = 0;
(*GL)->data = ch ;
}
scanf("%c",&ch);
if(*GL== NULL)
{
return ;
}
else if( ch==',' )
{
CreateGList( &(*GL)->next );
}
else if( (ch==')') || (ch==';') )
{
(*GL) ->next = NULL;
}
}

void PrintGList(PGNode GL)
{
if( GL->NodeTag == 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 );
}
}

int Depth( PGNode GL )
{
int max = 0;
while(GL != NULL )
{
if(GL->NodeTag == 1){
int dep = Depth( GL->sublist );
if( dep>max )
{
max = dep;
}
}
GL = GL->next ;
}
return (max+1);
}

int LengthGList( PGNode GL )
{
if( GL !=NULL )
{
return (1+LengthGList(GL->next) );
}
else
{
return 0;
}
}

int main()
{
PGNode GL;
int depth,length;
printf("******采用递归方法进行广义表的基本操作******\n");
printf("请输入一个广义表,以分号结束 : ");
CreateGList(&GL);
printf("\n此方法输出的输出广义表-> :");
PrintGList(GL);
printf("\n\n");
depth = Depth( GL->sublist );
printf("广义表的深度depth为-> %d \n",depth);
length = LengthGList( GL->sublist );
printf("广义表的长度width为-> %d \n",length);
return 0;
}

  结果如下:
程序截图

五、学习心得

  广义表作为对线性表的一种推广,秉承了线性表的基本思想,也采取了和线性表相似的存储结构,但是,要比线性表复杂好多,从CRUD操作就可以看出来,我的掌握也不是很透彻,只会一些基本的CRUD操作,以后用到,还得要继续深入理解,欢迎交流。

文章作者: IT之旅
文章链接: https://www.meijindong.top/posts/2679146056.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 程序员在旅途
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论