【文章內(nèi)容簡介】 x(int MaxTerms=defaultSize)。 ~SparseMatrix() {delete [ ] smArray。} SparseMatrixType Compression(smDataType)。 SparseMatrixType Transpose()。 SparseMatrixType Add(SparseMatrix Type b)。 SparseMatrixType Multiply(SparseMatrixType b)。 private: int Rows, Cols, Terms,MaxTerms。 Trituple Type smArray[MaxTerms]。 } 2021/12/1 35 說明： （ 1）壓縮前的稀疏矩陣為 Rows 行 , Cols 列的矩陣 smData ，壓縮后的稀疏矩陣存放在一維數(shù)組 smArray 中，其中的元素為 Trituple 類型的對象。 聲明中的 Terms 對應(yīng)于順序表定義中的 last， MaxTerms 對應(yīng)于順序表定義中的 Maxsize， smArray 對應(yīng)于順序表定義中的 data （ 2）為稀疏矩陣聲明了四種操作： 壓縮（ Compression） 轉(zhuǎn)置（ Transpose） 相加（ Add） 相乘（ Multiply） 根據(jù)實際需要還可以聲明其他操作。 （ 3）數(shù)值計算與非數(shù)值計算的數(shù)據(jù)結(jié)構(gòu)中所定義的基 本操作有很大的不同 2021/12/1 36 稀疏矩陣的轉(zhuǎn)置操作 快速轉(zhuǎn)置算法思路： （ 1）引入兩個輔助數(shù)組 rowSize[ ] 和 rowStart[ ] rowSize [ i ]——表示稀疏矩陣第 i 列的非零元素個數(shù) rowStart[ i ]——表示稀疏矩陣第 i 列的第一個（行號最?。? 非零元素在轉(zhuǎn)置矩陣的三元組表中的位置。 顯然應(yīng)有： rowStart[ i ] + rowSize[ i ] = rowStart[ i+1 ] . . . . . . . . . 共有 rowSize[ i ] 個元素 2021/12/1 37 上述公式表示，若已知稀疏矩陣第 i 列的第一個非零元素在轉(zhuǎn)置 矩陣的三元組表中的位置 rowStart [ i ] , 以及稀疏矩陣第 i 列的非零 元素個數(shù) rowSize [ i ] , 就可以算出第 i+1 列非零元素在轉(zhuǎn)置矩陣的 三元組表中的位置 rowStart [ i+1] 另外，根據(jù)轉(zhuǎn)置矩陣的定義可知： rowStart [ 0 ] = 0 因此： rowStart [ 1 ] = rowSize [ 0 ] + rowStart [ 0 ] = rowSize [ 0 ] rowStart [ 2 ] = rowSize [ 1 ] + rowStart [ 1 ] . . . . . . 因此，只要預(yù)先統(tǒng)計得到 rowSize [ i ] ( i = 0 , 1 , 2 , . . .) 就可以得到第 i + 1 列非零元素在轉(zhuǎn)置矩陣的三元組表中的位置 2021/12/1 38 template class Type SparseMatrixType SparseMatrixType:: FastTranspos( )// { int *rowSize = new int[Cols]。 int *rowStart = new int[Cols]。 SparseMatrixType b。 = Cols。 = Rows。 = Terms。 if (Terms 0 ) { for (int i = 0。 iCols。 i ++) rowSize[i] = 0。 for (i=0。iTerms。i++) rowSize[smArray[i].col]++。 rowStart[0]=0。 for (i=1。iCols。i++) rowStart[i]=rowStart[i1]+rowSize[i1]。 for (i=0。iTerms。i++){ int j=rowStart[smArray[i].col]。 [j].row=smArray[i].col。 [j].col=smArray[i].row。 [j].value=smArray[i].value。 rowStart[smArray[i].col]++。} } delete [] rowSize。 delete [] rowStart。 return b。 } 2021/12/1 39 2。 5 字符串 定義： 字符串（簡稱為串） 是 n ( n = 0 ) 個字符的有限序列 通?？捎洖椋? S = ? a0 a1 a2 … an1 ‘ 其中： 串名 ——S 串值 ——引號中的內(nèi)容 n——串長，即串中的字符個數(shù)（不包括串結(jié)束符 ‘ \0 ‘ ） 空串 —— n = 0 的串（但包含串結(jié)束符） 空白串 ——僅由若干個空格字符組成的串，其長度不為零 子串 ——從非空串中連續(xù)取出的若干個字符組成的串 子串的位置 ——子串的第 0個字符在原串中的位置 可以認(rèn)為：串是限制數(shù)據(jù)元素為字符的順序表 2021/12/1 40 字符串抽象數(shù)據(jù)類型和類定義 class String{ public: String(const String amp。)。String(const char *const)。String()。 ~String() {delete [ ] ch。} int Length() const {return curLen； } String amp。 operator()(int pos,int len)。 int operator ==(const String amp。 ob) const {return strcmp(ch,)==0。} int operator !=(const String amp。 ob) const{return strcmp(ch,)!=0。} int operator ! () const {return curLen==0； } String amp。 operator = (const String amp。)。 String amp。 operator += (const String amp。)。 char amp。 operator [ ] (int i )。 int Find(String pat) const。 private: int curLen。 char * ch。 } 2021/12/1 41 有了上述的串類定義，就可以進(jìn)行下列操作： String s1。 String s2 ( ― Hello World ‖ )。 s1 = s2。 String s3 ( ― 。 nice to here ! ‖ )。 s1 + = s3。 int len=()。 String s4。 s4=s1(6,5)。 If (s1==s2)… If (s1!=s2)… If (! s1)… Char c=s1[6]。 s1[6]=?w‘。 2021/12/1 42 文本編輯 計算機(jī)應(yīng)用中要涉及大量的文本文件，文本文件由大量的串 （行）組成，在某些文本文件（如源程序）中，串（行）長差異 很大，若每行都用等長的串來存貯，則會浪費存貯空間 解決的辦法之一是建立一個很大的字符數(shù)組作為所有串的共享空間 ——串值共享空間，再為每個串建立一個描述子，用于描述該串的長度以及該串在串值共享空間中的位置等信息，并將這些描述子存入一順序表中，參見下圖： 2021/12/1 43 行表 (linelist) 串值共享空間（ space） MaxSize1 . . . . free 行號 0 1 2 3 行長 位置 行 2 行 3 行 0 行 1 . . . . . . . . . . . 自由空間起始地址 0 串值共享空間 ——String（串） 行表 ——Seqlist（順序表） 設(shè)計行內(nèi)字符插入、刪除操作算法 設(shè)計整行插入、刪除操作算法 2021/12/1 44 第三章 鏈表 順序表有下列缺點： （ 1）插入、刪除操作時需要移動大量元素， 效率較低； （ 2）最大表長難以估計，太大了浪費空間， 太小了容易溢出。 因此，在插入和刪除操作是經(jīng)常性操作的應(yīng)用場合 選用順序存儲結(jié)構(gòu)不太合適，此時可以選用鏈?zhǔn)酱鎯Y(jié) 構(gòu)。 定義：用指針來表示數(shù)據(jù)元素之間關(guān)系的存儲結(jié)構(gòu) 稱之為鏈?zhǔn)酱鎯Y(jié)構(gòu)。 2021/12/1 45 定義：用由指針連接起來的一串結(jié)點來存儲一個線性表 的存儲結(jié)構(gòu)稱為線性鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈表。 當(dāng)每一結(jié)點中只有一個指針，并用來表示一個數(shù) 據(jù)元素到其后繼元素之間的接續(xù)關(guān)系，則稱這種 存儲結(jié)構(gòu)為單鏈表。 注：此處的結(jié)點是指通過指針型變量動態(tài)索取到的存儲空間 . . . ^ first first——頭指針 指針域 (link) last last ——尾指針 數(shù)據(jù)元素域 (data) ^ ——空指針 結(jié)點 1 頭結(jié)點 結(jié)點 0 結(jié)點 n1 e0 e1 en1 2021/12/1 46 上述的單鏈表表頭設(shè)置了一頭結(jié)點，頭結(jié)點的數(shù)據(jù) 域中可以為空，或者存放一些輔助數(shù)據(jù)。 設(shè)置頭結(jié)點的目的是為了簡化對空表的特殊處理， 使得算法更簡單、更有效。 對于帶頭結(jié)點的單鏈表，可以很容易地表示空鏈表： 頭指針 頭結(jié)點 first ^ last 尾指針 2021/12/1 47 用模板定義的單鏈表類 template class Type class