Day Day Up

• 广义表
• • 引入
  • 定义
  • 元素组成
  • 重要的特性
  • 表名
  • 广义表字符串表示转图形表示
  • 储存结构
  • • 空表的结构
    • 两种方法理解递归性
  • 广义表运算
  • • 求表长度
    • 求表深度（我感觉这个挺难懂的）
  • 广义表字符串转链式储存(重点)

广义表

引入

广义表是线性表的推广，将线性的表推广到平面。

定义

广义表：是(n≥0)的元素组成的 有限 的序列，当 n=0 时，称为空表。
空表的表示： (#)

元素组成

GL = {a1,a2,a3,a4,a5,a6};
原子：当a1是一个元素时，称为原子，深度为0
子表：当a1是一个广义表时，称为子表，深度为1

重要的特性

1. 广义表的数据元素既可以原子 也可以是 子表
2. 广义表的元素是有序的，数据元素是有限的（深度可以是无限的）
3. 广义表的 长度 ：最外一层所包含的元素个数
4. 广义表的 深度 ：括号的重数（数一下左括号个数）
5. 广义表是可以共享的
6. 广义表可以是递归的，自己可以是自己的子表，此时深度是无限的，长度是有限的
7. 广义表的拆分：可以分为表头，和表尾，其中表尾是用( )括起来的，所以 表尾一定是一个广义表

表名

名为A的空表：A(#)
无名的空表：· (#) 注意前面的点，表示匿名

广义表字符串表示转图形表示

例：D( A(#) , B(e) , C(a,(b,c,d) ))

1. D是一个广义表，元素 为表A，表B，表C
   
2. 表A为空表，表B的元素为e，表C的元素为a，匿名表
   
3. 该匿名表中元素为 b c d
   

储存结构

1. tag：标记结点的类型
2. union联合域：根据tag做不同的处理
3. link：指向兄弟结点，或者置NULL

空表的结构

空表 不是 ghead == NULL，而是 ghead->sublist == NULL

两种方法理解递归性

解决1：对 广义表 的操作是一致的，子表也是一个独立的广义表

void func1(Node * g){// param g :  广义表的头结点Node * g1 = g->sublist; //指向该表的第一个元素while(g1 != NULL){ //判断是否遍历完了这个广义表if(g1->tag == 1) func(g1); //处理子表元素，传入的g1为子表的表头else {//处理原子操作}g1 = g1->link; // 指向兄弟结点}
}

解决2：对 广义表的结点 操作是一致的

void func2(Node * g){//param g : 广义表结点if(g == NULL) // 递归结束条件return;if(g->tag == 1)//该结点为子表func2(g->sublist); //处理子表的第一个元素结点elsefunc2(g->link); //处理兄弟结点
}

广义表运算

求表长度

思路：不用深入，横向扫到NULL

int getLength(){int ans = 0;Node * g1 = ghead->sublist; //获取第一个元素的地址，ghead为广义表的表头结点while(g1!=NULL){ans++;g1 = g1 -> link; //跳转到兄弟结点}return ans;
}

求表深度（我感觉这个挺难懂的）

注意点：

1. 空表的深度是 1
2. 原子的深度是 0
3. 子表是深度是 1

int getDepth(){return getDepth(ghead); //传入的是表头结点
}
// 用于递归调用
int getDepth1(Node * g){int max = 0,dep;if(g->tag == 0) return 0; //判断头结点为原子Node g1 = g->sublist; //已经确定是子表，则指向首元素if(g1->link ==NULL) return 1;//子表为空表while(g1 != NULL){ // 遍历该非空子表if(g1->tag == 1){dep = getDepth1(g1); //递归调用子表元素if(dep > max) max = dep;//更新最大值}g1 = g1 -> link; //指向兄弟结点}return max + 1; // 返回表的深度 + 自身的深度1
}

广义表字符串转链式储存(重点)

从左到右扫字符串

1. 遇到 #：说明前面的广义表是空表
2. 遇到 (：说明是一个广义表
3. 遇到) ：最近的一个广义表结束了
4. 遇到，：添加一个兄弟结点

Node* create1(char* &s){Node * g;char chr =  * s++; //获取后自增 s++，是指针的自增if(chr != '\0'){g = new Node;if (ch == '('){//左括号说明遇到了一个子表g -> tag =1;g -> sublist = create1(s);}else if(ch == '#' ) delete g ; g = NULL; //空表else{// 是一个原子g->tag = 0;g->data = ch;}}else  delete g ; g = NULL;//结束遍历//以下为处理兄弟的部分ch = * s++;//取下一个字符if(g!=NULL){if(ch == ','){g->link = create1(s);}else{g->link = NULL;}}return g;
}

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