程序员在旅途

用这生命中的每一秒，给自己一个不后悔的未来！

0%

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

发表于 更新于 分类于 Valine：
本文字数： 6k 阅读时长 ≈ 5 分钟

一，广义表的基本概念

　　广义表(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操作，以后用到，还得要继续深入理解，欢迎交流。

相关文章推荐