第3章 栈和队列幻灯片1.pptVIP

第3章 栈和队列; 3.1栈 一. 栈的定义 栈(Stack)是限制仅能在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。;举例: 纸箱内放书,先放进去的在下面,后放进去 的在上面,往外取的时候,先取上面(后放进去的)的,后取下面的(先放进去的).;二 基本操作: InitStack(S) 构造一个空栈S ClearStack(S) 栈S存在则清为空栈 EmptyStack(S)栈S为空则返回TRUE，否则FALSE FullStack (S) 栈S已满则返回TRUE,否则 FALSE GetTop(S,e) 栈S存在且非空则返回S的 栈顶元素 Push(S,e) 栈S存在则插入元素e为新的栈顶元素 Pop(S,e) 栈S存在且非空则删除S的栈顶元素并用e返回其值 ;三.堆栈的顺序表示和实现 1.栈的存储方式： 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置 2.存储方式的C语言实现 typedef struct{ datatype data[maxsize];//存放栈中元素 int top; //栈顶元素的下表 }SqStack; 用该类型定义堆栈变量 sqstack *s;;四.堆栈的基本操作算法描述 1.建立一个空的堆栈 status initstack(sqstack s){ s.base=(char *)malloc(100*sizeof(char));//分配存 储空间 if(!s.base) exit(); s.top==s.base; s.stacksize=100; };2.在堆栈中插入新的元素(入栈) status push(sqstack s,char e){ if(s.top-s.base=s.stacksize){ s.base=(char*)realloc …… s.top=s.base+s.stackzize; } *s.top=e; s.top++; };3.从堆栈中删除一个元素(出栈) status pop(sqstack s, char e){ if(s.top==s.base) printf(“stack is enpty!”); s.top--; e=*s.top; };3.返回栈顶元素的值 status gettop(sqstack s,char e){ if(s.top==s.base) printf(“stack is empty!”); e=*(s.top-1); } 注意:此处s.top的值有没有改变? s.top没有改变.只是取了它下面一个元素的值.; 3.2栈的应用举例; 3.3 函数的递归调用;int f1(x) int x; { int y,z; ….. z=f2( y); …… return (2*z); };特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。; int fact ( int n) { int f; if(n0) printf(“n0,data error!\n”); else if(n= =0||n= =1) f=1; else f=fac(n-1)* n ; return f; };以求4的阶乘为例：;利用栈实现递归调用;队列的主要运算;二. 队列的存储结构;1）线性队列; 2）循环队列;3）。举例 医院各诊室排队就诊，各为了方便病人，设置了座椅，每个科室六个，先来先看病。用队列描述某个科室的排队情况， 思考：如何判断队列空和队列满;4）循环队