【正文】 ,(0,4,5),(1,0,7),(1,2,7),(3,1,8),(4,2,9))同理，稀疏矩陣B可用三元組順序表示為向量：((0,1,7),(1,3,8),(2,0,9),(2,1,7),(2,4,9),(4,0,5))3．稀疏矩陣的基本操作由于稀疏矩陣是一種特殊的矩陣，所以有關(guān)稀疏矩陣的基本運(yùn)算即為矩陣的基本運(yùn)算。2．稀疏矩陣的三元組表示在稀疏矩陣的壓縮存儲(chǔ)過(guò)程中，可以只考慮非零元素的存儲(chǔ)以達(dá)到壓縮矩陣存儲(chǔ)空間的目的。假設(shè)矩陣Amn中有t個(gè)非零元素，令δ=t/(mn)，則稱δ為矩陣A的稀疏因子。可將帶寬為m的n階方陣Ann中的非零元素壓縮存儲(chǔ)到一維數(shù)組B[(n1)m+1]中。3．帶狀矩陣的壓縮存儲(chǔ)如果矩陣中的所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域內(nèi)，則稱該矩陣為帶狀陣。A中元素A[i][j]與M中元素M[k]的對(duì)應(yīng)關(guān)系是：(a)(b)所示。若矩陣中值相同的元素或零元素的分布有一定的規(guī)律，則稱此類的矩陣為特殊矩陣。在高級(jí)語(yǔ)言程序設(shè)計(jì)中，通常是用二維數(shù)組來(lái)存儲(chǔ)矩陣元素的。1 2 3 4 5↙3 4 5 6 7↙5 6 7 8 9↙7 8 9 0 1↙A2結(jié)果為:1 2 3 4 53 4 5 6 75 6 7 8 97 8 9 0 1A2的轉(zhuǎn)置矩陣為:1 3 5 72 4 6 83 5 7 94 6 8 05 7 9 1以行為主序的順序輸入A[3*4*5]中的60個(gè)元素的值。 coutA4結(jié)果為:\n。 coutA3結(jié)果為:\n。 coutA2的轉(zhuǎn)置矩陣為:\n。 //定義A2為二維數(shù)組大小為4*5 ArrayInput(A2)。 //定義A1為一維數(shù)組長(zhǎng)度為5 ArrayInput(A1)。}8．矩陣操作的演示主程序在演示程序中，首先按左下標(biāo)（行）優(yōu)先的順序分別建立一維、二維、三維和四維數(shù)組，以及二維數(shù)組的轉(zhuǎn)置，然后顯示輸出各個(gè)數(shù)組的值。s[1][1]。 InitArray(A,dim,bounds)。int Trans(Arrayamp。 coutendl。i++)len*=[i]。 } } break。s[1]++) { for(s[2]=0。s[0][0]。s[1]++) coutValue(A,s) 。 case 2: //按二維數(shù)組格式輸出 for(s[0]=0。s[0][0]。i++)cin[i]。 cout]中的length個(gè)元素的值。*39。 cout以行為主序的順序輸入A。 A){ int length=1,i。 return 1。i。如果下標(biāo)合理返回1表示修改成功，否則返回0表示操作失敗。i++)off+= script[i]*[i]。}簡(jiǎn)化的提取數(shù)組元素操作函數(shù)EType Value(Array A,int* script)，該操作對(duì)下標(biāo)越界不做檢查。i++) { if(script[i]=[i]|| script[i]0) return 0。int Value(Array A,int* script,EType amp。 return 1。 //分配數(shù)組元素的存儲(chǔ)空間 [dim1]=1。i++) { length*=bounds[i]。 =new int[dim]。如果輸入維數(shù)dim合理返回1，表示操作成功，否則返回0表示操作失敗。 //數(shù)組維界向量基地址 int *constent。所以：LOC(A[1][2][3])=100+(354+24+1)2=238LOC(A[3][2][0])=100+(054+24+3)2=122LOC(A[1][3][5])=100+(554+34+1)2=3261．?dāng)?shù)組的順序存儲(chǔ)結(jié)構(gòu)表示在C++語(yǔ)言環(huán)境中，順序數(shù)組的存儲(chǔ)表示如下include //標(biāo)準(zhǔn)輸入輸出頭文件typedef int EType?！尽恳阎狝456為按左下標(biāo)為主序存儲(chǔ)的3維數(shù)組，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且元素A[0][0][0]的首地址為1000，分別計(jì)算元素A[1][2][3]、A[3][2][0]和A[1][3][5]的首地址。地址計(jì)算公式為： 其中b1為數(shù)組第2維的長(zhǎng)度（界）。（2）以列（右下標(biāo)）為主序的存儲(chǔ)結(jié)構(gòu)該存儲(chǔ)結(jié)構(gòu)以最右面的下標(biāo)為主序，左下標(biāo)優(yōu)先變化，即下標(biāo)變化順序是從左到右。但是，由于內(nèi)存地址是一維結(jié)構(gòu)，而數(shù)組可以是多維結(jié)構(gòu)，所以，必須有一個(gè)從多維下標(biāo)到一維地址的對(duì)應(yīng)關(guān)系。 A,int* script,EType e)：該操作根據(jù)下標(biāo)script修改數(shù)組A中的元素為e的值。A,int dim,int* bounds)：該操作根據(jù)數(shù)組元素類型、維數(shù)dim和長(zhǎng)度bounds定義一個(gè)數(shù)組（初始化數(shù)組）A。從邏輯結(jié)構(gòu)上看，n維數(shù)組Array中各元素的位置由該元素的下標(biāo)唯一確定，一旦給定一組下標(biāo)(j0,j1,j2,…,jn1)，都存在唯一的一個(gè)與其相對(duì)應(yīng)的元素值a稱為數(shù)組元素，記為a(j0,j1,j2,…,jn1)。廣義表被廣泛應(yīng)用于人工智能等領(lǐng)域。在前面討論的線性結(jié)構(gòu)中，其數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素的值是不可再分解的。本章所討論的數(shù)組可以看成是線性表的一種擴(kuò)展，即線性表中的每個(gè)數(shù)據(jù)元素本身也是一個(gè)線性表。如果一個(gè)向量的所有元素又都是向量（或稱子向量），且這些子向量具有相同的上限和下限標(biāo)號(hào)，那么這種特殊形式的向量稱為數(shù)組。其中，0=jibi，bi稱為第i維的長(zhǎng)度(i=0,1,2,…,n1)。（2）讀取操作Value(Array A,int* script,EType amp。（4）銷毀操作：該操作回收一個(gè)數(shù)組所占的資源（銷毀數(shù)組）。1．?dāng)?shù)組的兩種順序存儲(chǔ)方法（1）以行（左下標(biāo)）為主序的存儲(chǔ)結(jié)構(gòu)該存儲(chǔ)結(jié)構(gòu)以最左面的下標(biāo)為主序，右下標(biāo)優(yōu)先變化，即下標(biāo)變化順序是從右到左。以二維數(shù)組：為例，（a）所示。對(duì)于以行為主序的n維數(shù)組，數(shù)組元素a(j0,j1,...,jn1)的地址計(jì)算公式為：其中為數(shù)組元素a[0][0]...[0]的地址，L為每個(gè)元素所占內(nèi)存的字節(jié)數(shù)，b0,b1,...,bn1為每一維的長(zhǎng)度。解：按左下標(biāo)為主序的地址計(jì)算公式為：LOC(A[i][j][k])= LOC(A[0][0][0])+(ib1b2+jb2+k)L。 //便于上機(jī)操作定義數(shù)組類型為整型（int）struct Array{ EType *base。 //數(shù)組元素的映像常數(shù)向量}。int InitArray(Array amp。 //分配維界向量的存儲(chǔ)空間 =new int[dim]。 //計(jì)算數(shù)組元素的總數(shù) [i]=bounds[i]。 for(i=dim2。}3．根據(jù)下標(biāo)(script)提取數(shù)組元素的操作操作int Value(Array A,int* script,EType amp。e){ int i,off=0。 off+= script[i]*[i]。EType Value(Array A,int* script){ int i,off=0。 return [off]。int Assign(Arrayamp。i++) { if(script[i]=[i]|| script[i]0) return 0。}5．?dāng)?shù)組的按行序輸入操作操作void ArrayInput(Arrayamp。 for(i=0。 for(i=0。:39。\n。}6．?dāng)?shù)組的按行序輸出操作操作void Arrayoutput(Array A)的功能是，按左下標(biāo)為主序，輸出一維、二維、三維和多維數(shù)組A中的元素。s[0]++) coutValue(A,s) 。s[0][0]。 coutendl。s[0]++) { cout第s[0]+1頁(yè):\n。s[2][2]。 default: //三維以上按左下標(biāo)優(yōu)先的一維數(shù)組格式輸出 cout維數(shù)為大于3\n按左下標(biāo)為主序輸出所有元素的值:\n。 for(i=0。 } }7．矩陣的轉(zhuǎn)置操作操作int Trans(Array amp。 A,Array B){ if(!=2)return 0。 //初始化數(shù)組A for(s[0]=0。s[1]++) { s1[0]=s[1],s1[1]=s[0]。void main(){ Array A1,A2,A22,A3,A4。 coutA1結(jié)果為:\n。 coutA2結(jié)果為:\n。 Arrayoutput(A22)。 Arrayoutput(A3)。 Arrayoutput(A4)。1 2 3 4 5↙2 3 4 5 6↙3 4 5 6 7↙4 5 6 7 8↙21 22 23 24 25↙22 23 24 25 26↙23 24 25 26 27↙24 25 26 27 28↙31 32 33 34 35↙32 33 34 35 36↙33 34 35 36 37↙34 35 36 37 38↙A3結(jié)果為:第1頁(yè):1 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8第2頁(yè):21 22 23 24 2522 23 24 25 2623 24 25 26 2724 25 26 27 28第3頁(yè):31 32 33 34 3532 33 34 35 3633 34 35 36 3734 35 36 37 38以行為主序的順序輸入A[2*3*2*3]中的36個(gè)元素的值。然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中又有許多值相同元素或者是零元素。1．對(duì)稱矩陣的壓縮存儲(chǔ)若n階方陣Ann中的元素a[i][j]滿足性質(zhì)：，則稱A為n階對(duì)稱矩陣。2．下三角矩陣的壓縮存儲(chǔ)若n階方陣Ann中的元素a[i][j]滿足性質(zhì)：當(dāng)ij時(shí)a[i][j]=0(0≤i,jn),則稱A為n階下三角矩陣。帶狀區(qū)域若包含主對(duì)角線上下各b條對(duì)角線上的元素，那么b稱為該帶狀陣的半帶寬，該帶狀陣的帶寬為m=(2b+1)。壓縮存儲(chǔ)過(guò)程是，對(duì)所有帶狀區(qū)域中的元素按行優(yōu)先的順序存儲(chǔ)，并且除了第一行和最后一行外，每行都按照m（即2b+1）個(gè)非零元素計(jì)算，如果該行中的區(qū)域元素不夠m個(gè)時(shí)要采用左、右零補(bǔ)齊的方法。通常認(rèn)為，當(dāng)δ≤n為稀疏矩陣。但是，稀疏矩陣中非零元素的出現(xiàn)是沒(méi)有規(guī)律的，如果只是簡(jiǎn)單地將它們一個(gè)挨一個(gè)存放起來(lái)，將來(lái)就很難按行、列號(hào)找到它們。其主要操作有：（1）創(chuàng)建CreatSMatrix(amp。C) 其功能是求稀疏矩陣A減B的差C；（5）轉(zhuǎn)置TransSMatrix(M,amp。 //此處定義數(shù)組元素的類型為整型以便于上機(jī)操作struct Triple //定義三元組結(jié)構(gòu)類型{ int i,j。 int mu,nu,tu。其中，、。T){ int k。 cout輸入 i j e:\n。amp。 。 for(i=1。 cout[i].e)\n。 //根據(jù)T中的函數(shù)、列數(shù)定義矩陣A for(i=0。j++) A[i*n+j]=0。 j=[p].j。i++) //以矩陣的形式輸出A的值 { for(j=0。 coutendl。由于三元組表中的元素是按行號(hào)遞增的順序排列，在行號(hào)相同的情況下再按列號(hào)遞增排列。算法思想，先找其值為j=0的，若有，則將其行、(1,0,7)224。(2,1,7)，(4,2,9)224。void Trans_TSM(TSMatrix S,TSMatrix amp。 =。j。 [n].i=j。顯然，雖然節(jié)省了存儲(chǔ)空間，但是時(shí)間復(fù)雜度卻大于通常矩陣轉(zhuǎn)置算法的時(shí)間復(fù)雜度。由num可算出轉(zhuǎn)置矩陣B的每行元素中第一個(gè)元素的初始位置序列cpot。 int* num=new int[]。 for(col=0。t=。col。p++) //通過(guò)一次性掃描求出轉(zhuǎn)置矩陣T { col=[p].j。 [q].e=[p].e。6．三元組矩陣的加法運(yùn)算假定矩陣M、N均為三元組表示的稀疏矩陣且具有相同的行數(shù)和列數(shù)，可對(duì)稀疏矩陣進(jìn)行求和操作：A=M+N。 int p=1,q=1,r=1。 else if([p].j[q].j) [r++]=[q++]。q++。while(q=)[r++]=[q++]。 A)實(shí)現(xiàn)三元組矩陣的減法運(yùn)算A=MN。p=。void Frpot(int rpot[],TSMatrix M){ int* num=new int[]。raw++)num[raw]=0。 //求每行非零元素的個(gè)數(shù) rpot[0]=1。 //求第raw行的起始位置rpot[raw] delete[]num。e,int i,int j,int rpot[],TSMatrix M){ int k=rpot[i]。([k].i==