【正文】 元素之和 。 (2) 求從 A[0][0]開始的行 、 列互不相鄰的各元素之和 。 (3) 當 m=n時 ,分別求兩條對角線上的元素之和 ,否則打印出 m≠n的信息 。 解： (1) 對應算法如下： void proc1(ElemType A[][n]) { int s=0,i,j。 for (i=0。im。i++) /*第一列 */ s=s+A[i][0]。 for (i=0。im。i++) /*最后一列 */ s=s+A[i][n1]。 for (j=0。jn。j++) /*第一行 */ s=s+A[0][j]。 for (j=0。jn。j++) /*最后一行 */ s=s+A[m1][j]。 s=sA[0][0]A[0][n1]A[m1][0]A[m1][n1]。 /*減去 4個角的重復元素值 */ printf(s=%d\n,s)。 } (2) 對應算法如下： void proc2(maxix A) { int s=0,i=0,j=0。 do { do { s=s+A[i][j]。 j=j+2。 /*跳過一列 */ } while (jn)。 i=i+1。 /*下一行 */ if (j==0) j=1。 else j=0。 } while (im)。 printf(s=%d\n,s)。 } (3) 對應算法如下： void proc3(maxix A) { int i,s=0。 if (m!=n) printf(m≠n)。 else { for (i=0。im。i++) s=s+A[i][i]。 /*求第一條對角線之和 */ for (i=0。in。i++) s=s+A[ni1][i]。 /*累加第二條對角線之和 */ s=A[n/2][n/2]。 printf(s=%d\n,s)。 } } 稀疏矩陣 一個階數(shù)較大的矩陣中的非零元素個數(shù) s相對于矩陣元素的總個數(shù) t十分小時 ,即 st時 ,稱該矩陣為稀疏矩陣 。 例如一個 100 100的矩陣 ,若其中只有 100個非零元素 ,就可稱其為 稀疏矩陣 。 稀疏矩陣的三元組表示 稀疏矩陣的壓縮存儲方法是只存儲非零元素 。 由于稀疏矩陣中非零元素的分布沒有任何規(guī)律 ,所以在存儲非零元素時還必須同時存儲該非零元素所對應的行下標和列下標 。 這樣稀疏矩陣中的每一個非零元素需由一個三元組 (i,j,ai,j)惟一確定 ,稀疏矩陣中的所有非零元素構成三元組線性表 。 假設有一個 6 7階稀疏矩陣 A(為圖示方便 ,我們所取的行列數(shù)都很小 ),A中元素如下圖所示 。 則對應的三元組線性表為： ((0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4)) ??????????????????????47000000060000000500000000030000020000010076A一個稀疏矩陣 A 若把稀疏矩陣的三元組線性表按順序存儲結構存儲 ,則稱為稀疏矩陣的三元組順序表 。 則三元組順序表的數(shù)據(jù)結構可定義如下： define MaxSize 100 /*矩陣中非零元素最多個數(shù) */ typedef struct { int r。 /*行號 */ int c。 /*列號 */ ElemType d。 /*元素值 */ } TupNode。 /*三元組定義 */ typedef struct { int rows。 /*行數(shù)值 */ int cols。 /*列數(shù)值 */ int nums。 /*非零元素個數(shù) */ TupNode data[MaxSize]。 } TSMatrix。 /*三元組順序表定義 */ 其中 ,data域中表示的非零元素通常以行序為主序順序排列 ,它是一種下標按行有序的存儲結構 。這種有序存儲結構可簡化大多數(shù)矩陣運算算法 。下面的討論假設 data域按行有序存儲 。 (1) 從一個二維矩陣創(chuàng)建其三元組表示 以行序方式掃描二維矩陣 A,將其非零的元素插入到三元組 t的后面 。 算法如下： void CreatMat(TSMatrix amp。t,ElemType A[M][N]) { int i,j。 =M。=N。=0。 for (i=0。iM。i++) { for (j=0。jN。j++) if (A[i][j]!=0) /*只存儲非零元素 */ { [].r=i。[].c=j。 [].d=A[i][j]。++。 } } } (2) 三元組元素賦值 先在三元組 t中找到適當?shù)奈恢?k,將 k～ 元素后移一位 ,將指定元素 x插入到 [k]處 。 算法如下： int Value(TSMatrix amp。t,ElemType x,int rs,int cs) { int i,k=0。 if (rs= || cs=) return 0。 while (k amp。amp。 rs[k].r) k++。 /*查找行 */ while (k amp。amp。 cs[k].c) k++。 /*查找列 */ if ([k].r==rs amp。amp。 [k].c==cs) [k].d=x。 /*存在這樣的元素 else /*不存在這樣的元素時插入一個元素 */ { for (i=。ik。i) /*元素后移 */ { [i+1].r=[i].r。 [i+1].c=[i].c。 [i+1].d=[i].d。 } [k].r=rs。[k].c=cs。[k].d=x。 ++。 } return 1。 } (3) 將指定位置的元素值賦給變量 先在三元組 t中找到指定的位置 ,將該處的元素值賦給 x。 算法如下： int Assign(TSMatrix t,ElemType amp。x,int rs,int cs) { int k=0。 if (rs= || cs=) return 0。 while (k amp。amp。 rs[k].r) k++。 while (k amp。amp。 cs[k].c) k++。 if ([k].r==rs amp。amp。 [k].c==cs) { x=[k].d。 return 1。 } else return 0。 } (4) 輸出三元組 從頭到尾掃描三元組 t,依次輸出元素值 。 算法如下： void DispMat(TSMatrix t) { int i。 if (=0) return。 printf(“\t%d\t%d\t%d\n,)。 printf( \n)。 for (i=0。i。i++) printf(\t%d\t%d\t%d\n,[i].r,[i].c, [i].d)。 } (5) 矩陣轉(zhuǎn)置 對于一個 m n的矩陣 Am n,其轉(zhuǎn)置矩陣是一個n m 的矩陣 。 設為 Bn m, 滿足 ai,j=bj,i, 其中1≤i≤m,1≤j≤n。 其完整的轉(zhuǎn)置算法如下： void TranTat(TSMatrix t,TSMatrix amp。tb) { int p,q=0,v。 /*q為 */ =。=。=。 if (!=0) { for (v=0。v。v++) for (p=0。p。p++) /*p為 */ if ([p].c==v) { [q].r=[p].c。 [q].c=[p].r。 [q].d=[p].d。 q++。 } } } 以上算法的時間復雜度為 O(*),而將二維數(shù)組存儲在一個 m行 n列矩陣中時 ,其轉(zhuǎn)置算法的時間復雜度為 O(m*n)。最壞情況是當稀疏矩陣中的非零元素個數(shù) m*n同數(shù)量級時 ,上述轉(zhuǎn)置算法的時間復雜度就為 O(m*n2)。 對其他幾種矩陣運算也是如此?？梢?,常規(guī)的非稀疏矩陣應采用二維數(shù)組存儲 ,只有當矩陣中非零元素個數(shù) s滿足 sm*n時 ,方可采用三元組順序表存儲結構。這個結論也同樣適用于下面要討論的十字鏈表。 稀疏矩陣的十字鏈表表示 十字鏈表 為稀疏矩陣的每一行設置一個單獨鏈表 ,同時也為每一列設置一個單獨鏈表 。 這樣稀疏矩陣的每一個非零元素就同時包含在兩個鏈表中 ,即每一個非零元素同時包含在所在行的行鏈表中和所在列的列鏈表中 。 這就大大降低了鏈表的長度 ,方便了算法中行方向和列方向的搜索 ,因而大大降低了算法的時間復雜度 。 (a) 結點結構 (b) 頭結點結構 對于一個 m n的稀疏矩陣 ,每個非零元素用一個結點表示 ,結點結構可以設計成如下圖 (a)所示結構 。 其中 i,j,value分別代表非零元素所在的行號 、 列號和相應的元素值； down和 right分別稱為向下指針和向右指針 ,分別用來鏈接同列中和同行中的下一個非零元素結點 。 十字鏈表中設置行頭結點、列頭結點和鏈表頭結點。它們采用和非零元素結點類似的結點結構 ,具體如上圖 (b)所示。其中行頭結點和列頭結點的 i,j域值均為 0；行頭結點的 right指針指向該行鏈表的第一個結點 ,它的 down指針為空；列頭結點的 down指針指向該列鏈表的第一個結點 ,它的 right指針為空。行頭結點和列頭結點必須順序鏈接 ,這樣當需要逐行 (列 )搜索時 ,才能一行 (列 )搜索完后順序搜索下一行 (列 ),行頭結點和列頭結點均用 link指針完成順序鏈接。 ??????????400003002021B 43一個稀疏矩陣 1 3 4 0 0 0 3 2 1 2 3 2 3 4 h4 h3