tree.c

可以在嵌入式应用中

#include <CsAgb.h>
#define math_total 32
#define str_total 16
#define key_total 61
extern u8 rb_xp,rb_yp;
extern struct tre_node *rb_int;
extern struct tre_node *rb_str;
extern struct tre_node *rb_float;
extern struct tre_node *rb_key;
extern struct tre_node *rb_int_dim;
extern struct tre_node *rb_str_dim;
extern struct tre_node *rb_float_dim;//数组变量树
extern struct tre_node *rb_math_key;//标准数学函数
extern struct tre_node *rb_str_key;//标准字符函数
const char rb_math_std[32][10]={
"SIN","COS","TAN","LOG","LN","POW","EXP","SQR","ABS","SGN",//10
"INT","ARCSIN","ARCCOS","ARCTAN","SINH","COSH","TANH","RND","TIME",//19
"PEEK","CSRLIN","POS","GETBG","GETCOR","GETPET","GETKEY",//26
"LEN","VAL","INSTR","ASC","CMP","CALCU"//32
};//数字标准函数
const char rb_str_std[16][10]={
"STR$","LEFT$","RIGHT$","MID$","CHR$","STRING$","REVERSE$",//7
"LOWSTR$","UPSTR$","REPLACE$","COVER$","CVSTR$","NOBLANK$",//13
"TROP$","STRMV$","INKEY$"//16
};//标准字符串处理函数
const char rb_key_std[59][10]={
"LET","PRINT","INPUT","TAB","READ","DATA",//6
"RESTORE","END","STOP","REM","IF","THEN","ELSE","GOTO","ON",//15
"FOR","NEXT","STEP","WHILE","WEND","BREAK","DEF","DIM","CLS",//24
"LOCATE","COLOR","SCREEN","DRAW","LINE","BOX","CIRCLE",//31
"WRITE","OPEN","CLOSE","GET","CALL","POKE","BEEP","PLAY",//39
"GOSUB","RET",//41
"WAIT","LOAD","SAVE","LIST","EDIT","CONT","SYSTEM","NEW",//49
"SVSCR","LDSCR","EXEC","SWAP","SQRT","AVER","MAX","MIN","VAR",//58
"AND","OR","NOT"//61
};//命令或语句关健词

struct tre_child //结点子树
{
	struct tre_node *first; //结点首子树
	struct tre_child *next; //其它子树
};

struct tre_node //树结点
{
	char name; //结点名
	struct tre_child *ch;//结点子树
};

struct tre_node * new_tre(char name)//创建新树
{
	struct tre_node *tre=(struct tre_node *)malloc(sizeof(struct tre_node));
	tre->name=name;
	tre->ch=NULL;
	return tre;
}

struct tre_node * ins_node(struct tre_node *tre,char name)//插入结点
{
	struct tre_child *ntre;
	if (tre->ch==NULL)//树无子树
	{
		tre->ch=(struct tre_child *)malloc(sizeof(struct tre_child));
		(tre->ch)->first=new_tre(name);
		(tre->ch)->next=NULL;
		return (tre->ch)->first;
	}
	else
	{
		ntre=tre->ch;
		while (ntre->next!=NULL)
		{
			if ((ntre->first)->name==name) return ntre->first;//结点已经存在
			ntre=ntre->next;
		}
		if ((ntre->first)->name==name) return ntre->first;//结点已经存在
		ntre->next=(struct tre_child *)malloc(sizeof(struct tre_child));
		ntre=ntre->next;
		ntre->next=NULL;
		ntre->first=new_tre(name);
		return ntre->first;
	}
}
struct tre_node * ins_word(struct tre_node *tre,char *word)//将单词从根结点处插入树中
{
	u8 i=0;
	struct tre_node *loc=tre;
	while (*(word+i)!='\0')
	{
		loc=ins_node(loc,*(word+i));
		i++;
	}
	loc=ins_node(loc,'#');//置单词结束标记
	return loc;//返回最后插入的结点
}

struct tre_node * node_is_exists(struct tre_node *tre,char node)//结点是否存在
{
	struct tre_child *loc=tre->ch;
	if (loc==NULL) return NULL;
	while ((loc->first)->name!=node)
	{
		loc=loc->next;
		if (loc==NULL) return NULL;
	}
	return loc->first;
}

struct tre_node * word_is_exists(struct tre_node *tre,char *word) //单词是否存在
{
	struct tre_node *loc=tre;
	u8 i=0;
	if (loc==NULL) return 0;//树不存在
	while (*(word+i)!='\0')
	{
		loc=node_is_exists(loc,*(word+i));
		if (loc==NULL) return NULL;//不存在
		i++;
	}
	loc=node_is_exists(loc,'#');//检查是否有结束标志
	return loc;
}

void tre_destroy(struct tre_node *tre)//树销毁
{
	struct tre_child *loc,*temp;
	if (tre==NULL) return;
   //prtchar(RGB(30,0,30),tre->name);
	if (tre->ch!=NULL)//存在子树
	{
      loc=tre->ch;
      while(loc!=NULL)//删除所有子树
      {
         tre_destroy(loc->first);//销毁子树的子树
         temp=loc->next;
         free(loc);
         loc=temp;
      }
   }
   free(tre);
}

u8 is_keyword(struct tre_node *key,char *word)//是否为关键字
{
	struct tre_node *loc=word_is_exists(key,word);
	if (loc==NULL) return 0;
	return ((loc->ch)->first)->name;//返回关健字编号
}

void show_tre(struct tre_node *tre)
{
	struct tre_node *loc=(tre->ch)->first;
	while (loc!=NULL)
	{
		prtchar(RGB(15,20,25),loc->name);
		if (loc->ch==NULL) return;
		loc=(loc->ch)->first;
	}
}
void tree()
{
	u8 i;
	rb_key=new_tre('/');//创建树根(关健字)
	rb_math_key=new_tre('/');
	rb_str_key=new_tre('/');
	for (i=0;i<key_total;i++) ins_node(ins_word(rb_key,rb_key_std[i]),i+1);//构造关健字树
	for (i=0;i<math_total;i++) ins_node(ins_word(rb_math_key,rb_math_std[i]),i+1);//构造数学函数树
	for (i=0;i<str_total;i++) ins_node(ins_word(rb_str_key,rb_str_std[i]),i+1);//构造数学函数树
	rb_int=new_tre('/');
	rb_str=new_tre('/');
	rb_float=new_tre('/');
	rb_int_dim=new_tre('/');
	rb_str_dim=new_tre('/');
	rb_float_dim=new_tre('/');
}