| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1216 人关注过本帖
标题:关于十字链表建立的问题,高手请帮忙分析哈这段代码
只看楼主 加入收藏
yfleee
Rank: 2
等 级:论坛游民
帖 子:28
专家分:20
注 册:2011-3-9
结帖率:100%
收藏
已结贴  问题点数:0 回复次数:13 
关于十字链表建立的问题,高手请帮忙分析哈这段代码
//建立十字链表的函数
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记录头结点的个数
   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-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;//      

       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;
       }
        // {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>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;
    }
    ////////////////////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;}
/////////////////////////////////////////////////////////////
注:第一个函数是建立链表的,第二个是取节点的,都能运行,举个例子比如3*3的矩阵,如果9哥节点全部都为非零,则返回值是正确的,但是如果不全是另节点则会有错误
第二个函数p=p-right会一直执行!!!!求高手指点错误
搜索更多相关主题的帖子: 矩阵 元素 
2011-03-21 21:33
变幻小子
Rank: 6Rank: 6
来 自:广东陆丰
等 级:侠之大者
帖 子:188
专家分:473
注 册:2011-3-4
收藏
得分:0 
路过学习

明天的梦
2011-03-21 22:40
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
程序不长 就全部贴上来
2011-03-21 22:43
yfleee
Rank: 2
等 级:论坛游民
帖 子:28
专家分:20
注 册:2011-3-9
收藏
得分: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;
}
     
2011-03-22 09:17
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
程序代码:
#include <iostream.h>
#include <windows.h>

//友元函数的前置声明
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>
class MatrixNode
{
    friend class LinkMatrix<Type>;
    friend istream & operator >> ( istream &, LinkMatrix<Type>& );
    friend ostream & operator << ( ostream &, const LinkMatrix<Type>& ); 

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;     //分别存放同一行或同一列下一个结点的地址
    Type data; //元素结点的数据域
};
/*************************十字链表类**********************/
template<class Type>
class LinkMatrix
{
    friend istream & operator >> ( istream &, LinkMatrix & );
    friend ostream & operator << ( ostream &, const LinkMatrix<Type>& ); 

public:
    LinkMatrix();
    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 Init();
    void Display();

private:

    MatrixNode<Type> *array_row;//行数组
    MatrixNode<Type> *array_col;//列数组
    void InsertInCol( MatrixNode<Type> *p );//将结点p插入第p->col列的列链表中
    void DeleteInCol( MatrixNode<Type> *p );  //将结点p从其所在的列链表中删除,并释放其空间
    void Give_copy_fc( const LinkMatrix<Type> &a );
    void Adjust_Link( MatrixNode<Type> *param );//调整十字链表到正确的位置
    int max;   //非零元素个数 

};

template <class Type>
LinkMatrix<Type>::LinkMatrix()
{
    array_row = NULL;
    array_col = NULL;
    max = 0;
}
//建立十字链表的函数
template<class Type>
void LinkMatrix<Type>::Setup()
{ 
    Init();
   
    return;
}
///返回r行c列的元素
////////////////////////////////////////////////////////////
template<class Type>
Type LinkMatrix<Type>::GetValue( int i, int j )const
{
    MatrixNode<Type> *p_row = array_row[i - 1].right;
    MatrixNode<Type> *p_col = array_col[j - 1].down;
    while( p_row && p_row->col != j )
    {
        p_row = p_row->right;
    }
    while( p_col && p_col->row != i )
    {
        p_col = p_col->down;
    }
    if( p_row == p_col )
    {
        if( !p_row && !p_col )
        {
            return 0;
        }
    }
    else
    {
        cout << "\t十字链表调整错误!" << endl;
        exit( -1 );
    }

    return p_row->data;
}
template<class Type>//ostream&operator<<<>(ostream&out,LinkMatrix<Type>&a)
void LinkMatrix<Type>::Display()
{
    cout << "行数:" << array_row[0].row << endl;
    cout << "列数:" << array_col[0].col << endl;

    for( int i=1; i <= array_row[0].row; i++ )
    {
        for( int j=1; j <= array_col[0].col; j++ )
        {
            cout << GetValue(i,j) << "  ";
        }

        cout<<endl;
    }
}

///复制构造函数
template<class Type>
LinkMatrix<Type>::LinkMatrix( const LinkMatrix<Type>&a )
{     
    Give_copy_fc( a );
}
///重载=操作符
template<class Type>
LinkMatrix<Type> & LinkMatrix<Type>::operator = ( const LinkMatrix<Type> &a )
{
    if( NULL != array_row )
    {
        clear();
    }

    Give_copy_fc( a );

    return *this;
}  

