数据结构实验报告

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