【正文】 = currentrLink。 currentrLinklLink = current。 ( first lLink = current ) first template class Type void DblListType :: Insert ( const Type amp。 value ) { if ( firstrlink == first ) //空表情形 current = firstrLink = new DblNodeType ( value, first, first )。 else { //非空表情形 currentrLink = new DblNodeType ( value, current, currentrLink )。 current = currentrLink。 } currentrLinklLink = current。 } 刪除 48 雙向循環(huán)鏈表的刪除算法 first first 非空表 31 48 15 current 31 15 current currentrLinklLink = currentlLink。 currentlLinkrLink = currentrLink。 刪除 31 雙向循環(huán)鏈表的刪除算法 first first 31 current current currentrLinklLink = currentlLink。 currentlLinkrLink = currentrLink。 template class Type void DblListType :: Remove ( ) { if ( current != first ) { DblNode *temp = current。 //被刪結(jié)點(diǎn) current = currentrLink。 //當(dāng)前指針進(jìn)到 下一結(jié)點(diǎn) currentlLink = templLink。 //將被刪結(jié)點(diǎn)從鏈中摘下 templLinkrLink = current。 delete temp。 //刪去 } } template class Type int DblListType :: First ( ) { if ( !IsEmpty ( ) ) { current = firstrLink。 return 1。 } current = first。 return 0。 } 其他雙向循環(huán)鏈表的公共操作 template class Type int DblListType :: Next ( ) { if ( currentrLink == first ) //最后結(jié)點(diǎn) { current = first rLink。 return 0。 } current = currentrLink。 return 1。 } template class Type int DblListType :: Prior ( ) { if ( currentlLink == first ) //第一個(gè)結(jié)點(diǎn) { current = first lLink。 return 0。 } current = currentlLink。 return 1。 } 五、稀疏矩陣 ? 在矩陣操作 (+、 、 *、 /)時(shí)矩陣非零元素會(huì)發(fā)生動(dòng)態(tài)變化，用稀疏矩陣的鏈接表示可適應(yīng)這種情況。 ? 稀疏矩陣的鏈接表示采用正交鏈表：行鏈表與列鏈表十字交叉。 ? 行鏈表與列鏈表都是帶表頭結(jié)點(diǎn)的循環(huán)鏈表。用表頭結(jié)點(diǎn)表征是第幾行，第幾列。 ?稀疏矩陣的結(jié)點(diǎn) head down next right (a) 表頭結(jié)點(diǎn) (b) 非零元素結(jié)點(diǎn) right value down row col a[i][j] False i j (c) 建立 a[i][j]結(jié)點(diǎn) head 稀疏矩陣的正交鏈表表示的示例 稀疏矩陣的鏈表表示的類定義 enum Boolean { False, True }。 struct Triple { int row, col。 float value。 }。 class Matrix。 class MatrixNode { //矩陣結(jié)點(diǎn)定義 friend class Matrix。 friend istream amp。operator ( istream amp。, Matrix amp。 )。 //矩陣輸入重載函數(shù) private: MatrixNode *down, *right。 //列 /行鏈指針 Boolean head。 //結(jié)點(diǎn)類型 Union { Triple triple。 MatrixNode *next。 } //矩陣元素結(jié)點(diǎn) (False)或鏈頭結(jié)點(diǎn) (True) MatrixNode ( Boolean, Triple* )。 //結(jié)點(diǎn)構(gòu)造函數(shù) } MatrixNode::MatrixNode ( Boolean b, Triple *t ) { //矩陣結(jié)點(diǎn)構(gòu)造函數(shù) head = b。 //結(jié)點(diǎn)類型 if ( b ) { right = next = this。 } else triple = *t。 } typedef MatrixNode *MatrixNodePtr。 //一個(gè)指針數(shù)組 , 用于建立稀疏矩陣 class Matrix { friend istreamamp。 operator ( istream amp。, Matrix amp。 )。 //矩陣輸入 public: ~Matrix ( )。 //析構(gòu)函數(shù) private: MatrixNode *headnode。 //稀疏矩陣的表頭 }。 用正交鏈表表示的稀疏矩陣的建立 istream amp。 operator ( istream amp。 is, Matrix amp。 matrix ) { Triple s。 int p。 is 。 //輸入矩陣的行數(shù) , 列數(shù)和非零元素個(gè)數(shù) if ( ) p = 。 else p = 。 //取行、列數(shù)大者 = //整個(gè)矩陣表頭結(jié)點(diǎn) new MatrixNode ( False, amp。s )。 if ( !p ) { //零矩陣時(shí) right = 。 return is。 } MatrixNodePtr *H = new MatrixNodePtr ( p )。 //建立表頭指針數(shù)組 , 指向各鏈表的表頭 for ( int i = 0。 i p。 i++ ) H[i] = new MatrixNode ( True, 0 )。 int CurrentRow = 0。 MatrixNode *last = H[0]。 //當(dāng)前行最后結(jié)點(diǎn) for ( i = 0。 i 。 i++ ) { //建立矩陣 Triple t。 is 。 //輸入非零元素的三元組 if ( CurrentRow ) { //如果行號(hào)大于當(dāng)前行 ,閉合當(dāng)前行 lastright = H[CurrentRow]。 CurrentRow = 。 last = H[CurrentRow]。 } last = lastright = //鏈入當(dāng)前行 new MatrixNode ( False, amp。t )。 H[]next = H[]nextdown = last。 //鏈入列鏈表 } lastright = H[CurrentRow]。 //閉合最后一行 //閉合各列鏈表 for ( i = 0。 i 。 i++ ) H[i]nextdown = H[i]。 //鏈接所有表頭結(jié)點(diǎn) for ( i = 0。 i p1。 i++ ) H[i]next =H[i+1]。 H[p1]next = 。 right = H[0]。 delete [ ] H。 return is。 } 稀疏矩陣的刪除 ? 為執(zhí)行稀疏矩陣的刪除，需要使用可利用空間表來(lái)管理回收的空間。 ? 可利用空間表是單鏈表結(jié)構(gòu)，只允許在表頭插入或刪除，其表頭指針為 av。 ? 使用可利用空間表，可以高效地回收循環(huán)鏈表。 ? 如果需要建立新的稀疏矩陣，還可以從可利用空間表中分配結(jié)點(diǎn)。 用正交鏈表表示的稀疏矩陣的刪除 Matrix :: ~Matrix ( ) { if ( headnode == NULL ) return。 MatrixNode *x = headnoderight, *y。 headnoderight = av。 av = headnode。 while ( x != headnode ) { y = xright。 xright = av。 av = y。 x = xnext。 } headnode = NULL。 }