czm1324.cpp

广义表的创建以及相关操作。

#include "stdio.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0
typedef int tagtype;
typedef char atomtype;
typedef struct gl_node
{
	tagtype tag;
	union 
	{
		atomtype atom;
		struct gl_node *hp;
	} uval;
	struct gl_node *tp;
}glists;

glists *create_grlist()
{
	glists *gh;
	char ch;

	scanf("%c",&ch);
	if (ch!=' ')
	{
		gh=(glists *)malloc(sizeof(glists));
		if (ch=='(')
		{
			gh->tag=1;
			gh->uval.hp=create_grlist();
		}
		else
		{
			gh->tag=0;
			gh->uval.atom=ch;
		}
	}
	else 
		gh=NULL;
	scanf("%c",&ch);
if (gh!=NULL)
{
	if (ch==',')
		gh->tp=create_grlist();
	else 
		gh->tp=NULL;
}
return(gh);
}


void print_grlist(glists *p)
{
	if(p!=NULL)
	{
		if (p->tag==1)
		{
			printf("(");
			if (p->uval.hp==NULL)

				printf(" ");
			else 
				print_grlist(p->uval.hp);
		}
		else 
			printf("%c",p->uval.atom);
		if (p->tag==1)
			printf(")");
		if (p->tp!=NULL)
		{
			printf(",");
			print_grlist(p->tp);
		}
	}
	else printf("空广义表");
}


	int depth_grlist(glists *p)
	{
		int h,maxh;
		glists *q;
		if(p==NULL)return 1;
		else  if(p->tag && !p->uval.hp) return 1;
				
			for  (maxh=0,q=p->uval.hp; q; q=q->tp)
			{
              if (q->tag==0)  h=0;
			    else h=depth_grlist(q);
				if (h>maxh) maxh=h;
               

			}
			return (maxh+1);
		
	}


	int locate_grlist(glists *g, char x)
	{   
		char y=x;
	
		int found=0;
		if (g!=NULL)
		{
			if (g->tag==0 && g->uval.atom==y)
				return(1);
			else if (g->tag==1)
				found=locate_grlist(g->uval.hp,y);
			if (found)
				return(1);
			else
				return(locate_grlist(g->tp,y));
		}
		else
			return(0);
	}




 void   main()
	{
		int h1;
		char x;

		glists *g1;
		g1=create_grlist();
		printf("General list 1 is the following:\n");
		print_grlist(g1);
		h1=depth_grlist(g1);
		printf("\nThe depth of g1 is  %d\n",h1);
		printf("Input the character that you want to search:\n");
		scanf("%c",&x);
		if (locate_grlist(g1,x))
			printf("The character you input is in g1. \n");
		else 
			printf("There is no such character in g1. \n");
	
	    
	}