《栈和队列的详细讲解》由会员分享，可在线阅读，更多相关《栈和队列的详细讲解（113页珍藏版）》请在金锄头文库上搜索。
1、1,4.1 栈 4.2 栈的实现 4.3 栈的应用 4.4 队列 4.5 队列的实现 4.6 队列的应用,栈和队列是运算 受限的线性表。,第四章 栈与队列,2,3.1 栈,3.1.1 栈的概念及运算 3.1.2 顺序栈 3.1.3 链栈,3,3.1.1 栈的概念及运算,栈,限制仅在一端进行 插入和删除运算的线性 表,栈顶,进行插入、删除的 一端,栈底,栈顶,栈底,进栈,退栈,a2,a1,an,.,栈是后进先出表（ LIFO 表）,4,（1）置空栈 createEmptyStack(void)：空栈； （2）判栈空 isEmptytack（st）：这是一个布尔函数。若st为空栈，则函数值为“真”
2、, 否则为“假”。 （3）进栈 push（st，x）：在st的顶部插入(亦称压入）元素 x。 （4）退栈 pop（st）：删除（亦称弹出）栈st的顶部元素。 （5）取栈顶 top（st）：取栈st的顶部元素。,栈的五种基本运算,3.1.1 栈的概念及运算,5,3.1.2 顺序栈,栈的顺序存储结构简称为顺序栈，它是运算受限 的顺序表。,#define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ DataType sMAXNUM;int t; /*栈顶
3、*/ ； typedef struct SeqStack, *PSeqStack; PSeqStack pastack; /*指向顺序栈的指针变量*/,6,注意:,t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号),约定:,1、栈空时，t=-1 2、栈满时，t=MAXNUM-1 3、栈顶元素：St 4、若t=-1时，执行pop,产生“下溢” 5、若t=MAXNUM-1时，执行push,产生“上溢”,7,6543210 -1,A,B,C,D,进栈和退栈,3.1.2 顺序栈,8,3.1.2 顺序栈,（1）置空栈 （2）判栈空 （3）进栈 （4）退栈 （5）取栈顶,在顺序栈下实现栈的五种基本
4、运算,当程序中同时使用两个栈时， 可共享存储空间。,9,1. 置空栈（算法4.1）,PSeqStack createEmptyStack_seq(void) PSeqStack pastack;pastack=malloc(sizeof(struct SeqStack);if(pastack=NULL)printf(“out of space!n”);elsepastack-t= -1;return pastack; /*SETNULL*/,10,2. 判栈空（算法4.2）,int isEmptyStack_seq(pastack) PSeqStack pastack; if (pastack
5、-t=0) return FALSE;else return TRUE;,11,3. 进栈（算法4.3）,先修改 t 值，再放入数据,t+,st=x,(*pastack).t+,(*pastack).s(*pastack).t=x,push_seq(pastack,x),12,push_seq(pastack,x) PSeqStack pastack; datatype x; if (pastack-t=MAXNUM-1) print(“overflow”); else pastack-t+;pastack-spastack-t=x; /* push_seq */,3. 进栈（算法4.3）,1
6、3,4. 退栈（算法4.4）,pop_seq(pastack),修改 t 值,t-,pastack-t - -,14,pop_seq(pastack) PSeqStack pastack; if (pastack-t=-1 )print(“underflow”); else pastack-t-; /* pop_seq */,4. 退栈（算法4.4）,15,5. 取栈顶元素（算法4.5）,datatype top_seq(pastack) PSeqStack pastack; if (pastack-t=-1 ) print(“stack is empty”);return NULL; els
7、e return(pastack-spastack-t; /* top_seq */,16,多个栈共享存储空间, .,栈1,栈2,栈1底,栈1顶,栈2底,栈2顶,让多个栈共享存储空间，可以相互调节余缺，节约存储空间，降低发生上溢的概率。,17,多个栈共享存储空间,多栈共享：采用链栈,Typedef struct datatype sMAXNUM;int top1,top2; DStack;Push(x,i) Pop(i),18,3.1.3 链栈,栈的链式存储结构称为链栈。它是运算受限的 单链表。,由于只能在链表头部进行操作，故链栈没有必 要象单链表那样需附加头结点。栈顶指针top就是 链表的头
8、指针head。,19,typedef int DataType; struct Node; typedef struct Node *pNode; struct Node /* 单链表结点结构 */ DataType info;pNode link; ; struct LinkStack /* 链接栈类型定义 */ pNode top; /* 指向栈顶结点 */ ; typedef struct LinkStack *PLinkStack;,3.1.3 链栈,pLinkstack plstack; /*变量声明*/,plstack,top,info,link,栈的链接表示,21,3.1.3 链
9、栈,相当于链表在 top 结点前插入,出栈,相当于链表在将top 结点删除,进栈,22,void push_link( PLinkStack plstack, DataType x ) /* 在栈中压入一元素x */ PNode p;p = (PNode)malloc( sizeof( struct Node ) );if ( p = NULL )printf(“Out of space!n“);else p-info = x;p-link = plstack-top;plstack-top = p; ,进栈算法（算法4.8）,23,void pop_link( PLinkStack plst
10、ack ) PNode p;if( isEmptyStack_link( plstack ) )printf( “Empty stack pop.n“ );else p = plstack-top;plstack-top = plstack-top-link;free(p); ,退栈算法（算法4.9）,24,3.2 栈的应用,栈的应用非常之广，只要问题满足LIFO 原则， 均可使用栈做数据结构。我们先看几个例子。 例3.1 文字编辑器例3.2 栈与递归例3.3 数制转换例3.4 括号匹配的检验 例3.5 表达式求值,25,例3.1 设计一个简单的文字编辑器，使其具有删除打错字符的功能。,# 删
11、除前面一个字符 删除前面所有字符 * 输入结束,“abc#defg*”,我们用栈来实现这种功能的文字编辑器,每读入一个字符,退栈,置空栈,编辑结束,26,PSeqStack str; /*顺序栈 str 是全程变量*/ EDIT( ) /*编辑好的字符串在 str 中*/ char c; str=createEmptyStack(); c=getchar( );while(c!=*) /*字符*为编辑结束符*/ if (c=#) POP(str);elseif (c=) str=createEmptyStack();else PUSH(str,c); c=getchar( )； /*EDIT*
12、/,例3.1 设计一个简单的文字编辑器，使其具有删除打错字符的功能。,27,如果一个对象部分的由自己组成，或者是按它自己定义的，则称为递归的。一个递归定义必须一步比一步简单，最后是有终结的，决不能无限循环下去。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。,例3.2 栈与递归,递归的定义,28,例3.2 栈与递归,递归函数的特点：在函数内部可以直接或间接地 调用函数自身。如阶乘函数：,阶乘的递归计算（算法4.11 ）int fact (int n) if (n = = 0) return 1;else return(n*fact(n-1); r2
13、main( ) int n;scanf(“%dn”, r1,3,3,r1,2,r2,1,r2,0,r2,1,1,2,6,30,调用前： （1）为被调用函数的局部变量分配存储区；（活动记录， 数据区） （2）将所有的实参、返回地址传递给被调用函数；实参和形参的结合，传值。 （3）将控制转移到被调用函数入口。 调用后返回： （1）保存被调用函数的计算结果； （2）释放被调用函数的存储区； （3）依照被调用函数保存的返回地址将控制转移到调用函数。,递归函数到非递归函数的转换,函数嵌套调用时，按照“后调用先返回”的原则进行。,int main() int m,n;.first(m,n); 1: ,in
14、t first(int s, int t) int i;second(i); 2: ,int second(int d) int x,y; 3: ,int main() int m,n;.int i;int x,y;3: 2: 1: ,函数嵌套结构,算法4.12 阶乘的非递归计算 程序员自己管理一个栈，并模拟函数调用的执行过程。int nfact(int n); int res; pSeqStack st;st=createEmptyStack-seq();while (n0) while (!isEmptyStack-seq(st) ) push-seq(st,n); res=res*top-seq(st);n=n-1; pop-seq(st); res=1; free(st); return(res);,阶乘递归算法：int fact (int n) if (n = = 0) return 1;else return(n*fact(n-1);,
