再发个稀疏矩阵转置和乘法的代码，前几天才写完。
写成模板了，转置和乘法都没问题。其他如修改，删除，添加，都没检查错误，你们可以找找看
程序代码：
/*******************************************************
*
* 稀疏矩阵运算
*
* by Bghost
*
* 2010-06-23
*
*
*
*******************************************************/
#define MAX_SIZE 500
template<class T>
class triad //三元组
{
public:
T value; //值
int X; //行
int Y; //列
public:
triad(){}
triad(int x, int y, T v)
{
X = x;
Y = y;
value = v;
}
};
template<class T>
class ArrayMatrix
{
public:
triad<T> *buffer; //三元组缓冲区
int *indexRow; //行首非0元位置表
int *numRow; //每行元素数
int rows; //行数
int cols; //列数
int size; //非零元素个数
public:
ArrayMatrix(int r, int c);
~ArrayMatrix();
void printMatrix(); //输出
void inputMatrix(); //输入
bool addElem(triad<T> *e); //添加元素
bool editElem(triad<T> *e); //编辑元素
bool deleteElem(triad<T> *e); //删除元素
int length(); //返回非零元素个数
int getRows(); //返回矩阵行数
int getCols(); //返回矩阵列数
void countIndexRow();
bool plus(ArrayMatrix *m); //加
bool minus(ArrayMatrix *m); //减
bool multiply(ArrayMatrix *m); //乘
bool transpose(); //转置
};
template<class T>
ArrayMatrix<T>::ArrayMatrix(int r, int c)
{
rows = r;
cols = c;
buffer = new triad<T>[(rows*cols) / 2];
indexRow = new int[rows];
numRow = new int[rows];
size = 0;
for(int i = 0; i < rows; i++)
{
indexRow[i] = 0;
numRow[i] = 0;
}
}
template<class T>
ArrayMatrix<T>::~ArrayMatrix()
{
}
template<class T>
void ArrayMatrix<T>::printMatrix()
{
int index = 0;
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
if(buffer[index].X == i && buffer[index].Y == j)
{
cout<<buffer[index].value<<" ";
index++;
}else
{
cout<<"0 ";
}
}
cout<<endl;
}
}
template<class T>
void ArrayMatrix<T>::countIndexRow()
{
for(int i = 0; i < rows; i++)
{
indexRow[i] = 0;
}
for(int i = 1; i < rows; i++)
{
indexRow[i] = indexRow[i-1] + numRow[i-1];
}
}
template<class T>
void ArrayMatrix<T>::inputMatrix()
{
cout<<"请输入矩阵"<<endl;
T num = 0;
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
cin>>num;
if(num != 0)
{
addElem(new triad<T>(i, j, num));
}
}
}
countIndexRow();
}
template<class T>
bool ArrayMatrix<T>::addElem(triad<T> *e)
{
buffer[size].value = e->value;
buffer[size].X = e->X;
buffer[size].Y = e->Y;
numRow[e->X]++;
size++;
return true;
}
template<class T>
bool ArrayMatrix<T>::editElem(triad<T> *e)
{
bool find = false;
int end = ;
for(int i = indexRow[e->X]; i < indexRow[e->X] + numRow[e->X]; i++)
{
if(e->Y == buffer[i].Y)
{
buffer[i].value = e->value;
find = true;
break;
}
}
return find;
}
template<class T>
bool ArrayMatrix<T>::deleteElem(triad<T> *e)
{
bool find = false;
for(int i = indexRow[e->X]; i < indexRow[e->X] + numRow[e->X]; i++)
{
if(e->Y == buffer[i].Y)
{
for(int j = i; j < size-1; j++)
{
buffer[j] = buffer[j+1];
}
size--;
find = true;
if(numRow[e->X] == 1)
{
indexRow[e->X] = indexRow[e->X - 1];
}
for(int j = e->X+1; j < rows; j++)
{
if(indexRow[j] >= 0)
{
indexRow[j]--;
}
}
break;
}
}
return find;
}
template<class T>
int ArrayMatrix<T>::length()
{
return size;
}
template<class T>
int ArrayMatrix<T>::getRows()
{
return rows;
}
template<class T>
int ArrayMatrix<T>::getCols()
{
return cols;
}
template<class T>
bool ArrayMatrix<T>::plus(ArrayMatrix<T> *m)
{
int i = 0;
int j = 0;
int k = 0;
triad<T> *tempbuffer = new triad<T>[rows*cols];
for(int i = 0; i < rows; i++)
{
numRow[i] = 0;
}
while(i < size || j < m->length())
{
if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y == m->buffer[j].Y)
{
tempbuffer[k].value = buffer[i].value + m->buffer[j].value;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
k++;
i++;
j++;
}else if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y < m->buffer[j].Y)
{
tempbuffer[k].value = buffer[i].value;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
i++;
k++;
}else if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y > m->buffer[j].Y)
{
tempbuffer[k].value = m->buffer[j].value;
tempbuffer[k].X = m->buffer[j].X;
tempbuffer[k].Y = m->buffer[j].Y;
j++;
k++;
}else if(i == size)
{
tempbuffer[k].value = m->buffer[j].value;
tempbuffer[k].X = m->buffer[j].X;
tempbuffer[k].Y = m->buffer[j].Y;
j++;
k++;
}else if(j == m->length())
{
tempbuffer[k].value = buffer[i].value;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
i++;
k++;
}
numRow[tempbuffer[k].X]++;
}
delete buffer;
buffer = tempbuffer;
size = k;
countIndexRow();
}
template<class T>
bool ArrayMatrix<T>::minus(ArrayMatrix<T> *m)
{
int i = 0;
int j = 0;
int k = 0;
triad<T> *tempbuffer = new triad<T>[rows*cols];
for(int i = 0; i < rows; i++)
{
numRow[i] = 0;
}
while(i < size || j < m->length())
{
if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y == m->buffer[j].Y)
{
tempbuffer[k].value = buffer[i].value - m->buffer[j].value;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
k++;
i++;
j++;
}else if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y < m->buffer[j].Y)
{
tempbuffer[k].value = buffer[i].value - 0;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
i++;
k++;
}else if(i < size && j < m->length() && buffer[i].X == m->buffer[j].X && buffer[i].Y > m->buffer[j].Y)
{
tempbuffer[k].value = 0 - m->buffer[j].value;
tempbuffer[k].X = m->buffer[j].X;
tempbuffer[k].Y = m->buffer[j].Y;
j++;
k++;
}else if(i == size)
{
tempbuffer[k].value = 0 - m->buffer[j].value;
tempbuffer[k].X = m->buffer[j].X;
tempbuffer[k].Y = m->buffer[j].Y;
j++;
k++;
}else if(j == m->length())
{
tempbuffer[k].value = buffer[i].value - 0;
tempbuffer[k].X = buffer[i].X;
tempbuffer[k].Y = buffer[i].Y;
i++;
k++;
}
numRow[tempbuffer[k].X]++;
}
delete buffer;
buffer = tempbuffer;
size = k;
countIndexRow();
}
template<class T>
bool ArrayMatrix<T>::multiply(ArrayMatrix<T> *m)
{
if(cols != m->rows)
{
return false;
}
int tempRows = rows;
int tempCols = m->cols;
int tempSize = 0;
triad<T> *tempBuffer = new triad<T>[tempRows*tempCols ];
int *tempIndex = new int[tempRows];
int *tempNum = new int[tempRows];
if(size * m->size == 0)
{//结果为0矩阵
//处理
rows = tempRows;
cols = tempCols;
size = 0;
buffer = new triad<T>[1];
indexRow = new int[1];
numRow = new int[1];
indexRow[0] = 0;
numRow[0] = 0;
return true;
}
for(int i = 0; i < tempRows; i++)
{
T *result = new T[tempCols];
for(int j = 0; j < tempCols; j++)
{
result[j] = 0;
}
tempIndex[i] = tempSize;
for(int j = indexRow[i]; j < indexRow[i] + numRow[i]; j++)
{
triad<T> *a = &buffer[j];
for(int k = m->indexRow[a->Y]; k < m->indexRow[a->Y] + m->numRow[a->Y]; k++)
{
triad<T> *b = &m->buffer[k];
result[b->Y] += a->value * b->value;
}
}
//压缩存储
for(int j = 0; j < tempCols; j++)
{
if(result[j] != 0)
{
tempBuffer[tempSize].X = i;
tempBuffer[tempSize].Y = j;
tempBuffer[tempSize].value = result[j];
tempSize++;
tempNum[i]++;
}
}
}
rows = tempRows;
cols = tempCols;
size = tempSize;
delete buffer;
delete numRow;
numRow = tempNum;
buffer = tempBuffer;
countIndexRow();
return true;
}
template<class T>
bool ArrayMatrix<T>::transpose()
{
triad<T> *tempBuffer = new triad<T>[rows*cols / 2];
int *tempIndex = new int[cols];
int *tempNum = new int[cols];
for(int i = 0; i < cols; i++)
{
tempIndex[i] = 0;
tempNum[i] = 0;
}
for(int i = 0; i < size; i++)
{
tempNum[buffer[i].Y]++;
}
for(int i = 0; i < cols-1; i++)
{
tempIndex[i+1] = tempIndex[i] + tempNum[i];
}
int *index = new int[cols];
for(int i = 0; i < cols; i++)
{
index[i] = tempIndex[i];
}
for(int i = 0; i < size; i++)
{
int j = index[buffer[i].Y];
tempBuffer[j].X = buffer[i].Y;
tempBuffer[j].Y = buffer[i].X;
tempBuffer[j].value = buffer[i].value;
index[buffer[i].Y]++;
}
delete buffer;
delete indexRow;
delete numRow;
buffer = tempBuffer;
indexRow = tempIndex;
numRow = tempNum;
int temp = rows;
rows = cols;
cols = temp;
return true;
}
