吉林师范大学计算机学院《数据结构》课件：3.ppt

数据结构 C语言版 第三章:栈和队列 5. 判断栈是否为空 int link_empty(Linkstack S)????{//若栈为空则返回1，否则返回0??????if(S==NULL) return(1);??????else retrun(0);????} 3.5栈的应用举例---表达式求值 算法的基本思想是： ??（1）首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；? （2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优符后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。 算法描述 　　p53 ＊栈与递归的实现 5、求循环队列中元素的个数 int QueueLength(SqQueue Q){????//返回Q的元素个数，即队列的长度????return(Q.rear-Q.front+MAXQSIZE)??????????%MAXQSIZE;} 6、进队算法 Status EnQueue(SqQueue Q,QElemType e){????//插入元素为Q的新的队尾元素????if((Q.rear+1) % MAXQSIZE==Q.front)return ERROR;//队列满????Q.base[Q.rear]=e;????Q.rear=(Q.rear+1) % MAXQSIZE;????return OK;} 7、出队算法 Status DeQueue(SqQueue Q,QElemType e){????//若队列不空，则删除Q的队头元素，??????用e返回其值，并返回OK；否则返回ERROR????if(Q.front==Q.rear) return ERROR;????e=Q.base[Q.front];????Q.front=(Q.front+1)%MAXQSIZE;????return OK;} * * 内 容 3.1栈的概念 3.2栈的存储结构 3.3顺序栈的操作算法 3.4链栈的操作算法 3.5栈的应用举例---表达式求值 3.6队列的概念 3.7队列的存储结构 3.8循环队列的操作算法 3.9链队的操作算法 3.1栈的概念 1.定义： 栈(Stack) 是限定仅在表的一端进行插入或删除操作的线性表。 2.栈的示意图 P44 3.栈的抽象数据类型定义 P45 3.2栈的存储结构。 有两种存储结构: 1、顺序栈 顺序栈的类型定义： //-- -- --栈的顺序存储表示-- -- --#define STACK_NINT_SIZE 100;//存储空间初始分配量#define STACKINCREMENT 10; //存储空间分配增量typedef struct{????SElemType *base; //在栈构造之前和销毁之后，base的值为NULL????SElemType *top; //栈顶指针????int stacksize; //当前已分配的存储空间，以元素为单位}SqStack //-- -- --基本操作的函数原型说明-- -- --Status InitStack(SqStack S);????//构造一个空栈SStatus GetTop(SqStack S,SElemType e);????//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORStatus Push(SqStack S,SElemType e);????//插入元素e为新的栈顶元素Status Pop(SqStack S,SElemType e);????//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR 2、链栈 链栈的类型定义： typedef struct LNode{//结点类型????ElemType data;????struct LNode *next;}Lnode,*Linkstack;Linkstack S; 3.3顺序栈的操作算法 1建立一个空栈Status InitStack(SqStack S){????//构造一个空栈S??S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));????if(!S.base)exit(overflow); //存储分配失效????S.top=S.base;????S.stacksize=STACK_INIT_SIZE;????r