数据结构 数组与广义表.pptVIP

十字链表表示的稀疏矩阵举例 i j e down right 结点结构： 稀疏矩阵M： M的十字链表： M.chead M.rhead 1 1 3 1 4 5 ^ ^ 2 2 -1 ^ ^ ^ ^ 3 1 2 采用十字链表存储稀疏矩阵，创建稀疏矩阵、稀疏矩阵的运算见教材P104－106 * 5.3 广义表 (General Lists ) 广义表(列表):n (?0)个表元素组成的有限序列，记作 LS = (a1, a2, …, an) 表头(head):n0时,表的第一个表元素 表尾(tail):其它表元素组成的表 空表:n = 0 的广义表。 广义表的特性： 有长度：n 有深度：广义表中括号的重数 可递归 可共享 表名 表元素 表长 非空列表表头可是原子或列表,表尾必定是列表 * 广义表的图形表示 1、A=(/) 2、B=(e) 3、C=(a,(b,c,d)) 4、D=(A，B，C) 注： ○：表 □：原子 * 5.3.1广义表的定义 GetHead(L):在广义表L存在的条件下，取L的表头。 GetTail(L):在广义表L存在的条件下，取L的表尾。 举例： 1 A=() 　　 GetHead(A)=NULL,GetTail(A)=NULL 2 B=(e) 　　 GetHead(B)=e, GetTail(B)=() 3 C=(a,(b,c,d)) GetHead(C)=a, GetTail(C)=(b,c,d) GetHead((b,c,d))=b, GetTail((b,c,d))=(c,d) GetHead((c,d))=c, GetTail((c,d))=(d) 4 D=(A,B,C) GetHead(D)=A, GetTail(D)=(B,C) 　　　 GetHead((B,C))=B, GetTail((B,C))=(C) 5 E=(()) 　 GetHead(B)=(), GetTail(B)=() * 5.3.2 广义表的存储结构 采用链式存储结构，元素包括原子和子表，结点结构： 表结点： 表示列表 原子结点： 表示原子 1、广义表的头尾链表存储表示： typedef enum {ATOM,LIST}ElemTag;//ATOM=0:原子,LIST=1:子表 typedef struct GLNode{ ElemTag tag;//公共部分，用来区分原子结点和表结点 Union{//原子结点和表结点的联合部分 AtomType atom; Struct{struct GLNode *hp,*tp;}ptr;//hp指向表头,tp指向表尾 }; }*Glist; tag=1 hp tp tag=0 atom * A=(/) B=(e) C=(a,(b,c,d)) D=(A，B，C) E=(a，E) 5.5 广义表的存储结构示例 B 0 e 1 ^ C 1 1 ^ 0 a 1 1 1 ^ 0 b 0 d 0 c D 1 ^ 1 1 ^ E 1 1 ^ 0 a A=NIL 表结点： 原子结点： tag=1 hp tp tag=0 atom * 5.5 广义表的存储结构示例 对广义表：C = (a,(b,c,d))，其头尾链表为： 1 C 0 a 1 ^ 1 0 b 1 0 c 1 ^ 0 d * 2、广义表的扩展线性链表存储表示： typedef enum {ATOM,LIST}ElemTag; //ATOM==0:原子，LIST==1：子表 typedef struct GLNode{ ElemTag tag; //公共部分，用来区分原子结点和表结点 Union{//原子结点和表结点的联合部分 AtomType atom;//原子结点的值域 Struct GLNode *