【正文】 Ttag = Ltag。T, Glist L) { if (!L) T = NULL。 原子結(jié)點(diǎn)可以直接復(fù)制求得。 } 例如 : pp pp pp pp pp pp 1 1 1 L … ?例二 復(fù)制廣義表 新的廣義表由新的表頭和表尾構(gòu)成。 pp=pp){ dep = GlistDepth(pp)。 for (max=0, pp=L。 } // GlistDepth if (!L) return 1。 if (dep max) max = dep。 pp。 }。 // 原子結(jié)點(diǎn)的數(shù)據(jù)域 struct {struct GLNode *hp, *tp。 // ATOM==0:原子 , LIST==1:子表 typedef struct GLNode { ElemTag tag。 算法設(shè)計(jì)中的關(guān)鍵問題是， 如何將 l 個(gè)子問題的解組合成原問題的解。 可遞歸求解 Traverse(RBT) 廣義表從結(jié)構(gòu)上可以分解成 廣義表 = 表頭 + 表尾 或者 廣義表 = 子表 1 + 子表 2 + 3) 遍歷右子樹 。 2) 將 n號盤從 x 軸移動至 z 軸 。 例如 : 焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個(gè)盤分成兩個(gè)子集 (1至 n1 和 n )，從而產(chǎn)生下列三個(gè)子問題 : 1) 將 1至 n1號盤從 x 軸移動至 y 軸 。若子問題還相當(dāng)大， 則可以反復(fù)使用分治法，直至最后所分得 的子問題足夠小，以至可以直接求解為止。 (PreOrderTraverse(Trchild, Visit)。 } } 二叉樹的遍歷 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P)) { if (T) { Visit(Tdata)。 move(x, n, z)。 例如 : 梵塔的遞歸函數(shù) void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z)。 指向子表 2 的指針 指向子表 n 的指針 例如 : ? ls ((x)) LS=( a, (x,y), ((x)) ) a (x, y) 廣義表操作的遞歸函數(shù) 遞歸函數(shù) 一個(gè) 含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件 : 1)在每一次調(diào)用自己時(shí)，必須是 (在某 種意義上 )更接近于解 。 廣義表的表示方法 通常采用頭、尾指針的鏈表結(jié)構(gòu) 表結(jié)點(diǎn) : 原子結(jié)點(diǎn)： tag=0 data tag=1 hp tp 1) 表頭、表尾分析法 : 構(gòu)造存儲結(jié)構(gòu)的兩種分析方法 : 若表頭為原子，則為 空表 ls = NIL 非空表 ls tag=1 指向表頭的指針 指向表尾的指針 tag=0 data 否則，依次類推。e)。 DeleteFirst_GL(amp。 ? 插入和刪除操作 InsertFirst_GL(amp。 GetHead(L)。 GListDepth(L)。T, L)。L, S)。L)。L)。 遞歸表的深度是無窮值，長度是有限值 。 4) 廣義表可以 共享 。 注意 :“原子”的深度為 0 。 2) 廣義表的 長度 定義為最外層包含元素個(gè)數(shù) 。 n≥0。 若 M是 m行 n列的稀疏矩陣， N是 n行 p列的稀疏矩陣， 則 M中非零元的個(gè)數(shù) = ?M?m?n， N中非零元的個(gè)數(shù) = ?N?n?p， 相乘算法的時(shí)間復(fù)雜度就是 ?(m?p?(1+n?M?N)) ， 當(dāng) ?M 和 ?N n 1000時(shí)， 相乘算法的時(shí)間復(fù)雜度就相當(dāng)于 ?(m?p)。 [] = {arow, ccol, ctemp[ccol]}。 ccol=。 // 乘積元素在 Q中列號 ctemp[ccol] += [p].e * [q].e。 q t。 if (brow ) t = [brow+1]。 p[arow+1]。 // 當(dāng)前行各元素累加器清零 [arow] = +1。 ++arow) { // 處理 M的每一行 } // for arow } // if return OK。 if (* != 0) { // Q是非零矩陣 for (arow=1。 = 。Q) { if ( != ) return ERROR。 ++arow) { // 處理 M的每一行 ctemp[] = 0。 if Q是非零矩陣 { // 逐行求積 for (arow=1。 ++k) Q[i][j] += M[i][k] * N[k][j]。 for (k=1。 j=n2。 i=m1。 else return 0。amp。[p].j c) p++。 while ([p].i==r amp。 // 行邏輯鏈接順序表類型 修改前述的稀疏矩陣的結(jié)構(gòu)定義，增加一個(gè)數(shù)據(jù)成員 rpos, 其值在稀疏矩陣的初始化函數(shù)中確定。 int mu, nu, tu。 二、行邏輯聯(lián)接的順序表 define MAXMN 500 typedef struct { Triple data[MAXSIZE + 1]。 ++p) … … 三元組順序表又稱 有序的雙下標(biāo)法 ，它的特點(diǎn)是，非零元在表中按行序有序存儲，因此 便于進(jìn)行依行順序處理的矩陣運(yùn)算 。 ++col) … … for (p=1。 ++t) … … for (col=2。 ++col) … … for (t=1。 ++cpot[col] 分析算法 FastTransposeSMatrix的時(shí)間復(fù)雜度： 時(shí)間復(fù)雜度為 : O(+) for (col=1。 [q].j = [p].i。 q = cpot[col]。 ++p) { } } // if return OK。 for (p=1。 col=。 cpot[1] = 1。 t=。 ++col) num[col] = 0。 if () { for (col=1。 = 。 Status FastTransposeSMatrix(TSMatrix M, TSMatrix amp。 col=。 1 2 151 5 52 2 73 1 363 4 28 co l 1 2 3 4 5N u m [ p os] 1 2 0 1 1C p ot [ c ol ] 1 2 4 4 5 cpot[1] = 1。 ++row) T[col][row] = M[row][col]。 ++col) for (row=1。 // 稀疏矩陣類型 如何求轉(zhuǎn)置矩陣？ ????????????028003600070500140??????????????????005280000007143600用常規(guī)的二維數(shù)組表示時(shí)的算法 其時(shí)間復(fù)雜度為 : O(mu nu)