template<class Type>
void LinkMatrix<Type>::Give_copy_fc( const LinkMatrix<Type> &a )
{
    array_row = new MatrixNode<Type> [a.array_row[0].row];
    array_row[0].row = a.array_row[0].row;

    array_col = new MatrixNode<Type> [a.array_col[0].col];
    array_col[0].col = a.array_col[0].col;

    max = a.max;

    MatrixNode<Type> *rep_a;
    int i = 1;
    while( a.array_row[0].row >= i )
    {
        rep_a = a.array_row[i-1].right;
       
        while( NULL != rep_a )
        {
            Adjust_Link( rep_a );
           
            rep_a = rep_a->right;
        }

        ++i;
    }
}
template<class Type>
void LinkMatrix<Type>::Adjust_Link( MatrixNode<Type> *param )
{
    MatrixNode<Type> *p, *temp, *fr_temp;

    p = new MatrixNode<Type>;
    p->row = param->row;
    p->col = param->col;
    p->data = param->data;

    //行调整
    fr_temp = temp = array_row[p->row - 1].right;
    while( temp && temp->col < p->col )
    {
        fr_temp = temp;
        temp = temp->right;
    }

    if( fr_temp == temp )
    {
        p->right = array_row[p->row - 1].right;
        array_row[p->row - 1].right = p;
    }
    else
    {
        p->right = fr_temp->right;
        fr_temp->right = p;
    }

    //列调整
    fr_temp = temp = array_col[p->col - 1].down;
    while( temp && temp->row < p->row )
    {
        fr_temp = temp;
        temp = temp->down;
    }

    if( fr_temp == temp )
    {
        p->down = array_col[p->col - 1].down;
        array_col[p->col - 1].down = p;
    }
    else
    {
        p->down = fr_temp->down;
        fr_temp->down = p;
    }

    return;
}
////////////////////////////////////////////////////////////////////////
template<class Type>//重载复合赋值运算符+=
LinkMatrix<Type> & LinkMatrix<Type>::operator += ( const LinkMatrix<Type> &a )
{
    MatrixNode<Type> *p_this, *p_a;
    int i = 1;
    max = 0;

    while( array_row[0].row >= i )
    {
        p_this = array_row[i-1].right;
        p_a = array_row[i-1].right;
        while( NULL != p_this && NULL != p_a )
        {
            if( p_this->col == p_a->col )
            {
                p_this->data = p_this->data + p_a->data;//当结果为零时要删除该节点
                if( 0 != p_this->data )
                {
                    ++max;
                }
                p_this = p_this->right;
                p_a = p_a->right;
            }
            else if( p_this->col > p_a->col )
            {
                Adjust_Link( p_a );
                ++max;
                p_a = p_a->right;
            }
            else
            {
                p_this = p_this->right;
            }
        }
        if( NULL != p_a )
        {
            while( NULL != p_a )
            {
                Adjust_Link( p_a );
                ++max;
                p_a = p_a->right;
            }
        }

        ++i;
    }

   return *this;
}
//将十字链表清空,只剩总头结点
template<class Type>
void LinkMatrix<Type>::clear()
{
    MatrixNode<Type> *p;

    for( int i=1; i<= array_row[0].row; ++i )
    {
        while( NULL != array_row[i - 1].right )
        {
            p = array_row[i - 1].right;
            array_row[i - 1].right = p->right;

            delete p;
        }
    }
   
    delete [] array_row;
    delete [] array_col;

    array_row = NULL;
    array_col = NULL;

    return;
}

template<class Type>
istream & operator >> ( istream &in, LinkMatrix<Type> &a )
{
    if( NULL != a.array_row )
    {
        a.clear();
    }

    a.Init();

    return in;
}

