好嘛那我就全部发上来,还有重载=和复制构造函数没有完全实现应为要用到GetValue
#include<iostream>
using namespace std;
//友元函数的前置声明
template<class Type>class LinkMatrix;
template<class Type>class MatrixNode;
template<class Type>istream &operator>>(istream &,LinkMatrix<Type> &);
template<class Type>ostream &operator<<(ostream &,const LinkMatrix<Type> &);
template<class Type> LinkMatrix<Type> operator+(const LinkMatrix<Type> &a,const LinkMatrix<Type>&b);
/**********************结点类****************************/
template<class Type>class MatrixNode{
friend class LinkMatrix<Type>;
friend istream& operator>><>(istream &,LinkMatrix<Type>&);
friend ostream& operator<<<>(ostream &,const LinkMatrix<Type>&);
friend LinkMatrix<Type>operator+<>(const LinkMatrix<Type>&a,const LinkMatrix<Type>&b);
public:
MatrixNode(int r=0,int c=0):row(r),col(c),right(NULL),down(NULL){};
MatrixNode(const MatrixNode<Type>*p):row(p->row),col(p->col),right(NULL),down(NULL),data(p->data){};
private:
int row,col;
//结点的行号和列号
MatrixNode<Type>*right,*down;
//分别存放同一行或同一列下一个结点的地址
union{
Type data;
//元素结点的数据域
MatrixNode<Type>*next;
//头结点使用next指针指向后继头结点
};
};
/*************************十字链表类**********************/
template<class Type>class LinkMatrix{
friend istream& operator>><>(istream&,LinkMatrix&);
friend ostream& operator<<<>(ostream&,const LinkMatrix&);
friend LinkMatrix<Type>operator+<>(const LinkMatrix &a,const LinkMatrix &b);
public:
LinkMatrix(){head=new MatrixNode<Type>();head->next=head;};
LinkMatrix(const LinkMatrix<Type>&a);
//复制构造函数
~LinkMatrix(){clear(); delete head;}
void clear();
//将十字链表清空，只剩总头结点
void Insert(int i,int j, Type e);
//把非零元素插入表
Type GetValue(int i,int j)const;
//返回第i行j列的元素
LinkMatrix<Type>& operator=(const LinkMatrix<Type>&a); //赋值运算符重载
LinkMatrix<Type> operator+=(const LinkMatrix<Type>&a);//复合赋值运算符重载
MatrixNode<Type>*Head(int i);
//取得第i行(或第i列)的链表的头结点
MatrixNode<Type>*Locate(int i,int j);
//读取第i行第j列的非零元结点
void Setup();
void Display();
private:
MatrixNode<Type>*head,**HeadList;
//HeadList = new MatrixNode<Type>[max+1];
//十字链表的头指针
void InsertInCol(MatrixNode<Type>*p);//将结点p插入第p->col列的列链表中
void DeleteInCol(MatrixNode<Type>*p);
//将结点p从其所在的列链表中删除，并释放其空间
int max;
//非零元素个数
};
//取得第i行(或第i列)的链表的头结点
template<class Type>MatrixNode<Type>*LinkMatrix<Type>::Head(int i){
return HeadList[i];
}
//把非零元素插进表
template<class Type>void LinkMatrix<Type>::Insert(int i, int j, Type e)
{
MatrixNode<Type> *node = new MatrixNode<Type>;
node->row=i;
node->col=j;
node->data=e;
node->right=HeadList[i];
node->down=HeadList[j];
MatrixNode<Type> *p = HeadList[i];cout<<"test3"<<endl;
//while(q->right != HeadList[i] && q->right->col != j)
//q = q->right;
//node->right = q->right;
//q->right = node;cout<<"test0"<<endl;
//q = HeadList[j];
//
while(q->down != HeadList[j] && q->down->row != i)
//
q = q->down;
//node->down = q->down;
//
q->down = node;cout<<"test1"<<endl;
int m=p->right->col;
while(m!=j)//&& p->right != HeadList[i] )//||p->right->colde的 值根本么变
{m++;cout<<"p->right->col:"<<m<<endl;
p = p->right;cout<<"p右滑"<<endl;if(p->right == HeadList[i])break;
}node->right = p->right;
p->right=node;cout<<"在行链表插入"<<endl;
p = HeadList[j];cout<<"p=j列头结点"<<endl;
int k=p->down->row ;
while( k!= i)//q->down != HeadList[j]&&
{
p = p->down;k++;cout<<"p下滑"<<endl;if(p->down == HeadList[j])break;
}node->down=p->down;
p->down=node;cout<<"在列链表插入"<<endl;
cout<<"testtest"<<endl;
}
///返回r行c列的元素
template<class Type>Type LinkMatrix<Type>::GetValue(int i, int j)const
{
MatrixNode<Type> *p = HeadList[i];//第i行的头结点
MatrixNode<Type> *q = HeadList[j];//第j行的头结点
while((p->right->col !=j)&& p->right != HeadList[i] )//||
{//if(p->right == HeadList[i])break;
p = p->right;//
cout<<"testtest"<<endl;
}
////////////////////for(;p->right->col !=j;)
////////////////{p = p->right;
//////////////if(p->right == HeadList[i])
///////////////////////
break;}
while(( q->down->row != i)&&q->down != HeadList[j])//&&)
{if(q->down == HeadList[j])break;
q = q->down;
}
if((p->right->col == j) && q->down->row == i)
{
return p->right->data;}
return 0;}
//将十字链表清空，只剩总头结点
template<class Type>void LinkMatrix<Type>::clear()
{
MatrixNode<Type>*p;
for(int i=1;i<=max;i++)
{
while(HeadList[i-1]->right!=HeadList[i])
{
p=HeadList[i]->right;
HeadList[i]->right=p->right;
delete p;
}
}
delete[]HeadList;
head=0;
}
///复制构造函数
template<class Type>LinkMatrix<Type>::LinkMatrix(const LinkMatrix<Type>&a)
{
MatrixNode<Type>*p,*q, *m;
//p=new
MatrixNode<Type>;
// a.Display();
max= a.max;
///a.Display();
HeadList = new MatrixNode<Type>*[max+1];
HeadList[0]=a.HeadList[0];
for(int i = 1; i <= max; i++)
{ HeadList[i] =a.HeadList[i];HeadList[i-1]->next= HeadList[i];}
HeadList[max]->next=head;
m=a.HeadList[0]; cout<<"a的还回值："<<a.GetValue(3,1)<<endl;
for(int i = 1; i <=m->row; i++)
{ for(int j= 1; j<= m->col; j++)
{ cout<<"("<<i<<","<<j<<")"<<endl;//<< //int kk=a.GetValue(i,j);
cout<<"a的还回值："<<a.GetValue(i,j)<<endl;
}
}
}
///重载＝操作符
template<class Type>LinkMatrix<Type>&LinkMatrix<Type>:: operator=(const LinkMatrix<Type>&a)
{
MatrixNode<Type>*p,*q, *m;
//p=new
MatrixNode<Type>;
// a.Display();
max= a.max;
///a.Display();
HeadList = new MatrixNode<Type>*[max+1];
HeadList[0]=a.HeadList[0];
for(int i = 1; i <= max; i++)
{ HeadList[i] =a.HeadList[i];HeadList[i-1]->next= HeadList[i];}
HeadList[max]->next=head;
m=a.HeadList[0];
}
//将结点p插入到p->col列中
template<class Type>void LinkMatrix<Type>::InsertInCol(MatrixNode<Type>*p)
{
MatrixNode<Type>*pre,*ch=HeadList[p->col];
//Head(i)返回地i行/列链表的头结点
pre=ch; //在p->col插入结点p，该列是以行值递增的循环链表
while(pre->down!=ch&&pre->down->row<p->row)pre=pre->down;
p->down=pre->down;
pre->down=p;
}
/*****************在p->col列中删除结点p，并释放空间**********************/
template<class Type>void LinkMatrix<Type>::DeleteInCol(MatrixNode<Type>*p){
MatrixNode<Type>*pre,*ch=HeadList[p->col];
pre=ch; //在p->列删除结点p，该列是以行值递增的循环链表
while(pre->down!=ch&&pre->down!=p) pre=pre->down;
if(pre->down==p) {pre->down=p->down; delete p;}
else cout<<"内存分配错误！";
}
////////////////////////////////////////////////////////////////////////
template<class Type>
//istream&operator>>(istream & in,LinkMatrix<Type>&a)
void LinkMatrix<Type>::Setup()
{
//重载输入运算符，建立稀疏矩阵的十字链表
int m,n,terms;
//HeadList = new MatrixNode<Type>[max+1];
MatrixNode<Type>*p,*q;
cout<<"输入矩阵的行数，列数和非零元素飞个数"<<endl;
cin>>m>>n>>terms;
//输入矩阵的行数，列数和非零元素个数
// if(n>m)max=n; else max=m;
//s记录头结点的个数
max=terms;
head=new MatrixNode<Type>;
//生成总表头结点
head->right=head->down=NULL;
head->col=n;head->row=m;
HeadList=new MatrixNode<Type>*[max+1];
//数组cp用于存放所有头结点的地址
HeadList[0]=head;
int i;
for(i=1;i<=max;i++)
//生成所有头结点，并将所有头结点组成一个循环链表
{
p=new MatrixNode<Type>;
p->row=0;p->col=0;
p->right=p;p->down=p;
HeadList[i]=p;HeadList[i]->right=HeadList[i];HeadList[i]->down=HeadList[i];// HeadList[i-1]->next=p;
HeadList[i-1]->next= HeadList[i];
}
HeadList[max]->next=head;
for(i=1;i<=terms;i++)
{
cout<<"输入"<<i<<"个非零三元组(row,col,value)"<<endl;
q=new MatrixNode<Type>;
p=new MatrixNode<Type>;
//为输入的三元组分配结点
cin>>p->row>>p->col>>p->data;
p->right=HeadList[p->row];
p->down=HeadList[p->col];//输入一个非零元素的三元组
q=HeadList[p->row];
//将输入的三元组结点插入到行链表的正确位置
while((q->right!=HeadList[p->row])&&(q->right->col!=p->col))q=q->right;
p->right=q->right; q->right=p;//gg这里根本没有吧头尾连接起来
cout<<"插入到正确的行位子"<<endl;
q=HeadList[p->col];
//将输入的三元组结点插入到列链表的正确位置
while((q->down!=HeadList[p->col])&&(q->down->row!=p->row))q=q->down;
p->down=q->down; q->down=p;
cout<<"插入到正确的列位子"<<endl;
}
// {while(q->right!=HeadList[p->row])q=q->right;
// q->right=p;p->right=HeadList[p->row];
// q=HeadList[p->col];while(q->down!=HeadList[p->col])q=q->down;
//
q->down=p;p->down=HeadList[p->col];}
// }
delete[]q;
//return 1;
}
template<class Type>//重载复合赋值运算符+=
LinkMatrix<Type>LinkMatrix<Type>::operator+=(const LinkMatrix<Type>&a){
MatrixNode<Type>*pre,*pa,*h,*ah,*p,*tmp;
if(head->col!=a.head->col||head->row!=a.head->row)//非同类型矩阵不可相加
cout<<"类型不匹配！";
h=head->next; ah=a.head->next;//h,ah指向当前处理行的头结点
while(h!=head){//逐一处理各行
pre=h; p=h->right;//p指向被加矩阵的当前结点，pre指向其前驱
pa=ah->right; //pa分别指向加矩阵的当前结点
while(pa!=ah){//处理当前行
if(p!=h&&(p->col<pa->col)){//若被加矩阵的列标更小，则比较下一个
pre=p; p=p->right;
}
else if(p==h||p->col>pa->col){//若加矩阵的列标更小，则插入
tmp=new MatrixNode<Type>(pa);
pre->right=tmp;//在行链表中插入pa的复制结点tmp
tmp->right=p;
InsertInCol(tmp);//在行链表中插入tmp
pre=tmp;//当前指针p的前驱变为tmp
pa=pa->right;
}
else {//列标相同，则做加法
p->data+=pa->data;
if(!p->data){//和为0，则删除之（行，列都要删）
pre->right=p->right;
//tmp=p;p=p->right;pre->right=p;//在行链表中将tmp摘下
DeleteInCol(tmp);//在列链表中将tmp删除
}
else{ pre=p;p=p->right;pa=pa->right;}
}
}
h=h->next; ah=ah->next;//处理下一行
}
return *this;
}
/***********************重载加法运算符*****************************/
template<class Type>
LinkMatrix<Type>operator+(const LinkMatrix<Type>&a,const LinkMatrix<Type>&b){
LinkMatrix<Type>c(a);//复制构造函数得到被加矩阵A的一个副本放在矩阵C中
c+=b;return c;
}
template<class Type>//ostream&operator<<<>(ostream&out,LinkMatrix<Type>&a)
void LinkMatrix<Type>::Display(){
MatrixNode<Type>*p;
p=HeadList[0];
cout<<"行数："<<p->row<<endl;
cout<<"列数："<<p->col<<endl;cout<<"节点数"<<max<<endl;
for(int i=1;i<=p->row;i++)
{for(int j=1;j<=p->col;j++)
cout<<GetValue(i,j)<<"
";
cout<<endl;
}//cout<<"test"<<endl;
}
int main(){
LinkMatrix<int> m1,m3;
m1.Setup();
m1.Display();
LinkMatrix<int>m2(m1);
//m2.Setup();
cout<<"第二个："<<endl;
m2.Display();cout<<"第3个："<<endl;
//m3=m2; m3.Display();
//(m1+m2).Display();
//cin>>m1>>m2;
//m3=m1+m2;
// cout<<m3;
system("PAUSE");
return EXIT_SUCCESS;
}
程序代码：
嗯哈，我知道那个存放所有头结点的数组 为了加快查找速度 我觉得添加为成员更好额，免得后面要用还得去声明
版主的代码写得太规范了。膜拜