glist.cpp

这是一个关于广义表问题的程序

#include<iostream>
#include<fstream>
using namespace std;
template <class T>
class List;
template<class T>
class Iterator;
template <class T>
class Node{
	friend List<T>;
    friend Iterator<T>;
	private:
		T data;
		Node<T> *next;
};
template <class T>
class List{
    friend Iterator<T>;
	private:
		Node<T>*frist;
	public:
		List(){frist=0;}
		~List();
		List<T>&Insert(int k,const T&x);
};
template<class T>
List<T>::~List()
{
	Node<T>*next;
	while(frist){
		next=frist->next;
		delete frist;
		frist=next;
	}
}
template<class T>
List<T>&List<T>::Insert(int k,const T&x)
{
	Node<T>*p=frist;
	for(int index=1;index<k&&p;index++)
		p=p->next;
	Node<T> *y=new Node<T>;
    y->data=x;
	if(k){
		y->next=p->next;
		p->next=y;}
	else{
		y->next=frist;
		frist=y;}
	return *this;
}
template<class T>
class Iterator{
		public:
		T*Init(const List<T>&c)
		{location=c.frist;
		if (location) return &location->data;
		return 0;}
		T*Next()
		{if(! location) return 0;
		location=location->next;
		if(location) return &location->data;
		return 0;}
	private:
		Node<T>*location;
};
void main()
{
	ifstream in ("input.txt");
	ofstream out ("output.txt");
	int n,i,x,m,j,num,sum=0,max=0;
	in>>n;
	List<int>*L;
	L=new List<int>[n+1];
	for(i=1;i<=n;i++)
	{
		in>>m;
		for(j=1;j<=m;j++)
		{
			in>>x;
			if(x<0)
			{
				num=-x;
				Iterator<int>p;
				int *q=p.Init(L[num]);
				while(q)
				{
					L[i].Insert(0,*q);
					q=p.Next();
				}
			}
			else
				L[i].Insert(0,x);
		}
	}
	Iterator<int>p;
	int *q=p.Init(L[n]);
	while(q)
	{
		max>(*q)?max:max=*q;
		sum=sum+(*q);
		q=p.Next();
	}
	out<<max<<endl;
	out<<sum<<endl;
}