template<class Type>
void LinkMatrix<Type>::Init()
{
    int p_row, p_col;
  
    cout << "输入矩阵的行数,列数" << endl;
    cin >> p_row
        >> p_col;    //输入矩阵的行数,列数

    if( NULL == p_row && NULL == p_col )
    {
        cout << "\t输入有错误!"  << endl;
        exit( -1 );
    }
   
    array_row = new MatrixNode<Type> [p_row];
    array_row[0].row = p_row;

    array_col = new MatrixNode<Type> [p_col];
    array_col[0].col = p_col;

    MatrixNode<Type> *p;
    max = 0;

    cout << "非零元数个数" << endl;
    while( cin >> max, max > array_col[0].col * array_row[0].row )
    {
        cout << "非零元数个数" << endl;
    }
    for( int i=1; i <= max; i++ )
    {  
        cout << "输入" << i << "个非零三元组(row, col, value)" << endl;

        p = new MatrixNode<Type>;   //为输入的三元组分配结点
        cin >> p->row
            >> p->col
            >> p->data;
       
        if( p->row > array_row[0].row || p->col > array_col[0].col )
        {
            cout << "\t输入有错误!"  << endl;
            exit( -1 );
        }

        Adjust_Link( p );
    }   
}
template<class Type>
ostream & operator << ( ostream &out, const LinkMatrix<Type> &a )
{
    out << "行数:" << a.array_row[0].row << endl;
    out << "列数:" << a.array_col[0].col << endl;
    out << "总数: " << a.max << endl;

    for( int i=1; i <= a.array_row[0].row; i++ )
    {
        for( int j=1; j <= a.array_col[0].col; j++ )
        {
            out << a.GetValue(i,j) << "  ";
        }

        out << endl;
    }    

    return out;
}
/*
//取得第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 )
{

 }
//将结点p插入到p->col列中
template<class Type>
void LinkMatrix<Type>::InsertInCol(MatrixNode<Type>*p)
{ 
}
*/
/*****************在p->col列中删除结点p,并释放空间**********************/
/*
template<class Type>
void LinkMatrix<Type>::DeleteInCol( MatrixNode<Type>*p )
{
}
*/

int main()
{
    LinkMatrix<int> m1;

    m1.Setup();
    m1.Display();

    LinkMatrix<int> m2(m1);
    cout << "第二个:" <<endl;
    m2.Display();

    LinkMatrix<int> m3;
    cout << "第3个:" << endl;
    m3 = m2;
    m3.Display();

    m1 += m2;
    m1.Display();
    //cin>>m1>>m2;

    cout << m3;
   
    cin >> m3;
    cout << m3;

    system("PAUSE");

    return EXIT_SUCCESS;
} 


 

/////////////////////////////////////////////////////////////
/*
注:第一个函数是建立链表的,第二个是取节点的,都能运行,
举个例子比如3*3的矩阵,如果9哥节点全部都为非零,则返回值是正确的,
但是如果不全是另节点则会有错误
第二个函数p=p-right会一直执行!!!!求高手指点错误
*/
2011-03-22 18:49
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
框架差不多  

代码。。。。

你的十字链表 结构不知道怎么理解    要知道(十字链表)增加辅助空间 是为了加快查找速度
2011-03-22 18:54
yfleee
Rank: 2
等 级:论坛游民
帖 子:28
专家分:20
注 册:2011-3-9
收藏
得分:0 
嗯哈,我知道那个存放所有头结点的数组 为了加快查找速度 我觉得添加为成员更好额,免得后面要用还得去声明
2011-03-22 21:58
yfleee
Rank: 2
等 级:论坛游民
帖 子:28
专家分:20
注 册:2011-3-9
收藏
得分:0 
版主的代码写得太规范了。膜拜
2011-03-22 22:29
yfleee
Rank: 2
等 级:论坛游民
帖 子:28
专家分:20
注 册:2011-3-9
收藏
得分:0 
1>new十字链表.obj : error LNK2019: 无法解析的外部符号 "class std::basic_istream<char,struct std::char_traits<char> > & __cdecl operator>>(class std::basic_istream<char,struct std::char_traits<char> > &,class LinkMatrix<int> &)" (??5@YAAAV?$basic_istream@DU?$char_traits@D@std@@@std@@AAV01@AAV?$LinkMatrix@H@@@Z),该符号在函数 _main 中被引用
1>E:\Documents and Settings\Administrator\桌面\数据结构\数值计算方法练习\十字链表(new)\Debug\十字链表(new).exe : fatal error LNK1120: 1 个无法解析的外部命令
1>生成日志保存在“file://e:\Documents and Settings\Administrator\桌面\数据结构\数值计算方法练习\十字链表(new)\十字链表(new)\Debug\BuildLog.htm”
注:缺少了using namespacestd;还有就是使用重载后的<<,>>会有面的错误呢
2011-03-22 22:32
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册
2011-03-22 22:58
快速回复:关于十字链表建立的问题,高手请帮忙分析哈这段代码
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037873 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved