数组与广义表.ppt

广义表的存储举例．对于前面所给的广义表A、B、C、D、E、F，孩子兄弟表示法如下图所示。D＝（A，B，C）=(（），（e），（a，（b，c，d））)第69页,共82页，星期六，2024年，5月5．4．3广义表的基本操作算法算法思想：假设广义表以串S的形式给出，当广义表为空时，即S=()，此时直接返回L=NULL。当广义表为不空时，S=(a1,a2,…,an)，其中ai(i=1,2,…,n)为S的子串表示的子表。建立广义表S就是建立n个子表结点拉成的链表。第i个（1≤i≤n）表结点的tp指针指向第i+1个表结点，第n个表结点的tp指针为NULL。第i个表结点的hp指针指向由ai建立的子表。由此可见，建立广义表S转化为建立子表ai（1≤i≤n）的问题。而建立子表ai（1≤i≤n）的过程与建立广义表S的过程完全相同，这显然是一个递归问题。对每个ai又分三种情况：（1）ai是带括号的空串；（2）ai是长度为1的单字符串；（3）ai是长度大于1的字符串。前两种情况就是递归的终结状态，第三种情况是递归调用。第70页,共82页，星期六，2024年，5月广义表的基本操作算法递归过程如下：基本项：置空广义表，当S为空表串时；建立原子结点子表，当S为单字符串时；归纳项：假定S=(a1,a2,…,an)，sub=’s1,s2,…,sn’是S脱去的最外层括号之后的字符串，其中si(i=1,2,…,n)是非空的字符串，对每个si建立一个表结点，结点的hp指针域指向由si建立的子表，tp指针指向由si+1（in）建立的表结点，最后一个表结点的tp指针为NULL。第71页,共82页，星期六，2024年，5月广义表的基本操作算法算法描述：statusCreateGLint(GListL,SStringS){if(StrEmpty(S))L=NULL;//创建空表else{if(!(L=(GList)malloc(sizeof(GLNode))))exit(OVERFLOW);//建表结点if(StrLength(S)==1){L-tag=ATOM;L-atom=S;}//创建原子结点else{L-tag=LIST;p=L;//重复建立n个子表SubString(sub,S,2,StrLength(S)-2);//脱去外层括号do{sever(sub,hsub);//从sub中分离出表头串CreateGList(p-ptr.hp,hsub);q=p;if(!StrEmpty(sub))//表尾不空{if(!(p=(GList)malloc(sizeof(GLNode))))exit(OVERFLOW);p-tag=LIST;q-ptr.tp=p;}}while(!StrEmpty(sub));q-ptr.tp=NULL;}}returnOK;}第72页,共82页，星期六，2024年，5月广义表的基本操作算法statussever(SStringstr,SStringhstr){n=StrLength(str);i=1;k=0;for(i=1,k=0;i=n||k!=0;++i){ch=SubStr(ch,str,i,1);if(ch==()++k;elseif(ch==))--k;}if(i=n){hstr=SubStr(hstr,str,1,i-2);str=SubStr(str,str,i,n-i