数据结构第3章栈和队列讲解.ppt
文本预览下载声明
栈 和 队 列;1、栈和队列的定义及特点; 2、栈的顺序存储表示; 3、队列的顺序存储表示;队列的链接存储表示; 4、栈和队列的应用举例。 ;限定仅在表尾进行插入或删除操作。 ; 栈的抽象数据类型的定义 ;GetTop(S, e)
初始条件:栈 S 已存在且非空。
操作结果:用 e 返回 S 的栈顶元素。
StackEmpty(S) 初始条件:栈 S 已存在。
操作结果:若栈 S 为空栈,则返回 TRUE,否则 FALSE。
StackLength(S) 初始条件:栈 S 已存在。
操作结果:返回 S 的元素个数,即栈的长度。 ; ClearStack(S) 初始条件:栈 S 已存在。
操作结果:将 S 清为空栈。
Push(S, e)
初始条件:栈 S 已存在。
操作结果:插入元素 e 为新的栈顶元素。
Pop(S, e) 初始条件:栈 S 已存在且非空。
操作结果:删除 S 的栈顶元素,并用 e 返回其值。 } ADT Stack ;3.1.2 栈的表示和实现 ;#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量typedef struct { ElemType *elem; // 数组指针,指示线性表的基地址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) } SqList; ; 栈的基本操作在顺序栈中的实现 ;栈顶指针;3.2 栈的应用举例 ;例: (1348)10=(2504)8,其运算过程如下: ;bottom ;3.2.2 括号匹配的检验 ;算法的设计思想:;3.2.3 行编辑程序 ;void LineEdit( ) {
InitStack(S);
ch=getchar();
while (ch != EOF) { //EOF为全文结束符
while (ch != EOF ch != \n) {
switch (ch) {
case # : Pop(S, c); break;
case ‘@’: ClearStack(S); break; // 重置S为空栈
default : Push(S, ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}
将从栈底到栈顶的字符传送至调用过程的数据区;
ClearStack(S); // 重置S为空栈
if (ch != EOF) ch = getchar();
}
DestroyStack(S);
} ;3.2.4 迷宫求解 ;3.2.5 表达式求值 ; “四染色”定理是计算机科学中著名定理之一,
即可以用不多于四种颜色对地图着色,使相邻的行政
区域不重色。 ;例:已知 7 个行政区域地图,对其进行染色。 ;作业:
3.1、3.2、3.3、3.4、3.18 ;3.3 栈与递归的实现 ; 当在一个函数的运行期间调用另一个函数时,在运行
该被调用函数之前,需先完成三件事:
将实参等传递给被调用函数,保存返回地址(入栈);
为被调用函数的局部变量分配存储区;
将控制转移到被调用函数的入口。 ;float fact(int n)
{float s;
if (n = = 0)
s =1;
else
s = n*fact(n -1);
return (s);
};限定在表的一端插入、另一端删除。 ; 队列的抽象数据类型的定义 ;QueueEmpty(Q)
初始条件:队列 Q 已存在。
操作结果:若 Q 为空队列,则返回 TRUE,
否则返回 FALSE。
QueueLength(Q)
初始条件:队列 Q 已存在。
操作结果:返回 Q 的元素个数,即队列的长度。
GetHead(Q, e)
初始条件:Q 为非
显示全部