实验7-矩阵的压缩存储.md

实验7-矩阵的压缩存储

#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;
#define  MAXSIZE 100
typedef int ElemType;	//数据元素的类型为ElemType，将ElemType定义为int类型

//结构体定义
typedef struct     //三元组的类型定义
{    
    int  row;    //非零元素行号
	int  col;    //非零元素列号
    ElemType  val;	//非零元素值
}tupletype;

typedef struct      //三元组顺序表存储结构定义
{	
    tupletype data[MAXSIZE];		//非零元素的三元组表
    int  rnum;    	//矩阵行数
	int  cnum;   	//矩阵列数
	int  len;   	//矩阵总非零元素个数 
}table;


//按矩阵形式输出
void DispTable(table *m)
{  	
    int i,j,k,e;
    for(i=0;i<m->rnum;i++)
    { 
        for(j=0;j<m->cnum;j++)
        {
            e=0;
            for(k=0;k<m->len;k++)
            {
                if(i==m->data[k].row&&j==m->data[k].col)
                {
                    e=m->data[k].val;
                    break;
                }
            }
            cout<<e<<"\t";
       }
       cout<<endl;
    }
}

//按三元组表形式输出
void print(table *m)
{  	
    cout<<"按三元组表形式输出:\n";
    cout<<"行\t列\t值"<<endl;
    for(int i=0;i<m->len;i++)
    {
        cout<<m->data[i].row<<"\t"
            <<m->data[i].col<<"\t"
            <<m->data[i].val<<endl;
    }
}

//稀疏矩阵转置(普通转置）
void trans(table *ta,table *tb)
{	
    int k,p,q;    	 	 
    tb->rnum=ta->cnum;
    tb->cnum=ta->rnum;
    tb->len=ta->len;
    q=0;	/*q为tb->data的下标*/
    if (tb->len!=0) 
    {   
        for (k=0;k<ta->cnum;k++) 	
            for (p=0;p<ta->len;p++)  /*p为ta->data的下标*/
                if (ta->data[p].col==k) 
                {	  
                    tb->data[q].row=ta->data[p].col;
                    tb->data[q].col=ta->data[p].row;
                    tb->data[q].val=ta->data[p].val;
                    q++;
                }
    }
}


//稀疏矩阵转置（分段定位）
void _trans(table *ta,table *tb)
{    
    int k,q,i,p,j;
    int *num = new int[ta->cnum];
    int *pot = new int[ta->cnum];	
   	tb->rnum=ta->cnum;
	tb->cnum=ta->rnum;
	tb->len=ta->len;
    for (k=0;k<ta->cnum;k++) 	/*初始化num[  ]为0*/
    {	
        num[k]=0;
    }
    for (i=0;i<ta->len;i++) 	/*将三元组表ta扫描一遍，对于其中列号为k的元素，给相应的num[k]加1。*/
    {	
        num[ta->data[i].col]++;	
    }
    pot[0]=0;
    for (k=1;k<ta->cnum;k++)	 /*计算pot[  ]各数组元素的值*/
    {	
        pot[k]=pot[k-1]+num[k-1];
    }
    for (p=0;p<ta->len;p++) 
    {	
        j=ta->data[p].col;
        q=pot[j];	
        tb->data[q].row=ta->data[p].col;
        tb->data[q].col=ta->data[p].row;
        tb->data[q].val=ta->data[p].val;
        pot[j]++;		 /*矩阵A本列上下一个非零元素的位置，即矩阵B本行上下一个非零元素的位置*/
    }	
}

//稀疏矩阵的加法运算
int tableAdd(table M, table N, table *Q)
{
    int i,j,k;
	//矩阵信息
	Q->cnum = M.cnum;
	Q->rnum = M.rnum;
	Q->len = 0;

	while (i < M.len && j < N.len)
	{
		// 如果 i j 指向元素是同一行的元素
		if (M.data[i].row == N.data[j].row)
		{
			// 如果 i 和 j 指向的元素指向的是同一个元素
			if (M.data[i].col == N.data[j].col)
			{
				Q->data[k].row = M.data[i].row;
				Q->data[k].col = M.data[i].col;
				Q->data[k].val = M.data[i].val + N.data[j].val;
				Q->len++;

				i++;
				j++;
				k++;
			}
			// 如果 i 指向元素的列下标大于 j 指向元素的列下标
			// 把下标小（j 指向的元素）的放入到 Q 矩阵中
			else if (M.data[i].col > N.data[j].col)
			{
				Q->data[k].row = N.data[j].row;
				Q->data[k].col = N.data[j].col;
				Q->data[k].val = N.data[j].val;
				Q->len++;

				j++;
				k++;
			}
			// 如果 i 指向元素的列下标小于 j 指向元素的列下标
			// 把下标小（i 指向的元素）的放入到 Q 矩阵中
			else if (M.data[i].col < N.data[j].col)
			{
				Q->data[k].row = M.data[i].row;
				Q->data[k].col = M.data[i].col;
				Q->data[k].val = M.data[i].val;
				Q->len++;

				i++;
				k++;
			}
		}
		// 如果 i 指向的元素行下标大于 j 指向元素的行下标
        // 把行下标小（j 指向的元素）的放入到 Q 矩阵中
		else if (M.data[i].row > N.data[j].row)
		{
			Q->data[k].row = N.data[j].row;
			Q->data[k].col = N.data[j].col;
			Q->data[k].val = N.data[j].val;
			Q->len++;

			k++;
			j++;
		}
		// 如果 i 指向元素行下标小于 j 指向元素的行下标
        // 把行下标小（i 指向的元素）的放入到 Q 矩阵中
		else if (M.data[i].row < N.data[j].row)
		{
			Q->data[k].row = M.data[i].row;
			Q->data[k].col = M.data[i].col;
			Q->data[k].val = M.data[i].val;
			Q->len++;

			i++;
			k++;
		}
	}

	// 如果还有剩余元素，按顺序把元素添加到结果矩阵中
	while (i < M.len)
	{
		Q->data[k].row = M.data[i].row;
		Q->data[k].col = M.data[i].col;
		Q->data[k].val = M.data[i].val;
		Q->len++;

		i++;
		k++;
	}

	while (j < N.len)
	{
		Q->data[k].row = N.data[j].row;
		Q->data[k].col = N.data[j].col;
		Q->data[k].val = N.data[j].val;

		Q->len++;

		j++;
		k++;
	}
}

//查找稀疏矩阵的i行j列的值
ElemType getVal(table *ta,int i,int j){
    for(int k=0;k<ta->len;k++){
        if(ta->data[k].row==i && ta->data[k].col == j){
            return ta->data[i].val;
        }
    }
    return 0;
}

//修改稀疏矩阵的i行j列的值
void editVal(table *ta,int i,int j,ElemType e){
    tupletype t;
    t.row = i;
    t.col = j;
    t.val = e;
    int k = 0;
    while(ta->data[k].row<t.row && k < ta->len){
        k++;
    }
    if(ta->data[k].row==t.row){
        while(ta->data[k].col<t.col && k < ta->len){
            k++;
        }
        if(ta->data[k].col==t.col){
            ta->data[k] = t;
            return;
        }
    }
    for(int a=ta->len;a>k;a--){  //右移，然后插入
        ta->data[a] = ta->data[a-1];
    }
    ta->data[k] = t;
    ta->len++;
    return;
}