数据结构2第2章：线性表.ppt

广义表的操作 boolean EQUAL( listpointer S, T ) { boolean x, y ; y = FALSE ; if ( ( S == NULL ) ( T == NULL ) ) y = TRUE ; else if ( ( S != NULL ) ( T != NULL ) ) if ( S-tag == T-tag ) { if ( S-tag == FALSE { if ( S-element.data == T-element.data ) x = TRUE ; else x = FALSE ; else x = EQUAL( S-element.data,T-element.data ); if ( x== TRUE ) y = EQUAL( S-link, T-link ) ; } return y ; } 线性表小结 单向链表 单向循环链表 双向链表 双向循环链表 线性表的ADT 数学模型 操作集 线性表的逻辑结构 线性表的存储结构 顺序存储 链式存储 游标 限定性数据结构 栈（Stack） 队（Queue） 串 数组(压缩存储) 广义表 顺序存储 与 链式存储 的 比较 本章作业： 教材：Page 72 4 8 15 18 19 22 ⑤ Void DEQUEUE ( QUEUE Q ) ; { if ( EMPTY ( Q ) ) error ( “空队列” ) ; else Q.front = addone ( Q.front ) ; } ; ④ Void ENQUEUE ( elementtype x, QUEUE Q ) { if ( addone ( addone( Q.rear ) ) ==Q.front ) error ( “队列满” ) ; else { Q.rear = addone ( Q.rear ) ; Q.datas[ Q.rear ] = x ; } } 实验一 多项式的代数运算 P(x) = ∑ai x i i=n-1 0 方案1：数组一 方案2：数组二 n-1 an-1 … … i ai … … 3 a3 2 a2 1 a1 0 a0 coefn-1 expn-1 coefn-2 expn-2 … … coefi expi … … coef2 exp2 coef1 exp1 coef0 exp0 … … P(x)=3x14+2x8+1 P(x)=3x14+2x8+1 14 3 13 0 12 0 11 0 10 0 9 0 8 2 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 1 3 14 2 8 1 0 … coeftype p[N}; Struct { coeftype coef; exptype exp; } p[N] 结点结构 coef exp link 系数 指数 下一项地址 结点类型： struct polynode { int coef ； int exp ； polylink *link ； } typedef polynode *polypointer ； P(x) = ∑ai x i i=n 0 方案3：链表 例如： 多项式 p ( x ) = 3x14 + 2x8 +