【顺序栈的出栈,链栈的表示和实现,递归定义】

顺序栈的出栈

（1）判断是否栈空，若空则出错（下溢）。
（2）获取栈顶元素e。
（3）栈顶指针减1。

//顺序栈的出栈
int Pop(SqStack& S, SElemType& e) {
	//若栈不为空，则删除栈顶元素，用e返回其值，并返回ok；
	if (S.top == S.base) {
		return 0;
	}
	--S.top;
	e = *S.top;
	return 1;
}
1
2
3
4
5
6
7
8
9
10

链栈的表示和实现

链表的实现
链栈是运算受限的单链表，只能在链表头部进行操作。

//链栈的表示
typedef struct StackNode {
	int data;
	struct StackNode* next;
}StackNode,*LinkStack;
LinkStack S;

1
2
3
4
5
6
7

• 链表的头指针就是栈顶。
• 不需要头结点。
• 基本不存在满栈的情况。
• 空栈相当于头指针指向空。
• 插入和删除仅在栈顶处执行。

链表的初始化

void InitStack(LinkStack& S) {
	S = NULL;
}
1
2
3

判断链栈是否为空

//链栈是否为空
bool StackEmpty(LinkStack S) {
	if (S == NULL) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8
9

链栈的入栈

//链栈上的入栈
void Push(LinkStack S, int e) {
	LinkStack p;
	p = new StackNode;//生成新结点
	p->data = e;//将新结点的数据域置为e
	p->next = S;//将S结点赋值给p结点的next域
	S = p;//修改栈顶指针

}
1
2
3
4
5
6
7
8
9

链栈的出栈

//链栈的出栈
int Pop(LinkStack S,int e) {
	LinkStack p;
	if (S == NULL) {
		return 0;
	}
	e = S->data;
	p = S;
	S = S->next;
	delete p;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

递归定义

若一个对象部分地包含他自己，或用他自己给自己的定义，就称这个对象是递归的。
若一个过程直接或间接地调用自己，则这个调用过程
是递归的过程。
分治法求解递归问题算法的一般形式：

void p(参数表）{
	if(递归结束条件）可直接求解步骤;-------基本项
	else p（较小参数）;---归纳项
}
1
2
3
4

例：求阶乘

long Fact（long n）{
if（n==0）{return 1}  ;
else return n*Fact(n-1);

1
2
3
4

函数的调用过程

调用前，系统完成：
（1）将实参，返回地址等传递给被调用函数
（2）为被调函数的局部变量分配存储区域
（3）将主调函数转移到被调函数
调用后，系统完成：
（1）保存被调函数的计算结果
（2）释放被调函数的数据区
（3）依照被调函数保存的返回地址转移到主调函数。
当多个函数嵌套调用时：
遵循后调用先返回。需要用栈来实现。