堆栈队列和数组-行逻辑链接稀疏矩阵

#include<iostream>
#include <iomanip>
#include"windows.h"
using namespace std;
struct Tripple
{
    int x,y,value;
};
struct RLSMatrix
{
    int r,c,cnt;
    Tripple* tripples;
    int* rpos;
};

RLSMatrix* createRLSMatrix(int r,int c,int maxCnt)
{
    RLSMatrix* p = (RLSMatrix*)malloc(sizeof(RLSMatrix));
    p->r=r;
    p->c=c;
    p->cnt=0;
    p->tripples=new Tripple[maxCnt];
    p->rpos=new int[p->r+1];
    for(int i=1;i<=p->r;i++)
        p->rpos[i]=-1;
    p->rpos[0]=0;
    return p;
}
RLSMatrix* transpose(RLSMatrix*  src)
{
    RLSMatrix* ans =createRLSMatrix(src->c,src->r,src->cnt);
    int* ccnts = new int[src->c+1];
    int* cpos = new int[src->c+1];
    int lst=0;
    cpos[0]=0;
    for(int i=0;i<=src->c;i++)
        ccnts[i]=0;
    for(int i=0;i<src->cnt;i++)
        ccnts[src->tripples[i].y]++;
    for(int i=1;i<=src->c;i++)
    {
        if(ccnts[i]!=0)
        {
            ans->rpos[i]=ans->rpos[lst]+ccnts[lst];
            cpos[i] = ans->rpos[i];
            lst=i;
        }
    }

    delete[] ccnts;
    Tripple newTripple;
    for(int i=0;i<src->cnt;i++)
    {
        newTripple.x=src->tripples[i].y;
        newTripple.y=src->tripples[i].x;
        newTripple.value=src->tripples[i].value;
        ans->tripples[cpos[newTripple.x]++]=newTripple;
        ans->cnt++;
    }
    return ans;
}
RLSMatrix* multiple(RLSMatrix*  op1,RLSMatrix*  op2)
{
    if(op1->c!=op2->r)
        return NULL;
    RLSMatrix*  ans = createRLSMatrix(op1->r,op2->c,op1->cnt+op2->cnt);
    for(int i=1;i<=op1->r;i++)
    {
        if(op1->rpos[i]==-1)
            continue;
        int* tempSum= new int[op2->c+1];
        for(int k=0;k<=op2->c;k++)
            tempSum[k]=0;
        int st=op1->rpos[i];
        int nexti=i+1;
        while(nexti<=op1->r && op1->rpos[nexti]==-1)
            nexti++;
        int ed= nexti<=op1->r ? op1->rpos[nexti]:(op1->cnt);
        for(int k=st;k<ed;k++)
        {
            int cindex=op1->tripples[k].y;
            if(op2->rpos[cindex]==-1)
                continue;
            int _st=op2->rpos[cindex];
            int nextk= cindex+1;
            while(nextk<=op2->r && op2->rpos[nextk]==-1)
                nextk++;
            int _ed=nextk<=op2->r ? op2->rpos[nextk]:(op2->cnt);
            for(int j=_st;j<_ed;j++)
            {
                tempSum[op2->tripples[j].y]+=(op2->tripples[j].value*op1->tripples[k].value);
            }
        }
        bool firstC=1;
        for(int k=1;k<=ans->c;k++)
        {
            if(tempSum[k]!=0)
            {
                Tripple newTripple;
                newTripple.x = i;
                newTripple.y = k;
                newTripple.value=tempSum[k];
                ans->tripples[ans->cnt] = newTripple;
                if(firstC)
                    ans->rpos[i]=ans->cnt;
                ans->cnt++;
                firstC=0;
            }
        }
        i=--nexti;
    }
    return ans;
}
void output(RLSMatrix* src)
{
    int cur=0;
    for(int i=1;i<=src->r;i++)
    {
        for(int j=1;j<=src->c;j++)
        {
            if(src->tripples[cur].x==i && src->tripples[cur].y==j)
            {
                SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);//彰显非0元
                cout<<std::left<<setw(3)<<src->tripples[cur].value;
                SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);//设置三色相加
                cur++;
            }
            else cout<<std::left<<setw(3)<<0;
        }
        cout<<endl;
    }
}
void main()
{
     SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);//设置三色相加
     int r=6,c=6,maxCnt=8;
     RLSMatrix* m= createRLSMatrix(r,c,maxCnt);
     int lstR=0;
     for(int i=1;i<=r;i++)
     {
         for(int j=1;j<=c;j++)
         {
             if(rand()%3==1 && m->cnt<maxCnt)
             {
                 m->tripples[m->cnt].x=i;
                 m->tripples[m->cnt].y=j;
                 m->tripples[m->cnt].value=rand()%10;
                 if(i!=lstR)
                      m->rpos[i]=m->cnt;
                 m->cnt++;
                 lstR=i;
             }
         }
         
     }
     output(m);
     cout<<endl;
     output(transpose(transpose(m)));
     cout<<endl;
     output(transpose(m));
     cout<<endl;

     r=6,c=6,maxCnt=12;
     RLSMatrix* m2= createRLSMatrix(r,c,maxCnt);
     lstR=0;
     for(int i=1;i<=r;i++)
     {
         for(int j=1;j<=c;j++)
         {
             if(rand()%3==1 && m2->cnt<maxCnt)
             {
                 m2->tripples[m2->cnt].x=i;
                 m2->tripples[m2->cnt].y=j;
                 m2->tripples[m2->cnt].value=rand()%10;
                 if(i!=lstR)
                      m2->rpos[i]=m2->cnt;
                 m2->cnt++;
                 lstR=i;
             }
         }
          
     }
     output(m2);
     cout<<endl;
      
     output(multiple(m,m2));
     cout<<endl;
      output(transpose(multiple(transpose(m2),transpose(m))));
     cout<<endl;
 
     cin>>r;
}