ch4堆栈及其应用.ppt

?4.1堆栈的基本概念 4.2 顺序栈及其基本算法 4.3 链栈及其基本运算实现 4.4 栈的应用举例 ?4.1.1 堆栈定义 4.1.2 堆栈的逻辑结构 4.1.3 堆栈的基本运算 定义4.1 堆栈简称栈，是满足下列条件的数据结构： (1) 有限个具有相同数据类型的数据元素的集合，D={ ai | i=1，2，…，n }，ai为数据元素。 (2) 数据元素之间的关系R={ ai，ai+1 | ai，ai+1∈D}； (3) a1为栈底元素，an为栈顶元素；入栈时，数据元素按a1，a2，…，an的次序进栈，出栈的第一个元素应为栈顶元素an。 设 栈 S = (a1,a2…an) 则 a1为栈底元素， an为栈顶元素; 若n＝0，则为空栈。 4.1堆栈的基本概念 ? 4.2 顺序栈及其基本算法 4.3 链栈及其基本运算实现 4.4 栈的应用举例 ?4.2.1 顺序栈概念及数据类型 4.2.2 顺序栈的基本算法 4.2.1 顺序栈概念及数据类型 ? 4.2.2 顺序栈的基本算法 4.1堆栈的基本概念 4.2 顺序栈及其基本算法 ? 4.3 链栈及其基本运算实现 4.4 栈的应用举例 ?4.3.1 链栈概念及数据类型 4.3.2 链栈的基本算法 4.3.1 链栈概念及数据类型 ? 4.3.2 链栈的基本算法 ? 链栈的运算实现 ? 由于链栈中的结点可以动态生成，所以链栈无栈满状态。 ? top = NULL 时，为空栈。 ? top-data为栈顶元素 4.1堆栈的基本概念 4.2 顺序栈及其基本算法 4.3 链栈及其基本运算实现 ? 4.4 栈的应用举例 应用一、数制转换问题 将一个十进制的整数 N 转换成其它 d 进制的数，方法是将 ( N ÷ d ) 取余数a1，并再将其商与d整除，取余数a2 … …直到商为0。 得到的 d 进制数为： an an-1 … a2 a1 由于最先输出的是 an ，最后输出的是a1 即：最先算出的 最后输出。 我们可以将算出的余数按顺序入栈，而按顺序出栈的即是 d 进制数。 ? 链栈的出栈算法 top a1 a2 ∧ an p datatype data; LinkStack *Pop(LinkStack *top) { LinkStack *p; if (top==NULL) { printf(“under flow\n”); return NULL;} else{data＝top-data; p＝top; top＝top-next; free(p); return top;} } ? 链栈的置空栈算法 在链栈中实现置空栈运算可以通过调用出栈Pop( )函数，将栈中元素依次出栈，释放所有节点所占空间，最终使栈顶指针LS为NULL。算法描述为： LinkStack *InitStack (LinkStack *top){ while(top ! = NULL) top = Pop( top )； return (top)； } 链栈实际上是运算受限制的链表。 除置空栈运算InitStack ( )外，其它操作都在表头进行，算法的执行时间与栈的大小无关。即建空栈SetStack ( )、判栈空StackEmpty( )、取栈顶元素GetTop( ) 以及入栈Push( )与出栈Pop( )等算法的时间复杂度均为О(1)。 置空栈运算InitStack ( )，需要将所有元素依次出栈，算法所需时间与栈的大小有关，其时间复杂度为О(n) 。 ? 链栈基本算法性能分析 第4章 栈及其应用 建空栈S 输入 N N=0 n = N%d Push ( S, n) N =N/d N Y N empty(S) = 0 Pop(S) Y void Conversion (SeqStack *S，int n，int d ){ //对于任何一个输入的非负十进制整数n，输出与之等值的d进制数 SetStack(S)；//建空栈 if(n0){ //若n为负数