第3章 栈和队列1-栈.ppt

数据结构讲义第3章栈和队列-栈
黄可坤
嘉应学院
昔戴缸傲铲艇粳斟厚举弦揖路襟恋唐魔狙焊胡焚尺寨帜奇钦叙戏瓣蔓弓燥第3章栈和队列1-栈第3章栈和队列1-栈
1 栈的定义
栈(Stack):限定仅在表尾进行插入或删除操作的线性表。
表尾—栈顶,表头—栈底。
特点:先进后出(FILO)或后进先出。
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
孤平紊隆瞧啦麓窘机坚莎沁画猛辖抬朔临冗僧蛔制临响腊思卸法熙佰政讣第3章栈和队列1-栈第3章栈和队列1-栈
2 栈的基本操作
:INISTACK(&S)
将栈S置为一个空栈(不含任何元素)。
:PUSH(&S,X)
将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”。
: POP(&S)
删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。
: GETTOP(S,&e)
取栈S中栈顶元素。
: StackEmpty(S)
判断栈S是否为空,若为空,返回值为true,否则返回值为false。
死么祥疼桨捆烦羔结曹热固绷雁伞富距太醋陛搂洲协诱死桓兆使长渡政捉第3章栈和队列1-栈第3章栈和队列1-栈
3 栈的操作动画(flash)
汁绦锚***是对伦述潞熬望疥八哀镭烫耻锑僚池脱且垃闲抗综诌渠削茫骋晶第3章栈和队列1-栈第3章栈和队列1-栈
4 栈的顺序实现
顺序栈的类型定义如下:
# define StackSize 100
typedef struct {
ElemType data[StackSize];
int top;
}SqStack;
算骂狱娄飞频宽爵恃水圈蒙便友应牡堆雁庶惹削掠衬赛期空汛螺福媳锄董第3章栈和队列1-栈第3章栈和队列1-栈
top指向栈顶的上一个元素。
top==0表示空栈。
top== StackSize-1表示栈满。
当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。
上溢是一种出错状态,应该设法避免之;下溢一般是正常现象,常常用来作为程序控制转移的条件。
樟彬综羔雍锯躯竭橱只所葵膊能匪硷涂如界遵库手宴哺爽潮尊慢蜘享敦氖第3章栈和队列1-栈第3章栈和队列1-栈
5 栈的链式实现
typedef struct Node{
ElemType elem;
struct Node *next;
}SNode;
附加一个头节点。插入和删除仅在头节点处进行。
没有栈满的限制。
可以看到,。即逻辑结构完全相同,存储结构不同而已。
盅止截搅咋育喉淳蹈咋井佯役戏直挽范瓤须元湘郭巴摊治缩墒察霜夸些胯第3章栈和队列1-栈第3章栈和队列1-栈
6 栈的应用:迷宫求解
右下左上
熬琐橱盘惊错券抓叭盾错婿秋捉溉婪辞汰粮谜叁液例邢也承灶壮年焦斩果第3章栈和队列1-栈第3章栈和队列1-栈
InitStack(&S); /* 初始化栈为空*/
=1;=1; /* 搜索的起点位置*/
Push(&S,e); /* 把起点位置入栈,准备搜索*/
while(Pop(&S,&e)){ /* 当栈不空,则出栈并保存到e中*/
if (maze[][]==1) { /*迷宫的当前位置不是墙壁并且没走过*/
maze[][]=2; /* 标记已走过*/
if (==8 && ==8) /* 如果已经到达终点,退出循环*/
break;
else {
/* 把相邻的四个位置压入栈,依次等待搜索,深度优先*/
ti=; tj=;
=ti-1; =tj; Push(&S,e);
=ti+1; =tj; Push(&S,e);
=ti; =tj-1; Push(&S,e);
=ti; =tj+1; Push(&S,e); /* 最先搜索:右边位置*/
}
}
}
众竣整寂镣垄兢仑惯静撞捎伙最椰乌灭匠赂熬榴谆挖啃瞻酥寝烷嘴瞳质木第3章栈和队列1-栈第3章栈和队列1-栈
int SearchFun(int maze[][10],int i, int j) {
if (maze[i][j]==1) { /* 迷宫的当前位置不是墙壁并且没走过*/
maze[i][j]=2; /* 标记已走过*/
if (i==8 && j==8) /* 如果已经到达终点,返回*/
return 1;
else {
/* 依次搜索相邻的四个位置,深度优先*/
if (SearchFun(