,数据结构,
第三章 (上 )
数据结构
tjm
第三章 栈和队列
3.1 栈
3.1.1 抽象数据类型栈的定义
3.1.2 栈的表示和实现
3.2 栈的应用举例
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.3 行编辑程序
3.2.4 迷宫求解
3.2.5 表达式求值
3.3 栈与递归的实现
3.4 队列
3.4.1 抽象数据类型队列的定义
3.4.2 链队列－队列的链式表示和实现
3.4.3 循环队列－队列的顺序表示和实现
数据结构
tjm
3.1 栈
3.1.1 抽象数据类型栈的定义
栈 (Stack)是限制在表的一端进行插入和删除
运算的线性表，通常称插入、删除的这一端为栈顶
(Top)，另一端为栈底 (Bottom)。当表中没有
元素时称为空栈。
假设栈 S=(a1,a2,a3,…an)，则 a1称为
栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…an的次序进栈，退栈的第一个元素应为栈
顶元素。
数据结构
tjm
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶
栈底
栈的 ADT定义参见 p45
特点：后进先出
（ LIFO）。
数据结构
tjm
3.1.2 栈的表示和实现
一,顺序栈
由于 栈是操作受限的线性表,因此线性表的存
储结构对栈也适应。
栈的顺序存储结构简称为 顺序栈,可用数组来
实现顺序栈。因为栈底位置是固定不变的，所以可
以将栈底位置设置在数组的两端的任何一个端点。
栈顶位置是随着进栈和退栈操作而变化，故需
用一个指针 top来指示当前栈顶的位置，通常称
top为栈顶指针。因此，顺序栈的类型定义只需将
顺序表的类型定义中的长度属性改为 top指针即可。
数据结构
tjm
顺序栈的类型定义如下,
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
数据结构
tjm
栈的几个常用的基本操作的实现：
1、栈的初始化 InitStack操作 （ P47）
2、进栈 Push操作 （ P47）
3、出栈 Pop操作 （ P47）
4、取栈顶元素 GetTop操作 （ P47）
当栈满时再做进栈运算必定产生空间溢出，简
称,上溢” ;当栈空时再做退栈运算也将产生溢
出，简称,下溢” 。溢出是一种出错状态，应
该设法避免。
数据结构
tjm
二,链栈
栈的链式存储结构称为 链栈,它 是操作受限的
单链表,其插入和删除操作仅限制在表头位置
上进行。链栈通常用不带头结点的单链表来实
现。栈顶指针就是链表的头指针。
链栈的类型说明如下,
typedef struct SNode
{ SElemType data;
struct SNode *next;
}SNode,*LinkStack;
数据结构
tjm
^…...
栈底
SS
ep
1、进栈操作的实现：
void Push_LS(LinkStack &S,SElemType e)
{
p=(LinkStack)malloc(sizeof(SNode));
p–>data=e;
p–>next=S;
S=p;
}
数据结构
tjm
Status Pop_LS(LinkStack &S,SElemType &e)
{
if(S==NULL) return ERROR;
e=S->data;
p=S;
S=S->next;
free(p);
}
S
^…...
栈底S
p
2、退栈操作的实现：
数据结构
tjm
3.2 栈的应用举例
3.2.1 数制转换
例如 (159)10=(?)8
(159)10=(237)8
1598
198
28
0 2 3 7
余 7
余 3
余 2
数据结构
tjm
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
数据结构
tjm
3.2.2 括号匹配的校验
按“期待的急迫程度”处理。
算法设计思想：
1) 凡是出现作括弧，则进栈。
2)凡是出现右括弧，首先检查栈是否空，若栈空，
则表明“右括弧”多了，否则和栈顶元素比较，
若相匹配，则“左括弧出栈”，否则不匹配。
3)表达式检验结束时，若栈空，则匹配正确，否则
表明“左括弧”多了。
数据结构
tjm
3.2.3 行编辑程序
在编辑程序中，设立一个输入缓冲区，用于接受
用户输入的一行字符，然后逐行存入用户数据区。
允许用户输入错误，并在发现有误时可以及时更
正。 ‘ #‘ 删除刚输入的字符，‘ @‘删除刚输入
的一行。
行编辑程序算法如下,
void LineEdit( )
{ InitStack(s);
ch=getchar( );
while(ch!=EOF)
{ while(ch!=EOF && ch!=?\n‘)
数据结构
tjm
{ switch(ch)
{ case ?#‘, Pop(S,c);
case ?@‘, ClearStack(S);
default, Push(S,ch);
}
ch=getchar( );
}
ClearStack(S);
if(ch!=EOF)
ch=getchar( );
}
DestroyStack(S);
}// LineEdit
数据结构
tjm
求解思想：
采用 回溯法 。回溯法是一种不断试探且及时纠正错
误的搜索方法。本问题可从入口出发，按某一方向
向未走过的前方探索，若能走通，则到达新点，否
则试探下一方向 ; 若所有的方向均没有通路，则沿
原路返回前一点，换下一个方向再继续试探，直到
所有可能的通路都探索到，或找到一条通路，或无
路可走又返回到入口点。
这也是一种“穷举求解”的方法。
3.2.4 迷宫求解
数据结构
tjm
数据结构
tjm
需要解决的问题：
1、表示迷宫的数据结构
2、试探方向
3、栈的设计
4、防止重复到达某点，避免发生死循环
1、表示迷宫的数据结构
表示一个 m行 n列迷宫：
用 maze[m][n]表示,0≤i<m,0≤j<n
maze[i][j] = 0 通路
maze[i][j] = 1 不通
改进：
用 maze[m+2][n+2]表示
且 maze[i][j]=1,i=0或 m＋ 1,j=0或 n＋ 1
入口坐标为（ 1,1），出口坐标为（ m,n）
数据结构
tjm
0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 0 0 0 1 0 1
2 1 0 0 1 0 0 0 1 0 1
3 1 0 0 0 0 1 1 0 0 1
4 1 0 1 1 1 0 0 0 0 1
5 1 0 0 0 1 0 0 0 0 1
6 1 0 1 0 0 0 1 0 0 1
7 1 0 1 1 1 0 1 1 0 1
8 1 1 0 0 0 1 0 0 0 1
9 1 1 1 1 1 1 1 1 1 1
数据结构
tjm
迷宫的定义：
#define m 8 /*迷宫的实际行 */
#define n 8 /*迷宫的实际列 */
int maze [m+2][n+2] ;
2、试探方向
表示位置的类型 PosType定义如下：
typedef struct
{
int x,y;
} PosType ;
数据结构
tjm
试探顺序规定为,从正东沿顺时针方向
与点 (x,y)相邻的 4个点及坐标
(x,y) (x,y+1)(x,y-1)
(x+1,y)
(x-1,y)
数据结构
tjm
3、栈的设计
栈中每个元素的组成：
通道块在路径上的序号
坐标位置
前进方向（东为 1，南为 2，西为 3，北为 4）
栈元素的类型定义：
typedef struct {
int ord;
PosType seat;
int di;
}SElemType;
4、防止重复到达某点
走过不通之处要加以标记（ MarkPrint操作）
迷宫求解算法思想及算法参见 P51
数据结构
tjm
表达式求值 是程序设计语言编译中一个最基本的问
题。它的实现需要栈的加入。
表达式 是由 运算对象、运算符、括号 组成的有意义
的式子。
运算符 从运算对象的个数上分，有单目运算符和双
目运算符；从运算类型上分，有算术运算、关系运
算、逻辑运算。
下面只讨论双目运算符的算术表达式。假设所讨论
的算术运算符包括,+, -, *,/,%,^（乘
方）和括号（）。
3.2.5 表达式求值
数据结构
tjm
设运算规则为：
．运算符的优先级为：
（） —> ^ —> ＊ / % —> + -
,先括号内后括号外，多层括号时由内向外
．乘方连续出现时先算最右面的
算子,运算符、界限符
两个相继出现的算子 ?1,?2(?1在前,?2在
后 ), 优先级关系有三种：
?1 < ?2
?1 = ?2
?1 > ?2
数据结构
tjm
优先关系表：
+
?2
?1
-
*
/
(
)
#
+ - * / ( ) #
> > < < < > >
> > < < < > >
> > > > < > >
> > > > < > >
< < < < < =
> > > > > >
< < < < < =
数据结构
tjm
算法思想,建立两个工作栈。 OPTR栈用以保存算
子； OPND栈用以保存操作数或运算结果。
1 ） 初始化 OPND 空栈； OPTR存 ‘ #‘ 为栈底元素
2 ）从左到右输入字符：
当 前字符是操作数，入 OPND栈
当 前字符是运算符，则
若 该运算符 OPTR栈顶运算符优先级高则入算符
栈，继续向后处理
若 该运算符比栈顶运算符优先级低则从 OPND栈
出栈两个操作数，从 OPTR栈出栈一个运算符进行
运算，并将其运算结果入 OPND栈
重复上述操作，直到表达式求值完毕（ OPTR的栈
顶元素和当前读入的字符均为,#‖ ）。
数据结构
tjm
例,3 * ( 7 - 2 )
OPND OPTR
#3
7
2
5
15
*
(
- )#
算法参见 P53
数据结构
tjm
3 3 # 3入栈 s1
* 3 #* *入栈 s2
2 3,2 #* 2入栈 s1
^ 3,2 #*^ ^入栈 s2
( 3,2 #*^( (入栈 s2
4 3,2,4 #*^( 4入栈 s1
+ 3,2,4 #*^(+ +入栈 s2
2 3,2,4,2 #*^(+ 2入栈 s1
* 3,2,4,2 #*^(+* *入栈 s2
2 3,2,4,2,2 #*^(+* 2入栈 s1
- 3,2,4,4 #*^(+ 做 2+2=4，结果入栈 s1
3,2,8 #*^( 做 4+4=8，结果入栈 s1
3,2,8 #*^(- -入栈 s2
1 3,2,8,1 #*^(- 1入栈 s1
读入 OPND OPTR 说明
3*2^（ 4+2*2-1*3） -5的求值过程：
数据结构
tjm
* 3,2,8,1 #*^(-* *入栈 s2
3 3,2,8,1,3 #*^(-* 3入栈 s1
) 3,2,8,3 #*^(- 做 1*3，结果 3入栈 s1
3,2,5 #*^( 做 8-3，结果 5入栈 s1
- 3,32 #* 做 2^5，结果 32入栈 s1
96 # 做 3*32，结果 96入栈 s1
96 #- -入栈 s2
5 96,5 #- 5入栈 s1
# 91 # 做 96-5,结果 91入栈 s1
3*2^（ 4+2*2-1*3） -5
第三章 (上 )
数据结构
tjm
第三章 栈和队列
3.1 栈
3.1.1 抽象数据类型栈的定义
3.1.2 栈的表示和实现
3.2 栈的应用举例
3.2.1 数制转换
3.2.2 括号匹配的检验
3.2.3 行编辑程序
3.2.4 迷宫求解
3.2.5 表达式求值
3.3 栈与递归的实现
3.4 队列
3.4.1 抽象数据类型队列的定义
3.4.2 链队列－队列的链式表示和实现
3.4.3 循环队列－队列的顺序表示和实现
数据结构
tjm
3.1 栈
3.1.1 抽象数据类型栈的定义
栈 (Stack)是限制在表的一端进行插入和删除
运算的线性表，通常称插入、删除的这一端为栈顶
(Top)，另一端为栈底 (Bottom)。当表中没有
元素时称为空栈。
假设栈 S=(a1,a2,a3,…an)，则 a1称为
栈底元素,an为栈顶元素。栈中元素按 a1,a2，
a3,…an的次序进栈，退栈的第一个元素应为栈
顶元素。
数据结构
tjm
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶
栈底
栈的 ADT定义参见 p45
特点：后进先出
（ LIFO）。
数据结构
tjm
3.1.2 栈的表示和实现
一,顺序栈
由于 栈是操作受限的线性表,因此线性表的存
储结构对栈也适应。
栈的顺序存储结构简称为 顺序栈,可用数组来
实现顺序栈。因为栈底位置是固定不变的，所以可
以将栈底位置设置在数组的两端的任何一个端点。
栈顶位置是随着进栈和退栈操作而变化，故需
用一个指针 top来指示当前栈顶的位置，通常称
top为栈顶指针。因此，顺序栈的类型定义只需将
顺序表的类型定义中的长度属性改为 top指针即可。
数据结构
tjm
顺序栈的类型定义如下,
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
数据结构
tjm
栈的几个常用的基本操作的实现：
1、栈的初始化 InitStack操作 （ P47）
2、进栈 Push操作 （ P47）
3、出栈 Pop操作 （ P47）
4、取栈顶元素 GetTop操作 （ P47）
当栈满时再做进栈运算必定产生空间溢出，简
称,上溢” ;当栈空时再做退栈运算也将产生溢
出，简称,下溢” 。溢出是一种出错状态，应
该设法避免。
数据结构
tjm
二,链栈
栈的链式存储结构称为 链栈,它 是操作受限的
单链表,其插入和删除操作仅限制在表头位置
上进行。链栈通常用不带头结点的单链表来实
现。栈顶指针就是链表的头指针。
链栈的类型说明如下,
typedef struct SNode
{ SElemType data;
struct SNode *next;
}SNode,*LinkStack;
数据结构
tjm
^…...
栈底
SS
ep
1、进栈操作的实现：
void Push_LS(LinkStack &S,SElemType e)
{
p=(LinkStack)malloc(sizeof(SNode));
p–>data=e;
p–>next=S;
S=p;
}
数据结构
tjm
Status Pop_LS(LinkStack &S,SElemType &e)
{
if(S==NULL) return ERROR;
e=S->data;
p=S;
S=S->next;
free(p);
}
S
^…...
栈底S
p
2、退栈操作的实现：
数据结构
tjm
3.2 栈的应用举例
3.2.1 数制转换
例如 (159)10=(?)8
(159)10=(237)8
1598
198
28
0 2 3 7
余 7
余 3
余 2
数据结构
tjm
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
数据结构
tjm
3.2.2 括号匹配的校验
按“期待的急迫程度”处理。
算法设计思想：
1) 凡是出现作括弧，则进栈。
2)凡是出现右括弧，首先检查栈是否空，若栈空，
则表明“右括弧”多了，否则和栈顶元素比较，
若相匹配，则“左括弧出栈”，否则不匹配。
3)表达式检验结束时，若栈空，则匹配正确，否则
表明“左括弧”多了。
数据结构
tjm
3.2.3 行编辑程序
在编辑程序中，设立一个输入缓冲区，用于接受
用户输入的一行字符，然后逐行存入用户数据区。
允许用户输入错误，并在发现有误时可以及时更
正。 ‘ #‘ 删除刚输入的字符，‘ @‘删除刚输入
的一行。
行编辑程序算法如下,
void LineEdit( )
{ InitStack(s);
ch=getchar( );
while(ch!=EOF)
{ while(ch!=EOF && ch!=?\n‘)
数据结构
tjm
{ switch(ch)
{ case ?#‘, Pop(S,c);
case ?@‘, ClearStack(S);
default, Push(S,ch);
}
ch=getchar( );
}
ClearStack(S);
if(ch!=EOF)
ch=getchar( );
}
DestroyStack(S);
}// LineEdit
数据结构
tjm
求解思想：
采用 回溯法 。回溯法是一种不断试探且及时纠正错
误的搜索方法。本问题可从入口出发，按某一方向
向未走过的前方探索，若能走通，则到达新点，否
则试探下一方向 ; 若所有的方向均没有通路，则沿
原路返回前一点，换下一个方向再继续试探，直到
所有可能的通路都探索到，或找到一条通路，或无
路可走又返回到入口点。
这也是一种“穷举求解”的方法。
3.2.4 迷宫求解
数据结构
tjm
数据结构
tjm
需要解决的问题：
1、表示迷宫的数据结构
2、试探方向
3、栈的设计
4、防止重复到达某点，避免发生死循环
1、表示迷宫的数据结构
表示一个 m行 n列迷宫：
用 maze[m][n]表示,0≤i<m,0≤j<n
maze[i][j] = 0 通路
maze[i][j] = 1 不通
改进：
用 maze[m+2][n+2]表示
且 maze[i][j]=1,i=0或 m＋ 1,j=0或 n＋ 1
入口坐标为（ 1,1），出口坐标为（ m,n）
数据结构
tjm
0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 0 0 0 1 0 1
2 1 0 0 1 0 0 0 1 0 1
3 1 0 0 0 0 1 1 0 0 1
4 1 0 1 1 1 0 0 0 0 1
5 1 0 0 0 1 0 0 0 0 1
6 1 0 1 0 0 0 1 0 0 1
7 1 0 1 1 1 0 1 1 0 1
8 1 1 0 0 0 1 0 0 0 1
9 1 1 1 1 1 1 1 1 1 1
数据结构
tjm
迷宫的定义：
#define m 8 /*迷宫的实际行 */
#define n 8 /*迷宫的实际列 */
int maze [m+2][n+2] ;
2、试探方向
表示位置的类型 PosType定义如下：
typedef struct
{
int x,y;
} PosType ;
数据结构
tjm
试探顺序规定为,从正东沿顺时针方向
与点 (x,y)相邻的 4个点及坐标
(x,y) (x,y+1)(x,y-1)
(x+1,y)
(x-1,y)
数据结构
tjm
3、栈的设计
栈中每个元素的组成：
通道块在路径上的序号
坐标位置
前进方向（东为 1，南为 2，西为 3，北为 4）
栈元素的类型定义：
typedef struct {
int ord;
PosType seat;
int di;
}SElemType;
4、防止重复到达某点
走过不通之处要加以标记（ MarkPrint操作）
迷宫求解算法思想及算法参见 P51
数据结构
tjm
表达式求值 是程序设计语言编译中一个最基本的问
题。它的实现需要栈的加入。
表达式 是由 运算对象、运算符、括号 组成的有意义
的式子。
运算符 从运算对象的个数上分，有单目运算符和双
目运算符；从运算类型上分，有算术运算、关系运
算、逻辑运算。
下面只讨论双目运算符的算术表达式。假设所讨论
的算术运算符包括,+, -, *,/,%,^（乘
方）和括号（）。
3.2.5 表达式求值
数据结构
tjm
设运算规则为：
．运算符的优先级为：
（） —> ^ —> ＊ / % —> + -
,先括号内后括号外，多层括号时由内向外
．乘方连续出现时先算最右面的
算子,运算符、界限符
两个相继出现的算子 ?1,?2(?1在前,?2在
后 ), 优先级关系有三种：
?1 < ?2
?1 = ?2
?1 > ?2
数据结构
tjm
优先关系表：
+
?2
?1
-
*
/
(
)
#
+ - * / ( ) #
> > < < < > >
> > < < < > >
> > > > < > >
> > > > < > >
< < < < < =
> > > > > >
< < < < < =
数据结构
tjm
算法思想,建立两个工作栈。 OPTR栈用以保存算
子； OPND栈用以保存操作数或运算结果。
1 ） 初始化 OPND 空栈； OPTR存 ‘ #‘ 为栈底元素
2 ）从左到右输入字符：
当 前字符是操作数，入 OPND栈
当 前字符是运算符，则
若 该运算符 OPTR栈顶运算符优先级高则入算符
栈，继续向后处理
若 该运算符比栈顶运算符优先级低则从 OPND栈
出栈两个操作数，从 OPTR栈出栈一个运算符进行
运算，并将其运算结果入 OPND栈
重复上述操作，直到表达式求值完毕（ OPTR的栈
顶元素和当前读入的字符均为,#‖ ）。
数据结构
tjm
例,3 * ( 7 - 2 )
OPND OPTR
#3
7
2
5
15
*
(
- )#
算法参见 P53
数据结构
tjm
3 3 # 3入栈 s1
* 3 #* *入栈 s2
2 3,2 #* 2入栈 s1
^ 3,2 #*^ ^入栈 s2
( 3,2 #*^( (入栈 s2
4 3,2,4 #*^( 4入栈 s1
+ 3,2,4 #*^(+ +入栈 s2
2 3,2,4,2 #*^(+ 2入栈 s1
* 3,2,4,2 #*^(+* *入栈 s2
2 3,2,4,2,2 #*^(+* 2入栈 s1
- 3,2,4,4 #*^(+ 做 2+2=4，结果入栈 s1
3,2,8 #*^( 做 4+4=8，结果入栈 s1
3,2,8 #*^(- -入栈 s2
1 3,2,8,1 #*^(- 1入栈 s1
读入 OPND OPTR 说明
3*2^（ 4+2*2-1*3） -5的求值过程：
数据结构
tjm
* 3,2,8,1 #*^(-* *入栈 s2
3 3,2,8,1,3 #*^(-* 3入栈 s1
) 3,2,8,3 #*^(- 做 1*3，结果 3入栈 s1
3,2,5 #*^( 做 8-3，结果 5入栈 s1
- 3,32 #* 做 2^5，结果 32入栈 s1
96 # 做 3*32，结果 96入栈 s1
96 #- -入栈 s2
5 96,5 #- 5入栈 s1
# 91 # 做 96-5,结果 91入栈 s1
3*2^（ 4+2*2-1*3） -5
