listses.h

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

  #include"tools.h";
   //typedef  node * lists;
    struct    node
	       { node * tp ;
		boolean haveaddr;
		int x,y;
		int tag;
		/*case tag:0..1  of
		0:(data:char);
		1:(hp:lists)
		*/
		union
		  {
		  char data;
		  node * hp;
		  };
	      };
     typedef  node * lists;


	  struct lists_varnode
	     {char name;
	     lists data;
	     boolean have_card;
	     lists_varnode * next;
	     };
     typedef lists_varnode * lists_link;

	lists_link lists_variables_list=nil;
    const int  width=30;
    const int high=10;
    const int stepx=10;
    const int stepy=10;

     boolean   have_lists(char title);
     lists   name_to_lists(char title);
     char   lists_name(lists ls);
     lists_link  lists_info_ptr(lists ls);
     lists  head(lists ls);
     int   len(lists ls);
     lists   tail(lists ls);
     void  create_lists( lists& ls,char  title,unsigned char s[]);
     void  lists_to_str(lists ls,unsigned char  st[]);
     void    name_to_str(char title,unsigned char st[]);
     void  print_lists(char  title, lists ls);
     void  list_all_lists_from(int x0,int y0);
     void  list_all_lists();

     boolean   have_lists(char title)
	{lists_link p;
	 p=lists_variables_list;
	       while  ( (p!=nil)&&( p->name!=title) )
		      p=p->next;
	 boolean      have_lists=p!=nil;
	 return       have_lists;
	 }
     lists name_to_lists(char title)
      { lists_link p;
	 lists    name_to_lists=nil;
	  p=lists_variables_list;
	       while  ( (p!=nil)&& (p->name!=title)  )
		    p=p->next;
	   if(p!=nil&&p->name==title)
	      name_to_lists=p->data;
	   return   name_to_lists;
	 }

     char   lists_name(lists ls)
       {lists_link p;
	    p=lists_variables_list;
	       while ( (p!=nil)&& (p->data!=ls) )
		  p=p->next;
	     char  lists_name=p->name;
	 return lists_name;
       }

	lists_link  lists_info_ptr(lists ls)
	{ lists_link p;
	  p=lists_variables_list;
	       while  ( (p!=nil)&& (p->data!=ls) )
		  p=p->next;
	     lists_link  lists_info_ptr=p;
	     return      lists_info_ptr;
	     }

     void  new_lists(lists ls, char title)
	{ lists_link p;
	  p=lists_variables_list;
	  while ( (p!=nil)&&( p->name!=title)  )
	       p=p->next;
	  if (p!=nil)
	    p->data=ls;
	  else
	      {
	      p=new  lists_varnode;
	      p->data=ls;
	      p->name=title;
	      p->next=lists_variables_list;
	      lists_variables_list=p;
	      p->have_card=false;
	      }
	}
     lists head(lists ls)
       {  lists head;
	  if (ls->tag==0)
	     Error("This is an atom, connot find head ");
	  else if (ls->hp==nil)
		   Error("No head ");
	       else
		  head=ls->hp;
	 return head;
       }

     int  len(lists ls)
       { lists p;
	 int i;

	  if (ls->tag==0)
	    Error("This is not a lists, connot find length ");
	  else
	    {
	     p=ls->hp;
	     i=0;
	     while (p!=nil)
	      { i=i+1;
		p=p->tp;
	      }
	    int	len=i;
	    return len;
	    }
      }

     lists tail(lists ls)
      {lists p;
	lists tail;
	 if (ls->tag==0)
	   Error("This is an atom, connot find tail ");
	 else if (ls->hp==nil)
	   Error("Empty lists, No head and tail ");
	 else
	   {
	   p=new node;
	   p->tag=1;
	   p->tp=nil;
	   p->hp=ls->hp->tp;
	   tail=p;
	   }
     return  tail;
    }

    void  Getchar(char& c,string s,int& i)
	  {
	   while (i<strlen(s) && (s[i]==' '))
		    i=i+1;
		 if  (i<=strlen(s) )
			c=s[i];
		     else
			c=' ';
		 i=i+1;
	   }


     void create1( lists& ls,char& c, string s, int& i,int level)
	  {  Getchar(c,s,i); //{ ls:=nil;}
	    if (c==')')
	     if (level<1)
		   Error_exit("Error in string ");
		 else
		   ls=nil;
	    else if (c==',')
		create1(ls,c,s,i,level) ;
		 else if (c=='(')  //{ and (level>1)}
		     {
		      ls=new node;
		      ls->tag=1;
		      create1(ls->hp,c,s,i,level+1);
		      create1(ls->tp,c,s,i,level);
		      }
	    else if ( (c>='A'&&c<='Z')&& have_lists(c) )
		  {  ls=new node;
		      ls->tag=1;
		      ls->hp=name_to_lists(c)->hp;
		      create1(ls->tp,c,s,i,level);
		    }
		 else {
		       ls=new node;
		       ls->tag=0;
		       ls->data=c;
		       create1(ls->tp,c,s,i,level);
		      }
	   }

     void  create_lists(lists& ls,char title,string s)
      { Into_graph();
	char c;
	int   i=0;
	unsigned char s1[50]="";
	unsigned char s2[50]="";
	Ltrim(s,s1);
	Rtrim(s1,s2);
	strcpy(s,s2);

	 Getchar(c,s,i);
	   ls=new node;
	   ls->tag=1;
	   ls->tp=nil;
	   ls->hp=nil;
	  new_lists(ls,title);
	  if (c=='(')
	       create1(ls->hp,c,s,i,1);
	    else if ( (c>='A'&&c<='Z')&& have_lists(c) )
		   ls->hp=name_to_lists(c)->hp;
		 else
		     Error_exit("Error in string ");
	}

    void  print_lists_node(lists ls,unsigned char  s[])
	 {lists p;
	  int j;
	   if (ls->tag==0)
	     {
	     j=strlen(s);
	     s[j]=ls->data;
	     s[j+1]='\0';
	     }
	else
	       {
		j=strlen(s);
	       s[j]='(';
	       s[j+1]='\0';
		p=ls->hp;
	       while (p!=nil)
		   { print_lists_node(p,s);
		     if (p->tp!=nil)
			 {
			 j=strlen(s);
			 s[j]=',';
			 s[j+1]='\0';
			 }
			 p=p->tp;
		    }
		    j=strlen(s);
		    s[j]=')';
		    s[j+1]='\0';
	  }
     }

    void  lists_to_str(lists ls,unsigned char  st[])
       { print_lists_node(ls,st);
	 }

     void    name_to_str(char title,unsigned char st[])
       {
	 lists_to_str(name_to_lists(title),st);

	 }


     void  print_lists_node(lists ls)
	{lists p;
	  if (ls->tag==0 )
		 cout<<ls->data;
		else
		    { cout<<'(';
			p=ls->hp;
			 while( p!=nil)
				  { print_lists_node(p);
				  if (p->tp!=nil)
				    cout<<',';
				    p=p->tp;
				   }
				  cout<<')';
	     }
    }


     void  print_lists(char  title, lists ls)   ////
	{ cout<<' '<<title<<'=';
	 print_lists_node(ls);
	 }

     void  clear_line(int y)
      {int i;
       gotoxy(1,y);
       for (i=1;i<=80;i++)
	cout<<' ';
	}

     void list_all_lists_from(int x0,int y0)
       { lists_link p;
	  int y;
	  p=lists_variables_list;
	  y=y0;
	  while  (p!=nil)
	   { clear_line(y);
	    gotoxy(x0,y);
	    print_lists(p->name,p->data);
	    p=p->next;
	    y=y+1;
	  }
	  clear_line(y);
      }

     void  list_all_lists()
       {list_all_lists_from(1,1); }


	boolean check(string s)
	 {int dep,states;
	 boolean chk; //{states=front:  1=',' 0=not;}
	  dep=0;
	  states=0;
	  chk=true;
	 int i=0;
	 char c;
	 unsigned char s1[50]="";
	 unsigned char s2[50]="";
	 Ltrim(s,s1);
	 Rtrim(s1,s2);
	 strcpy(s,s2);
	 while (i<strlen(s))
		   { Getchar(c,s,i);
			 if (c=='(')
			      dep++;
			   else if (c==')')
				  dep--;
			    else if (c==',')
			     states=1;
		   }
	  }


	  void  comput1(lists ls,int  x0,int y0)//   {count}
	   { if (ls!=nil)
		 {}
	   }

		void  comput2(lists ls,int gx,int gy)//   {graph x,y}
	   {
	    }


      void  comput_lists_card_from(lists ls,int  gx,int gy)
	 {lists_link p;
	    comput1(ls,1,1);
	    comput2(ls,gx,gy);
	    p=lists_info_ptr(ls);
	    if (p!=nil)
		p->have_card=true;
	 }


  /*    main()
      {
      lists la,lb,lc,ld,le;
      char ch;
      unsigned char s[50]="";
	// {***main***}
	Into_graph();
	 create_lists(la,'A',"((a,b,c),d,(e,f,g))");
	 print_lists('A',la);
	 cout<<endl;
	 getch();
	 lists_to_str(la,s);
	 cout<<s<<endl;
	 strcpy(s,"");
	 name_to_str('A',s);
	 cout<<s<<endl;
	 create_lists(lb,'B',"(((a,b,c)),d,(e,f,g))");
	 print_lists_node(lb);
	 cout<<endl;
	 getch();
	 create_lists(lc,'C',"(a,b,c)");
	 print_lists('C',lc);
	 cout<<endl;
	 getch();
	 create_lists(ld,'D',"(())");
	 print_lists_node(ld);
	 cout<<endl;
	 getch();
	 create_lists(le,'E',"(A,B,C,D)");
	 print_lists('E',le);
	 cout<<endl;
	 getch();
	 print_lists_node(head(head(tail(tail(la)))) );
	 list_all_lists();
	 getch();
	 cout<<"length(A)="<<len(la);
	 getch();
      }
 */