? 3.1 栈
3.1.1抽象数据类型栈的定义
3.1.2栈的表示与实现
? 3.2 栈的应用举例
3.2.1 数制转换
3.2.4 迷宫求解
3.2.5 表达式求值
? *3.3 栈和递归的实现
? 3.4 队列
3.4.1抽象数据类型队列的定义
3.4.2 链队列 -- 队列的链式表示与实现
3.4.3 循环队列 -- 队列的顺序表示与实现
第三章 栈和队列 -----
操作受限 的 线性表
? 栈 （ stack）, 先进后出 ( FILO） 的线性表 。
? 或 后进先出 （ LIFO） 的线性表 。
? 或仅在表尾进行插入和删除操作的线性表 。
? 栈顶 （ top）, 线性表的表尾端, 即可操作端 。
? 栈底 （ bottom）, 线性表的表头 。
3.1 栈
3.1.1 抽象数据类型 栈的定义
栈底 栈顶
......a1 a2 a3 an-1 an
入栈 (push)
出栈 (pop)
栈的抽象数据类型
?ADT Stack {
? 数 据 对 象, D = {ai | ai 属于 Elemset,
(i=1,2,…,n,n≥ 0)}
? 数据关系, R1 = { ＜ ai-1,ai ＞ |ai-1,ai 属于
D,(i=2,3,…,n)} 约定 an为栈顶,a1为栈底 。
? 基本操作,
? InitStack(&S); DestroyStack(&S);
? ClearStack(&S); StackEmpty(S);
? StackLength(S) ; GetTop(S,&e);
? Push(&S,e); Pop(&S,&e);
? StackTraverse(S,visit ())
?}ADT Stack
栈的 基本操作 (之一 )
? InitStack(&S)
? 操作结果,构造一个空的栈 S。
? DestroyStack(&S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 销毁栈 S。
?ClearStack(&S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 将栈 S重置为空栈 。
栈的 基本操作 (之二 )
?StackEmpty(S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 若栈 S为空栈, 则返回 TURE;否则
返回 FALSE。
?StackLength(S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 返回栈 S中的数据元素个数 。
?GetTop(S,&e)
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 用 e返回栈 S中栈顶元素的值 。
栈的 基本操作 (之三 )
?Push(&S,e)
? 初始条件, 栈 S已经存在 。
? 操作结果, 插入元素 e为新的栈顶元素 。
?Pop(&S,&e)
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 删除 S的栈顶元素并用 e返回其值 。
?StackTraverse(S,visit ())
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 从栈底到栈顶依次对 S的每个元素
调用函数 visit ()。 一旦 visit ()失败, 则操作
失败 。
3.1.2 栈的顺序表示与实现 ---
(顺序栈 )
? typedef struct{
? SElemType *base;
? /* 在栈构造之前和销毁之后,base的值为 NULL*/
? SElemType *top; /* 栈顶指针 */
? int stacksize; /* 当前已分配的存储空间，以元素为单位 */
? }SqStack;
? #define STACK_INIT_SIZE 100
? #define STACKINCREMENT 10
? #define OK 1
? #define OVERFLOW -1
? #define ERROR 0
顺序栈示意图
*base
*top
stacksize
......a1,.,ai an
*base
*top
stacksize
初始 空 栈
*top = *base;
stacksize = STACK_INIT_SIZE
顺序栈
顺序栈的操作实现举例
InitStack /* 构造一个空的栈 S*/
?Status InitStack(SqStack *s)
? { s->base=( SElemType *)malloc
? (STACK_INIT_SIZE * sizeof(SElemType));
? if(!s -> base) return(OVERFLOW);
? s -> top = s -> base;
? s -> stacksize = STACK_INIT_SIZE;
? return OK;
?} /* InitStack */
顺序栈的操作实现 (GetTop)
栈 S 非空,则用 e 返回栈 S 中 栈 顶 元 素 的 值,
并返回 OK,则返回 ERROR。
? Status GetTop(SqStack s,SElemType *e)
? { if (s.top == s.base)return ERROR;
? *e = *(s.top-1);
? return OK;
? } /* GetTop */
*base
*top
stacksize
......a1,.,ai an
s
e
*e = *(s.top-1);
顺序栈的操作实现 （ Push）
插入元素 e为新的栈顶元素 。
? Status Push(SqStack *s,SElemType e)
? { if (s->top – s->base >= s->stacksize)
? /* 栈满, 追加存储空间 */
? { l_temp=(SElemType*)realloc
? (s->base,(s->stacksize+STACKINCREMENT)
? *sizeof(SElemType));
? if (!l_temp) return(OVERFLOW);
? s->base = l_temp;
? s->top = s->base + s->stacksize;
? s->stacksize += STACKINCREMENT;
? }
? *(s->top++) = e; return OK;
? } /* Push */
插入新的栈顶元素时, 堆栈变化示意
e
*base
*top
stacksize
......a1,.,ai an
s
*base
*top
stacksize
......a1,.,ai an
s 栈满时，追加存储空间
*(s->top++) = e;
顺序栈的操作实现 (Pop)
栈 S非空,则 删除 S的栈顶元素,用 e返回栈 S中栈顶元素的
值, 并返回 OK,否 则返回 ERROR。
? Status Pop(SqStack *s,SElemType *e)
? { if (s->top == s->base)return ERROR;
? *e = *(--s->top);
? return OK;
? } /* Pop */
*base
*top
stacksize
......a1,.,ai an
s
e
*e = *(--s->top);
3.2 栈的应用举例
3.2.1 数制转换
? N = (N div d)× d + N mod d;
? 1348 = 1348/8 * 8 +1348%8
? 例,（ 1348） 10 = （ 2504） 8
? N (N div 8) N mod 8
? 1348 168 4
? 168 21 0
? 21 2 5
? 2 0 2
? 先进后出：
? 数据生成的顺序,4,0,5,2
? 读出的顺序,2,5,0,4
*base
*top
stacksize
4
0
5
2
数 制 转 换 算 法 （ 算法 3.1 ）
输入一个非负的十进制数, 输出等值的八进制数
? void conversion()
? { InitStack(&s);
? scanf(“%d”,N);
? while(N){
? Push(&s,N%8);
? N = N/8;
? }
? while(!StackEmpty(s)){
? Pop(&s,&e);
? printf(“%d”,e);
? }
? } /* conversion */
?#define STACK_INIT_SIZE 100
?#define STACKINCREMENT 10
?#define OK 1
?#define OVERFLOW -1
?#define ERROR 0
?typedef struct{ int *base;
? int *top;
? int stacksize;
?}sqstack;
栈使用的完整 C程序实例
int initstack(sqstack *s)
{
s->base=(int *)malloc
(STACK_INIT_SIZE*sizeof(int));
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
return OK;
}
void pop(sqstack *s,int *e)
{
if(s->top==s->base)return ERROR;
*e=*(--s->top);
}
?void push(sqstack *s,int e)
?{
? if(s->top-s->base>=s->stacksize){
? s->base=(int*)realloc(s->base,(s->
stacksize+STACKINCREMENT)*sizeof(int));
? if (!s->base)exit(OVERFLOW);
? s->top=s->base+s->stacksize;
? s->stacksize+=STACKINCREMENT;
? }
? *(s->top++)=e;
?}
?main()
?{ sqstack s;
? int n,m,e;
? initstack(&s);
? clrscr();
? scanf("%d %d",&n,&m);
? while(n){
? push(&s,n%m);
? n=n/m; }
? while(!(s.top==s.base))
? {
? pop(&s,&e);
? printf("%d",e);
?} }
3.2.4 迷宫求解例 1,start, (1,1) end, (1,4)
0 1 2
3 4
5
0 1 2 3 4 5
(1,3) (2,3) (3,2) (4,5) (5,4) (3,5) (3,3) (2,5) (1,4)
(1,4)
(2,4) (2,4)
(3,4) (3,4) (3,4) (3,4)
(4,4) (4,4) (4,4) (4,4) (4,4) (4,4)
(4,3) (4,3) (4,3) (4,3) (4,3) (4,3)
(4,2) (4,2) (4,2) (4,2) (4,2) (4,2)
(4,1) (4,1) (4,1) (4,1) (4,1) (4,1)
(3,1) (3,1) (3,1) (3,1) (3,1) (3,1)
(2,1) (2,1) (2,1) (2,1) (2,1) (2,1)
(2,2) (2,2) (2,2) (2,2) (2,2) (2,2) (2,2) (2,2)
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1)
当前位置,
栈 s.seat的变化
迷 宫 求 解 的 算 法 思 想,
? 设定当前位置的初值为入口位置 ;
? do {
? 若 当前位置可通,
? 则 { 将当前位置插入栈顶 ;
? 若该位置是出口位置, 则结束 ;
? 否则切换当前位置的 东邻 方块为新的当前位置 ;
? } 否则
? 若 栈不空且栈顶位置尚有其它方向未经探索,
? 则 设定新的当前位置为 顺时针方向 旋转找到的栈顶位置
? 的下一相邻块 ;
? 若 栈不空但栈顶位置的四周均不可通,
? 则 { 删去栈顶位置 ;
? 若栈不空,则重新测试新的栈顶位置,
? 直至找到一个可通的相邻块或出栈至空栈 ;
? }
? }while (栈不空 );
迷宫求解的算法, typedef struct {int ord;
PosType seat;
int di;
}SElemType;
? Status MazePath (MazeType maze,PosType start,PosType end)
? { InitStack(s); curpos = start;
? curstep = 1;
? do{
? if(Pass(curpos)){ // 当前位置可通
? FootPrint(curpos); // 留下足迹
? e = (curstep,curpos,1);
? Push(s,e); // 加入路径
? if(curpos == end) return (TRUE); // 到达终点 (出口 )
? curpos = NextPos(curpos,1);
? // 下一个位置是当前位置的东邻方块
? curstep ++ ; // 探索下一步
? }
? else{ // 当前位置不能通过
? if(!StackEmpty(s)){
? Pop(s,e);
? While(e.di==4 && !StackEmpty(s)){
? MarkPrint(e.seat); // 留下不能通过的足迹
? Pop(s,e); // 退回一步
? }
? if(e.di<4){
? e.di++; Push(s,e); // 换一个方向探索
? curpos = NextPos(e.seat,e.di);
? // 设定当前位置是该新方向上的相邻方块
? }
? }
? }
? }while (!StackEmpty(s));
? return (FALSE);
? } // MazePath
迷宫求解的算法 (续 ):
例 2,start, (1,1) end, (2,4)
0 1 2 3 4 5
0 1 2
3 4
5
当前位置 和 栈 s.seat的变化,
( 1,4 ) ( 2,3 ) ( 0,3 ) ( 2,2 ) ( 0,2 ) ( 0,2 ) ( 3,2 ) ( 4,5 ) ( 5,4 ) ( 3,5 ) ( 3,3 ) ( 2,4 )
( 2,4 )
( 3,4 ) ( 3,4 ) ( 3,4 )
( 4,4 ) ( 4,4 ) ( 4,4 ) ( 4,4 ) ( 4,4 )
( 4,3 ) ( 4,3 ) ( 4,3 ) ( 4,3 ) ( 4,3 )
( 4,2 ) ( 4,2 ) ( 4,2 ) ( 4,2 ) ( 4,2 )
( 4,1 ) ( 4,1 ) ( 4,1 ) ( 4,1 ) ( 4,1 )
( 1,3 ) ( 1,3 ) ( 1,3 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 )
( 1,2 ) ( 1,2 ) ( 1,2 ) ( 1,2 ) ( 1,2 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 )
( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 )
例 3,start, (1,1) end, (2,4)
0 1 2 3 4 50
1 2 3 4 5
栈 s.seat的变化表
作为习题
实验与习题
?理论习题 2.2,3.2,3.3,3.4,3.5,3.15
? 写出例 3的栈的变化过程
?实验题,
? ① 写一个主程序来 上机验证算法 3.1；
? ② 3.15
3.1.1抽象数据类型栈的定义
3.1.2栈的表示与实现
? 3.2 栈的应用举例
3.2.1 数制转换
3.2.4 迷宫求解
3.2.5 表达式求值
? *3.3 栈和递归的实现
? 3.4 队列
3.4.1抽象数据类型队列的定义
3.4.2 链队列 -- 队列的链式表示与实现
3.4.3 循环队列 -- 队列的顺序表示与实现
第三章 栈和队列 -----
操作受限 的 线性表
? 栈 （ stack）, 先进后出 ( FILO） 的线性表 。
? 或 后进先出 （ LIFO） 的线性表 。
? 或仅在表尾进行插入和删除操作的线性表 。
? 栈顶 （ top）, 线性表的表尾端, 即可操作端 。
? 栈底 （ bottom）, 线性表的表头 。
3.1 栈
3.1.1 抽象数据类型 栈的定义
栈底 栈顶
......a1 a2 a3 an-1 an
入栈 (push)
出栈 (pop)
栈的抽象数据类型
?ADT Stack {
? 数 据 对 象, D = {ai | ai 属于 Elemset,
(i=1,2,…,n,n≥ 0)}
? 数据关系, R1 = { ＜ ai-1,ai ＞ |ai-1,ai 属于
D,(i=2,3,…,n)} 约定 an为栈顶,a1为栈底 。
? 基本操作,
? InitStack(&S); DestroyStack(&S);
? ClearStack(&S); StackEmpty(S);
? StackLength(S) ; GetTop(S,&e);
? Push(&S,e); Pop(&S,&e);
? StackTraverse(S,visit ())
?}ADT Stack
栈的 基本操作 (之一 )
? InitStack(&S)
? 操作结果,构造一个空的栈 S。
? DestroyStack(&S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 销毁栈 S。
?ClearStack(&S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 将栈 S重置为空栈 。
栈的 基本操作 (之二 )
?StackEmpty(S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 若栈 S为空栈, 则返回 TURE;否则
返回 FALSE。
?StackLength(S)
? 初始条件, 栈 S已经存在 。
? 操作结果, 返回栈 S中的数据元素个数 。
?GetTop(S,&e)
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 用 e返回栈 S中栈顶元素的值 。
栈的 基本操作 (之三 )
?Push(&S,e)
? 初始条件, 栈 S已经存在 。
? 操作结果, 插入元素 e为新的栈顶元素 。
?Pop(&S,&e)
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 删除 S的栈顶元素并用 e返回其值 。
?StackTraverse(S,visit ())
? 初始条件, 栈 S已经存在且非空 。
? 操作结果, 从栈底到栈顶依次对 S的每个元素
调用函数 visit ()。 一旦 visit ()失败, 则操作
失败 。
3.1.2 栈的顺序表示与实现 ---
(顺序栈 )
? typedef struct{
? SElemType *base;
? /* 在栈构造之前和销毁之后,base的值为 NULL*/
? SElemType *top; /* 栈顶指针 */
? int stacksize; /* 当前已分配的存储空间，以元素为单位 */
? }SqStack;
? #define STACK_INIT_SIZE 100
? #define STACKINCREMENT 10
? #define OK 1
? #define OVERFLOW -1
? #define ERROR 0
顺序栈示意图
*base
*top
stacksize
......a1,.,ai an
*base
*top
stacksize
初始 空 栈
*top = *base;
stacksize = STACK_INIT_SIZE
顺序栈
顺序栈的操作实现举例
InitStack /* 构造一个空的栈 S*/
?Status InitStack(SqStack *s)
? { s->base=( SElemType *)malloc
? (STACK_INIT_SIZE * sizeof(SElemType));
? if(!s -> base) return(OVERFLOW);
? s -> top = s -> base;
? s -> stacksize = STACK_INIT_SIZE;
? return OK;
?} /* InitStack */
顺序栈的操作实现 (GetTop)
栈 S 非空,则用 e 返回栈 S 中 栈 顶 元 素 的 值,
并返回 OK,则返回 ERROR。
? Status GetTop(SqStack s,SElemType *e)
? { if (s.top == s.base)return ERROR;
? *e = *(s.top-1);
? return OK;
? } /* GetTop */
*base
*top
stacksize
......a1,.,ai an
s
e
*e = *(s.top-1);
顺序栈的操作实现 （ Push）
插入元素 e为新的栈顶元素 。
? Status Push(SqStack *s,SElemType e)
? { if (s->top – s->base >= s->stacksize)
? /* 栈满, 追加存储空间 */
? { l_temp=(SElemType*)realloc
? (s->base,(s->stacksize+STACKINCREMENT)
? *sizeof(SElemType));
? if (!l_temp) return(OVERFLOW);
? s->base = l_temp;
? s->top = s->base + s->stacksize;
? s->stacksize += STACKINCREMENT;
? }
? *(s->top++) = e; return OK;
? } /* Push */
插入新的栈顶元素时, 堆栈变化示意
e
*base
*top
stacksize
......a1,.,ai an
s
*base
*top
stacksize
......a1,.,ai an
s 栈满时，追加存储空间
*(s->top++) = e;
顺序栈的操作实现 (Pop)
栈 S非空,则 删除 S的栈顶元素,用 e返回栈 S中栈顶元素的
值, 并返回 OK,否 则返回 ERROR。
? Status Pop(SqStack *s,SElemType *e)
? { if (s->top == s->base)return ERROR;
? *e = *(--s->top);
? return OK;
? } /* Pop */
*base
*top
stacksize
......a1,.,ai an
s
e
*e = *(--s->top);
3.2 栈的应用举例
3.2.1 数制转换
? N = (N div d)× d + N mod d;
? 1348 = 1348/8 * 8 +1348%8
? 例,（ 1348） 10 = （ 2504） 8
? N (N div 8) N mod 8
? 1348 168 4
? 168 21 0
? 21 2 5
? 2 0 2
? 先进后出：
? 数据生成的顺序,4,0,5,2
? 读出的顺序,2,5,0,4
*base
*top
stacksize
4
0
5
2
数 制 转 换 算 法 （ 算法 3.1 ）
输入一个非负的十进制数, 输出等值的八进制数
? void conversion()
? { InitStack(&s);
? scanf(“%d”,N);
? while(N){
? Push(&s,N%8);
? N = N/8;
? }
? while(!StackEmpty(s)){
? Pop(&s,&e);
? printf(“%d”,e);
? }
? } /* conversion */
?#define STACK_INIT_SIZE 100
?#define STACKINCREMENT 10
?#define OK 1
?#define OVERFLOW -1
?#define ERROR 0
?typedef struct{ int *base;
? int *top;
? int stacksize;
?}sqstack;
栈使用的完整 C程序实例
int initstack(sqstack *s)
{
s->base=(int *)malloc
(STACK_INIT_SIZE*sizeof(int));
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
return OK;
}
void pop(sqstack *s,int *e)
{
if(s->top==s->base)return ERROR;
*e=*(--s->top);
}
?void push(sqstack *s,int e)
?{
? if(s->top-s->base>=s->stacksize){
? s->base=(int*)realloc(s->base,(s->
stacksize+STACKINCREMENT)*sizeof(int));
? if (!s->base)exit(OVERFLOW);
? s->top=s->base+s->stacksize;
? s->stacksize+=STACKINCREMENT;
? }
? *(s->top++)=e;
?}
?main()
?{ sqstack s;
? int n,m,e;
? initstack(&s);
? clrscr();
? scanf("%d %d",&n,&m);
? while(n){
? push(&s,n%m);
? n=n/m; }
? while(!(s.top==s.base))
? {
? pop(&s,&e);
? printf("%d",e);
?} }
3.2.4 迷宫求解例 1,start, (1,1) end, (1,4)
0 1 2
3 4
5
0 1 2 3 4 5
(1,3) (2,3) (3,2) (4,5) (5,4) (3,5) (3,3) (2,5) (1,4)
(1,4)
(2,4) (2,4)
(3,4) (3,4) (3,4) (3,4)
(4,4) (4,4) (4,4) (4,4) (4,4) (4,4)
(4,3) (4,3) (4,3) (4,3) (4,3) (4,3)
(4,2) (4,2) (4,2) (4,2) (4,2) (4,2)
(4,1) (4,1) (4,1) (4,1) (4,1) (4,1)
(3,1) (3,1) (3,1) (3,1) (3,1) (3,1)
(2,1) (2,1) (2,1) (2,1) (2,1) (2,1)
(2,2) (2,2) (2,2) (2,2) (2,2) (2,2) (2,2) (2,2)
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1)
当前位置,
栈 s.seat的变化
迷 宫 求 解 的 算 法 思 想,
? 设定当前位置的初值为入口位置 ;
? do {
? 若 当前位置可通,
? 则 { 将当前位置插入栈顶 ;
? 若该位置是出口位置, 则结束 ;
? 否则切换当前位置的 东邻 方块为新的当前位置 ;
? } 否则
? 若 栈不空且栈顶位置尚有其它方向未经探索,
? 则 设定新的当前位置为 顺时针方向 旋转找到的栈顶位置
? 的下一相邻块 ;
? 若 栈不空但栈顶位置的四周均不可通,
? 则 { 删去栈顶位置 ;
? 若栈不空,则重新测试新的栈顶位置,
? 直至找到一个可通的相邻块或出栈至空栈 ;
? }
? }while (栈不空 );
迷宫求解的算法, typedef struct {int ord;
PosType seat;
int di;
}SElemType;
? Status MazePath (MazeType maze,PosType start,PosType end)
? { InitStack(s); curpos = start;
? curstep = 1;
? do{
? if(Pass(curpos)){ // 当前位置可通
? FootPrint(curpos); // 留下足迹
? e = (curstep,curpos,1);
? Push(s,e); // 加入路径
? if(curpos == end) return (TRUE); // 到达终点 (出口 )
? curpos = NextPos(curpos,1);
? // 下一个位置是当前位置的东邻方块
? curstep ++ ; // 探索下一步
? }
? else{ // 当前位置不能通过
? if(!StackEmpty(s)){
? Pop(s,e);
? While(e.di==4 && !StackEmpty(s)){
? MarkPrint(e.seat); // 留下不能通过的足迹
? Pop(s,e); // 退回一步
? }
? if(e.di<4){
? e.di++; Push(s,e); // 换一个方向探索
? curpos = NextPos(e.seat,e.di);
? // 设定当前位置是该新方向上的相邻方块
? }
? }
? }
? }while (!StackEmpty(s));
? return (FALSE);
? } // MazePath
迷宫求解的算法 (续 ):
例 2,start, (1,1) end, (2,4)
0 1 2 3 4 5
0 1 2
3 4
5
当前位置 和 栈 s.seat的变化,
( 1,4 ) ( 2,3 ) ( 0,3 ) ( 2,2 ) ( 0,2 ) ( 0,2 ) ( 3,2 ) ( 4,5 ) ( 5,4 ) ( 3,5 ) ( 3,3 ) ( 2,4 )
( 2,4 )
( 3,4 ) ( 3,4 ) ( 3,4 )
( 4,4 ) ( 4,4 ) ( 4,4 ) ( 4,4 ) ( 4,4 )
( 4,3 ) ( 4,3 ) ( 4,3 ) ( 4,3 ) ( 4,3 )
( 4,2 ) ( 4,2 ) ( 4,2 ) ( 4,2 ) ( 4,2 )
( 4,1 ) ( 4,1 ) ( 4,1 ) ( 4,1 ) ( 4,1 )
( 1,3 ) ( 1,3 ) ( 1,3 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 ) ( 3,1 )
( 1,2 ) ( 1,2 ) ( 1,2 ) ( 1,2 ) ( 1,2 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 ) ( 2,1 )
( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 ) ( 1,1 )
例 3,start, (1,1) end, (2,4)
0 1 2 3 4 50
1 2 3 4 5
栈 s.seat的变化表
作为习题
实验与习题
?理论习题 2.2,3.2,3.3,3.4,3.5,3.15
? 写出例 3的栈的变化过程
?实验题,
? ① 写一个主程序来 上机验证算法 3.1；
? ② 3.15
