数据结构实验报告
KMP算法
GetNextval（）
由t求出nextval的值
KMPIndexpro（）
17
数据结构实验报告
改进后的KMP算法
3、实验数据与结果
2.4实验4(exp6-4)
1、题目
假设n*n的稀疏矩阵A采用三元组表示，设计一个程序exp6-4.cpp实现如下功能
（1） 生成如下两个稀疏矩阵的三元组a，b
1 0 3 0 3 0 0 0 0 1 0 0 0 4 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 2
（2） 输出a转置矩阵的三元组； （3） 输出a+b的三元组
18
数据结构实验报告
（4） 输出a*b的三元组
2、算法设计
(1) 设计思路
用一个结构体创建三元组，加法只需要将行号和列号相同的数相加即可，如果连个数都
是零，就可以不必计算，乘法的话可以根据矩阵乘法的规则，用循环求行和列的和，得出结果。转置矩阵的算法类似，先理解转置矩阵的意思，然后交换行号和列号即可。
(2) 程序关系图
CreatMatDispMatmainTransMatMatAddGetValueMatMul
(3) 函数功能描述 CreateMat（）
19
数据结构实验报告
创建稀疏矩阵的三元组表示法 DispMat（）
输出矩阵 TransMat（）
20