数据结构第五章(三元组十子链表)

#include
using namespace std;
enum TagField{ELEMENT,HEAD};
template

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

 

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

 

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

 

/////////////////////////////////////////////////////////////
//从键盘输入三元组
/////////////////////////////////////////////////////////////
template
istream& operator >> (istream& in,LinkTriple& x)
{
Entry s;
int max;
cout<<"Rows Cols NonZeros"<in>>s.row>>s.col>>s.value;
max=s.row>s.col? s.row:s.col;       //行头结点和列头结点采用一个结构体
x.head=new EntryNode(ELEMENT,s); //头结点保存总行数，列数与非零元个数
if(!max)
{
x.head->right=x.head;
return in;
}
EntryNode **hd=new EntryNode*[max]; //申请头结点空间
for(int i=0;ihd[i]=new EntryNode(HEAD,s);
int currentRow=0;
EntryNode* last=hd[0];        
cout<<"row col value"<for(int i=0;i{
Entry 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(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;inext->down=hd[i]; //使列链表循环链
for(int i=0;inext=hd[i+1];     //使头结点形成循环链
hd[max-1]->next=x.head;                         //总头结点指向第一个头结点
x.head->right=hd[0];
delete []hd;
return in;
}

 

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