2022年稀疏矩阵(十字链表宣贯 .pdf

《2022年稀疏矩阵(十字链表宣贯 .pdf》由会员分享，可在线阅读，更多相关《2022年稀疏矩阵(十字链表宣贯 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构学习（C+ ） 稀疏矩阵（十字链表【1】 ）happycock （原作）转自CSDN先说说什么叫稀疏矩阵。你说， 这个问题很简单吗，那你一定不知道中国学术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。这是清华2000 年的一道考研题：“表示一个有 1000 个顶点， 1000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？”如果你是个喜欢研究出题者心理活动的人，你可以看出这里有两个陷阱，就是让明明会的人答错，我不想说出是什么，留给读者思考。姑且不论清华给的标准答案是什么，那年的参考书是严蔚敏的数据结构（ C 语言版），书上对于稀疏矩阵的定义是这样的：“非零元较零元少（

2、注：原书下文给出了大致的程度），且分布没有一定规律”，照这个说法，那题的答案应该是不一定是稀疏矩阵，因为可能是特殊矩阵（非零元分布有规律）。自从2002 年换参考书后，很多概念都发生了变化，最明显的是从多少开始计数（0 还是 1），从而导致的是空树的高度变成了1，只有一个根节点的树高度是0。很不幸的是树高的问题几乎年年都考，在你下笔的时候，总是犯点嘀咕， 总不是一朝天子一朝臣吧，会不会答案是个兼容版本？然后，新参考书带的习题集里引用了那道考研题，答案是是稀疏矩阵。你也许会惊讶这年头咸鱼都会游泳了，但这个答案和书并不矛盾，因为在这本黄皮书里，根本就没有什么特殊矩阵，自然就一定是稀疏矩阵了。其实，

3、这两本书在这个问题上也没什么原则上的问题，C 版的是从数据结构实现区分出特殊矩阵和稀疏矩阵，毕竟他们实现起来很不相同；新书一股脑把非零元少的矩阵都当成稀疏矩阵，当你按照这种思路做的时候就会发现，各种结构特殊的非零元很少的矩阵，如果用十字链表来储存的话，比考虑到它的特殊结构得出的特有储存方法，仅仅是浪费了几个表头节点和一些指针域，再有就是一些运算效率的降低。从我个人角度讲，我更喜欢多一些统一，少一些特别，即使牺牲一点效率；所以在这一点上我赞同新参考书的做法。而在计数起点上，我更喜欢原来的做法；毕竟，研究数据结构要考虑人的思考习惯，而不是计算机喜欢什么；你非得说表中的第一个元素是第0 个，空树的高

4、是1，怎么不让人心里起疙瘩。数据结构是人们构造算法时思维和计算机实现的桥梁、中介，它应该符合人的思考习惯，即使在它实现的时候内部做了某些转换。开始废话了这么多，希望没打消了你往下看的心情，好，言归正传。这里的十字链表是这样构成的：用链表模拟矩阵的行（或者列， 这可以根据个人喜好来定），然后， 再构造代表列的链表，将每一行中的元素节点插入到对应的列中去。书中为了少存几个表头节点，将行和列的表头节点合并到了一起实际只是省了几个指针域，如果行和列数不等，多余的数据域就把这点省出的空间又给用了。这点小动作让我着实废了半天劲，个人感觉， 优点不大，缺点不少， 不如老老实实写得象个十字链表，让人也好看一些

5、，这是教科书， 目的是教学。实在看得晕的人，参阅C 版的这部分内容，很清晰。我也不会画图，打个比方吧：这个十字链表的逻辑结构就像是一个围棋盘（没见过，你就想一下苍蝇拍，这个总见过吧），而非零元就好像是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。最后，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。现在，让我们看看非零元节点最少需要哪几个域，data 必须的， down 、right 把线画下去，好像不需要别的了。再看看表头节点，由于是链表的表头节点，所以就和后边的节点一样了。然后，行链表和列链表的表头节点实际上也各构成了一个链表，我们给他们添加

6、一个公有的表头节点。最后， 通过指向这个行列链表表头构成的链表的公有的表头节点的指针，我们就可以访问稀疏矩阵了。好像和书上的不一样非零元节点没了指示位置的I、j，实际上，对于确定非零元在矩阵中的位置， I、j 不是必须的，看着围棋盘你就会很清楚。但是很不幸，不是把他们存起来就万事大吉了，最起码，必须考虑加法和乘法的效率，请你想想如果用上面的那种结构，如何完成。考名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 虑到到这里已经写了不

7、少字，我将实现部分放在下篇，今天该休息了。据结构学习（ C+ ）稀疏矩阵（十字链表【2】）如果你细想想，就会发现，非零元节点如果没有指示位置的域，那么做加法和乘法时，为了确定节点的位置，每次都要遍历行和列的链表。因此，为了运算效率，这个域是必须的。为了看出十字链表和单链表的差异，我从单链表派生出十字链表，这需要先定义一种新的结构，如下：class MatNode public: int data; int row, col; union Node *down; List *downrow; ; ;另外， 由于这样的十字链表是由多条单链表拼起来的，为了访问每条单链表的保护成员，要声明十字链表类为

8、单链表类的友元。即在class List 的声明中添加friend class Matrix; 稀疏矩阵的定义和实现#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 ostr

9、eam & operator (ostream & strm, MatNode &mtn) strm ( mtn.row , mtn.col ) mtn.data; return strm; ; class Matrix : List public: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - Matrix() : row(0), col(0), num(0) Matrix(int row, int col, int num

10、) : 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 row; if (!col) cout col; if (!num) cout

11、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;

12、 j = 1; q = first-data.downrow; First(); t = pNext(); for (k = 0; k col) break; cout endl 输入第 j 列非零元素 endl; cout i; if (i row) j+; k-; q = first-data.downrow; t = pNext(); continue; cout v; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - if

13、 (!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 first-data.downrow; Matrix & Add(Matrix &matB) /初始化

14、赋值辅助变量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+) pATj = pNext(); pBTj

15、 = matB.pNext(); /开始for (int i = 1; i First(); qB-First(); pA = qA-pNext(); pB = qB-pNext(); while (pA != NULL & pB !=NULL) if (pA-data.col = pB-data.col) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - pA-data.data += pB-data.data; pBTpB-data.col-data.down = pB-data.down; qB-Remove(); if (!pA-data.data) pATpA-data.col-data.down = pA-data.down; qA-Remove(); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -