# 数据结构学习（C++）——稀疏矩阵（十字链表【2】） (转)

class MatNodeXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

{

public:

int data;

int row, col;

union { Node *down; List *downrow; };

};

### 稀疏矩阵的定义和实现

#ifndef Matrix_H

#define Matrix_H

#include "List.h"

class MatNode

{

public:

int data;

int row, col;

union { Node *down; List *downrow; };

MatNode(int value = 0, Node *p = NULL, int i = 0, int j = 0)

: data(value), down(p), row(i), col(j) {}

friend ostream & operator << (ostream & strm, MatNode &mtn)

{

stRM << '(' << mtn.row << ',' << mtn.col << ')' << mtn.data;

return strm;

}

};

class Matrix : List

{

public:

Matrix() : row(0), col(0), num(0) {}

Matrix(int row, int col, int num) : row(row), col(col), num(num) {}

~Matrix() { MakeEmpty(); }

void MakeEmpty()

{

List *q;

while (first->data.downrow != NULL)

{

q = first->data.downrow;

first->data.downrow = q->first->data.downrow;

delete q;

}

List::MakeEmpty();

row = col = num = 0;

}

void Input()

{

if (!row) { cout << "输入矩阵行数："; cin >> row; }

if (!col) {  cout << "输入矩阵列数："; cin >> col; }

if (!num) { cout << "输入非零个数："; cin >> num; }

if (!row || !col || !num) return;

cout << endl << "请按顺序输入各个非零元素，以列序为主，输入0表示本列结束" << endl;

int i, j, k, v;//i行数 j列数 k个非零元 v非零值

Node *p = first, *t;

List *q;

for (j = 1; j <= col; j++) LastInsert(MatNode(0, NULL, 0, j));

for (i = 1; i <= row; i++)

{

q = new List;

q->first->data.row = i;

p->data.downrow = q;

p = q->first;

}

j = 1; q = first->data.downrow; First(); t = pNext();

for (k = 0; k < num; k++)

{

if (j > col) break;

cout << endl << "输入第" << j << "列非零元素" << endl;

cout << "行数："; cin >> i;

if (i < 1 || i > row) { j++; k--; q = first->data.downrow; t = pNext(); continue; }

cout << "非零元素值"; cin >> v;

if (!v)  { k--; continue; }

MatNode matnode(v, NULL, i, j);

p = new Node(matnode);

t->data.down = p; t = p;

while (q->first->data.row != i) q = q->first->data.downrow;

q->LastInsert(t);

}

}

void Print()

{

List *q = first->data.downrow;

cout << endl;

while (q != NULL)

{

cout << *q;

q = q->first->data.downrow;

}

}

{

//初始化赋值辅助变量

if (row != matB.row || col != matB.col || matB.num == 0) return *this;

Node *pA, *pB;

Node **pAT = new Node*[col + 1];

Node **pbt = new Node*[matB.col + 1];

List *qA = pGetFirst()->data.downrow, *qB = matB.pGetFirst()->data.downrow;

First(); matB.First();

for (int j = 1; j <= col; j++)

{

pAT[j] = pNext();

pBT[j] = matB.pNext();

}

//开始

for (int i = 1; i <= row; i++)

{

qA->First(); qB->First();

pA = qA->pNext(); pB = qB->pNext();

while (pA != NULL && pB !=NULL)

{

if (pA->data.col == pB->data.col)

{

pA->data.data += pB->data.data;

pBT[pB->data.col]->data.down = pB->data.down; qB->Remove();

if (!pA->data.data)

{

pAT[pA->data.col]->data.down = pA->data.down;

qA->Remove();

}

else

{

pAT[pA->data.col] = pA;

qA->pNext();

}

}

else

{

if (pA->data.col > pB->data.col)

{

pBT[pB->data.col]->data.down = pB->data.down;

qB->pRemove();

pB->data.down = pAT[pB->data.col]->data.down;

pAT[pB->data.col]->data.down = pB;

pAT[pB->data.col] = pB;

qA->InsertBefore(pB);

}

else if (pA->data.col < pB->data.col)

{

pAT[pA->data.col] = pA;

qA->pNext();

}

}

pA = qA->pGet();pB = qB->pGet();

}

if (pA == NULL && pB != NULL)

{

while (pB != NULL)

{

pBT[pB->data.col]->data.down = pB->data.down;

pB->data.down = pAT[pB->data.col]->data.down;

pAT[pB->data.col]->data.down = pB;

pAT[pB->data.col] = pB;

}

}

if (pA !=NULL)

{

while (qA->pGet() != NULL)

{

pAT[pA->data.col] = pA;

qA->pNext();

}

}

qA = qA->first->data.downrow; qB = qB->first->data.downrow;

}

delete []pAT; delete []pBT;
return *this;

}

private:

int row, col, num;

};

#endif

【说明】对于十字链表来说，只要记住对每个节点的操作，要同时考虑它的两个指针域，那么，各种算法的理解都不是很难。比如说矩阵加法，“两个矩阵相加和两个一元多项式相加极为相似，所不同的是一元多项式只有一个变元（指数项），而矩阵中每个非零元有两个变元（行值和列值），每个节点既在行表中又在列表中，致使插入和删除节点时指针的修改稍为复杂，故需要更多的辅助指针。”（《数据结构（C语言版）》）其实private的row等可以放在首行的头节点里的，但为了清晰一点（本来就够乱了），我把他们单立出来了。另外，很多地方考虑不是很周全，要是不按照注明的要求使用，很容易就会出错。

【后记】按理说，十字链表应该不算是线性链式结构，按照原书的安排，放在链表这章不是很合适；《数据结构（C语言版）》将它和广义表放在一章还是合理的。其实十字链表不是很难，就是很烦人；并且，如果不是数值运算，基本很少用到矩阵，就算是用到矩阵运算，在矩阵规模不大的时候，可以用二维数组代替十字链表。从历届考研题来看，这部分几乎没有题，原因就是麻烦（你写起来麻烦，他批起来也麻烦）、不常用、算法固定没新意。所以，你要是闹心，这部分跳过去也可以。

• 博文量
3984
• 访问量
7338940