【正文】 第五章 數(shù)組和廣義表 習(xí)題五 ： ： 利用稀疏矩陣的三元組壓縮存儲(chǔ) 、 實(shí)現(xiàn)壓縮存儲(chǔ)時(shí)的矩陣轉(zhuǎn)置運(yùn)算； 。 第五章 數(shù)組和廣義表 4. 掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，讀者可根據(jù)自己的習(xí)慣熟練掌握任意一種結(jié)構(gòu)的鏈表，學(xué)會(huì)對(duì)非空廣義表進(jìn)行分解的兩種分析方法：即可將一個(gè)非空廣義表分解為表頭和表尾兩部分或者分解為 n個(gè)子表。 2. 掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式 。 q = NULL。 q=p。 if (!StrEmpty(sub) { if(!(p=GList)malloc(sizeof( GLNode)))) exit(OVERFLOW)。 q=p。 第五章 數(shù)組和廣義表 do { sever(sub, hsub)。 // 脫去串 S 的外層括弧 } // else return OK。 p=L。Latom=S。 // 創(chuàng)建空表 else { if(!(L = （ GList)malloc(sizeof( GLNode)))) exit(OVERFLOW)。 第五章 數(shù)組和廣義表 Status CreateGList(Glist amp。 若剩余串非空，則構(gòu)造第二個(gè)表結(jié)點(diǎn) L, 并從串 S 中分解出第二個(gè)子串 ?2, 對(duì)應(yīng)建第二個(gè)子廣義表 ………。 先看第一個(gè)子表和廣義表的關(guān)系 : 1 L 指向廣義表 的頭指針 指向第一個(gè) 子表的頭指針 第五章 數(shù)組和廣義表 再看相鄰兩個(gè)子表之間的關(guān)系 : 1 1 指向第 i+1個(gè) 子表的頭指針 指向第 i個(gè) 子表的頭指針 可見，兩者之間通過表結(jié)點(diǎn)相鏈接。 由單字符建立的子表只有一個(gè)原子結(jié)點(diǎn)。 由于 S中的每個(gè)子串 ?i定義 L 的一個(gè) 子表 ，從而產(chǎn)生 n 個(gè)子問題，即分別由這 n個(gè)子串 (遞歸 )建立 n 個(gè)子表，再 組合 成 一個(gè)廣義表。 // 復(fù)制求得表尾 T 的一個(gè)副本 L 第五章 數(shù)組和廣義表 例三 創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu) 對(duì)應(yīng)廣義表的不同存儲(chǔ)結(jié)構(gòu)，相應(yīng)地有不同的創(chuàng)建存儲(chǔ)結(jié)構(gòu)的算法。 } // CopyGList 分別復(fù)制表頭和表尾 第五章 數(shù)組和廣義表 CopyGList(T, L)。 if (Ltag == ATOM) Tatom = Latom。 // 復(fù)制空表 else { if ( !(T = （ Glist)(malloc(sizeof( GLNode))) ) exit(OVERFLOW)。 將廣義表分解成表頭和表尾兩部分，分別(遞歸 )復(fù)制求得新的表頭和表尾， 第五章 數(shù)組和廣義表 若 LS= NULL 則 NEWLS=NULL 否則 產(chǎn)生結(jié)點(diǎn) NEWLS 和 LS相同，即若 LS為元素結(jié)點(diǎn)，則直接將 LS的值賦給 NEWLS，否則為表結(jié)點(diǎn)，則完成下列工作： 將表頭 LS 復(fù)制到 NEWLS 將表尾 LS 復(fù)制到 NEWLS 復(fù)制求廣義表的算法描述如下 : 第五章 數(shù)組和廣義表 Status CopyGList(GList amp。 可以直接求解的兩種簡單情況為 : 空表復(fù)制求得的新表自然也是空表 。 if (dep max) max = dep。 pp。 //L為空表 if (Ltag == ATOM) return 0。 } return max + 1。 pp=pp){ dep = GlistDepth(pp)。 } *GList tag=1 hp tp ptr 表結(jié)點(diǎn) tag=0 atom 原子結(jié)點(diǎn)： 第五章 數(shù)組和廣義表 例一 求廣義表的深度 例二 復(fù)制廣義表 例三 創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu) 第五章 數(shù)組和廣義表 例 1: 求廣義表的深度 設(shè)廣義表 LS為： LS = ( ?1, ?2, ???, ?n ) 則 LS的深度定義為： 0 當(dāng) LS為原子時(shí) DEPTH（ LS） = 1 當(dāng) LS為空表時(shí) 1+ Max{ DEPTH（ ?i） } n≥ 1 1≤i≤n 在按數(shù)學(xué)式子寫遞歸算法時(shí)，一定不要懷疑它的正確性??！ 第五章 數(shù)組和廣義表 int GlistDepth(Glist L) { // 返回指針 L所指的廣義表的深度 for (max=0, pp=L。} ptr。 // 標(biāo)志域 union{ AtomType atom。 第五章 數(shù)組和廣義表 廣義表的頭、尾鏈表存儲(chǔ)表示： typedef enum {ATOM, LIST} ElemTag。 + 子表 n 因此常利用分治法求解之。 2) 將 n號(hào)盤從 x 軸移動(dòng)至 z 軸 。 分治法的設(shè)計(jì)思想為 : 在利用分治法求解時(shí)，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解 第五章 數(shù)組和廣義表 例如 :焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個(gè)盤分成兩個(gè)子集 (1至 n1 和 n )，從而產(chǎn)生下列三個(gè)子問題 : 1) 將 1至 n1號(hào)盤從 x 軸移動(dòng)至 y 軸 。 } // fact 第五章 數(shù)組和廣義表 對(duì)于一個(gè) 輸入規(guī)模為 n 的函數(shù)或問題，用某種方法把輸入 分割成 k(1k≤ n)個(gè)子集 ，從而 產(chǎn)生 l 個(gè)子問題 ，分別求解這 l 個(gè)問題， 得出 l 個(gè)問題的子解 ，再用某種方法把它們 組合成原來問題的解 。 } } // hanoi 第五章 數(shù)組和廣義表 求階乘算法： n!=n*(n1)! int fact(int n ) { if (n==0 ) return 1。 move(x, n, z)。 第五章 數(shù)組和廣義表 例如 : 梵塔的遞歸函數(shù) void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z)。//廣義表類型 原子結(jié)點(diǎn)： tag=1 hp tp tag=0 atom tp 表結(jié)點(diǎn) : 第五章 數(shù)組和廣義表 A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) A 1 ^ ^ B 1 ^ 0 e ^ 1 ^ 1 1 ^ D 1 C 1 ^ 1 ^ 0 d ^ 0 a 0 b 0 c 第五章 數(shù)組和廣義表 m元多項(xiàng)式的表示： P 110112 自學(xué)！ 第五章 數(shù)組和廣義表 廣義表的遞歸算法 遞歸函數(shù) 一個(gè) 含直接或間接調(diào)用本函數(shù)語句 的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件 : 1)在每一次調(diào)用自己時(shí)，必須是 (在某種意義上 )更接近于解 。 // 表結(jié)點(diǎn)的表頭指針 struct GLNode *tp。 //atom是原子結(jié)點(diǎn)的值域 struct GLNode *hp。 // typedef struct GLNode{ ElemTag tag。//廣義表類型 第五章 數(shù)組和廣義表 空表 LS = NULL 非空表 LS tag=1 指向表頭的指針 指向表尾的指針 若表頭為原子，則為 tag=0 atom 否則，依次類推。 }H。 struct { struct GLNode *hp,*tp。// typedef struct GLNode{ ElemTag tag。 第五章 數(shù)組和廣義表 廣義表是遞歸定義的線性結(jié)構(gòu)，可以形式的寫為： LS = ( ?1, ?2, ???, ?n ) 其中： ?i或?yàn)樵踊驗(yàn)閺V義表 例如 : A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) E=( a , E ) 相當(dāng)于一個(gè)無限的列表 ( a , ( a , ( a ,…) ) ) 基本概念： 原子、子表、表長、空表、 表頭 、 表尾 、表的深度 第五章 數(shù)組和廣義表 廣義表是一個(gè) 多層次 的 線性結(jié)構(gòu) 例如： D=( A , B , C )=( ( ) , ( e ), ( a , ( b , c , d ) )) A C a e B b c d D 第五章 數(shù)組和廣義表 任何一個(gè)非空廣義表 LS = ( ?1, ?2, ???, ?n ) 均可分解為 表頭 Head(LS) = ?1和 表尾 Tail(LS) = (?2, ???, ?n ) 兩部分 例如： F=( ( a , b ) , c, ( d ) ) Head(F)= ( a , b ) , Tail(F)=( c , ( d ) ) Head(Head(F))=a。e)。 DeleteFirst_GL(amp。 ? 插入和刪除操作 InsertFirst_GL(amp。 GetHead(L)。 GListDepth(L)。T, L)。L, S)。L)。L)。 n≥0。} else {在相應(yīng)的行、列中，刪除 pa所指結(jié)點(diǎn)； pa、 pb后 移； break。pa=paright。 第五章 數(shù)組和廣義表 if( k) { pae=k。break。 case pajpbj: pre=pa。pb= [row]。row++) { pre=NULL。A, CrossList B){ //A=A+B for( row=1。 }//列插入，在 q后 } return OK。 pdown=qdown。 qdownii。 qdown amp。 [j]=p。 qright=p。 q=qright)。amp。 } else {//將 p插在合適的位置上 for(q=[i]。 //生成結(jié)點(diǎn) if( [i]==NULL|| [i]jj) {//插在表頭 pright=[i]。 pj=j。e) ) {//按任意次 序輸入非零元； 第五章 數(shù)組和廣義表 if(!(p=(OL