三元组

data_structure

首先先痛斥下vc6.0，并记住以后遇到模板类的，一定要全部重建。

一、介绍

如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩阵（sparse matrix）。
概念很清楚，矩阵中，0元素比较多的矩阵是稀疏矩阵，
这样的矩阵可以用三元组以及十字链表存贮，这里介绍三元组的用法。

二、三元组介绍

含有在矩阵中的行列数，以及元素值的结构体。定义如下：

template<class T>
struct Triple
{
    int r,c;
    T elem;
    bool operator <(const Triple<T>& rhs) const // 升序排序时必须写的函数  
    {  
        return r < rhs.r;  
    }  
};

重载运算符是为了后面调用vector的排序，省的自己费心的按顺序插入，这样全部插好了，直接排序就好了。

三、稀疏矩阵

这是一个类，类里面包含行数，列数，还有非零元的个数，同时非零元的具体值，即三元组，用的是向量存储，动态扩容，随机访问复杂度为o(1),很强大的工具。

3.1构造函数的撰写

构造函数，我准备写两种形式，

• 第一种无参，那就要求从键盘键入值，
• 第二种有参，那数据来源是文件

3.1.1无参

先存储数据的个数，如行数，列数，非零元个数，然后循环读取数据，存入，并压入向量，最后对其排序。
最好能对重复元素位置做检测，这边没有实现这个功能，以后再补吧。

template<class T>
SparseMatrix<T>::SparseMatrix()
{
    do {
        cout<<"请分别输入矩阵的行数、列数和非零元个数：\n";
        cout<<"行数：";
        cin>>this->row;
        cout<<"列数：";
        cin>>this->col;
        cout<<"非零元的个数：";
        cin>>this->num;
        if(this->row < 0 || this->col < 0 || this->num < 0 || this->num > this->row * this->col) cout<<"有错。。";
    } while(this->row < 0 || this->col < 0 || this->num < 0 || this->num > this->row * this->col);
    //保证了数据的正确性。。
    if (this->num==0) return ;//每个元素都是空的。
    for(int k =0;k<this->num;k++)
    {
        Triple<T> tmp;
        do {
            cout<<"请输入第"<<k+1<<"个非零元的行和列：\n";
            cout<<"行：";
            cin>>tmp.r;
            cout<<"列：";
            cin>>tmp.c;          
            cout<<"元素:";
            cin>>tmp.elem;
            if(tmp.r <= 0 || tmp.r > this->row || tmp.c <= 0 || tmp.c > this->col)   cout<<"有错。。重输";
        } while(tmp.r <= 0 || tmp.r > this->row || tmp.c <= 0 || tmp.c > this->col);//检测输入是否合法 
        triList.push_back(tmp);
    }
    sort(triList.begin(), triList.end());
/*  for (int i=0;i<triList.size();i++)
    {
        cout<<triList[i].r<<"   ";
    }
*///    std::sort(triList,0);   ！！！重要的，一定要排序或者想办法顺序插入。
}

3.1.2有参构造函数

这边的数据，准备来源于文件，所以先介绍文件的格式

5
5 5
2 3 1
3 2 2
2 4 3
5 5 4
1 2 5

第一行为非零元个数
第二行是矩阵规模
后面是三元组的内容。
所以设计load函数也很方便。

int num;
int r;
int c;
Triple<int> * Load(char *fname)
{
    ifstream fin(fname);
    int n;
    fin>>n;
    num=n;
    fin>>r;
    fin>>c;
    Triple<int> *list=new Triple<int> [n];
    int i=0;
    while(!fin.eof())
    {
        fin>>list[i].r;
        fin>>list[i].c;
        fin>>list[i++].elem;
    }
    fin.close();
    return list;
}

全局变量num，r，c便于传递有参函数的参数，Load函数返回的是结构体数组，我们利用这个来构造矩阵。同样也需要判重，这边不写。

template<class T>
SparseMatrix<T>::SparseMatrix(int rs,int cs,int n,Triple<T> *list)
{
    this->col=cs;
    this->row=rs;
    this->num=n;
    for (int i=0;i<n;i++)
    {
        Triple<T> tmp;
        tmp.r=list[i].r;
        tmp.c=list[i].c;  
        tmp.elem=list[i].elem;
        triList.push_back(tmp);
    }
    sort(triList.begin(), triList.end());
}

这样，调用的方式为
SparseMatrix<int> sm(r,c,num,Load("data.txt"));
但是很奇怪的是，
如果声明为：
SparseMatrix(Triple<T> *list,int rs,int cs,int n);
这样在调用时错的，这个问题我前面也遇到过，尝试解释过，但不知道对不对。

3.2输出矩阵

目的很明确，把矩阵输出。
没什么好办法，一个个的遍历，因为triList里面的元素是按照行来排序的，所以依次遍历，对比该位置是否存在值，存在输出，不存在输出0.

template<class T>
void SparseMatrix<T>::print()
{
    int i, j, k;//中间变量
    //输出
    for(i = 1, k = 0; i <= this->row; i++)
    {
        for(j = 1; j <=this->col; j++)
        {
            int r=this->triList[k].r;
            int c=this->triList[k].c;
            if(i ==  r &&j == c) 
            {
                cout<<this->triList[k].elem<<"\t";
                k++;
            }
            else cout<<0<<"\t";
        }
        cout<<endl;
    }
}

3.3转置

这块运用的是快速转置。这边遇到的问题是，调试的时候，多次遇到错，检测不出来，到最后发现，是因为没有全部重建，导致部分语句并没有被重编译，给debug带来巨大的麻烦，切记。
代码本身还是很好理解的，书上也给了详细的说明：

/*
输出
*/
template<class T>
void SparseMatrix<T>::trans(SparseMatrix<T>& B)
{
    int co=col;
    B.row = this->col;
    B.col = this->row;
    B.num = this->num;
    B.triList.resize(num);
    if(num == 0)
        return;
    int* cnum = new int [100];
    int* cpot = new int [100];
    for(int i=0; i<co; i++)
        cnum[i] = 0;
    for(int t=0; t<num;t++)
    {
    //  cout<<t<<endl;
    //  cout<<triList[t].c ;
        ++cnum[triList[t].c];   
    }
    cpot[1] = 0;
    for(i=2; i<=co; i++)
        cpot[i] = cpot[i-1]+cnum[i-1];
    for(int p=0; p<num; p++)
    {
        int n = triList[p].c;
        int q = cpot[n];
        B.triList[q].r = triList[p].c;
        B.triList[q].c = triList[p].r;
        B.triList[q].elem = triList[p].elem;
        ++cpot[n];
    }
    delete[] cnum;
    delete[] cpot;
}

四、测试

最后，做一个小小的测试，由于无参构造函数也需要输入值，如果不真的需要值，可以输入0 0 0；

int main()
{
    SparseMatrix<int> sm(r,c,num,Load("data.txt"));
    sm.print();
    SparseMatrix<int> sm1;
    sm.trans(sm1);
        cout<<"转置后"<<endl;
    sm1.print();
    return 0;
}

测试截图：

2015年4月22日晚