#include <iostream.h>
                #include <stdio.h>

		enum Boolean { False, True };
		struct Triple { int row, col;  float value; };					//三元組類的定義
		class Matrix;										//稀疏矩陣類的前視聲明

		class MatrixNode {									//矩陣結點類的定義
		friend class Matrix;
		friend istream & operator >> ( istream &, Matrix & );			//矩陣讀入
                friend ostream & operator << ( ostream &, Matrix & );
		private:
		   MatrixNode *down, *right;							//列/行鏈表指針
		   Boolean head;									//結點類型
		   union { Triple triple;  MatrixNode *next; };				//無名聯合
		   MatrixNode ( Boolean, Triple* );						//構造函數
		};

		MatrixNode::MatrixNode ( Boolean b, Triple *t ){				//構造函數
		   head = b;									//結點類型
		   if ( b ) { right = next = this; }						//各行/列鏈表的表頭結點
		   else triple = *t;									//頭結點鏈表的表頭或非零元素結點
		}
		typedef MatrixNode *MatrixNodePtr;						//一個指針數組

		class Matrix {									//稀疏矩陣的類定義
		friend istream & operator >> ( istream &, Matrix & );
                friend ostream & operator << ( ostream &, Matrix & );
		public:
		   ~Matrix ( );									//析構函數
		private:
		   MatrixNode *headnode; 							//稀疏矩陣的表頭
		};


		istream & operator >> ( istream & is, Matrix & matrix )	//讀入稀疏矩陣, 建立它的鏈表表示
		{
		   Triple s;  int p;
		   is >> s.row >> s.col >> s.value; 						//讀入矩陣行數、列數和非零元素個數
		   if ( s.row > s.col ) p = s.row;						//確定行/列鏈表表頭結點個數p
		   else p = s.col;									// p = max { s.row, s.col }
		   matrix.headnode = new MatrixNode ( False, &s );				//創建表的表頭結點
		   if ( !p ) { matrix.headnode->right = matrix.headnode;  return is; }	//至少一行或一列
		   MatrixNodePtr *H = new MatrixNodePtr [ p ];				//初始化表頭指針數組，指向各鏈表頭
		   for ( int i=0; i<p; i++ ) H[i] = new MatrixNode ( True, 0 );		//指向各鏈表頭結點
		   int CurrentRow = 0;
		   MatrixNode *last = H[0];							//last為當前行的最后結點指針
		   for ( i=0; i<s.value; i++ ) {							//輸入三元組, s.value給出三元組個數
			 Triple t;
		 is >> t.row >> t.col >> t.value;					//輸入三元組
			 if ( t.row > CurrentRow ) {						//行號大于當前行號，閉合當前行
			    last->right = H[CurrentRow];					//在行的方向向表頭結點拉鏈
			    CurrentRow = t.row;  last = H[CurrentRow];			//當前行改變為新的一行
			 }
			 last = last->right = new MatrixNode ( False, &t );			//新結點鏈入行鏈表，last跟上
			 H[t.col]->next = H[t.col]->next->down = last;			//鏈入列鏈表，next記下該結點地址
		   }
		   last->right = H[CurrentRow];						//閉合最后一行
		   for ( i=0; i<s.col; i++ ) H[i]->next->down = H[i];			//閉合所有列鏈表
		   for ( i=0; i<p-1; i++ ) H[i]->next = H[i+1];				//所有表頭結點鏈接在一起
		   H[p-1]->next = matrix.headnode;  matrix.headnode->right = H[0];
		   delete [ ] H;
		   return is;
		}


	      /*	if ( first != NULL ) {								//鏈表不空
		   CircListNode<Type> *second = first->link;			//循環鏈表的第二個結點
		   first->link = av;    av = second;					//第一個結點鏈接到av
		   first = NULL;
		}


		if ( av == NULL ) newnode = new CircListNode<Type>;	//可利用空間表為空，動態分配
		else { newnode = av;  av = av->link; }				//不空，從可利用空間表分配
		*/
                MatrixNode *av;

		Matrix::~Matrix ( ) {
		//將所有結點回收到可利用空間表中, 這個表是用right域鏈接的。av是一個具有MatrixNode*
		//類型的全局變量, 且指向它的前端第一個結點。
		   if ( headnode == NULL ) return;					//空鏈表, 無法回收
		   MatrixNode *x = headnode->right, *y;
		   headnode->right = av;  av = headnode;				//回收表頭結點的循環鏈表
		   while ( x != headnode ) {						//按行回收各行的循環鏈表
		      y = x->right;  x->right = av;  av = y;			//回收行 (循環) 鏈表
		      x = x->next;							//下一行
		   }
		   headnode = NULL;
		}

		ostream & operator << ( ostream & os, Matrix & matrix )
		{
		    MatrixNode *current = matrix.headnode , *temp;
		    cout << "row:  " << current->triple.row << endl;
		    cout << "column: " << current->triple.col << endl;
		    cout << "nonzero: " << current->triple.value << endl;
		    cout << "order in column:" << endl;
		    temp = current = current->right;
		    for (int column = 0 ; column < matrix.headnode->triple.col; column++) {
			cout << "column " << column << " : " ;
			temp = temp->down ;
			while ( temp != current ) {
			    cout << "(" << temp->triple.row << ",";
			    cout << temp->triple.col << ",";
			    cout << temp->triple.value << ") ";
			    temp = temp->down;
			};
			cout << endl;
			temp = current = current->next;
		    }

		    cout << "order in row:" << endl;
		    temp = current = current->right;
		    for (int row = 0; row < matrix.headnode->triple.row; row++) {
			cout << "row " << row << " : " ;
			temp = temp->right ;
			while ( temp != current ) {
			    cout << "(" << temp->triple.row << ",";
			    cout << temp->triple.col << ",";
			    cout << temp->triple.value << ") ";
			    temp = temp->right;
			};
			cout << endl;
			temp = current = current->next;
		    }


		    return os;
		}