数据结构：深入理解广义表常用的两种存储结构（头尾链，孩子兄弟链）

目录

前言：

结点和定义结构体

头尾链（如图1）：

 孩子兄弟链（如图3）：

广义表结构图

 头尾链存储结构（如图5）：

孩子兄弟存储结构（如图6）：

当有空表的时候：

优缺点：

头尾链结构优点：

头尾链结构缺点：

孩子兄弟链结构优点：

孩子兄弟链结构缺点：

前言：

广义表内的元素有两种：原子，广义表；很难顺序结构，因此通常都是链结构。

对于同一逻辑结构可以有不同的存储结构，(表)头(表)尾链，孩子兄弟链都是链式存储结构，但是其中的结点构成不一样，因此都是链式也不能说是相同的存储结构。

结点和定义结构体

头尾链（如图1）：

        原子结点：tag=0（表示此节点为原子型）data用于存放数据

        表结点：tag=1（表示表结点）指针head用于指向表头，指针tail用于指向表尾

 可以定义为两个结构体：不过我认为这样麻烦因为还是无法避免需要共用体,表头可以能是表，也可能是原子，更长用的是下面定义一个结构体

typedef char Elemtype;typedef struct {int tag;Elemtype data;
} Atom;typedef struct node {int tag;union {struct node * gl;Atom * atom;} head;struct node * tail;
} Glist;

定义一个结构体：

typedef char Elemtype; //广义表采用表头表尾链的方式存储
typedef struct Node{int tag;						//0表示原子，1表示广义表 union {Elemtype data;				//共用体，tag值0，存放原子数据 struct {			//tag值1 struct Node * head;		//指向表头的指针 struct Node * tail;		//指向表尾的指针 } Link;};
} GLNode, *Glist; 

tag和一个共用体，data和结构体Link公用一段空间，结构体Link里包含head和tail指针，如图2

 孩子兄弟链（如图3）：

        原子结点：tag，data（存放元素），link（指向兄弟结点）

        表结点：tag，sublist（存放子表），link

 结构体的定义就是data和sublist共用体，就不放图了，看看代码：

typedef char Elemtype; //广义表采用孩子兄弟链的方式存储
typedef struct Node{int tag;						//0表示原子，1表示广义表 union {Elemtype data;				//共用体，tag值0，存放原子数据 struct Node * sublist;};struct Node * link;
} GLNode, *Glist; 

广义表结构图

广义表：LS = (a,(b,(c),d)); 设B = (c); A = (b,(c),d) = (b,B,d);（如图4）

 头尾链存储结构（如图5）：

LS的表头：原子a，表尾：广义表(A),注意是(A)不是A；（A）的表头：广义表A，表尾：^；A的表头：原子a，表尾：广义表(B,d)；(B,d)的表头：广义表B，表尾广义表(d)；B的表头：原子c，表尾：^；(c)的表头：原子c，表尾^；

孩子兄弟存储结构（如图6）：

 sulist指针会指向第一个孩子，剩下的孩子都靠前一个“哥哥”的link指针链接

当有空表的时候：

 弄一个刁钻的广义表：LS = ((),(((),(()))))；

 在有空表的头尾链结构存储会破坏广义表的层次结构

优缺点：

我学疏才浅，就我目前的知识储备也不是很清楚优缺点，可以后来再补充，就目前看到的：

头尾链结构优点：

1.存储空间更独立

2.第一层数量即为长度

3.除空表外head指针不为空，为空也是有空表，所以head指针一直有意义

头尾链结构缺点：

1.第一个表头缺少“表尾头节点”，结构与后续表尾的表头结构不同一

2.有空表的时候不方便观察层次

孩子兄弟链结构优点：

1.层次结构清晰明了

2.结构同一性

孩子兄弟链结构缺点：

这个我确实没想到，后续学到了再补充吧！！！

会破坏树存储的层次结构（树中一个分叉为一层）

最后

广义表因为结构具有同一性，在写对应算法的时候只需要对正在处理的广义表负责，剩下的交给递归即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！