文档详情

数据结构第3章栈和队列讲解.ppt

发布:2017-04-16约字共51页下载文档
文本预览下载声明
栈 和 队 列;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 为非
显示全部
相似文档