數(shù)據(jù)結(jié)構(gòu)--第五章數(shù)組和廣義表-資料下載頁
2025-01-18 18:43本頁面
【正文】 l D=（） 空表；其長度為零。 lA=(a， (b， c))表長度為 2的廣義表，其中第一個元素是單個數(shù)據(jù) a，第二個元素是一個子表（ b， c）。 lB=（ A， A， D）長度為 3的廣義表，其前兩個元素為表 A，第三個元素為空表 D。 lC=（ a， C） 長度為 2遞歸定義的廣義表， C相當于無窮表 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)成： 標志域 ， 指向表頭的指針域 ，指向表尾的指針域 。而 元素結(jié)點 只需要兩個域： 標志域 和 值域 。 ? D ? ? 1 1 1 A c 0 b 0 a 0 ? 1 1 ? 1 1 1 B C a 0 廣義表 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。 /*標志位 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)圖為： tp atom tag=0 tp hp tag=1 表結(jié)點 原子結(jié)點 ? ? 1 ? 1 a 0 b 0 ? 1 ? c 0 ? 1 1 ? 1 a 0 D A B C ? 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)的形式說明如下：
教學課件相關(guān)推薦
鄂ICP備17016276號-1