数据结构05-数组.pptVIP

第5章　数组和广义表 25 0 0 64 0 -8 0 0 20 0 0 0 M= ∧ ∧ 20 1 3 ∧ ∧ -8 2 2 ∧ ∧ 64 4 1 25 1 1 ∧ right down e j i 行号 列号 值 下一行的 非0元素 下一列的 非0元素 列头指针数组 行头 指 针 数 组 2.十字链接表 例 稀疏矩阵 5.4 广义表(generalized list), 列表(lists) 5.4.1广义表的定义和术语 n(n≥0)个数据元素或广义表的一个有限序列叫做广义表。 记作: LS=(e1,e2,...,en)。 n为LS的长度。 其中: LS----广义表名 ei----单元素、原子,约定用小写, 1≤i≤n ei----广义表，约定用大写, 1≤i≤n (1)空表 LS=( ),n=0 (2)非空表 LS=(e1,e2,...,en) n0 其中: e1---LS的表头/首部，记作: Head(LS)=e1 (e2,...,en)--- LS的表尾/尾部, 记作： Tail(LS)=(e2,...,en) 广义表举例： (1) A=( ) // 空表 (2) B=(e) Head(B)=e Tail(B)=( ) (3) C=(a,b,c) Head(C)=a Tail(C)=(b,c) Head(Tail(C))=b Tail(Tail(C))=(c) (4) D=(a,(b,c)) Head(D)=a Tail(D)=((b,c)) D2=((a,b),c) Head(D2)=(a,b) Tail(D2)=(c) (5) E=((a,b),c,(d,e)) Head(E)=(a,b) Tail(E)=(c,(d,e)) Head(Tail(E))=c Tail(Tail(E))=((d,e)) (6) F=(A,B,C,d)=(( ),(e),(a,b,c),d) Head(F)=( ) Tail(F)=((e),(a,b,c),d) (7) G=(a,G) //递归广义表 =(a,(a,G))=(a,(a,(a,G))) =(a,(a,(a,(a,...G)))) Head(G)=a Tail(G)=(G)=((a,G)) (8) H=(( ),(( ),( ))) Head(H)=( ) Tail(H)=((( ),( ))) A B a 5.4.2 广义表的图型表示----树型结构 约定 □----单元素/原子 ○----列表,若有表名,附表名 例 (1) A=( ) (2) B=(a) C b D a c a b c (5) E=((a,b),c,(d,e)) (6) F=(A,B,C,d)=(( ),(e),(a,b,c),d) E b c a e d a d e c b F B A C (3) C=(a,b,c) (4) D=(a,(b,c)) H G a a G a G ... (7) G=(a,G) (8) H=(( ),(( ),( ))) 5.4.3 广义表的操作 1.求长度：Leng(LS) a=( ) Leng(A)=0 G=(a,G) Leng(G)=2 H=(( ),(( ),( ))) Leng(H)=2 F=(A,B,C,d) Leng(F)=4 2.求表头： Head(LS) G=(a,G) Head(G)=a E=((a,b),c,(d,e)) Head(E)=(a,b) 3.求表尾： Tail(LS) G=(a,G) Tail(G)=(G)=((a,G)) E=((a,b),c,(d,e)) Tail(E)=(c,(d,e)) 4.求第i个元素：GetElem(LS,i)=ei 1≤i≤n I=((a,b),c,( ),(d)) GetElem(I,1)=(