文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 法律资料 > 数据结构学习(C )稀疏矩阵(十字链表1)
侵权投诉

数据结构学习(C )稀疏矩阵(十字链表1)

数据结构学习(C )稀疏矩阵(十字链表1)

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

happycock(原作) 转自 CSDN

先说说什么叫稀疏矩阵。你说,这个问题很简单吗,那你一定不知道中国学术界的嘴皮子仗,对一个字眼的“抠”将会导致两种相反的结论。这是清华2000年的一道考研题:“表示一个有1000个顶点,1000条边的有向图的邻接矩阵有多少个矩阵元素?是否稀疏矩阵?”如果你是个喜欢研究出题者心理活动的人,你可以看出这里有两个陷阱,就是让明明会的人答错,我不想说出是什么,留给读者思考。姑且不论清华给的标准答案是什么,那年的参考书是严蔚敏的《数据结构(C语言版)》,书上对于稀疏矩阵的定义是这样的:“非零元较零元少(注:原书下文给出了大致的程度),且分布没有一定规律”,照这个说法,那题的答案应该是不一定是稀疏矩阵,因为可能是特殊矩阵(非零元分布有规律)。自从2002年换参考书后,很多概念都发生了变化,最明显的是从多少开始计数(0还是1),从而导致的是空树的高度变成了-1,只有一个根节点的树高度是0。很不幸的是树高的问题几乎年年都考,在你下笔的时候,总是犯点嘀咕,总不是一朝天子一朝臣吧,会不会答案是个兼容版本?然后,新参考书带的习题集里引用了那道考研题,答案是是稀疏矩阵。你也许会惊讶这年头咸鱼都会游泳了,但这个答案和书并不矛盾,因为在这本黄皮书里,根本就没有什么特殊矩阵,自然就一定是稀疏矩阵了。其实,这两本书在这个问题上也没什么原则上的问题,C版的是从数据结构实现区分出特殊矩阵和稀疏矩阵,毕竟他们实现起来很不相同;新书一股脑把非零元少的矩阵都当成稀疏矩阵,当你按照这种思路做的时候就会发现,各种结构特殊的非零元很少的矩阵,如果用十字链表来储存的话,比考虑到它的特殊结构得出的特有储存方法,仅仅是浪费了几个表头节点和一些指针域,再有就是一些运算效率的降低。从我个人角度讲,我更喜欢多一些统一,少一些特别,即使牺牲一点效率;所以在这一点上我赞同新参考书的做法。而在计数起点上,我更喜欢原来的做法;毕竟,研究数据结构要考虑人的思考习惯,而不是计算机喜欢什么;你非得说表中的第一个元素是第0个,空树的高是-1,怎么不让人心里起疙瘩。数据结构是人们构造算法时思维和计算机实现的桥梁、中介,它应该符合人的思考习惯,即使在它实现的时候内部做了某些转换。开始废话了这么多,希望没打消了你往下看的心情,好,言归正传。

这里的十字链表是这样构成的:用链表模拟矩阵的行(或者列,这可以根据个人喜好来定),然后,再构造代表列的链表,将每一行中的元素节点插入到对应的列中去。书中为了少存几个表头节点,将行和列的表头节点合并到了一起——实际只是省了几个指针域,如果行和列数不等,多余的数据域就把这点省出的空间又给用了。这点小动作让我着实废了半天劲,个人感觉,优点不大,缺点不少,不如老老实实写得象个十字链表,让人也好看一些,这是教科书,目的是教学。实在看得晕的人,参阅C版的这部分内容,很清晰。我也不会画图,打个比方吧:这个十字链表的逻辑结构就像是一个围棋盘(没见过,你就想一下苍蝇拍,这个总见过吧),而非零元就好像是在棋盘上放的棋子,总共占的空间就是,确定那些线的表头节点和那些棋子代表的非零元节点。最后,我们用一个指针指向这个棋盘,这个指针就代表了这个稀疏矩阵。

