31抽象数据型线性表32线性表的实现33栈stack34队

31抽象数据型线性表32线性表的实现33栈stack34队内容摘要：

e. 3 25 操作 ： ①在表左端插入结点 INSERT(x,FIRST(R),R)。 → LINSERT(x,R) Void LINSERT( elementtype x , LIST amp。 R ) { celltype *p。 p = new celltype。 p→element = x。 if ( R == NULL ) { p→next = p。 R = p。 } else { p→next = R→next。 R→next = p。 } }。 环形链表 ② 在表右端插入结点 INSERT(x,END(R),R)。 → RINSERT(x,R) Void RINSERT( elementtype x , LIST R ) { LINSERT ( x , R )。 R = R→next。 } 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 26 操作 ： ③从表左端删除结点 DELETE(FIRST(R),R)。 →LDELETE(R) Void LDELETE( LIST amp。 R ) { celltype *p。 if ( R == NULL ) error ( “空表” )。 else { p = R→next。 R→next = p→next。 if ( p == R ) R=NULL。 delete p。 } }。 环形链表 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 27 环形链表 双向环形链表 ： a1 ai an … … R 双向环形链表的结构与双向连表结构相同，只是将表头元素 的空 previous域指向表尾，同时将表尾的空 next域指向表头结点， 从而形成向前和向后的两个环形链表，对链表的操作变得更加灵 活。 举例：设计算法，将一个单向环形链表反向。 头元素变成尾 元素，尾元素变成新的头元素，依次类推。 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 28 环形链表 a1 a2 a3 an … R an an1 an2 a1 … R Void REVERS( LIST amp。 R ) { position p, q。 p = R→next。 R→next = p→next。 p→next = p。 while ( R != NULL ) { q = R→next。 R→next = q→next。 q→next = p→next。 p→next = q。 } R = p。 } ； 算法如下 ： 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 29 栈（ Stack） 栈是线性表的一种特殊形式，是一种限定性数据结构， 也就是在对线性表的操作加以限制后，形成的一种新的数 据结构。 定义 ：是限定只在表尾进行 插入和删除操作的线性表。 栈又称为 后进先出 (Last In First Out )的线性表。 简称 LIFO结构。 栈举例 a1 a2 an1 an Insert Delete top bottom 栈底 栈顶 栈示意图 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 30 栈 栈的基本 ① MAKENULL ( S ) 操作 ② TOP ( S ) ③ POP ( S ) ④ PUSH ( x , S ) ⑤ EMPTY ( S ) 举例 ：利用栈实现行编辑处理。 设定符号“ ”为擦讫符，用以删 除“ ”前的字符；符号“ @”为删 行符，用以删除当前编辑行。 原理： 一般字符进栈； 读字符 擦讫符退栈； 删行符则清栈 算法 ： Void LINEEDIT( ) { STACK Ｓ； char c。 MAKENULL ( S )。 c = getchar ( )。 while ( c != ‗\n‘ ) { if ( c == ‗‘ ) POP ( S )。 else if ( c == ‗@‘ ) MAKENULL ( S )。 else PUSH ( c , S )。 c = getchar( )。 } 逆序输出栈中所有元素； ｝ 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 31 栈的实现 栈 顺序存储 顺序栈示意图 an ai a3 a2 a1 maxlength1 3 2 1 0 top 结构类型： typedef struct { elementtype elements[maxlength]。 int top。 } STACK。 STACK S。 栈的容量： maxlength – 1。 栈空： = 0。 栈满： = maxlength – 1。 栈顶元素： [ ]。 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 32 栈的实现 顺序存储 操作 ： ① Void MAKENULL( STACK amp。 S ) { = 0。 }。 ② Boolean EMPTY( STACK S ) { if ( 1 ) return TRUE else return FALSE。 }。 ③ elementtype TOP( STACK S ) { if EMPTY( S ) return NULL。 else return ( [ ] )。 }。 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 33 栈的实现 顺序存储 操作 ： ④ elementtype POP( STACK amp。 S ) { if ( EMPTY (S ) ) error ( ―栈空” )。 else = – 1。 }。 ⑤ Void PUSH ( elementtype x, STACK amp。 S ) { if ( == maxlength 1 ) error ( ―栈满” )。 else { = + 1。 [ ] = x。 } }。 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 34 栈的实现 链式存储 采用由指针形成的线性链表来实现栈 的存储 ,要考虑链表的哪一端实现元素的插 入和删除比较方便。 实现的方式如右图所示，其操作与线 性链表的表头插入和删除元素相同。 an an1 a2 a1 ∧ top 多个栈共用一个存储空间的讨论 STACK[ maxlength ] bot[1] top[1] bot[2] top[2] bot[3] top[3] top[2] bot[n] top[n] 0 Maxlength1 bot[n+1] bot[i] top[i] 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 35 Int Is_Stack_i_Full ( STACK S , int bot , int top , int i ) /* 判断第 i 个栈是否满，满返回 1，否则返回 0 */ { … … } Void Move_Stack_i ( STACK amp。 S , int amp。 bot , intamp。 top , int i , int dt ) /* 移动第 i 个栈， dt 为位移量 */ { … … } 算法与数据结构 . 第三章 线 性 表 国家示范性软件学院 2020 秋 Slide. 3 36 出 口 入 口 迷宫示例 迷宫求解 栈的应用 问题： 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 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 一个迷宫可用上图所示方阵 [m,n]表示， 0表示能通过， 1 表 示不。