赞
踩
目录
广义表内的元素有两种:原子,广义表;很难顺序结构,因此通常都是链结构。
对于同一逻辑结构可以有不同的存储结构,(表)头(表)尾链,孩子兄弟链都是链式存储结构,但是其中的结点构成不一样,因此都是链式也不能说是相同的存储结构。
原子结点: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
原子结点: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)
LS的表头:原子a,表尾:广义表(A),注意是(A)不是A;(A)的表头:广义表A,表尾:^;A的表头:原子a,表尾:广义表(B,d);(B,d)的表头:广义表B,表尾广义表(d);B的表头:原子c,表尾:^;(c)的表头:原子c,表尾^;
sulist指针会指向第一个孩子,剩下的孩子都靠前一个“哥哥”的link指针链接
弄一个刁钻的广义表:LS = ((),(((),(()))));
在有空表的头尾链结构存储会破坏广义表的层次结构
我学疏才浅,就我目前的知识储备也不是很清楚优缺点,可以后来再补充,就目前看到的:
1.存储空间更独立
2.第一层数量即为长度
3.除空表外head指针不为空,为空也是有空表,所以head指针一直有意义
1.第一个表头缺少“表尾头节点”,结构与后续表尾的表头结构不同一
2.有空表的时候不方便观察层次
1.层次结构清晰明了
2.结构同一性
这个我确实没想到,后续学到了再补充吧!!!
会破坏树存储的层次结构(树中一个分叉为一层)
广义表因为结构具有同一性,在写对应算法的时候只需要对正在处理的广义表负责,剩下的交给递归即可。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。