genlist.cpp

数据结构中 广义表的建立几基本操作 可比较两表是否相等 计算非递归表的深度

#include "genlist.h"
#include <iostream.h>
#include <string.h>

Items& GenListNode :: Info ( ) {
//返回表元素的值
    Items pitem;
    pitem.utype = utype;
    pitem.value = value;
    return pitem;
}
void  GenListNode :: setInfo ( Items& x ) {
//修改表元素的值为 x
    utype = x.utype;
    value = x.value; 
}

GenList :: GenList ( ) {      //构造函数
    first = new GenListNode( );
    first->utype = 0;  
	first->value.ref = 0;  
    first->tlink = NULL;
}
GenListNode& GenList :: Head ( ) {
//若广义表非空，则返回其第一个元素的值，否则函数没有定义。
    if ( first->tlink == NULL ) {
		cout<<"Illegal head operation."<<endl;
		exit(1);
	}
    else {			           //非空表
       GenListNode temp;
       temp.utype = first->tlink->utype;
       temp.value = first->tlink->value;
       return temp;  	           //返回类型及值
    }
}
GenList& GenList :: Tail ( ) {
//若广义表非空，则返回广义表除第一个元素外其它元素组成的表, 否则函数没有定义
    if ( first->tlink == NULL ){
		cout<<"Illegal tail operation."<<endl;
		exit(1);
    }
    GenList temp; 
    temp.first = Copy ( first );
    return temp; 
}
GenListNode * GenList :: 
First ( ) {
    if ( first->tlink == NULL ) return NULL;
    else return first->tlink;
}

GenListNode * GenList :: 
Next ( GenListNode *elem ) {
    if ( elem->tlink == NULL ) return NULL;
    else return elem->tlink;
}
void GenList :: Copy ( const GenList& ls ) {
    first = Copy ( ls.first );	//共有函数
}

GenListNode* GenList :: Copy ( GenListNode* ls ) {				//私有函数 
    GenListNode *q = NULL;
    if ( ls != NULL ) {
    q = new GenListNode ( ls->utype, NULL );
	switch ( ls->utype ) {			
        case 0: q->value.ref = ls->value.ref;  
            break;
        case 1: 
            q->value.intinfo = ls->value.intinfo;
            break; 	          
        case 2: 
            q->value.charinfo = ls->value.charinfo;
            break;		
        case 3: 
            q->value.hlink = Copy (ls->value.hlink);
      }
	q->tlink = Copy (ls->tlink);
    }
    return q;
}
int GenList :: depth ( GenListNode *ls ) {
    if ( ls->tlink == NULL ) return 1;	  //空表
    GenListNode * temp = ls->tlink;  int m = 0;
    while ( temp != NULL ) {    //在表顶层横扫
        if ( temp->utype == 3 ) {  //结点为表结点
           int n = depth ( temp->value.hlink );
           if ( m < n ) m = n;          //m记最大深度
        }
        temp = temp->tlink;
    }
    return m+1;
}
int GenList :: depth ( ) {				
    return depth ( first );
}

GenList :: ~GenList ( ) {	     //析构函数	
    Remove ( first );  delete (first);
}

void GenList :: Remove ( GenListNode *ls ) {
//私有函数：释放以 ls 为表头指针的广义表  
    ls->value.ref --;	        //引用计数减1
	if ( ls->value.ref <= 0 ) {	       //如果减到0
        GenListNode *p = ls, *q;   //横扫表顶层
        while ( p->tlink != NULL ) {
            q = p->tlink;	      	      //到第一个结点
            if ( q->utype == 3 )       //递归删除子表
                 Remove ( q->value.hlink );
            p->tlink = q->tlink;  delete q;
        }
    }
}
int GenList ::CreateList ( GenListNode *ls,  char * s ) {
    char *sub, *hsub; 
    ls = new GenListNode ( );    //建立表头结点
    ls->utype = HEAD;  ls->value.ref = 1;
    if ( strlen (s) == 0 || !strcmp ( s,"( )" ) )
        ls->tlink = NULL;	     //空表	
    else {
        strncpy ( sub, s+1, strlen (s)-2 );   //脱去广义表外面的引号      
		GenListNode* p = ls;
        while ( strlen (sub) != 0 ) {   //建立表结点
            p = p->tlink = new GenListNode ( );     //创建新结点,向表尾链接
            if ( sever ( sub, hsub ) ) {    //以逗号为界,分离第一个表元素hsub
                if ( hsub[0] != '(' && hsub[0] != '\0' ) {   //非子表,非字符分界符
                    p->utype = INTGR;   //转换整型结点
                    p->value.intinfo = atoi ( hsub );
                } 
                else             
				if ( hsub[0] != '(' && hsub[0] == '\0' ) {  //非子表且是字符分界符
					p->utype = CH;  
                    p->value.charinfo = hsub[1];		
                }
                else {              //是子表,递归建立子表
                    p->utype = LST; 
                    CreateList ( p->value.hlink, hsub );
                }
			}
            else return 0;     //字符串表达式有错
        }       //循环完成
		p->tlink = NULL;  //封闭最后一个结点
    }
    return 1;
} 

int GenList :: sever ( char *str1, char *hstr1 ) { //对不含外分界符的字符串分离第一个元素
    char ch = str1[0];   
    int n = strlen ( str1 );
    int i = 0,  k = 0;    //检测str1,扫描完或遇到', '且括号配对则停    
	while ( i < n && ( ch != ',' || k != 0 ) ) {
        if ( ch == '(' ) k++;
        else if ( ch == ')' ) k--;
        i++;  ch = str1[i];         // i 计数, 取一字符
    }
    if ( i < n ) {
        strncpy ( hstr1, str1, i-1 );    //str1的前 i-1 个字符传送到hstr1
        strncpy ( str1, str1+i, n-i );   //后n-i个字符留在str1, 滤去‘,’
        return 1;
    }    
	else if ( k != 0 ) return 0;   //括号不配对出错
           else {	                     //括号配对
               strcpy ( hstr1, str1 );  str1 = 0;
               //str1全部传送给hstr1
               return 1;
           }
}