分枝单链表存贮方法 (a)为每个设置一个结点H,称其为a的头结点,其结构为 tag|…. pEle next tag:指示a是单元素还是广义表(我们设tag为0时表示a1为单元素)。 pele:若a1为单元素,则指向a1的内容,否则指向a1对应的广义表 (可以用第一个头结点H1的指针代表广义表) enext:单链表链指针,即指向l
11 分枝单链表存贮方法 (a) 为每个αi设置一个结点Hi，称其为αi的头结点，其结构为： •tag：指示αi是单元素还是广义表(我们设tag为0时表示αi为单元素）。 •pElem：若αi为单元素，则指向αi的内容，否则指向αi对应的广义表 (可以用第一个头结点H1的指针代表广义表). •next：单链表链指针，即指向Hi+1。 tag … pElem next
分枝单链表存贮方法 (b)a为单元素时,α的内容应对应一片连续区域,可在 它中设置一个长度字段。 (c)直接元素构成的单链表,根据具体问题的需要,可以 是带头结点的,或循环式的,或双向链式的或这些的组 人 (d)如果不共享单元素内容,且单元素内容的长度相等 (或差别不大),则可将单元素内容直接放到元素头结 点中。 12
12 分枝单链表存贮方法 (b) αi为单元素时，αi的内容应对应一片连续区域，可在 它中设置一个长度字段。 (c) 直接元素构成的单链表，根据具体问题的需要，可以 是带头结点的，或循环式的，或双向链式的或这些的组 合。 (d)如果不共享单元素内容，且单元素内容的长度相等 （或差别不大），则可将单元素内容直接放到元素头结 点中
广义表存储结构示例 B-0 a (a)B=(a, b, c) f 00 (b)C=(a,(b,c,d) 13
13 广义表存储结构示例 (a) B=(a, b, c) 0 a 0 0 ^ b c B 0 1 ^ 0 0 0 ^ b c d (b) C=(a, (b, c, d) ) C a
广义表存储结构示例 B 40 b10 (d)E=(a,E) (c)D=(B,(ab),c))
14 广义表存储结构示例 (c) D=(B, ((a,b), c) ) 0 ^ 1 1 ^ 1 B 0 0 ^ a b D 0 1 a (d) E=(a, E)