[題目分析]設稀疏矩陣的非零元素的三元組以行序為主存儲在三元組表中矩陣的相加是對應元素的相加對兩非零元素相加若行號不等則行號大者是結果矩陣中的非零元素若行號相同則列號大者是結果中一非零元素若行號列號相同若對應元素值之和為零不予存儲否則作為新三元組存到三元組表中題目中要求時間復雜度為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）
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23038.html
