分享
 
 
 

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

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

如果你细想想,就会发现,非零元节点如果没有指示位置的域,那么做加法和乘法时,为了确定节点的位置,每次都要遍历行和列的链表。因此,为了运算效率,这个域是必须的。为了看出十字链表和单链表的差异,我从单链表派生出十字链表,这需要先定义一种新的结构,如下:

class MatNode

{

public:

int data;

int row, col;

union { Node<MatNode> *down; List<MatNode> *downrow; };

};

另外,由于这样的十字链表是由多条单链表拼起来的,为了访问每条单链表的保护成员,要声明十字链表类为单链表类的友元。即在class List的声明中添加friend class Matrix;

稀疏矩阵的定义和实现

#ifndef Matrix_H

#define Matrix_H

#include "List.h"

class MatNode

{

public:

int data;

int row, col;

union { Node<MatNode> *down; List<MatNode> *downrow; };

MatNode(int value = 0, Node<MatNode> *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<MatNode>

{

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<MatNode> *q;

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

{

q = first->data.downrow;

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

delete q;

}

List<MatNode>::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<MatNode> *p = first, *t;

List<MatNode> *q;

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

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

{

q = new List<MatNode>;

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>(matnode);

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

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

q->LastInsert(t);

}

}

void Print()

{

List<MatNode> *q = first->data.downrow;

cout << endl;

while (q != NULL)

{

cout << *q;

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

}

}

Matrix & Add(Matrix &matB)

{

//初始化赋值辅助变量

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

Node<MatNode> *pA, *pB;

Node<MatNode> **pAT = new Node<MatNode>*[col + 1];

Node<MatNode> **pBT = new Node<MatNode>*[matB.col + 1];

List<MatNode> *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)

{

qA->pGetPrior()->link = pB;

qB->pGetPrior()->link = 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;

pB = pB->link;

}

}

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语言版)》将它和广义表放在一章还是合理的。其实十字链表不是很难,就是很烦人;并且,如果不是数值运算,基本很少用到矩阵,就算是用到矩阵运算,在矩阵规模不大的时候,可以用二维数组代替十字链表。从历届考研题来看,这部分几乎没有题,原因就是麻烦(你写起来麻烦,他批起来也麻烦)、不常用、算法固定没新意。所以,你要是闹心,这部分跳过去也可以。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有