数据结构-资源试题库及解析《数据结构》期末考试试卷B卷-简答题2-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷B卷-简答题2 主讲：章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷B中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第2题。 如下所示的稀疏矩阵采用列优先的顺序存储，请完成压缩存储的三元组表。 这道题5分。 该矩阵是一个5行5列，共25个数据，其中非零元素总共5个，远远少于0元素的个数，所以它是一个稀疏矩阵。为了节约存储空间，我们可以采用三元组表来存储稀疏矩阵。 幻灯片 4 三元组表存储稀疏矩阵的时候，我们要注意三点： 1、三元组表只存储稀疏矩阵中非0元素，而0元素不用存储。 2、存放非0元素的时候，每个非0元素需要存放3个信息：非0元素的值v，非0元素的行号i，非0元素的列号j。 3、存放的时候可以按行优先的顺序存放，也可以按列优先的顺序存放。 本题要求采用列优先的顺序存储，所以先存放第一列的非0元素的信息，接着存放第二列的非0元素的信息，第三列的元素全部为0，不用存放，然后存放第四列的非0元素的信息，最后存放第五列的非0元素的信息。 第一列的非0元素是3，3的行号i是1，列号j是0，值v是3。 第二列的非0元素是4，4的行号i是2，列号j是1，值v是4。 第三列没有非0元素存放。 第四列的非0元素有2个数据，8和5。 一定要先存放8，8的行号i是0，列号j是3，值v是8。 再存放5，5的行号i是4，列号j是3，值v是5。 第五列的非0元素是2，2的行号i是2，列号j是4，值v是2。 这就是稀疏矩阵的三元组表按列优先的最终存储结果。我们要注意，矩阵的行号i和列号j都是从0开始编号的。 稀疏矩阵的三元组表中，如果采用列优先存储，它存放的顺序一定按列号j从小到大排列：比如列号j为0,1,3,3,4；如果列号j相同，行号i就必须从小到大排列：比如列号j为3时，有2个元素，但是行号i是0的元素排在行号i为4的元素前面。 幻灯片 5 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。