#include <iostream>
using namespace std;
enum TagField{ELEMENT,HEAD};
template <class T>

/////////////////////////////////////////////////////////////
//三元组结构体
/////////////////////////////////////////////////////////////
struct Entry
{
 int row,col;
 T value;
};

 

/////////////////////////////////////////////////////////////
//十字链表结点结构体
/////////////////////////////////////////////////////////////
template <class T>
struct EntryNode
{
 EntryNode<T> *down,*right;
 TagField tag;
 union
 {
  Entry<T> element;
  EntryNode<T>* next;
 };
 EntryNode(TagField tf,Entry<T>& x);
};
template <class T>
EntryNode<T>::EntryNode(TagField tf,Entry<T>& x)
{
tag=tf;
if(tf)
down=right=next=this;
else
element=x;
}

 

/////////////////////////////////////////////////////////////
//十字链表类
/////////////////////////////////////////////////////////////
template <class T>
class LinkTriple
{
public:
 ~LinkTriple()
 {
  delete head;
 }
private:
 EntryNode<T> *head;
 friend istream& operator >> <>(istream&,LinkTriple<T>&);
 friend ostream& operator << <>(ostream&,LinkTriple<T>&);
};

 

/////////////////////////////////////////////////////////////
//从键盘输入三元组
/////////////////////////////////////////////////////////////
template <class T>
istream& operator >> (istream& in,LinkTriple<T>& x)
{
Entry<T> s;
int max;
cout<<"Rows Cols NonZeros"<<endl;
in>>s.row>>s.col>>s.value;
max=s.row>s.col? s.row:s.col;       //行头结点和列头结点采用一个结构体
x.head=new EntryNode<T>(ELEMENT,s); //头结点保存总行数，列数与非零元个数
if(!max)
{
x.head->right=x.head;
return in;
}
EntryNode<T> **hd=new EntryNode<T>*[max]; //申请头结点空间
for(int i=0;i<max;i++)
hd[i]=new EntryNode<T>(HEAD,s);
int currentRow=0;
EntryNode<T>* last=hd[0];        
cout<<"row col value"<<endl;
for(int i=0;i<s.value;i++)
{
Entry<T> x;
in>>x.row>>x.col>>x.value;
if(x.row>currentRow)
{
 last->right=hd[currentRow];  //如果当前行结束，当前行最后一个元素指针回指行头，构成循环。
 currentRow=x.row;
 last=hd[currentRow];
   
}
last->right=new EntryNode<T>(ELEMENT,x);  //插入新的三元组
last=last->right;                         //last指向行中最后插入的元素
hd[x.col]->next->down=last;               //hd[x.col]->next指向列最后插入的元素
hd[x.col]->next=last;                
}
last->right=hd[currentRow];
for(int i=0;i<max;i++) hd[i]->next->down=hd[i]; //使列链表循环链
for(int i=0;i<max;i++) hd[i]->next=hd[i+1];     //使头结点形成循环链
hd[max-1]->next=x.head;                         //总头结点指向第一个头结点
x.head->right=hd[0];
delete []hd;
return in;
}

 

/////////////////////////////////////////////////////////////
//输出十字链表元素
/////////////////////////////////////////////////////////////
template <class T>
ostream& operator << (ostream& out,LinkTriple<T>& x)
{
Entry<T> s=x.head->element;
out << "Rows=" << s.row << ",Cols="<<s.col <<",NonZeros="<<s.value<<endl;
out<<"the LinkTriple contains:"<<endl;
EntryNode<T> *line,*current;
for(line=x.head->right;line!=x.head;line=line->next)
for(current=line->right;current!=line;current=current->right)
out<<current->element.row<<","<<current->element.col<<","<<current->element.value<<endl;
return out;
}
int main()
{
LinkTriple<int> x;
cin>>x;
cout<<x;
system("pause");
return 0;
}