李春葆数据结构_第3章__栈和队列学案.ppt

3.2.2 队列的顺序存储结构及其基本运算的实现 假设队列的元素个数最大不超过整数MaxSize,所有的元素都具有同一数据类型ElemType,则顺序队列类型SqQueue定义如下: typedef struct { ElemType data[MaxSize]； int front,rear；/*队首和队尾指针*/ } SqQueue 从前图中看到,图(a)为队列的初始状态,有front==rear成立,该条件可以作为队列空的条件。 那么能不能用rear==MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。 为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。 循环队列首尾相连,当队首front指针满足 front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算(％)来实现: 队首指针进1:front=(front+1)％MaxSize 队尾指针进1:rear=(rear+1)％MaxSize 循环队列的除头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按逆时针方向进1。 怎样区分这两者之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为: (q-rear+1) % MaxSize==q-front 队空条件仍为: q-rear==q-front 循环队的入队和出队操作示意图 在循环队列中,实现队列的基本运算算法如下: (1) 初始化队列InitQueue(q) 构造一个空队列q。将front和rear指针均设置成初始状态即0值。对应算法如下: void InitQueue(SqQueue *q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q-front=q-rear=0; } (2) 销毁队列ClearQueue(q) 释放队列q占用的存储空间。对应算法如下: void ClearQueue(SqQueue *q) { free(q); } (3) 判断队列是否为空QueueEmpty(q) 若队列q满足q-front==q-rear条件,则返回1；否则返回0。对应算法如下: int QueueEmpty(SqQueue *q) { return(q-front==q-rear); } (8) 显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) { LiStack *p=s-next; while (p!=NULL) { printf(%c ,p-data); p=p-next; } printf(\n); } 例3.5 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。 解: 设置一个括号栈,扫描表达式：遇到左括号(包括(、[和{)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。 若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。 int correct(char exp[],int n) { char st[MaxSize]; int top=-1,i=0,tag=1; while (in tag) { if (exp[i]==( || exp[i]==[ || exp[i]=={) /*遇到(、[或{,则将其入栈*/ { top++; st[top]=exp[i]; } if (exp[i]==‘)’)