数据结构导论 第3章 栈、队列和数组

多个函数嵌套调用的规则是: 后调用先返回 ！ 此时的内存管理实行“栈式管理” “栈式管理”
例如：
void main( ){ … a( ); … }//main void a( ){ … b( ); void b( ){ … 函数b的数据区 函数a的数据区 Main的数据区 }// b
…
}// a
堆栈与函数的调用
else *x=sq->data[sq->top--]; return 1
}
*x = sq->data[sq->top]; sq->top--;
顺序栈操作总结
由于栈的插入和删除操作具有它的特殊性， 由于栈的插入和删除操作具有它的特殊性， 所以用顺序存储结构表示的栈并不存在插入 删除数据元素时需要移动的问题， 删除数据元素时需要移动的问题， 但栈容量难以扩充的弱点仍就没有摆脱。 但栈容量难以扩充的弱点仍就没有摆脱。
1. 堆栈在函数调 用中的应用: 设有三个函数A1， A2，A3，这三个 r 函数有如下的调 用关系：函数A1 在其函数体的某 处r调用函数A2， 函数A2又在其函 数体某处t调用函 数A3，函数A3不 调用其他函数。
A1 A2 A3 t
函数嵌套调用 A1调用A2，A2 调用A3时的返 回地址在堆栈 中的情况如右 图所示。
举例1 举例1：家里吃饭的碗。 举例2 举例2：在建筑工地上使用的砖块
下面我们先给出栈结构的基本操作： （1）初始化栈 InitStack(&S) （2）入栈 Push(＆S, x) 入栈 ＆ （3）出栈 Pop(&S,&x) 出栈 （4）获取栈顶元素内容 GetTop(S,＆e) （5）判断栈是否为空 EmptyStack (S) （6）清空栈 ClearStack(&S) （7）返回栈的长度 StackLength(S)
{ printf (“Stack is empty”); return 0; } else { p=ls *x=p->data; ls=ls->next; free(p); return 1; } }
3.1.4栈的应用举例 栈的应用举例 【举例1】将从键盘输入的字符序列逆 置输出 比如，从键盘上输入：tset a si sihT；算 法将输出：This is a test
3.1.5 堆栈与函数的调用及递归 当在一个函数的运行期间调用另一 个函数时，在运行该被调用函数之前， 需先完成三项任务： 将所有的实在参数、返回地址等信息传 递给被调用函数保存; 为被调用函数的局部变量分配存储区; 将控制转移到被调用函数的入口。
从被调用函数返回 返回调用函数之前 之前， 返回 之前 应该完成下列三项任务： 保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转 移到调用函数。
int EmptyStack (SqStackTp sq) { if (sq.top==-1) return 1; else return 0; }
(5)取栈顶元素 取栈顶元素
栈顶元素下标：sq.top 栈顶元素的表示：sq.data[sq.top]
int GetTop(SqStack sq, datatype *x) {
ቤተ መጻሕፍቲ ባይዱ
解决【举例1】问题的完整算法
void ReverseRead( ) { SqStackTp S; char ch; InitStack(&S); //初始化栈 while ((ch=getchar())!=’\n’) //从键盘输入字符，直到输入换 行符为止 Push(&S ,ch); while (!StackEmpty(S)) { Pop(&S,&ch); putchar(ch); } putchar(‘\n’); } //将输入的每个字符入栈 //依次退栈并输出退出的字符 //定义一个栈结构S
顺序栈类型定义如下所示： 顺序栈类型定义如下所示：
#define sqstack_maxsize 6
//栈的最大数据元素数目 //栈的最大数据元素数目
typedef struct sqstack{ datatype data[sqstack_maxsize ];
//存放栈中数据元素的存储单元 //存放栈中数据元素的存储单元
int top;
//栈顶指针, //栈顶指针,指示栈顶元素下标值 栈顶指针
}SqStackTp;
top 4 3 2 1 top 0 top A 4 3 2 1 0
E D C B A
4 3 2 1 0
top初值为 ，每插入一个元素增 ，始终指向栈顶元 初值为-1，每插入一个元素增1， 初值为 素。 栈空： 栈空：top==-1； ； 栈満： 栈満：top ==sqstack_maxsize –1； ；
3.1.3 栈的链式存储
若是栈中元素的数目变化范围较大或不 清楚栈元素的数目， 清楚栈元素的数目，就应该考虑使用链 式存储结构。 式存储结构。 人们将用链式存储结构表示的栈称作 链栈” “链栈”。 链栈通常用一个无头结点的单链表表示。 链栈通常用一个无头结点的单链表表示。 如图所示。 如图所示。
data
链栈
栈顶指针
an
an-1
a1 ∧
栈底元素
注意: 注意 链栈中 指针的方向
链栈的类型定义
栈的链式存储结构在C语言中可用下列类型定义实现： 栈的链式存储结构在 语言中可用下列类型定义实现： 语言中可用下列类型定义实现
typedef struct node {
//链栈的结点结构 链栈的结点结构
datatype data; //栈的数据元素类型 栈的数据元素类型 struct node *next; //指向后继结点的指针 指向后继结点的指针 }LStackTp;
int Push(SqStackTp *sq, DataType x) { if (sq->top== sqstack_maxsize -1) { printf(“栈已满，无法操作!”)；return 0; } else sq->data[++sq->top]=x; return 1; }
sq->top++; sq->data[sq->top]=x;
next
ls
栈顶
由于栈的插入删除操作只能在一 端进行，而对于单链表来说， 端进行，而对于单链表来说，在 首端插入删除结点要比尾端相对 地容易一些，所以， 地容易一些，所以，我们将 单链表的首端作为栈顶端 将单链表的头指针作为栈顶指针
^
图示：链栈通常用一个无头结点的单链表表示。 图示：链栈通常用一个无头结点的单链表表示。
t r STACK
top
递归函数执行的过程可视为同一函数 同一函数 进行嵌套调用。例如： P50
1 N!= N*(N-1)! (N=0) (N>0)
f(3)
3.2 队列
基本概念
队列是一种运算受限制的线性表， 队列是一种运算受限制的线性表，元素的 添加在表的一端进行， 添加在表的一端进行，而元素的删除在表 的另一端进行。 的另一端进行。 允许添加元素的一端称为队尾 队尾（ 允许添加元素的一端称为队尾（Rear）； ） 允许删除元素的一端称为队头 队头（ 允许删除元素的一端称为队头（Front） ） 向队列添加元素称为入队 入队， 向队列添加元素称为入队，从队列中删除 元素称为出队 出队。 元素称为出队。
定义链栈仅需定义栈顶指针(头指针 ： 定义链栈仅需定义栈顶指针 头指针)： LStackTp * ls 头指针
链栈各项基本操作的算法
(1). 初始化栈 初始化栈ls. 建立一个空栈，仅须栈顶指针为NULL void InitStack(LStackTp *ls) { ls=NULL;}
(4) 判断栈 是否空 判断栈S是否空
if (EmptyStack (sq)) { printf(“Stack is empty”); return 0; }
else *x=sq.data[sq.top]; return 1;
}
(2)进栈 在栈顶插入一个值为 的元素 进栈:在栈顶插入一个值为X的元素 进栈
算法步骤： 算法步骤： 验满 栈顶下标加1 栈顶下标加1 (top++) 在栈顶插入新的元素 54 3 2 1 top A 0
我们经常将栈用下图的形式描述
进栈 出栈
S=(a1，a2，a3，…an)， 则a1称为栈底元素 栈底元素， 栈底元素 an为栈顶元素 栈顶元素。 栈顶元素 栈的修改是按后进先出的 原则进行的。因此，栈称 为后进先出表（LIFO） 后进先出表（ 后进先出表 ） -----栈的结构特征
栈顶 top
an ... a2 a1
栈类型的存储实现
顺序实现------顺序栈 链接实现------链栈
3.1.2 栈的顺序存储
栈的顺序存储结构 顺序存储结构是用一组连续 连续的存储 顺序存储结构 连续 单元依次 依次存放栈中的每个数据元素，并 依次 用起始端作为栈底 起始端作为栈底。 起始端作为栈底
可以用一维数组表示一个栈。 用起始端作为栈底 栈底，它是固定的。 栈底 栈顶位置是随着进栈和退栈操作而变化的， 栈顶 top来标记当前栈顶元素下标 故需用一个指针top top 值。
基本操作在顺序栈上析实现 (1)初始化： 使栈为空-----栈顶元素下标初始化为0
int InItStack(SqStackTp *sq) { sq->top=-1; return(1); }
(4)判栈空 判栈空: 判栈空
若栈为空则让函数返回1，否则返回 若栈为空则让函数返回 ，否则返回0
栈空标志：top==-1
p x
(2)进栈 进栈
an an-1
a1 ∧
ls