Dotcpp  >  编程题库  >  数据结构-采用十字链表存储的稀疏矩阵
题目 1695:

数据结构-采用十字链表存储的稀疏矩阵

时间限制: 3s 内存限制: 96MB 提交: 401 解决: 262

题目描述

当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储的结构来表示三元组的线性表了。因此,在这种情况下,采用链式存储结构表示三元组更为恰当。十字链表就是能够实现这样功能的一种数据结构。
在十字链表中,每个非零元可以用一个包含5个域的结点表示。其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值,向右域right用来链接同一行中下一个非零元,而向下域down用来链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表,同一列的非零元通过down域链接成一个线性链表。每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵通过这样的结构形成了一个十字交叉的链表。
稀疏矩阵的十字链表类型可以描述如下:
十字链表存储的稀疏矩阵
下面是建立稀疏矩阵十字链表的算法描述:
十字链表存储的稀疏矩阵2
给出一个稀疏矩阵,请将其存储到一个十字链表中,并将存储完毕的矩阵输出。

输入格式

输入的第一行是两个整数r和c(r<200, c<200, r*c <= 12500),分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行,每行有c个整数,用空格隔开,表示稀疏矩阵的各个元素。

输出格式

输出读入的矩阵。输出共有r行,每行有c个整数,每个整数后输出一个空格。请注意行尾输出换行。

样例输入

5 6
0 18 0 0 0 0
0 0 67 0 0 0
0 0 0 0 0 41
0 0 47 62 0 0
0 0 0 0 0 35

样例输出

0 18 0 0 0 0 
0 0 67 0 0 0 
0 0 0 0 0 41 
0 0 47 62 0 0 
0 0 0 0 0 35 

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签