【正文】 l D=（） 空表；其長度為零。lA=(a， (b， c))表長度為 2的廣義表，其中第一個元素是單個數(shù)據(jù) a，第二個元素是一個子表（ b， c）。lB=（ A， A， D）長度為 3的廣義表，其前兩個元素為表 A，第三個元素為空表 D。lC=（ a， C） 長度為 2遞歸定義的廣義表， C相當(dāng)于無窮表 C=（ a，（ a，（ a，（ … ））））。 例如：head(A)=a 表 A的表頭是 a。 tail(A)=((b， c)) 表 A的表尾是 ((b， c)) ，廣義表的表尾一定是 一個表 。從上面的例子可以看出：（ 1）廣義表的元素可以是子表，而子表還可以是子表 … ，由此，廣義表是一個多層的結(jié)構(gòu)。 （ 2）廣義表可以被其他廣義表共享。如：廣義表 B就共享表 A。在表 B中不必列出表 A的內(nèi)容，只要通過子表的名稱就可以引用該表。 （ 3）廣義表具有遞歸性，如廣義表 C。 廣義表中有 兩類結(jié)點 ，一類是 單個元素結(jié)點 ，一類是 子表結(jié)點。任何一個非空的廣義表都可以將其分解成 表頭 和 表尾 兩部分，反之，一對確定的表頭和表尾可以唯一地確定一個廣義表。由此，一個 表結(jié)點 可由三個域構(gòu)成： 標(biāo)志域 ， 指向表頭的指針域 ， 指向表尾的指針域 。而 元素結(jié)點 只需要兩個域： 標(biāo)志域 和值域 。 ?D? ? 1 1 1Ac0 b0 a0? 1 1? 1 1 1BCa0廣義表 A、 B、 C、 D的存儲結(jié)構(gòu)圖形式說明如下： /*廣義表的頭尾鏈表存儲結(jié)構(gòu) */ 0 89typedef enum {ATOM, LIST} ElemTag。 /* ATOM＝ 0，表示原子； LIST＝ 1，表示子表 */ typedef struct GLNode { ElemTag tag。 /*標(biāo)志位 tag用來區(qū)別原子結(jié)點和表結(jié)點 */ union { AtomType atom。 /*原子結(jié)點的值域 atom*/ struct { struct GLNode * hp, *tp。} htp。 /*表結(jié)點的指針域 htp， 包括表頭指針域 hp和表尾指針域 tp*/ } atom_htp。 /* atom_htp 是原子結(jié)點的值域 atom和表結(jié)點的指針域 htp的聯(lián)合體域 */ } *GList； 另外，還有一種廣義表存儲結(jié)構(gòu)，在這種結(jié)構(gòu)中，無論是單元素結(jié)點還是子表結(jié)點均由三個域構(gòu)成。 其結(jié)點結(jié)構(gòu)圖為：tpatomtag=0tphptag=1表結(jié)點 原子結(jié)點??1? 1 a0 b0? 1?c0? 1 1? 1 a0DABC? 1 1 ??1廣義表的第二種存儲結(jié)構(gòu)圖typedef enum {ATOM,LIST} ElemTag。 /* ATOM＝ 0，表示原子； LIST＝ 1，表示子表 */ typedef struct GLNode { ElemTag tag。 union {AtomType atom。 struct GLNode * hp。 } atom_hp。 /*atom_hp是原子結(jié)點的值域 atom和表結(jié)點的表頭指針域 hp的聯(lián)合體域 */ struct GLNode * tp。 } *GList。 第二種存儲結(jié)構(gòu)的形式說明如下：實驗與習(xí)題b理論習(xí)題 , , , b實驗題 : ? ① 寫一個主程序來 上機(jī)驗證 求稀疏矩陣 M的轉(zhuǎn)置矩陣 T的快速方法 的存儲結(jié)構(gòu)；并計算 A的轉(zhuǎn)置? 15 0 0 22 ? A = 0 6 0 0 ? 91 0 0 0?