genlist.h

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

#ifndef GENLIST_H
#define GENLIST_H

#include <stdlib.h>

const int HEAD = 0;
const int INTGR = 1;
const int CH = 2;
const int LST = 3;

class GenList;	 //GenList类的前视声明

class GenListNode ;		//广义表结点类的前视声明

union Values{ 	             //联合       
	friend class GenlistNode;
	friend class Genlist;
    int ref;              //utype=0, 存放引用计数
    int intinfo;	         //utype=1, 存放整数值
    char charinfo;        //utype =2, 存放字符
    GenListNode *hlink;	 //utype =3, 存放指向子表的指针
};
struct Items {     //仅有结点信息的项
	friend class GenlistNode;
	friend class Genlist;
    int utype;	    //＝0 / 1 / 2 / 3
    union Values value;
};
	
class GenListNode {
	friend class GenList;
public:
	GenListNode ( ) : utype (0), tlink (NULL) { value.ref=0; }	    //构造函数, 建表头结点
	GenListNode ( int t, GenListNode *next = NULL ) { }	       //构造函数：建表结点
    Items& Info ( );    //返回表元素elem的值
    int nodetype ( ) { return utype; }	//返回表元素elem的数据类型
    void setInfo ( Items& x ); //将表元素中的值修改为x
private:
	int utype;
	GenListNode *tlink;
	union Values value;
};

class GenList {
public:
	GenList ( );              //构造函数
    ~GenList ( );		//析构函数 
    GenListNode& Head ( );  //返回表头元素
    GenList& Tail ( );		 //返回表尾
    GenListNode *First ( );	 //返回第一个元素
	GenListNode * Next ( GenListNode *elem );	         //返回表元素elem的直接后继元素
    void setNext ( GenListNode *elem1, GenListNode *elem2 ); //将elem2插到表中元素elem1后    
	void Copy ( const GenList & l );
 	 	  	//广义表的复制
    int depth ( ); 	//计算一个非递归表的深度
    int CreateList ( GenListNode *ls, char * s );	//从广义表的字符串描述 s 出发,建立一个带表头结点的广义表结构
//   void delvalue(GenListNode *,const int);
    int sever(char *,char *);
 //   friend int operator == (const GenList &,const GenList &);
 //   void print();
private:
    GenListNode *first;    //广义表头指针
    GenListNode *Copy ( GenListNode *ls );		  //复制一个 ls 指示的无共享非递归表
    int depth ( GenListNode *ls );			 	  //计算由 ls 指示的非递归表的深度
    int equal (GenListNode *s, GenListNode *t);	  //比较以s和t为表头的两个表是否相等
    void Remove (GenListNode *ls );		 	  //释放以 ls 为表头结点的广义表

};

#endif  // GENLIST_H