數(shù)據(jù)結(jié)構(gòu)ppt課件chap-wenkub
2022-08-18 22:05:00 本頁面
【正文】 置矩陣元素 Col = [p].j。 ++col) cpot[col] = cpot[col1] + num[col1]。 ++t) ++num[[t].j]。 col=。T){ = 。 for (col=2。 row=mu。 } TSMatrix。 //該非零元的行下標和列下標 ElemType e。 3) 操作方便 。 LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + ∑ ci ji i =1 n 假設(shè) m 行 n 列 的矩陣含 t 個非零元素 ，則稱 為 稀疏因子 通常認為 ? ? 的矩陣為稀疏矩陣 nm t??? 稀疏矩陣的壓縮存儲 何謂稀疏矩陣？ 以常規(guī)方法，即以二維數(shù)組表示 高階的稀疏矩陣時產(chǎn)生的 問題 : 1) 零值元素占了很大空間 。 2)以列序為主序 (高下標優(yōu)先 )。 操作結(jié)果： 若下標不超界，則將 e的值賦 給所指定的 A的元素，并返回 OK。e, index1, ..., indexn) 初始條件： A是 n維數(shù)組， e為元素變量， 隨后是 n 個下標值。A, n, bound1, ..., boundn) 操作結(jié)果： 若維數(shù) n 和各維長度合法， 則構(gòu)造相應(yīng)的數(shù)組 A，并 返回 OK。A, n, bound1, ..., boundn) DestroyArray(amp。A) Value(A, amp。 DestroyArray(amp。 操作結(jié)果： 若各下標不超界，則 e賦值為 所指定的 A 的元素值，并返 回 OK。 數(shù)組的順序表示和實現(xiàn) 類型特點 : 1) 只有引用型操作，沒有加工型操作 。 例如： 稱為 基地址 或基址。 2) 計算中進行了很多和零值的運算， 遇除法，還需判別除數(shù)是否為零 。 即 : 能盡可能快地找到 與下標值 (i, j) 對應(yīng)的元素 。 // 該非零元的值 } Triple。 // 稀疏矩陣類型 如何求轉(zhuǎn)置矩陣？ ????????????028003600070500140??????????????????005280000007143600用常規(guī)的二維數(shù)組表示時的算法 其時間復雜度為 : O(mu nu) for (col=1。 ++row) T[col][row] = M[row][col]。 col=。 = 。 ++col) num[col] = 0。 cpot[1] = 1。 for (p=1。 q = cpot[col]。 ++cpot[col] 分析算法 FastTransposeSMatrix的時間復雜度： 時間復雜度為 : O(+) for (col=1。 ++t) … … for (col=2。 ++p) … … 三元組順序表又稱 有序的雙下標法 ，它的特點是，非零元在表中按行序有序存儲，因此 便于進行依行順序處理的矩陣運算 。 int mu, nu, tu。 while ([p].i==r amp。amp。 i=m1。 for (k=1。 if Q是非零矩陣 { // 逐行求積 for (arow=1。Q) { if ( != ) return ERROR。 if (* != 0) { // Q是非零矩陣 for (arow=1。 // 當前行各元素累加器清零 [arow] = +1。 if (brow ) t = [brow+1]。 // 乘積元素在 Q中列號 ctemp[ccol] += [p].e * [q].e。 [] = {arow, ccol, ctemp[ccol]}。 n≥0。 注意 :“原子”的深度為 0 。 遞歸表的深度是無窮值，長度是有限值 。L)。T, L)。 GetHead(L)。 DeleteFirst_GL(amp。 廣義表的表示方法 通常采用頭、尾指針的鏈表結(jié)構(gòu) 表結(jié)點 : 原子結(jié)點： tag=0 data tag=1 hp tp 1) 表頭、表尾分析法 : 構(gòu)造存儲結(jié)構(gòu)的兩種分析方法 : 若表頭為原子，則為 空表 ls = NIL 非空表 ls tag=1 指向表頭的指針 指向表尾的指針 tag=0 data 否則，依次類推。 例如 : 梵塔的遞歸函數(shù) void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z)。 } } 二叉樹的遍歷 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P)) { if (T) { Visit(Tdata)。若子問題還相當大， 則可以反復使用分治法，直至最后所分得 的子問題足夠小，以至可以直接求解為止。 2) 將 n號盤從 x 軸移動至 z 軸 。 可遞歸求解 Traverse(RBT) 廣義表從結(jié)構(gòu)上可以分解成 廣義表 = 表頭 + 表尾 或者 廣義表 = 子表 1 + 子表 2 + 算法設(shè)計中的關(guān)鍵問題是， 如何將 l 個子問題的解組合成原問題的解。 // 原子結(jié)點的數(shù)據(jù)域 struct {struct GLNode *hp, *tp。 pp。 } // GlistDepth if (!L) return 1。 pp=pp){ dep = GlistDepth(pp)。 原子結(jié)點可以直接復制求得。 // 建表結(jié)點 Ttag = Ltag。 // 復制求得表頭 T L CopyGList(T, L)。 例三 創(chuàng)建廣義表的存儲結(jié)構(gòu) 對應(yīng)廣義表的 不同 定義方法相應(yīng)地有 不同 的創(chuàng)建存儲結(jié)構(gòu)的算法。 由單字符建立的子表只是一個原子結(jié)點。 若 剩余串 非空，則構(gòu)造 第二個表結(jié)點 L, 并從串 S 中分解出 第二個子串 ?2, 對應(yīng)建 第二個子 廣義表 ………。 // 創(chuàng)建空表 else { L = new GLNode。 // 脫去串 S 的外層括弧 } // else } 由 sub中所含 n個子串建立 n個子表 。 } } while (!StrEmpty(sub))。 ptag=ATOM。后置遞歸的設(shè)計思想為 : 遞歸的 終結(jié)狀態(tài) 是，當前的問題可以直接求解 ，對原問題而言，則是已走到了求解的 最后一步 。 分析 : 2) 從另一角度看，鏈表又是一個遞歸結(jié)構(gòu)，若 L 是線性鏈表 (a1, a2, ? , an) 的頭指針，則 Lnext是線性鏈表 (a2, ? , an)的頭指針。 free(p)。 不同處 :1)廣義表的數(shù)據(jù)元素可能還是個 廣義表 。 // 考察第一個子表 if ((headtag == Atom) amp。 // 修改指針
電大資料相關(guān)推薦
鄂ICP備17016276號-1