数据结构考研分类复习真题 第五章 答案[29]

[题目分析]设稀疏矩阵的非零元素的三元组以行序为主存储在三元组表中矩阵的相加是对应元素的相加对两非零元素相加若行号不等则行号大者是结果矩阵中的非零元素若行号相同则列号大者是结果中一非零元素若行号列号相同若对应元素值之和为零不予存储否则作为新三元组存到三元组表中题目中要求时间复杂度为O（m+n）因此需从两个三元组表的最后一个元素开始相加第一个非零元素放在A矩阵三元组表的第m+n位置上结果的三元组至多是m+n个非零元素最后若发生对应元素相加和为零的情况对三元组表中元素要进行整理以便使第一个三元组存放在下标的位置上

CONST maxnum=大于非零元素数的某个常量

TYPE tuple=RECORD

ijinteger velemtp

END

sparmattp=RECORD

munutuinteger

data: ARRAY[maxnum] OF tuple

END

PROC AddMatrix（VAR AsparmattpBsparmattp）

// 稀疏矩阵A和B各有m和n个非零元素以三元组表存储A的空间足够大本算法实现两个稀疏矩阵相加结果放到A中

L:=mp:=nk:=m+n// Lp为AB三元组表指针k为结果三元组表指针（下标）

Atu:=m+n// 暂存结果矩阵非零元素个数

WHILE（L≥）AND（p≥）DO

[CASE // 行号不等时行号大者的三元组为结果三元组表中一项

Adata[L]i>Bdata[p]iAdata[k]:=Adata[L]L:=L// A中当前项为结果项

Adata[L]i<Bdata[p]iAdata[k]:=Bdata[p]p:=p//B中当前项为结果当前项

Adata[L]i=Bdata[p]i

CASE //行号相等时比较列号

Adata[L]j>Bdata[p]jAdata[k]:=Adata[L]L:=L

Adata[L]j<Bdata[p]jAdata[k]:=Bdata[p]p:=p

Adata[L]j=Bdata[p]jIF Adata[L]v+Bdata[p]v≠ THEN

[Adata[L]v=Adata[L]v+ Bdata[p]v

Adata[k]:= Adata[L]]

L:=Lp:=p

ENDC //结束行号相等时的处理

ENDC //结束行号比较处理

k:=k //结果三元组表的指针前移（减）

]//结束WHILE循环

WHILE p> DO[Adata[k]:=Bdata[p]k:=kp:=p] //处理B的剩余部分

WHILE L> DO[Adata[k]:=Adata[L]k:=kL:=L] //处理A的剩余部分

IF k> THEN //稀疏矩阵相应元素相加时有和为零的元素因而元素总数<m+n

[FOR p:=k TO m+n DO A[pk+]:=A[p]// 三元组前移使第一个三元组的下标为

Atu=m+nk+] // 修改结果三元组表中非零元素个数

ENDP // 结束addmatrix

[算法讨论]算法中三元组的赋值是成组赋值可用行值列值和元素值的三个赋值句代替A和B的三元组表的当前元素的指针L和p在每种情况处理后均有修改而结果三元组表的指针k在CASE语句后统一处理（k:=k）算法在B的第一个元素大于A的最后一个元素时时间复杂度最佳为O（n）最差情况是每个元素都移动（赋值）了一次且出现了和为零的元素致使最后（m+nk+）个元素向前平移一次时间复杂度最差为O（m+n）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []