【文章內(nèi)容簡介】 例如。由num可算出轉(zhuǎn)置矩陣B的每行元素中第一個元素的初始位置序列cpot。，cpot中相應(yīng)元素將進行調(diào)整。 快速轉(zhuǎn)置算法的實現(xiàn)過程num cpot行位置的變化過程0101p0=1(3),21111+1=2p1=2(5),32322+1=3p2=3(1),4(4),5(6),63033+3=6p3=64146+0=6p4=6(2),7算法實現(xiàn)void FTrans_TSM(TSMatrix M,TSMatrix amp。T){ =,=,=。 int* num=new int[]。 //為向量num分配空間 int* cpot=new int[]。 //為向量cpot分配空間 int col,p,q,t。 if(!)return。 for(col=0。col。col++)num[col]=0。 for(t=1。t=。t++)++num[[t].j]。 //求每列中非零元素的個數(shù) cpot[0]=1。 //第0行的起始位置為1 for(col=1。col。col++)cpot[col]=cpot[col1]+num[col1]。 //求第col行的起始位置cpot[col] for(p=1。p=。p++) //通過一次性掃描求出轉(zhuǎn)置矩陣T { col=[p].j。 q=cpot[col]++。 [q].i=[p].j。 [q].j=[p].i。 [q].e=[p].e。 } delete[]num。 delete[]cpot。}算法分析在快速轉(zhuǎn)置操作函數(shù)FTrans_TSM()的算法中，比算法Trans_TSM()多使用了兩個輔助數(shù)組（num和cpot）的存儲空間，但是該算法的時間復(fù)雜度僅為O(nu+tu)，顯然比前者快了很多。6．三元組矩陣的加法運算假定矩陣M、N均為三元組表示的稀疏矩陣且具有相同的行數(shù)和列數(shù)，可對稀疏矩陣進行求和操作：A=M+N。算法思想[p],[q]：(1) (2) (3) 行、列都相等時求對應(yīng)元素的和。算法實現(xiàn)void Add_TSM(TSMatrix M,TSMatrix N,TSMatrixamp。 A){ Etype e。 int p=1,q=1,r=1。 while(p=amp。amp。q=) { if([p].i==[q].i) { if([p].j[q].j) [r++]=[p++]。 else if([p].j[q].j) [r++]=[q++]。 else { if(e=[p].e+[q].e) //如果和不為零則保存結(jié)果 { [r]=[p]。 [r++].e=e。 } p++。q++。 } } else if([p].i[q].i) [r++]=[p++]。 else [r++]=[q++]。}while(p=)[r++]=[p++]。while(q=)[r++]=[q++]。 =,=,=r1。}算法分析本算法的時間復(fù)雜度為O(+)，通過加法運算的函數(shù)調(diào)用可以實現(xiàn)稀疏矩陣的減法運算。7．三元組矩陣的減運算操作函數(shù)void Sub_TSM(TSMatrix M,TSMatrix N,TSMatrixamp。 A)實現(xiàn)三元組矩陣的減法運算A=MN。void Sub_TSM(TSMatrix M,TSMatrix N,TSMatrixamp。 A){ int p。 for(p=1。p=。p++) [p].e*=1。 Add_TSM(M,N,A)。}8．三元組矩陣的乘法（1）函數(shù)void Frpot(int rpot[],TSMatrix M)完成的操作是，求稀疏矩陣M中每行起始位置的向量rpot。void Frpot(int rpot[],TSMatrix M){ int* num=new int[]。 int raw,t。 for(raw=0。raw。raw++)num[raw]=0。 for(t=1。t=。t++)++num[[t].i]。 //求每行非零元素的個數(shù) rpot[0]=1。 //第0行的起始位置為1 for(raw=1。raw。raw++) rpot[raw]=rpot[raw1]+num[raw1]。 //求第raw行的起始位置rpot[raw] delete[]num。}（2）函數(shù)int Ffand(Etype amp。e,int i,int j,int rpot[],TSMatrix M)完成的操作是，求數(shù)組M中的元素a(i,j)到e，操作成功返回1，否則返回0。int Ffand(Etype amp。e,int i,int j,int rpot[],TSMatrix M){ int k=rpot[i]。 for(。k=amp。amp。([k].i==i)。k++) { if([k].j==j){ e=[k].e。 return 1。 } else if([k].jj) break。 } return 0。}（3）函數(shù)void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrixamp。 C)的功能是，實現(xiàn)三元組矩陣的乘法運算C=AB。void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrixamp。 C){ int i,j,k。 Etype s,e1,e2。 int *Anum=new int[]。 int *Bnum=new int[]。 Frpot(Anum,A)。 Frpot(Bnum,B)。 =。 =。 =0。 for(i=0。i。i++) for(j=0。j。j++) { s=0。 for(k=0。k。k++) { if(Ffand(e1,i,k,Anum,A)amp。amp。Ffand(e2,k,j,Bnum,B)) s+=e1*e2。 } if(s) { k=++。 [k].e=s。 [k].i=i。 [k].j=j。 } } delete[]Anum。 delete[]Bnum。}9．三元組矩陣運算的演示主程序程序中，首先以三元組順序結(jié)構(gòu)分別建立稀疏矩陣A和B，然后求出A的轉(zhuǎn)置矩陣C和快速轉(zhuǎn)置矩陣D，再分別求出：A與B的和E、A與B的差F、A與B的積G。并以矩陣形式顯示輸出每個矩陣的值。void main(){ TSMatrix A,B,C,D,E,F,G。 while(1) { cout輸入兩個行、列相同的矩陣：。 cout1求轉(zhuǎn)置與快速轉(zhuǎn)置，2矩陣的和與差，3矩陣的積.\n。 cout輸入三元組矩陣A：\n。 Create_TSM(A)。 cout輸入三元組矩陣B：\n。 Create_TSM(B)。 if((!=)||(!=)||(!=)) { cout維數(shù)不符合要求請重新輸入!\n。 continue。 } Trans_TSM(A,C)。 FTrans_TSM(A,D)。 coutA的轉(zhuǎn)置矩陣為:\n。 Print1_TSM(C)。 coutA的快速轉(zhuǎn)置矩陣為:\n。 Print1_TSM(D)。 Add_TSM(A,B,E)。 Sub_TSM(A,B,F)。 coutA+B的和為:\n。 Print1_TSM(E)。 coutAB的差為:\n。 Print1_TSM(F)。 Mult_TSM(A,B,G)。 coutA*B的積為:\n。 Print1_TSM(G)。 cout矩陣A為:\n。 Print1_TSM(A)。 cout矩陣B為:\n。 Print1_TSM(B)。 }}運行結(jié)果為：輸入兩個行、列相同的矩陣：1求轉(zhuǎn)置與快速轉(zhuǎn)置，2矩陣的和與差，3矩陣的積.輸入三元組矩陣A：請輸入行數(shù)和列數(shù):5 5↙輸入 i j e:0 2 9↙1 0 7↙1 2 7↙3 1 8↙4 2 9↙0 0 0↙輸入三元組矩陣B：請輸入行數(shù)和列數(shù):5 5↙輸入 i j e:0 1 7↙1 3 8↙2 0 9↙2 1 7↙2 4 9↙4 0 5↙0 0 0↙A的轉(zhuǎn)置矩陣為:0 7 0 0 00 0 0 8 09 7 0 0 90 0 0 0 00 0 0 0 0A的快速轉(zhuǎn)置矩陣為:0 7 0 0 00 0 0 8 09 7 0 0 90 0 0 0 00 0 0 0 0A+B的和為:0 7 9 0 07 0 7 8 09 7 0 0 90 8 0 0 05 0 9 0 0AB的差為:0 7 9 0 07 0 7 8 09 7 0 0 90 8 0 0 05 0 9 0 0A*B的積為:81 63 0 0 8163 98 0 0 630 0 0 0 00 0 0 64 081 63 0 0 81矩陣A為:0 0 9 0 07 0 7 0 00 0 0 0 00 8 0 0 00 0 9 0 0矩陣B為:0 7 0 0 00 0 0 8 09 7 0 0 90 0 0 0 05 0 0 0 0當(dāng)稀疏矩陣中非零元素的個數(shù)和位置在操作過程中變化比較大時，就不易采用順序存儲結(jié)構(gòu)來表示三元組。例如，在稀疏矩陣A中隨機增加或刪除一個非零元素。為此，下面給出三元組的另一種存儲表示法，即十字鏈表示法。1．十字鏈表的存儲結(jié)構(gòu)，其中的i,j,e分別表示非零元素所在的行、列下標(biāo)以及元素的值（三元組），指針down指向同列的下一個非零元素，指針right指向同行右邊的非零元素。由于該結(jié)點既是i行鏈表中的結(jié)點又是j列鏈表中的結(jié)點，所以矩陣的所有非零元素構(gòu)成一個十字交叉的鏈表，稱之為十字鏈表。稀疏矩陣A5。在C語言環(huán)境中稀疏矩陣的十字鏈表存儲結(jié)構(gòu)定義如下：typedef struct OLNode //定義十字鏈表中結(jié)點的類型OLNode{ int i,j。 Etype e。 OLNode* right,*down。}*Olink。 //定義十字鏈表中結(jié)點的指針類型Olinkstruct CrossList{ Olink *rhead,*chead。 int mu,nu,tu。}。2．十字鏈的初始化初始化操作void Init_OL(CrossListamp。 M,int m,int n)的功能是，創(chuàng)建一個m行n列的空十字鏈表M。void Init_OL(CrossListamp。 M,int m,int n){ int i。 =m。=n。=0。 =new Olink[m]。 =new Olink[n]。 for(i=0。im。i++)[i]=NULL。 for(i=0。in。i++)[i]=NULL。}3．在十字鏈中插入一個結(jié)點操作函數(shù)int Insert_OL(CrossListamp。 M,int i,int j,Etype e)的功能是，在十字鏈表M中隨機插入一個非零元素e的三元組(i,j,e)。插入成功返回1，否則返回0。int Insert_OL(CrossListamp。 M,int i,int j,Etype e){ Olink p,q。 if(!e||i0||i=||j0||j=)return(0)。 ++。 p=new OLNode。 pe=e,pi=i,pj=j。 if(![i]||[i]jj){ pright=[i]。[i]=p。} else { for(q=[i]。qrightamp。amp。qrightjj。q=qright)。 pright=qright。 qright=p。 } if(![j]||[j]ii){ pdown=[j]。[j]=p。} else { for(q=[j]。qdownamp。amp。qdownii。q=qdown)。 pdown=qdown。 qdown=p。 } return(1)。}4．十字鏈的建立操作函數(shù)void Create_OL(CrossListamp。 M)的功能是，在十字鏈表M中隨機插入若干個非零元素的三元組。void Create_OL(CrossListamp。 M){ int m,n,i,j。 Etype e。 coutCreate Cross Matrix:\n輸入行數(shù)和列數(shù)m n: \n 。 cinmn。