文档介绍：S3
§ 栈
第三章. 栈和队列(Chapter 3. Stack and Queue)
栈(stack)是插入和删除操作受限的线性表,是一种后进先出(Last In First Out -- LIFO)的线性表。表头端称为栈底(bottom),表尾端称为栈顶(top),插入和删除都在栈顶进行。
bottom
top
S1
S2
S5
S6
S3
S4
S3
S3
S3
S3
S3
PUSH
PUSH
PUSH
POP
PUSH
PUSH
PUSH
栈的基本操作:
Inistack
Clear
Gettop
Empty
Push
Pop
栈的实现:
#define STACK_INIT_SIZE user_supply
#define STACKINCREMENT user_supply
typedef struct {
elemtype * bottom ;
elemtype * top ;
int stackzise ;
} sqstack ;
顺序存储结构表示栈
Full
typedef strcut lnode {
elemtype data ;
struct lnode * next ;
} * linkedstack;
链式存储结构表示栈----链栈(Linked_stack)
上溢(overflow):若栈的容量已全部用完,再进行插入操作(PUSH),就会发生上溢错误。
下溢(underflow):若栈已空,再进行删除操作(POP),就会发生下溢错误。
§ 栈的应用----表达式求值
任一表达式(expression)都是由操作数(operand)、操作符(operator)和界限符(delimiter)组成。
我们通常习惯使用中缀表达式(infix expression),但中缀表达式离不开括号(bracket)。若使用前缀表达式(prefix expression)或后缀表达式( postfix expression)则不需要括号。利用栈,可以将中缀表达式变为前缀表达式或后缀表达式,再用栈进行运算即可得到表达式的值(value)。
§ 栈与递归
递归(recursive):一个程序直接调用自己或通过其它程序调用自己就称为递归。根据调用关系可分为直接递归(direct recursive)和间接递归(indirect recursive )。
第一次上机作业
输入表达式字符串,以“=”表示结束, 计算并输出表达式值。操作数可以是整数或实数,操作符有“+”、“-”、“*”、“/”、“^”(乘方)和“sin( )”(正弦)、“cos( )”(余弦)、“log( )”(对数)、“ln( )”(自然对数)等函数。
栈在程序的过程或函数调用中的作用:
过程一
过程二
过程三
过程四
断
点
三
断
点
一
断
点
二
断点一
断点二
断点三
stack
调用子程序
返回断点
程序执行
递归是程序设计中一种强有力的工具。下面三种情况可用递归解决:
1、有些数学函数是递归定义的,对其求解可用递归;
2、有些数据结构具有递归特性,对其操作可用递归;
3、有些问题的解决方法用递归描述,对其求解也可用递归。
例:
求阶乘(factorial):
Fact(n) =
1 当 n = 0
n·Fact(n-1) 当 n > 0
{
int Fact ( int n ) {
if ( ! n ) return 1 ; // 出口条件
return n * Fact ( n – 1 ) ; // 递归调用部分
}
例:
求 n 个数的最小值:
int Min ( sqlist S, int n )
{
if ( n==1 ) return S [ 1 ] ; // 出口条件
x = Min ( S, n-1 );
if ( x < S [ n ] ) return x;
else return S [ n ] ; // 递归调用部分
}
例:
河内塔(Hanoi Tower)问题求解:
A
B
C
A
B
C
如何解决这个问题呢?真伤脑筋啊!
题目要求:1、将 n 个盘子从 A 柱移到 B 柱,C 柱可用;
2、每次只能移动一个盘子;
3、在移动过程中,不得将大盘压在小盘上。
解决该问题可分三步走:
1、将 A 柱上面的 n-1 个盘子从 A 柱移到 C 柱;
2、将第 n 个盘子从 A 柱移到 B 柱;
3、再将 C 柱上面的 n-1 个盘子移到 B 柱。
void Hanoi ( int n , i