文档介绍：1. 栈(Stack)
第三章栈和队列
2. 队列(Queue)
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1
1. 定义
栈
与线性表相同,仍为一对一( 1:1)关系。
用顺序栈或链栈存储均可,但以顺序栈更常见
只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。
关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的存储结构有别而不同。
3. 存储结构
4. 运算规则
5. 实现方式
2. 逻辑结构
限定只能在表的一端进行插入和删除运算的线性表。
即栈顶
基本操作有:建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值,等等。
2
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底bottom
例如: 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作,称为入栈。
从栈顶删除最后一个元素的操作,称为出栈。
an称为栈顶元素
a1称为栈底元素
想一想:若要从栈中取出a1,该如何操作?
强调:插入和删除都只能在表的一端(栈顶)进行!
3
讨论1:栈是什么?它与一般线性表有什么不同?
答:栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。
与一般线性表的区别:仅在于运算规则不同。
一般线性表栈
逻辑结构:1:1 逻辑结构: 1:1
存储结构:顺序表、链表存储结构:顺序栈、链栈
运算规则:随机存取运算规则:后进先出(LIFO)
“进”=插入=压入=PUSH(an+1)
“出”=删除=弹出=POP(an)
4
a1
a2
……
an
顺序栈S
ai
……
顺序表和顺序栈的操作区别:
表头
表尾
低地址
高地址
写入:S[i]= ai
读出: e= S[i]
压入(PUSH): S[top++]=an+1
弹出( POP) : e=S[--top]
低地址
高地址
S[i]
a1
a2
ai
an
……
顺序表S
……
an+1
以线性表 S= (a1 , a2 , …. , an-1 , an )为例
栈底bottom
栈顶top
前提:一定要预设栈顶指针top
栈顶top
5
断点
讨论:为什么要设计栈?它有什么独特用途?
调用函数或子程序非它莫属;
递归运算的有力工具;
用于保护现场和恢复现场;
简化了程序设计的问题。
例:
输入x1≠0
输入x5=0
输入x2
输入x3
输入x4
输出sum=0
输出sum=0+x4
输出sum=x4+x3
输出sum= x4+x3 +x2
输出sum=x4+x3 +x2+x1
void test(int &sum)
{
int x;
scanf(x);
if(x==0)sum=0;
else{test(sum);
sum+=x;}
printf(sum);
}
答:
6
例:写出下面C程序段的执行结果。
递归概念及算法实现
运行结果为: 5,120
long int fact(n)
int n;
{ long f;
if(n>1)f=n*fact(n-1);
else f=1;
return(f); }
main( )
{ int n;
long y;
n=5;
y=fact(n);
printf(“%d,%ld\n”,n,y); }
此题为递归运算!
7
编制递归算法要注意些什么?
递归进行是有条件的。一般常把判断语句加在递归语句以前。
递归的最底层应该有返回值,以供上层递归的调用。否则死循环。
递归调用需要利用栈。
每次调用要把本次调用的参数和局部变量保存在栈顶。每次从下一层调用返回到上一层调用时,从栈顶恢复本层调用的参数和局部变量的值。
参量的初始化应该在递归以前。
void test(int &sum)
{
int x;
scanf(x);
if(x==0)sum=0;
else {
test(sum);
sum+= x; }
printf(sum);
}
一个直接或间接调用自身的函数被称为是递归(recursion)的。
什么叫递归?
8
例1 一个栈的输入序列为1,2,3,若在入栈的过程中允许出栈,则可能得到的出栈序列是什么?
答:
可以通过穷举所有可能性来求解:
① 1入1出, 2入2出,3入3出, 即123;
② 1入1出, 2、3入,3、2出, 即132;
③ 1、2入,2出, 3入3出, 即2