class.cpp

给定m个n维向量a , a , ,am 1 2 &#61516

#include<iostream.h>
#include<fstream.h>

template <class T>
class  Forest;

template <class T>
class  TreeNode { //树结点定义
  friend   Forest<T>;
  private:
	T  data;    
	TreeNode<T> *fc; //指向第一个子结点
	TreeNode<T> *rl; //指向右邻兄弟
};

template <class T>
class  Forest { //将森林中各棵树的根看成兄弟
 private:
	 TreeNode<T>  *root; //指向森林中第一棵树的根
 public:
	 Forest() {  root=0; } //构造函数中将森林初始化为空
	 
	 void  Insert(ifstream&  in,int n,int& count) { /*输入一个长度为n的向量,并将
		该向量作为一棵子树插入森林中的适当位置 */
	   T  x;
	   TreeNode<T> *p=root,*q,*prev,*r; 
	   for ( int i=0; i<n; i++) {
		   in>>x; //输入向量中的一个数字
		   for (q=p,prev=0; q; prev=q,q=q->rl) /*p总是指向树的第i+1层中由兄弟结点所构成链表的链头。
			 p的初始值为root,即指向森林中各棵树的根结点所构成的链表（森林中各棵树的根看作兄弟）*/
		   /*指针q在p所指向的链表中遍历，prev总指向q所指结点的前一结点*/
			  if (q->data==x)  break;  
			  /*向量的第i+1个数字在第i+1层已找到，不需要为该数字创建新结点*/
			  if (q==0) {	//找到了向量对应子树的插入位置，该子树的根插入作为prev所指结点的兄弟结点*/	
		    count++;  //该向量是一个新向量，令count加1
		    r=new TreeNode<T>;  //为该数字创建新结点
			r->data=x;  r->fc=0; r->rl=0;  
			
			if (prev)  prev->rl=r;
			//将该结点插入p所指向的链表的链尾，此时链尾结点由prev指向
			if (p==root && !prev)  root=r;
			//若该结点插入前森林为空，即输入的向量是第一个向量，令root指向新结点*/
            break;  
			/*跳出循环执构造一棵由新结点为根，其余数字构成的单支树，即该向量对应的子树*/
			  }
			  else 
                 p=q->fc; //p指向树的下一层，转向执行for循环输入向量的下一个数字
	   }
       
	   i++;  
	   if (i>=n)  return;
	   prev=r;
	   for (; i<n; i++) { //将向量的其余数字组成一棵单支树
		  in>>x;
		  r=new TreeNode<T>;
		  r->data=x;   r->rl=0;
		  prev->fc=r;
		  prev=r;
	   }
	    r->fc=0; 
	 }
};
void  main() {
  ifstream  in("input.txt");
  ofstream  out("output.txt");
  int count=0;
  int n,m;
   in>>m>>n;
  Forest<int>  f;
  
  for (int i=1; i<=m; i++)
	  
	  f.Insert(in,n,count);
  
  out<<count<<endl;
}