【文章內(nèi)容簡(jiǎn)介】 5 6 6 1 3 2 2 3 3 2 6 1 3 1 1 5 1 4 5 3 5 (二 ) 三元組對(duì)象描述 這種三元組表是一種具體的線性表順序存儲(chǔ)結(jié)構(gòu)，所以，它應(yīng)該是線性表順序存儲(chǔ)結(jié)構(gòu) (TLinearListSqu)的派生類，只是元素類型 TElem要具體定義： struct TTriTuple //定義三元組的元素類型 { long row, col。 //行號(hào)、列號(hào) float val。 //值 operator ==( TTriTuple amp。i1) //重載恒等算符 { return (row == amp。amp。 col== amp。amp。 val==)。 //兩個(gè)三元組元素的行號(hào)、列號(hào)、值全對(duì)應(yīng)相等時(shí)才算相等 }。 TTriTupleamp。 operator =( TTriTuple amp。i1) //重載賦值算符 { thisrow = 。 thiscol = 。 thisval = 。 return i1。 }。 }。 // TTriTuple 這里，我們對(duì)恒等 (==)和賦值 (=)算符進(jìn)行了重載，這是因?yàn)?，我們?cè)?TLinearListSqu(在下面將作為三元組類型的父類 )中要求元素類型 TElem(以可變類型出現(xiàn) )支持恒等與賦值運(yùn)算。為了支持父類的輸出操作 (Print)，還需要對(duì)標(biāo)準(zhǔn)輸出算符進(jìn)行重載： ostreamamp。 operator (ostreamamp。 oo, TTriTuple amp。i1) { oo(, , ) 。 return oo。 }。 下面是從線性表順序存儲(chǔ)結(jié)構(gòu)派生出的三元組表類： class TTriTupleArray : public TLinearListSquTTriTuple { long rows, cols。 //總行數(shù)、列數(shù) float theZero。 //具體的 “ 0”元素值，可以不是數(shù)值 0 long AddNew(long i, long j, float x)。 //在三元組表中加入一個(gè)新元素 (i,j,x) public: TTriTupleArray()。 TTriTupleArray(long mSize)。 floatamp。 Get(long i, long j)。 //讀出元素 (i,j)的值 void Set(long i, long j, float x)。 //將元素 (i,j)的值置為 x long GetRowsCols(long amp。r, long amp。c)。 //返回最大行號(hào)和列號(hào) float Delete(long i, long j)。 //刪除元素 (i,j) int Trans1(TTriTupleArray amp。tu)。 //轉(zhuǎn)置 int Trans2(TTriTupleArray amp。tu)。 //轉(zhuǎn)置 }。 該類的初始化函數(shù)的實(shí)現(xiàn)如下： TTriTupleArray::TTriTupleArray():TLinearListSquTTriTuple() {//初始化函數(shù) rows=0。 cols=0。 theZero=0。 }。 TTriTupleArray::TTriTupleArray(long mSize) :TLinearListSquTTriTuple(mSize) //先調(diào)用父類的構(gòu)造函數(shù)，申請(qǐng)了 mSize個(gè)空間 { rows=0。 cols=0。 heZero=0。 }。 167。 三元組表的操作 ? Get(i,j)返回下標(biāo)為（ i, j）的元素的值的引用。 ? Set(i, j, x)將下標(biāo)為（ i, j）的元素的值置為 x. 該操作的內(nèi)部動(dòng)作為：若該元素已在三元組表中存在（當(dāng)前為非零元素），則該操作只是簡(jiǎn)單地將 x的值賦予對(duì)應(yīng)元素；若該元素是零元素，則先在三元組表中插入一個(gè)元素，然后將其值置為 x；若 x的值為零，則由于我們規(guī)定不存儲(chǔ)零元素，則該操作相當(dāng)于將元素 (i,j)從三元組中刪除（若存在的話）。 ? ? 上面兩個(gè)基本操作是最基礎(chǔ)的，有了它們，就可以象訪問(wèn)普通二維數(shù)組那樣訪問(wèn)三元組數(shù)組了（直接使用下標(biāo)訪問(wèn)元素）。其他操作可根據(jù)使用的方便性設(shè)置，例如，關(guān)于矩陣的轉(zhuǎn)置、加法、乘法等，都可以設(shè)計(jì)為基本操作。 Trans1()和 Trans2()將三元組所代表的矩陣轉(zhuǎn)置。 下面的算法均假定矩陣下標(biāo)從 1開(kāi)始。 為了方便地動(dòng)態(tài)獲取三元組表矩陣的最大行號(hào)和列號(hào)，特設(shè)立 GetRowsCols(long amp。r, long amp。c)，它的實(shí)現(xiàn)按的源代碼為： long TTriTupleArray::GetRowsCols(long amp。r, long amp。c) {//求三元組表代表的矩陣的最大行號(hào)和最大列號(hào)，結(jié)果分別存入 r和 c。順便返回非 0元素個(gè)數(shù) long k。 r=0。 c=0。 for (k=0。 klen。 k++) { if (rroom[k].row) r =room[k].row。 // if (croom[k].col) c =room[k].col。 } return k。 //返回非零元素個(gè)數(shù) } 由于在三元組表中不保留零元素，所以，當(dāng)一個(gè)元素由零變?yōu)榉橇銜r(shí)，需要在三元組表中增加新元素，該工作由下面的 AddNew函數(shù)完成。但注意，若欲新增加的元素已存在，則該函數(shù)相當(dāng)于單純的賦值 Set(i, j, x). long TTriTupleArray::AddNew(long i, long j, float x) { long k, kk。 k=len1。 while (k=0) //從表的尾部起掃描，找到一個(gè) i行元素（或得知不存在 i行元素）時(shí)跳出 { if (i room[k].row) k。 else break。 } while (k=0 amp。amp。 room[k].row==i) //在 i行元素中找 j列元素，找到 (或得知不存在 )時(shí)跳出 { if (j room[k].col) k。 else break。 } if (k0 amp。amp。 j==room[k].col ) {//存在元素 (i, j)，不能增加新元素 ,只是將其值改為 x room[k].val = x。 return k。 } for (kk=len1。 kkk。 kk) //后移元素，準(zhǔn)備插入 room[kk+1] = room[kk]。 room[k+1].row=i。 //插入元素 (i,j,x) room[k+1].col=j。 room[k+1].val = x。 len++。 if (irows) rows=i。 if (jcols) cols=j。 return k+1。 //返回表中元素個(gè)數(shù) }。 下面是具體的 Get和 Set函數(shù)的實(shí)現(xiàn)： floatamp。 TTriTupleArray::Get(long i, long j) { long k。 k=0。 while (klen) { if (room[k].row==i) if (room[k].col==j) break。 k++。 } if (k==len) return theZero。 return room[k].val。 } void TTriTupleArray::Set(long i, long j, float x) { long k。 k=0。 while (klen) { if (room[k].row==i) { if (room[k].col==j) break。 } k++。 } if( k==len) {//表中無(wú) (i,j)，插入 if (x!=theZero) AddNew(i, j, x)。 } else {//表中存在元素 (i,j) if (x!=theZero) room[k].val = x。 //x非 0時(shí)將 x的值賦予 (i,j)元素 else Delete(i,j)。 //x為 0時(shí)刪除元素 (i,j) } } 167。 轉(zhuǎn)置操作 對(duì)矩陣的轉(zhuǎn)置，就是使 i行 j列元素與 j行 i列元素對(duì)換位置。若矩陣是用二維數(shù)組表示的，則轉(zhuǎn)置操作是很簡(jiǎn)單的。設(shè) a是一個(gè)用二維數(shù)組表示的 m n矩陣，其轉(zhuǎn)置的結(jié)果存于二維數(shù)組 b，它是一個(gè) n m矩陣。具體的轉(zhuǎn)置過(guò)程可描述如下： int a[m][n], b[n][m]。 ………… for (i=0。 im。 i++) for (j=0。 jn。 j++) b[j][i]=a[i][j]。 如果矩陣是用三元組表表示的，可以利用 Get和 Set，則轉(zhuǎn)置操作與上面的類似，基本形式為： for (i=0。 im。 i++) for (j=0。 jn。 j++) (j, i, (i, j))。 ? 這個(gè)例子表明，三元組表設(shè)置了 Get和 Set操作，其所用方式就與二維數(shù)組相同了，完全屏蔽了三元組表的存儲(chǔ)結(jié)構(gòu)。 若為了提高程序效率，可直接實(shí)現(xiàn)轉(zhuǎn)置（不使用Get和 Set），則轉(zhuǎn)置的實(shí)現(xiàn)沒(méi)有這樣直接。 分析轉(zhuǎn)置操作，其主要是將每個(gè)元素的行號(hào)和列號(hào)互換。 由于在三元組表中，元素是按行序（或列序）排列，所以，行號(hào)和列號(hào)互換后，還要調(diào)整元素位置，使其仍保持行序（或列序）排列。實(shí)現(xiàn)這一點(diǎn)的一個(gè)顯然的做法是： l 將每個(gè)元素的行號(hào)和列號(hào)分別互換； l 對(duì)三元組表排序，使其中元素按行序（或列序）排列。 此算法的時(shí)間復(fù)雜度為 O(n)+O(nlog(n))，這里， n為三元組表中元素個(gè)數(shù)。 O(nlog(n))是基于比較運(yùn)算的排序算法的平均最好時(shí)間復(fù)雜度，在簡(jiǎn)單排序情況（如冒泡排序等），時(shí)間復(fù)雜度可上升為 O(n2)。 如果要降低時(shí)間復(fù)雜度，一個(gè)顯然的做法是免去排序操作，使在進(jìn)行元素的行號(hào)和列號(hào)互換的過(guò)程中，順便實(shí)現(xiàn)行序（列序）排列。也就是（假定將 a轉(zhuǎn)置結(jié)果存于 b）： l 將 a的每個(gè)元素從三元組表中取出，交換它們的行號(hào)值與列號(hào)值； l 將所取出的三元組元素存入目標(biāo)三元組表 b中適當(dāng)位置，使三元組表 b保持行序 /列序。 下面假定三元組中元素按行序排序，即原矩陣 a與轉(zhuǎn)置結(jié)果均按行序排列， 至于列序排列情況，處理方法類似。 注意，由于我們這里假定三元組表內(nèi)元素按行序排列，且轉(zhuǎn)置后元素的行列號(hào)互換了，所以，轉(zhuǎn)置后的三元組表中，元