Sparse Matrix (Orthogonal Linked List)
October 13, 2018
简单实现了稀疏矩阵的加法减法乘法和转置
Crosslist.h
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define LOVERFLOW -2 //避免与<math.h>中的定义冲突
typedef int Status;
typedef int ElemType;
class CrossList; //类的提前声明
class OLNode {
protected:
int i, j;
ElemType e;
OLNode *right, *down;
public:
friend istream& operator >> (istream &in, OLNode &n); //输入一个OLNode型对象
friend ostream& operator << (ostream &out, const OLNode &n); //输出一个OLNode型对象
friend class CrossList; //友元
friend istream& operator >> (istream &in, CrossList &m); //取代CreateSMatrix功能，以三元组表的形式输入一个稀疏矩阵
friend ostream& operator << (ostream &out, const CrossList &m); //取代PrintSMatrix，以矩阵形式输出
};
class CrossList {
protected:
OLNode **rhead, **chead; int mu, nu, tu;
public:
/* 构造和析构函数 */
CrossList(); //增加的构造函数，对TSMatrix类的对象进行初始化
CrossList(const CrossList &m); //增加的复制构造函数，完成TSMatrix类的对象的复制（三种调用时机）
~CrossList(); //取代DestroySMatrix
/* cin/cout的重载 */
friend istream& operator >> (istream &in, CrossList &m); //取代CreateSMatrix功能，以三元组表的形式输入一个稀疏矩阵
friend ostream& operator << (ostream &out, const CrossList &m); //取代PrintSMatrix，以矩阵形式输出
/* 成员函数形式的运算符重载 */
CrossList& operator=(const CrossList m); //取代CopySMatrix，T=M表示把M矩阵复制到T中
CrossList operator+(const CrossList &m); //和=重载一起，取代AddSMatrix， Q=M+N 表示求稀疏矩阵M+N的和
CrossList operator-(const CrossList &m); //和=重载一起，取代SubSMatrix， Q=M-N 表示求稀疏矩阵M-N的差
CrossList operator*(const CrossList &m); //和=重载一起，取代MultSMatrix，Q=M*N 表示求稀疏矩阵M*N的乘积
CrossList operator!(); //和=重载一起，取代TranspostSMatrix，!M 表示求M的转置矩阵
};
Crosslist.cpp
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include "Crosslist.h"
using namespace std;
istream &operator>>(istream &in, OLNode &n)
{
return in;
}
ostream &operator<<(ostream &out, const OLNode &n)
{
return out;
}
istream &operator>>(istream &in, CrossList &m)
{
int i, j, k, mu, nu, tu;
ElemType e;
OLNode *p, *q;
in >> mu >> nu >> tu;
m.mu = mu;
m.nu = nu;
m.tu = tu;
m.rhead = (OLNode**)malloc((mu + 1) * sizeof(OLNode*));
m.chead = (OLNode**)malloc((nu + 1) * sizeof(OLNode*));
for (k = 1; k <= mu; k++)
m.rhead[k] = NULL;
for (k = 1; k <= nu; k++)
m.chead[k] = NULL;
for (k = 0; k < tu; k++)
{
in >> i >> j >> e;
i++; j++;
p = (OLNode*)malloc(sizeof(OLNode));
p->i = i;
p->j = j;
p->e = e;
if (m.rhead[i] == NULL || m.rhead[i]->j > j)
{
p->right = m.rhead[i];
m.rhead[i] = p;
}
else
{
for (q = m.rhead[i]; q->right&&q->right->j < j; q = q->right);
p->right = q->right;
q->right = p;
}
if (m.chead[j] == NULL || m.chead[j]->i > i)
{
p->down = m.chead[j];
m.chead[j] = p;
}
else
{
for (q = m.chead[j]; q->down&&q->down->i < i; q = q->down);
p->down = q->down;
q->down = p;
}
}
return in;
}
ostream &operator<<(ostream &out, const CrossList &m)
{
int i, j, tot = 1;
OLNode *p;
int row[10001], col[10001], num[10001];
for (j = 1; j <= m.mu; j++)
{
p = m.rhead[j];
while (p)
{
row[tot] = p->i;
col[tot] = p->j;
num[tot] = p->e;
p = p->right;
tot++;
}
}
for (i = 1; i <= m.mu; i++)
{
for (j = 1; j <= m.nu; j++)
{
bool flag = 0;
for (int k = 1; k <= m.tu; k++)
if (i == row[k] && j == col[k])
{
out << num[k] << " ";
flag = 1;
break;
}
if (flag == 0)
out << 0 << " ";
}
out << endl;
}
return out;
}
CrossList::CrossList()
{
rhead = chead = NULL;
mu = nu = tu = 0;
}
CrossList::CrossList(const CrossList &m)
{
int i;
OLNode *p, *q = NULL, *q1 = NULL, *q2;
mu = m.mu;
nu = m.nu;
tu = m.tu;
rhead = (OLNode**)malloc((m.mu + 1) * sizeof(OLNode*));
chead = (OLNode**)malloc((m.nu + 1) * sizeof(OLNode*));
for (i = 1; i <= m.mu; i++)
rhead[i] = NULL;
for (i = 1; i <= m.nu; i++)
chead[i] = NULL;
for (i = 1; i <= m.mu; i++)
{
p = m.rhead[i];
while (p)
{
q = (OLNode*)malloc(sizeof(OLNode));
q->i = p->i;
q->j = p->j;
q->e = p->e;
if (!rhead[i])
rhead[i] = q1 = q;
else
q1 = q1->right = q;
if (!chead[q->j])
{
chead[q->j] = q;
q->down = NULL;
}
else
{
q2 = chead[q->j];
while (q2->down)
q2 = q2->down;
q2->down = q;
q->down = NULL;
}
p = p->right;
}
if (q)
q->right = NULL;
}
}
CrossList::~CrossList()
{
int i;
OLNode *p, *q;
for (i = 1; i <= mu; i++)
{
p = *(rhead + i);
while (p)
{
q = p;
p = p->right;
free(q);
}
}
free(rhead);
free(chead);
rhead = chead = NULL;
mu = nu = tu = 0;
}
CrossList &CrossList::operator=(const CrossList m)
{
int i;
OLNode *p, *q = NULL, *q1 = NULL, *q2;
if (rhead)
{
for (i = 1; i <= mu; i++)
{
p = *(rhead + i);
while (p)
{
q = p;
p = p->right;
free(q);
}
}
}
mu = m.mu;
nu = m.nu;
tu = m.tu;
rhead = (OLNode**)malloc((m.mu + 1) * sizeof(OLNode*));
chead = (OLNode**)malloc((m.nu + 1) * sizeof(OLNode*));
for (i = 1; i <= m.mu; i++)
rhead[i] = NULL;
for (i = 1; i <= m.nu; i++)
chead[i] = NULL;
for (i = 1; i <= m.mu; i++)
{
p = m.rhead[i];
while (p)
{
q = (OLNode*)malloc(sizeof(OLNode));
q->i = p->i;
q->j = p->j;
q->e = p->e;
if (!rhead[i])
rhead[i] = q1 = q;
else
q1 = q1->right = q;
if (!chead[q->j])
{
chead[q->j] = q;
q->down = NULL;
}
else
{
q2 = chead[q->j];
while (q2->down)
q2 = q2->down;
q2->down = q;
q->down = NULL;
}
p = p->right;
}
if (q)
q->right = NULL;
}
return *this;
}
CrossList CrossList::operator+(const CrossList &m)
{
int i, k;
OLNode *p, *pq = NULL, *pm, *pn;
OLNode **col = NULL;
CrossList Q;
Q.mu = mu;
Q.nu = nu;
Q.tu = 0;
Q.rhead = (OLNode**)malloc((Q.mu + 1) * sizeof(OLNode*));
Q.chead = (OLNode**)malloc((Q.nu + 1) * sizeof(OLNode*));
for (k = 1; k <= Q.mu; k++)
Q.rhead[k] = NULL;
for (k = 1; k <= Q.nu; k++)
Q.chead[k] = NULL;
col = (OLNode**)malloc((Q.nu + 1) * sizeof(OLNode*));
for (k = 1; k <= Q.nu; k++)
col[k] = NULL;
for (i = 1; i <= mu; i++)
{
pm = rhead[i];
pn = m.rhead[i];
while (pm&&pn)
{
if (pm->j < pn->j)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pm->j;
p->e = pm->e;
p->right = NULL;
pm = pm->right;
}
else if (pm->j > pn->j)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = pn->e;
p->right = NULL;
pn = pn->right;
}
else if (pm->e + pn->e)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = pm->e + pn->e;
p->right = NULL;
pm = pm->right;
pn = pn->right;
}
else
{
pm = pm->right;
pn = pn->right;
continue;
}
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
while (pm)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pm->j;
p->e = pm->e;
p->right = NULL;
pm = pm->right;
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
while (pn)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = pn->e;
p->right = NULL;
pn = pn->right;
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
}
for (k = 1; k <= Q.nu; k++)
if (col[k])
col[k]->down = NULL;
free(col);
return Q;
}
CrossList CrossList::operator-(const CrossList &m)
{
int i, k;
OLNode *p, *pq = NULL, *pm, *pn;
OLNode **col = NULL;
CrossList Q;
Q.mu = mu;
Q.nu = nu;
Q.tu = 0;
Q.rhead = (OLNode**)malloc((Q.mu + 1) * sizeof(OLNode*));
Q.chead = (OLNode**)malloc((Q.nu + 1) * sizeof(OLNode*));
for (k = 1; k <= Q.mu; k++)
Q.rhead[k] = NULL;
for (k = 1; k <= Q.nu; k++)
Q.chead[k] = NULL;
col = (OLNode**)malloc((Q.nu + 1) * sizeof(OLNode*));
for (k = 1; k <= Q.nu; k++)
col[k] = NULL;
for (i = 1; i <= mu; i++)
{
pm = rhead[i];
pn = m.rhead[i];
while (pm&&pn)
{
if (pm->j<pn->j)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pm->j;
p->e = pm->e;
p->right = NULL;
pm = pm->right;
}
else if (pm->j>pn->j)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = -pn->e;
p->right = NULL;
pn = pn->right;
}
else if (pm->e - pn->e)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = pm->e - pn->e;
p->right = NULL;
pm = pm->right;
pn = pn->right;
}
else
{
pm = pm->right;
pn = pn->right;
continue;
}
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
while (pm)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pm->j;
p->e = pm->e;
p->right = NULL;
pm = pm->right;
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
while (pn)
{
p = (OLNode*)malloc(sizeof(OLNode));
Q.tu++;
p->i = i;
p->j = pn->j;
p->e = -pn->e;
p->right = NULL;
pn = pn->right;
if (Q.rhead[i] == NULL)
Q.rhead[i] = pq = p;
else
{
pq->right = p;
pq = pq->right;
}
if (Q.chead[p->j] == NULL)
Q.chead[p->j] = col[p->j] = p;
else
{
col[p->j]->down = p;
col[p->j] = col[p->j]->down;
}
}
}
for (k = 1; k <= Q.nu; k++)
if (col[k])
col[k]->down = NULL;
free(col);
return Q;
}
CrossList CrossList::operator*(const CrossList &m)
{
int i, j, e;
OLNode *q, *p0, *q0, *q1=NULL, *q2;
CrossList Q;
Q.mu = mu;
Q.nu = m.nu;
Q.tu = 0;
Q.rhead = (OLNode**)malloc((Q.mu + 1) * sizeof(OLNode*));
Q.chead = (OLNode**)malloc((Q.nu + 1) * sizeof(OLNode*));
for (i = 1; i <= Q.mu; i++)
Q.rhead[i] = NULL;
for (i = 1; i <= Q.nu; i++)
Q.chead[i] = NULL;
for (i = 1; i <= Q.mu; i++)
for (j = 1; j <= Q.nu; j++)
{
p0 = rhead[i];
q0 = m.chead[j];
e = 0;
while (p0&&q0)
{
if (q0->i<p0->j)
q0 = q0->down;
else if (q0->i>p0->j)
p0 = p0->right;
else
{
e += p0->e*q0->e;
q0 = q0->down;
p0 = p0->right;
}
}
if (e)
{
Q.tu++;
q = (OLNode*)malloc(sizeof(OLNode));
q->i = i;
q->j = j;
q->e = e;
q->right = NULL;
q->down = NULL;
if (!Q.rhead[i])
Q.rhead[i] = q1 = q;
else
q1 = q1->right = q;
if (!Q.chead[j])
Q.chead[j] = q;
else
{
q2 = Q.chead[j];
while (q2->down)
q2 = q2->down;
q2->down = q;
}
}
}
return Q;
}
CrossList CrossList::operator!()
{
int u, i;
OLNode **head, *p, *q, *r;
CrossList T = *this;
u = mu;
mu = nu;
nu = u;
head = rhead;
rhead = chead;
chead = head;
for (u = 1; u <= mu; u++)
{
p = rhead[u];
while (p)
{
q = p->down;
i = p->i;
p->i = p->j;
p->j = i;
r = p->down;
p->down = p->right;
p->right = r;
p = q;
}
}
return T;
}
About The Author
