数据结构 ch03.pptVIP

第3章 栈和队列 2．基本运算顺序队列的实现 队列初始化 void InitQueue(SQUEUE *SQ) { SQ-rear=SQ-front=0;} 入队列 int EnQueue(SQUEUE *SQ,ElemType x) { if((SQ-rear+1)%MaxSize==SQ-front){ printf(\n Queue is full!); return 0;} SQ-rear=(SQ-rear+1)%MaxSize; SQ-data[SQ-rear]=x; return 1;} 出队 int OutQueue(SQUEUE *SQ,ElemType *x) { if(Empty(SQ)){ printf(\n Queue is free); return 0; } SQ-front=(SQ-front+1)%MaxSize; *x=SQ-data[SQ-front]; return 1; } 判队列空 int Empty(SQUEUE *SQ) { return(SQ-rear==SQ-front)?1:0;} 3.4.3队列的链式存储结构及其基本运算的实现 1. 队列的链式存储结构 队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。 链队结构示意图 链队的数据类型定义如下 ： typedef struct qnode{ //链队结点的类型 ElemType data; struct qnode *next; }QTYPE; typedef struct qptr{ //链队指针类型 QTYPE *front,*rear; }SQUEUE; SQUEUE LQ; 链队运算指针变化情况 * 本章主题：栈和队列的应用 教学目的：掌握栈和队列的应用方法,理解栈的重要作用 教学重点：利用栈实现行编辑,利用栈实现表达式求值 教学难点：利用栈实现表达式求值 栈，也叫堆栈，是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等，都要用到栈的有关特性。它们是栈应用于实际问题的典型。 3.1 栈 1．栈的定义 栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。 特点：后进先出 栈又称为“后进先出”的线性表，简称LIFO表。 3.1.1 栈的定义和运算 2．栈的基本运算 初始化栈InitStack(S) 设置一个空栈S。 压栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素。 判栈空Empty(S) 若栈S为空栈，结果为1，否则结果为0。 3.1.2 栈的顺序存储结构及其基本运算的实现 栈有两种存储表示方法:顺序存储和链式存储 1.栈的顺序存储结构 栈的顺序存储结构简称为顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。 ElemType 为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。 data域:为一个一维数组，用于存储栈中元素。 top域:栈顶指针。取值范围为0～MaxSize-1。 top=-1表示栈空，top=MaxSize-1表示栈满。 #define MaxSize 存储数据元素的最大个数 typedef struct { ElemType data[MaxSize]; int top; }STACK; 顺序栈的C语言描述如下： 。 顺序栈的几种状态（最大长度MaxSize为4） （a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。 （b）表示在（a）基础上执行Push(S, ‘A’)后得到这种状态。 （c）又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。 （d）表示在（c）状态下，执行一次Pop(S，x)运算得到。 （e）表示在（d）状态下，执行三次Pop(S，x)运算得到。此时栈顶下标值top=-l，又变成栈空状态 2．基本运算在顺序存储结构的实现 初始化栈InitStack(S) vo