现在,让我们看看非零元节点最少需要哪几个域,data必须的,down、right把线画下去,好像不需要别的了。再看看表头节点,由于是链表的表头节点,所以就和后边的节点一样了。然后,行链表和列链表的表头节点实际上也各构成了一个链表,我们给他们添加一个公有的表头节点。最后,通过指向这个行列链表表头构成的链表的公有的表头节点的指针,我们就可以访问稀疏矩阵了。

好像和书上的不一样——非零元节点没了指示位置的I、j,实际上,对于确定非零元在矩阵中的位置,I、j不是必须的,看着围棋盘你就会很清楚。但是很不幸,不是把他们存起来就万事大吉了,最起码,必须考虑加法和乘法的效率,请你想想如果用上面的那种结构,如何完成。考

第1页

你可能喜欢

  • 人类辅助生殖技术
  • 会计专业
  • 党务公开内容
  • 稀疏矩阵的三元组表示
  • 邻接矩阵
  • 外国人学中文
  • 矩阵加法

热门文档

相关文档

  • 数据结构课程设计 报告 (十字链表实现稀疏矩阵的加法)

    MulSMatrix(&M,&N); //求稀疏矩阵 M 和 N 之积 }ADT SparseMatrix 2、存储结构选择 采用十字链表存储稀疏矩阵, 它是稀疏矩阵链式表示的一种较好的表示方法。...

  • 稀疏矩阵 引用 十字链表 运算

    稀疏矩阵 引用 十字链表 运算_信息与通信_工程科技_专业资料。课程设计稀疏...1.3课程设计目的其目的是让我们在学习完C、 数据结构等课程基础上, 掌握多维...

  • 稀疏矩阵十字链表的存储

    电子信息学院 实验报告书课 程名:题目: 数据结构稀疏矩阵十字链表的存储 设计 BX1001 41 赵艳 实验类别: 班学姓级: 号: 名: 2011 年 10 月 24 日 《...

  • 实验报告---数据结构课程设计稀疏矩阵的应用

    学习态度及平 技术水平与实 时成绩(30) 际能力(20) 创新 (5) 说明书(...21 稀疏矩阵的应用 摘 要 本课程设计主要实现在三元组存储结构与十字链表存储...

  • 数据结构课程设计之稀疏矩阵实现与应用1

    数据结构课程设计报告题目:十字链表成为存储结构,实现稀疏矩阵的求和运算 学生姓名:张旋 班级:软件三班 学号:201213040304 指导教师: 吴小平 一、需求分析 1.问题...

  • 采用十字链表表示稀疏矩阵,并实现矩阵的加法运算

    主要是运用所学知识,用十字链表的方法去表示稀疏矩阵,并使之可以在两矩阵间进行...(1)结构体和共用体的定义 ) #include<stdio.h> #include<malloc.h> #...

  • 稀疏矩阵相乘

    稀疏矩阵相乘_计算机软件及应用_IT/计算机_专业资料。C++语言用十字链表表示洗漱矩阵...结构学得不 好,但是数据结构可以说是计算机里一门基础课程,对于以后的学习尤为...

  • 稀疏矩阵的存储实现

    《数据结构》课程设计说明书 摘 要 本课程设计在学习数据结构的前提下,运用c语言,对稀疏矩阵进 行三元组存储和十字链表存储, 并完成稀疏矩阵的转置, 相加, 相乘...

  • 拓展阅读4——稀疏矩阵的十字链表

    拓展阅读4——稀疏矩阵的十字链表_计算机软件及应用_IT/计算机_专业资料。稀疏矩阵的十字链表 1.建立稀疏矩阵 A 的十字链表首先输入的信息是:m(A 的行数) ,n(A...

  • 数据结构-稀疏矩阵-实验报告与代码

    数据结构-稀疏矩阵-实验报告与代码_理学_高等教育_教育...// 定义十字链表对象结构体 template <class P> bool...衡水中学文科学霸高中数学笔记 清华附中文科学霸高...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email