关于十字链表建立的问题，高手请帮忙分析哈这段代码 - C++教室 - C++论坛

得分:0

好嘛那我就全部发上来,还有重载=和复制构造函数没有完全实现应为要用到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;
}