线性表的实现3.3栈（Stack）3.4队列（Queue）3.5串（.ppt

2.3.1 栈的实现 3.3 栈 1、顺序存储 顺序栈示意图 a1 a2 a3 ··· ai ··· an 0 1 2 3 ··· ··· maxlength-1 top 结构类型： typedef struct { elementtype elements[maxlength]; int top ; } STACK ; STACK S ; 栈的容量：maxlength – 1 ; 栈空：S.top = 0 ; 栈满：S.top = maxlength – 1 ; 栈顶元素：S.elements[ S.top ] ; 3.3.1 栈的实现 1、顺序存储 操作： ① Void MAKENULL( STACK S ) { S.top = 0 ; } ; ② Boolean EMPTY( STACK S ) { if ( S.top 1 ) return TRUE else return FALSE ; } ; ③ elementtype TOP( STACK S ) { if EMPTY( S ) return NULL; else return ( S.elements[ S.top ] ); }; 3.3.1 栈的实现 1、顺序存储 操作： ④ elementtype POP( STACK S ) { if ( EMPTY (S ) ) error ( “栈空” ) ; else S.top = S.top – 1 ; } ; ⑤ Void PUSH ( elementtype x, STACK S ) { if ( S.top == maxlength - 1 ) error ( “栈满” ) ; else { S.top = S.top + 1 ; S.elements[ S.top ] = x ; } } ; 3.3.1 栈的实现 2、链式存储 采用由指针形成的线性链表来实现栈 的存储,要考虑链表的哪一端实现元素的插 入和删除比较方便。 实现的方式如右图所示，其操作与线 性链表的表头插入和删除元素相同。 an an-1 a2 ······ a1 ∧ top 3、多个栈共用一个存储空间的讨论 STACK[ maxlength ] bot[1] top[1] bot[2] top[2] bot[3] top[3] top[2] bot[n] top[n] ··· ··· ··· ··· 0 Maxlength-1 bot[n+1] bot[i] top[i] Int Is_Stack_i_Full ( STACK S , int bot , int top , int i ) /* 判断第 i 个栈是否满，满返回1，否则返回0 */ { … … } Void Move_Stack_i ( STACK S , int bot , int top , int i , int dt ) /* 移动第 i 个栈，dt 为位移量 */ { … … } 出 口 入 口 迷宫示例 2、迷宫求解 3.3.2 栈的应用 问题： 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1