glist.cpp

来自「这是一个关于广义表问题的程序」· C++ 代码 · 共 116 行

#include<iostream>
#include<fstream>
#define Max 50
using namespace std;
template<class T>
class Node{
	  public:
	     T data;
		 Node<T> *next;
};
template<class T>
class Queue{
		 public:
			 Queue(){front=rear=0;}
			 ~Queue();
			 bool Empty()const
			 { return ((front)?false:true);}
			 bool Full()const;
		     T First()const;
			 T Last()const;
			 Queue<T>& EnQueue(const T& x);
			 Queue<T>& DeQueue(T& x);
		 private:
			 Node<T> *front;
			 Node<T> *rear;
};
template<class T>
Queue<T>::~Queue()
{        Node<T> *next;
          while(front) {
		  next=front->next;
		  delete front;
		  front=next;
	  }
}
template<class T>
bool Queue<T>::Full()const
{
	  Node<T> *p;
	  try{ p=new Node<T>;
	  delete p;
	  return false;}
	  catch(NoMem){ return true;}
}
template<class T>
T Queue<T>::First()const
{    if(Empty()) return 0;
      return  front->data;
}
template<class T>
T Queue<T>::Last()const
{     if(Empty()) return 0;      
       else return rear->data;
}
template<class T>
Queue<T>& Queue<T>::EnQueue(const T& x)
{     Node<T> *p=new Node<T>;
      p->data=x;
	  p->next=0;
	  if(front)  
	  rear->next=p;
	  else front=p;
	  rear=p;
	  return *this;
}
template<class T>
Queue<T>& Queue<T>::DeQueue(T& x)
{
	 if(Empty()) throw 0;
     x=front->data;
	 Node<T> *p=front;
	 front=front->next;
	 delete p;
	 return *this;
}
//主函数
int main()
{
	 ifstream in("input.txt");
	 ofstream out("output.txt");
	 int n,m,i,j,p,count=0,sum[Max],max,x,k;
	 Queue<int> q;
     max=-1;
	 sum[0]=0;
	 in>>n;
	 for(i=0;i<n-1;i++)
     {
		 in>>m;
		 p=0;
		 for(j=0;j<m;j++)
         {  in>>x;
		     if(x>max)  max=x;
             if(x<0)    p+=sum[-x];
			 else p+=x;
		 }
		 sum[i+1] = p;
	 }
	 
		 in>>m;
	 for(j=0;j<m;j++)
	 {  in>>x; 
	    if(x>max)  max=x;
	    q.EnQueue(x);
	 }
	 for(i=0;i<m;i++)
	 {	 q.DeQueue(k);
	     if(k>=0)
			 count+=k;
		 else count+=sum[-k];
	 }
	 out<<max<<endl;
	 out<<count<<endl;
     return 0;
}