数据结构课后习题3.docVIP

3.1 有5个元素，其进栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ （1）B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE； （2）B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA； （3）E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。 所以可能的次序有：CDBAE、CDBEA、CDEBA。 3.2 假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。 （1）下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO （2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回1；否则返回0。（假设被判定的操作序列已存入一维数组中）。 1） A、D均合法 2) 运行结果： 核心代码： bool Judge(char a[],int n) { LiStack *s; InitStack(s); int i=0; char e; bool match=true; while(in match) { if(a[i]==I) Push(s,a[i]); else if(a[i]==O) { if(GetTop(s,e)) { if(e!=I) match=false; else Pop(s,e); } else match=false; } i++; } if(!StackEmpty(s)) match=false; Destroy(s); return match; } 3.3 假设表达式中允许包含3种括号：圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对 运行结果： 核心源代码： bool Match(char exp[],int n) { int i=0; char e; bool match=true; LiStack *st; InitStack(st); while(in match) { if(exp[i]==( || exp[i]==[|| exp[i]=={) Push(st,exp[i]); else if(exp[i]==)|| exp[i]==]|| exp[i]==}) { if(GetTop(st,e)==true) { if( e-exp[i] 2 ) //////////////////////////////利用ASCII的值判断 match=false; else Pop(st,e); } else match=false; } i++; } if(!StackEmpty(st)) match=false; DestroyStack(st); return match; } 3.4 设从键盘输入一整数序列a1，a2，...an，试编程实现：当ai0时，ai进队，当ai0时，将队首元素出队，当ai=0时，表示输入结束。要求将队列处理成环形队列，入队和出队操作单独编写算法，并在异常情况时（如队满）打印出错。 运行结果： 源代码： #includestdio.h #includemalloc.h #includestring.h #define MAXSIZE 3 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int front,rear; }Queue; void InitQueue(Queue *s) { s=(Queue*)malloc(sizeof(Queue)); s-front=s-rear=0; } void DestroyQueue(Queue *s) { free(s); } bool QueueEmpty(Queue *q) { return (q-front==q-rear); } bool enQueue(Queue *q,ElemType e) { if((q-rear+1)%MAXSIZE==q-front) return false; q-rear=(q-rear+1)%MAXSIZE; q-data[q-rear]=e; // printf(rear=%d ,q-rear); return true; } bool deQueue(Queue *