如图所示,广义表的每一个结点相互串联,有些结点存储原子数据,有些结点则存储另一份广义表数据,我们创建数据string ss = "(2,3,4, (1, (3, ( 7,8 ) ),2) )";其基本可以分成4层,每一个层中一个括号表示下一层,在数学表示中,我们也常用括号的级数表示广义表。
因此,广义表的创建就需要进行连接,连接的方法是更具tag进行判断本结点中是Atom(原子)还是Node(结点),再根据其中的选择进行相对应的连接,可以由如下图可知。
对于代码的书写,我们首先需要对传入的字符串进行切割,将每一组括号”()”进行分割,每一组括号其中就表示的一份新的广义表,我们需要找到括号并且与这个括号相互匹配的括号数进行对应,找到并切割掉,以此分离出表头串,方便我们进行后续的操作。
void sever(string &str,string &hstr){ //将非空串str分割成两部分,hstr是表头 int n = str.size(); int i = -1; int k = 0; //k记录尚未配对的“(” 数 char ch; do{ //搜索最外层第一个( ++i; ch = str[i]; if(ch == '(') ++k; else if(ch == ')') --k; }while(i<n&&(ch != ','||k!=0)); if(i<n){ hstr =str.substr(0,i); str = str.substr(i+1,n-i-1); }else{ hstr = str.substr(0,str.size()); str.clear(); } }
我们通过分割以后可以通过上文介绍的方法进行指针的相互指引,核心就是要注意tag的判断,以及Atom/Node域是使用共用体创建的,要注意两者的空间不可以重叠,严格使用if(){}else{}的语法结构不要乱套。
void CreateGList(GList &L,string s){ //采用头尾链表存储结构,创建L if(s.compare(emp) == 0) L = NULL; else{ L = (GList)malloc(sizeof(GLNode)); if(!L) exit(0); if(s.size() == 1){ //单个元素,建立原子节点 L->tag = ATOM; L->atom = s[0]; }else{ //表节点 ,表尾 L->tag = LIST; GList p,q; p = L; //p是指向当前子表(表尾节点)的指针 string sub; sub = s.substr(1,s.size()-2); //去掉外层括号 string hsub; do{ //重复建立n个子表 sever(sub,hsub); //sub中分理出表头串hsub ,同时,sub去除了hsub CreateGList(p->ptr.hp,hsub); q = p; //记录p,下面sub不为空,要再建立一个表尾节点,q记录上一层的p,用以连接q->ptr.tp = q if(!sub.empty()) { p = (GList)malloc(sizeof(GLNode)); if(!p)exit(0); p -> tag = LIST; q -> ptr.tp = p; } }while(!sub.empty()); q -> ptr.tp = NULL; } } }
我们只需要根据表的情况进行一个递归调用即可判断,当然需要特判一下空表的情况。
int GListDepth(GList L) { if(!L) return 1; //空表1 if(L->tag ==ATOM ) return 0; GList pp; //遍历同一层,递归下一层,取表尾,取表头,第一步先去一个表头 int max; for(max = 0, pp =L;pp!=NULL;pp = pp->ptr.tp){ int dep = GListDepth(pp->ptr.hp) ; if(dep > max) max = dep; //这一步比较,是比较同一层的depth } return max+1; }
本文固定URL:https://www.dotcpp.com/course/133
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程